Author: Nicholas Prado <nmprado@nzen.ws>
Date: Thu Dec 5 06:58:08 UTC 2019
Parent: d271ce605572471f42422a4d171bc2bd97fb16c8
Log message:
tmp i1903-2 draft that skips points
This draft tries to find the shortest path by associating points
with sequence value. However, this skips values after 14 and has
21 twice, somehow, for the trivial input.
1: diff --git a/src/java/Exercise19031.java b/src/java/Exercise19031.java
2: index bb868ec..dcd9c57 100644
3: --- a/src/java/Exercise19031.java
4: +++ b/src/java/Exercise19031.java
5: @@ -93,19 +93,6 @@ public class Exercise19031
6: Set<Cpoint> crossover = intersectionsOf( pointsFirst, pointsSecond );
7: Cpoint closest = closestToOriginManhattanwise( crossover );
8: System.out.println( "\t"+ here + "closest "+ closest );
9: - /*
10: - make a set of integral points on the line of each part of the path
11: - for each point of first wire, check if second wire contains point
12: - if so add to intersection set
13: - calculate the distance of each point in the intersection set, directly or as 'manhattan' distance
14: - create a map of intersection points : 'manhattan' distance from the origin
15: - choose the lowest valued point, reply with this
16: -
17: - have an awareness of the current
18: - convert instruction into a vector
19: - gen the list of point pairs indicated
20: - */
21: - // 4TESTS
22: }
23:
24:
25: diff --git a/src/java/Exercise19032.java b/src/java/Exercise19032.java
26: new file mode 100644
27: index 0000000..89cdcec
28: --- /dev/null
29: +++ b/src/java/Exercise19032.java
30: @@ -0,0 +1,667 @@
31: +
32: +import java.awt.Point;
33: +import java.io.IOException;
34: +import java.nio.file.Files;
35: +import java.nio.file.InvalidPathException;
36: +import java.nio.file.Path;
37: +import java.nio.file.Paths;
38: +import java.util.ArrayList;
39: +import java.util.Collection;
40: +import java.util.LinkedList;
41: +import java.util.List;
42: +import java.util.HashSet;
43: +import java.util.Map;
44: +import java.util.Set;
45: +import java.util.SortedSet;
46: +import java.util.TreeMap;
47: +import java.util.TreeSet;
48: +
49: +public class Exercise19032
50: +{
51: +
52: + public static void main( String args[] )
53: + {
54: + final String here = Exercise19032.cl +"m ";
55: + if ( args.length < 1 )
56: + {
57: + throw new RuntimeException( here +"add a filename argument" );
58: + }
59: + String userSaysFile = args[ 0 ];
60: + List<String> fileLines = new LinkedList<>();
61: + try
62: + {
63: + Path where = Paths.get( userSaysFile );
64: + fileLines = Files.readAllLines( where );
65: + }
66: + catch ( IOException | InvalidPathException ie )
67: + {
68: + System.err.println( here +"couldn't read file "+ userSaysFile +" because "+ ie );
69: + return;
70: + }
71: + /*
72: + - interpretation of spec -
73: + input has two csv strings, each is a wire
74: + elements are cardinal vectors of operand {R D L U}
75: + note the paths these take
76: + note the intersections between them (but not of itself)
77: + of those intersections, choose the point with the shortest path that
78: + started from the origin, combined
79: +
80: + potential means
81: + for each point in the first wire
82: + save it in a map with the running count of points encountered
83: + start a min value with the combined length of both wires (for safety)
84: + for each point in the second wire
85: + if the first wire shares this point and we haven't seen it before (not that it could be fewer)
86: + add the steps of each
87: + if it is minimum
88: + save the new minimum
89: + reply with the minimum
90: + */
91: + new Exercise19032( fileLines.get( 0 ), fileLines.get( 1 ) )
92: + .stepsDistaceOfClosestIntersecton();
93: + }
94: +
95: +
96: + private static final String cl = "e19032.";
97: + private String firstWire;
98: + private String secondWire;
99: +
100: +
101: + public Exercise19032( String first, String second )
102: + {
103: + firstWire = first;
104: + secondWire = second;
105: + }
106: +
107: +
108: + public void stepsDistaceOfClosestIntersecton()
109: + {
110: + Collection<Vector> convertedFirst = converted( firstWire );
111: + Map<Cpoint, Integer> pointsFirst = countedStepsOfLine( convertedFirst );
112: + Collection<Vector> convertedSecond = converted( secondWire );
113: + int minimum = minimumDistanceIntersectionBySteps(
114: + pointsFirst, convertedSecond );
115: + System.out.println( "\tclosest "+ minimum );
116: + }
117: +
118: +
119: + public void manhattanDistanceOfClosestIntersection()
120: + {
121: + final String here = cl +"mdhoci ";
122: + // System.out.println( "\t"+ here + "--- "+ firstWire );
123: + Collection<Vector> convertedFirst = converted( firstWire );
124: + Set<Cpoint> pointsFirst = pointsOfLine( convertedFirst );
125: +
126: + // System.out.println( "\t"+ here + "--- "+ secondWire );
127: + Collection<Vector> convertedSecond = converted( secondWire );
128: + Set<Cpoint> pointsSecond = pointsOfLine( convertedSecond );
129: +
130: + // render( pointsFirst, pointsSecond );
131: + Set<Cpoint> crossover = intersectionsOf( pointsFirst, pointsSecond );
132: + Cpoint closest = closestToOriginManhattanwise( crossover );
133: + System.out.println( "\t"+ here + "closest "+ closest );
134: + }
135: +
136: +
137: + private Collection<Vector> converted( String which )
138: + {
139: + String[] notCsv = which.split( "," );
140: + Collection<Vector> converted = new ArrayList<>( notCsv.length );
141: + for ( String acronym : notCsv )
142: + {
143: + converted.add( vectorOfAcronym( acronym ) );
144: + }
145: + return converted;
146: + }
147: +
148: +
149: + private Vector vectorOfAcronym( String input )
150: + {
151: + Vector result = new Vector();
152: + result.magnitude = Integer.parseInt( input.substring( 1 ) );
153: + result.direction = CardinalDirection.from( input.substring( 0, 1 ) );
154: + return result;
155: + }
156: +
157: +
158: + private Map<Cpoint, Integer> countedStepsOfLine( Collection<Vector> instructions )
159: + {
160: + Map<Cpoint, Integer> steps = new TreeMap<>();
161: + Cpoint origin = new Cpoint( 0, 0 );
162: + Cpoint previous = origin;
163: + Cpoint tip = origin;
164: + int seen = 0;
165: + for ( Vector arrow : instructions )
166: + {
167: + // System.out.println( "\t\taa "+ arrow );
168: + switch ( arrow.direction )
169: + {
170: + case UP :
171: + {
172: + tip = new Cpoint( previous.x, previous.y + arrow.magnitude );
173: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
174: + steps.putIfAbsent( tip, Integer.valueOf( seen + arrow.magnitude ) );
175: + for ( int ind = previous.y; ind < tip.y; ind++ )
176: + {
177: + steps.putIfAbsent(
178: + new Cpoint( previous.x, ind ),
179: + Integer.valueOf( seen + ind ) );
180: + // System.out.println( "\t\t"+ previous.x +" : "+ ind );
181: + }
182: + break;
183: + }
184: + case DOWN :
185: + {
186: + tip = new Cpoint( previous.x, previous.y - arrow.magnitude );
187: + steps.putIfAbsent( tip, Integer.valueOf( seen + arrow.magnitude ) );
188: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
189: + steps.putIfAbsent( tip, Integer.valueOf( seen + arrow.magnitude ) );
190: + for ( int ind = tip.y; ind < previous.y; ind++ )
191: + {
192: + steps.putIfAbsent(
193: + new Cpoint( previous.x, ind ),
194: + Integer.valueOf( seen + ind ) );
195: + // System.out.println( "\t\t"+ previous.x +" : "+ ind );
196: + }
197: + break;
198: + }
199: + case LEFT :
200: + {
201: + tip = new Cpoint( previous.x - arrow.magnitude, previous.y );
202: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
203: + steps.putIfAbsent( tip, Integer.valueOf( seen + arrow.magnitude ) );
204: + for ( int ind = tip.x; ind < previous.x; ind++ )
205: + {
206: + steps.putIfAbsent(
207: + new Cpoint( ind, previous.y ),
208: + Integer.valueOf( seen + ind ) );
209: + // System.out.println( "\t\t"+ ind +" : "+ previous.y );
210: + }
211: + break;
212: + }
213: + case RIGHT :
214: + {
215: + tip = new Cpoint( previous.x + arrow.magnitude, previous.y );
216: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
217: + steps.putIfAbsent( tip, Integer.valueOf( seen + arrow.magnitude ) );
218: + for ( int ind = previous.x; ind < tip.x; ind++ )
219: + {
220: + steps.putIfAbsent(
221: + new Cpoint( ind, previous.y ),
222: + Integer.valueOf( seen + ind ) );
223: + // System.out.println( "\t\t"+ ind +" : "+ previous.y );
224: + }
225: + break;
226: + }
227: + default :
228: + {
229: + break;
230: + }
231: + }
232: + seen += arrow.magnitude;
233: + // System.out.println( "\t"+ here + tip );
234: + previous.setLocation( tip );
235: + }
236: + for ( Cpoint buh : steps.keySet() )
237: + {
238: + System.out.println( "\t"+ cl +"csol "+ buh +" is "+ steps.get( buh ) );
239: + }
240: + return steps;
241: + }
242: +
243: +
244: + private int minimumDistanceIntersectionBySteps(
245: + Map<Cpoint, Integer> pointsFirst, Collection<Vector> vectorsSecond )
246: + {
247: + int shortestPath = pointsFirst.size() + vectorsSecond.size();
248: + Cpoint origin = new Cpoint( 0, 0 );
249: + Cpoint previous = origin;
250: + Cpoint tip = origin;
251: + Cpoint currentP = null;
252: + int seen = 0;
253: + for ( Vector arrow : vectorsSecond )
254: + {
255: + switch ( arrow.direction )
256: + {
257: + case UP :
258: + {
259: + tip = new Cpoint( previous.x, previous.y + arrow.magnitude );
260: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
261: + if ( pointsFirst.containsKey( tip )
262: + && ! tip.equals( origin ) )
263: + {
264: + shortestPath = Math.min(
265: + shortestPath,
266: + seen + arrow.magnitude + pointsFirst.get( tip ) );
267: + }
268: + for ( int ind = previous.y; ind < tip.y; ind++ )
269: + {
270: + currentP = new Cpoint( previous.x, ind );
271: + if ( pointsFirst.containsKey( currentP )
272: + && ! currentP.equals( origin ) )
273: + {
274: + shortestPath = Math.min(
275: + shortestPath,
276: + seen + ind + pointsFirst.get( currentP ) );
277: + }
278: + // System.out.println( "\t\t"+ previous.x +" : "+ ind );
279: + }
280: + break;
281: + }
282: + case DOWN :
283: + {
284: + tip = new Cpoint( previous.x, previous.y - arrow.magnitude );
285: + if ( pointsFirst.containsKey( tip )
286: + && ! tip.equals( origin ) )
287: + {
288: + shortestPath = Math.min(
289: + shortestPath,
290: + seen + arrow.magnitude + pointsFirst.get( tip ) );
291: + }
292: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
293: + for ( int ind = tip.y; ind < previous.y; ind++ )
294: + {
295: + currentP = new Cpoint( previous.x, ind );
296: + if ( pointsFirst.containsKey( currentP )
297: + && ! currentP.equals( origin ) )
298: + {
299: + shortestPath = Math.min(
300: + shortestPath,
301: + seen + ind + pointsFirst.get( currentP ) );
302: + }
303: + // System.out.println( "\t\t"+ previous.x +" : "+ ind );
304: + }
305: + break;
306: + }
307: + case LEFT :
308: + {
309: + tip = new Cpoint( previous.x - arrow.magnitude, previous.y );
310: + if ( pointsFirst.containsKey( tip )
311: + && ! tip.equals( origin ) )
312: + {
313: + shortestPath = Math.min(
314: + shortestPath,
315: + seen + arrow.magnitude + pointsFirst.get( tip ) );
316: + }
317: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
318: + for ( int ind = tip.x; ind < previous.x; ind++ )
319: + {
320: + currentP = new Cpoint( ind, previous.y );
321: + if ( pointsFirst.containsKey( currentP )
322: + && ! currentP.equals( origin ) )
323: + {
324: + shortestPath = Math.min(
325: + shortestPath,
326: + seen + ind + pointsFirst.get( currentP ) );
327: + }
328: + // System.out.println( "\t\t"+ ind +" : "+ previous.y );
329: + }
330: + break;
331: + }
332: + case RIGHT :
333: + {
334: + tip = new Cpoint( previous.x + arrow.magnitude, previous.y );
335: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
336: + if ( pointsFirst.containsKey( tip )
337: + && ! tip.equals( origin ) )
338: + {
339: + shortestPath = Math.min(
340: + shortestPath,
341: + seen + arrow.magnitude + pointsFirst.get( tip ) );
342: + }
343: + for ( int ind = previous.x; ind < tip.x; ind++ )
344: + {
345: + currentP = new Cpoint( previous.x, ind );
346: + if ( pointsFirst.containsKey( currentP )
347: + && ! currentP.equals( origin ) )
348: + {
349: + shortestPath = Math.min(
350: + shortestPath,
351: + seen + ind + pointsFirst.get( currentP ) );
352: + }
353: + // System.out.println( "\t\t"+ ind +" : "+ previous.y );
354: + }
355: + break;
356: + }
357: + default :
358: + {
359: + break;
360: + }
361: + }
362: + seen += arrow.magnitude;
363: + // System.out.println( "\t"+ here + tip );
364: + previous.setLocation( tip );
365: + }
366: + return shortestPath;
367: + }
368: +
369: +
370: + @Deprecated
371: + private Set<Cpoint> pointsOfLine( Collection<Vector> instructions )
372: + {
373: + final String here = cl +"pol ";
374: + // Set<Cpoint> allPoints = new HashSet<>( instructions.size() * 10 );
375: + Set<Cpoint> allPoints = new TreeSet<>();
376: + Cpoint origin = new Cpoint( 0, 0 );
377: + Cpoint previous = origin;
378: + Cpoint tip = origin;
379: + for ( Vector arrow : instructions )
380: + {
381: + // System.out.println( "\t\taa "+ arrow );
382: + switch ( arrow.direction )
383: + {
384: + case UP :
385: + {
386: + tip = new Cpoint( previous.x, previous.y + arrow.magnitude );
387: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
388: + allPoints.add( tip );
389: + for ( int ind = previous.y; ind < tip.y; ind++ )
390: + {
391: + allPoints.add( new Cpoint( previous.x, ind ) );
392: + // System.out.println( "\t\t"+ previous.x +" : "+ ind );
393: + }
394: + break;
395: + }
396: + case DOWN :
397: + {
398: + tip = new Cpoint( previous.x, previous.y - arrow.magnitude );
399: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
400: + allPoints.add( tip );
401: + for ( int ind = tip.y; ind < previous.y; ind++ )
402: + {
403: + allPoints.add( new Cpoint( previous.x, ind ) );
404: + // System.out.println( "\t\t"+ previous.x +" : "+ ind );
405: + }
406: + break;
407: + }
408: + case LEFT :
409: + {
410: + tip = new Cpoint( previous.x - arrow.magnitude, previous.y );
411: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
412: + allPoints.add( tip );
413: + for ( int ind = tip.x; ind < previous.x; ind++ )
414: + {
415: + allPoints.add( new Cpoint( ind, previous.y ) );
416: + // System.out.println( "\t\t"+ ind +" : "+ previous.y );
417: + }
418: + break;
419: + }
420: + case RIGHT :
421: + {
422: + tip = new Cpoint( previous.x + arrow.magnitude, previous.y );
423: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
424: + allPoints.add( tip );
425: + for ( int ind = previous.x; ind < tip.x; ind++ )
426: + {
427: + allPoints.add( new Cpoint( ind, previous.y ) );
428: + // System.out.println( "\t\t"+ ind +" : "+ previous.y );
429: + }
430: + break;
431: + }
432: + default :
433: + {
434: + break;
435: + }
436: + }
437: + // System.out.println( "\t"+ here + tip );
438: + previous.setLocation( tip );
439: + }
440: + /*
441: + for ( Cpoint buh : allPoints )
442: + {
443: + System.out.println( "\t"+ here + buh );
444: + }
445: + */
446: + return allPoints;
447: + }
448: +
449: +
450: + private void render( Set<Cpoint> toShow )
451: + {
452: + int minXx = 0;
453: + int maxXx = 0;
454: + int minYy = 0;
455: + int maxYy = 0;
456: + for ( Cpoint candidate : toShow )
457: + {
458: + if ( candidate.x < minXx )
459: + minXx = candidate.x;
460: + if ( candidate.x > maxXx )
461: + maxXx = candidate.x;
462: + if ( candidate.y < minYy )
463: + minYy = candidate.y;
464: + if ( candidate.y > maxYy )
465: + maxYy = candidate.y;
466: + }
467: + Cpoint probe = new Cpoint( 0, 0 );
468: + for ( int indXx = minXx; indXx <= maxXx; indXx += 1 )
469: + {
470: + for ( int indYy = minYy; indYy <= maxYy; indYy += 1 )
471: + {
472: + probe.setLocation( indXx, indYy );
473: + if ( toShow.contains( probe ) )
474: + System.out.print( "x " );
475: + else
476: + System.out.print( "- " );
477: + }
478: + System.out.println();
479: + }
480: + }
481: +
482: +
483: + private void render( Set<Cpoint> first, Set<Cpoint> second )
484: + {
485: + int minXx = 0;
486: + int maxXx = 0;
487: + int minYy = 0;
488: + int maxYy = 0;
489: + for ( Cpoint candidate : first )
490: + {
491: + if ( candidate.x < minXx )
492: + minXx = candidate.x;
493: + if ( candidate.x > maxXx )
494: + maxXx = candidate.x;
495: + if ( candidate.y < minYy )
496: + minYy = candidate.y;
497: + if ( candidate.y > maxYy )
498: + maxYy = candidate.y;
499: + }
500: + for ( Cpoint candidate : second )
501: + {
502: + if ( candidate.x < minXx )
503: + minXx = candidate.x;
504: + if ( candidate.x > maxXx )
505: + maxXx = candidate.x;
506: + if ( candidate.y < minYy )
507: + minYy = candidate.y;
508: + if ( candidate.y > maxYy )
509: + maxYy = candidate.y;
510: + }
511: + Cpoint probe = new Cpoint( minXx, minYy );
512: + for ( int indXx = minXx; indXx <= maxXx; indXx += 1 )
513: + {
514: + for ( int indYy = minYy; indYy <= maxYy; indYy += 1 )
515: + {
516: + probe.setLocation( indXx, indYy );
517: + if ( first.contains( probe ) && second.contains( probe ) )
518: + System.out.print( "* " );
519: + else if ( first.contains( probe ) )
520: + System.out.print( "x " );
521: + else if ( second.contains( probe ) )
522: + System.out.print( "k " );
523: + else
524: + System.out.print( "- " );
525: + }
526: + System.out.println();
527: + }
528: + }
529: +
530: +
531: + @Deprecated
532: + private Set<Cpoint> intersectionsOf( Set<Cpoint> first, Set<Cpoint> second )
533: + {
534: + final String here = cl +"io ";
535: + Set<Cpoint> intersections = new HashSet<>( first.size() /10 );
536: + for ( Cpoint candidate : first )
537: + {
538: + if ( second.contains( candidate ) )
539: + {
540: + intersections.add( candidate );
541: + // System.out.println( here + candidate );
542: + }
543: + }
544: + return intersections;
545: + }
546: +
547: +
548: + @Deprecated
549: + private Cpoint closestToOrigin( Set<Cpoint> somePoints )
550: + {
551: + Cpoint origin = new Cpoint( 0, 0 );
552: + Cpoint probe = new Cpoint( 0, 0 );
553: + double minDistance = Double.MAX_VALUE, currDistance = -1;
554: + for ( Cpoint candidate : somePoints )
555: + {
556: + if ( candidate.compareTo( origin ) == 0 )
557: + continue;
558: + currDistance = origin.distance( candidate );
559: + if ( currDistance < minDistance )
560: + {
561: + probe.setLocation( candidate );
562: + minDistance = currDistance;
563: + }
564: + }
565: + System.out.println( cl +"coo "+ minDistance );
566: + return probe;
567: + }
568: +
569: +
570: + @Deprecated
571: + private Cpoint closestToOriginManhattanwise( Set<Cpoint> somePoints )
572: + {
573: + Cpoint origin = new Cpoint( 0, 0 );
574: + Cpoint probe = new Cpoint( 0, 0 );
575: + int minDistance = Integer.MAX_VALUE, currDistance = -1;
576: + for ( Cpoint candidate : somePoints )
577: + {
578: + if ( candidate.compareTo( origin ) == 0 )
579: + continue;
580: + currDistance = Math.abs( candidate.x ) + Math.abs( candidate.y );
581: + if ( currDistance < minDistance )
582: + {
583: + probe.setLocation( candidate );
584: + minDistance = currDistance;
585: + }
586: + }
587: + System.out.println( cl +"coo "+ minDistance );
588: + return probe;
589: + }
590: +
591: +
592: + private class Vector
593: + {
594: + int magnitude = 0;
595: + CardinalDirection direction = CardinalDirection.UNKNOWN;
596: +
597: + @Override
598: + public String toString()
599: + {
600: + return direction.toString() + Integer.valueOf( magnitude ).toString();
601: + }
602: + }
603: +
604: +
605: + private enum CardinalDirection
606: + {
607: + UP( "U" ),
608: + DOWN( "D" ),
609: + LEFT( "L" ),
610: + RIGHT( "R" ),
611: + UNKNOWN( "" );
612: +
613: + public static CardinalDirection from( String candidate )
614: + {
615: + for ( CardinalDirection canon : CardinalDirection.values() )
616: + {
617: + if ( canon.toString().equals( candidate ) )
618: + return canon;
619: + }
620: + return CardinalDirection.UNKNOWN; // NOTE fallback
621: + }
622: +
623: + private String equivalent;
624: +
625: + private CardinalDirection( String code )
626: + {
627: + equivalent = code;
628: + }
629: +
630: + @Override
631: + public String toString()
632: + {
633: + return equivalent;
634: + }
635: + }
636: +
637: +
638: + private class Cpoint extends Point implements Comparable<Cpoint>
639: + {
640: + public Cpoint( int xx, int yy )
641: + {
642: + super( xx, yy );
643: + }
644: +
645: + @Override
646: + public int compareTo( Cpoint another )
647: + {
648: + if ( this.x == another.x )
649: + {
650: + if ( this.y == another.y )
651: + return 0;
652: + else if ( this.y < another.y )
653: + return -1;
654: + else
655: + return 1;
656: + }
657: + else if ( this.x < another.x )
658: + return -1;
659: + else
660: + return 1;
661: + }
662: +
663: + @Override
664: + public String toString()
665: + {
666: + return "C"+ x +","+ y;
667: + }
668: + }
669: +
670: +}
671: +
672: +
673: +
674: +
675: +
676: +
677: +
678: +
679: +
680: +
681: +
682: +
683: +
684: +
685: +
686: +
687: +
688: +
689: +
690: +
691: +
692: +
693: +
694: +
695: +
696: +
697: +
698: diff --git a/src/res/19_03-2_input_results.txt b/src/res/19_03-2_input_results.txt
699: new file mode 100644
700: index 0000000..0515934
701: --- /dev/null
702: +++ b/src/res/19_03-2_input_results.txt
703: @@ -0,0 +1,3 @@
704: +trivial 30
705: +easy-159 610
706: +easy-135 410
707: \ No newline at end of file