Author: Nicholas Prado <nmprado@nzen.ws>
Date: Tue Dec 3 09:24:08 UTC 2019
Parent: cf8b3f1d5af1d5e024e52d55740a7645e72402ce
Log message:
feat solves D3 p1
Makes sets of integral points that the wires lay down. Finds a
set of intersectons. Determines which intersection point has
the smallest taxicab geometry distance from the origin. It's
worth noting that this renders the grid rotated from the trivial
example, but the coordinates are the same. This makes no provision
for the size of your console, should you render a large grid.
1: diff --git a/src/java/Exercise19031.java b/src/java/Exercise19031.java
2: new file mode 100644
3: index 0000000..bb868ec
4: --- /dev/null
5: +++ b/src/java/Exercise19031.java
6: @@ -0,0 +1,457 @@
7: +
8: +import java.awt.Point;
9: +import java.io.IOException;
10: +import java.nio.file.Files;
11: +import java.nio.file.InvalidPathException;
12: +import java.nio.file.Path;
13: +import java.nio.file.Paths;
14: +import java.util.ArrayList;
15: +import java.util.Collection;
16: +import java.util.LinkedList;
17: +import java.util.List;
18: +import java.util.HashSet;
19: +import java.util.Map;
20: +import java.util.Set;
21: +import java.util.SortedSet;
22: +import java.util.TreeMap;
23: +import java.util.TreeSet;
24: +
25: +public class Exercise19031
26: +{
27: +
28: + public static void main( String args[] )
29: + {
30: + final String here = Exercise19031.cl +"m ";
31: + if ( args.length < 1 )
32: + {
33: + throw new RuntimeException( here +"add a filename argument" );
34: + }
35: + String userSaysFile = args[ 0 ];
36: + List<String> fileLines = new LinkedList<>();
37: + try
38: + {
39: + Path where = Paths.get( userSaysFile );
40: + fileLines = Files.readAllLines( where );
41: + }
42: + catch ( IOException | InvalidPathException ie )
43: + {
44: + System.err.println( here +"couldn't read file "+ userSaysFile +" because "+ ie );
45: + return;
46: + }
47: + /*
48: + - interpretation of spec -
49: + input has two csv strings, each is a wire
50: + elements are cardinal vectors of operand {R D L U}
51: + note the paths these take
52: + note the intersections between them (but not of itself)
53: + of those intersections, choose the point closest to origin
54: + convert that distance to the 'manhattan'/'taxicab' distance (by making cardinal vectors to reach)
55: + this is the result to provide
56: +
57: + potential means
58: + make a set of integral points on the line of each part of the path
59: + for each point of first wire, check if second wire contains point
60: + if so add to intersection set
61: + calculate the distance of each point in the intersection set, directly or as 'manhattan' distance
62: + create a map of intersection points : 'manhattan' distance from the origin
63: + choose the lowest valued point, reply with this
64: +
65: + split by comma
66: + have an awareness of the current
67: + convert instruction into a vector
68: + gen the list of point pairs indicated
69: + */
70: + new Exercise19031( fileLines.get( 0 ), fileLines.get( 1 ) )
71: + .manhattanDistanceOfClosestIntersection();
72: + }
73: +
74: +
75: + private static final String cl = "e19031.";
76: + private String firstWire;
77: + private String secondWire;
78: +
79: +
80: + public Exercise19031( String first, String second )
81: + {
82: + firstWire = first;
83: + secondWire = second;
84: + }
85: +
86: +
87: + public void manhattanDistanceOfClosestIntersection()
88: + {
89: + final String here = cl +"mdhoci ";
90: + // System.out.println( "\t"+ here + "--- "+ firstWire );
91: + Collection<Vector> convertedFirst = converted( firstWire );
92: + Set<Cpoint> pointsFirst = pointsOfLine( convertedFirst );
93: +
94: + // System.out.println( "\t"+ here + "--- "+ secondWire );
95: + Collection<Vector> convertedSecond = converted( secondWire );
96: + Set<Cpoint> pointsSecond = pointsOfLine( convertedSecond );
97: +
98: + // render( pointsFirst, pointsSecond );
99: + Set<Cpoint> crossover = intersectionsOf( pointsFirst, pointsSecond );
100: + Cpoint closest = closestToOriginManhattanwise( crossover );
101: + System.out.println( "\t"+ here + "closest "+ closest );
102: + /*
103: + make a set of integral points on the line of each part of the path
104: + for each point of first wire, check if second wire contains point
105: + if so add to intersection set
106: + calculate the distance of each point in the intersection set, directly or as 'manhattan' distance
107: + create a map of intersection points : 'manhattan' distance from the origin
108: + choose the lowest valued point, reply with this
109: +
110: + have an awareness of the current
111: + convert instruction into a vector
112: + gen the list of point pairs indicated
113: + */
114: + // 4TESTS
115: + }
116: +
117: +
118: + private Collection<Vector> converted( String which )
119: + {
120: + String[] notCsv = which.split( "," );
121: + Collection<Vector> converted = new ArrayList<>( notCsv.length );
122: + for ( String acronym : notCsv )
123: + {
124: + converted.add( vectorOfAcronym( acronym ) );
125: + }
126: + return converted;
127: + }
128: +
129: +
130: + private Vector vectorOfAcronym( String input )
131: + {
132: + Vector result = new Vector();
133: + result.magnitude = Integer.parseInt( input.substring( 1 ) );
134: + result.direction = CardinalDirection.from( input.substring( 0, 1 ) );
135: + return result;
136: + }
137: +
138: +
139: + private Set<Cpoint> pointsOfLine( Collection<Vector> instructions )
140: + {
141: + final String here = cl +"pol ";
142: + // Set<Cpoint> allPoints = new HashSet<>( instructions.size() * 10 );
143: + Set<Cpoint> allPoints = new TreeSet<>();
144: + Cpoint origin = new Cpoint( 0, 0 );
145: + Cpoint previous = origin;
146: + Cpoint tip = origin;
147: + for ( Vector arrow : instructions )
148: + {
149: + // System.out.println( "\t\taa "+ arrow );
150: + switch ( arrow.direction )
151: + {
152: + case UP :
153: + {
154: + tip = new Cpoint( previous.x, previous.y + arrow.magnitude );
155: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
156: + allPoints.add( tip );
157: + for ( int ind = previous.y; ind < tip.y; ind++ )
158: + {
159: + allPoints.add( new Cpoint( previous.x, ind ) );
160: + // System.out.println( "\t\t"+ previous.x +" : "+ ind );
161: + }
162: + break;
163: + }
164: + case DOWN :
165: + {
166: + tip = new Cpoint( previous.x, previous.y - arrow.magnitude );
167: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
168: + allPoints.add( tip );
169: + for ( int ind = tip.y; ind < previous.y; ind++ )
170: + {
171: + allPoints.add( new Cpoint( previous.x, ind ) );
172: + // System.out.println( "\t\t"+ previous.x +" : "+ ind );
173: + }
174: + break;
175: + }
176: + case LEFT :
177: + {
178: + tip = new Cpoint( previous.x - arrow.magnitude, previous.y );
179: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
180: + allPoints.add( tip );
181: + for ( int ind = tip.x; ind < previous.x; ind++ )
182: + {
183: + allPoints.add( new Cpoint( ind, previous.y ) );
184: + // System.out.println( "\t\t"+ ind +" : "+ previous.y );
185: + }
186: + break;
187: + }
188: + case RIGHT :
189: + {
190: + tip = new Cpoint( previous.x + arrow.magnitude, previous.y );
191: + // System.out.println( "\t\tt "+ tip.x +" : "+ tip.y );
192: + allPoints.add( tip );
193: + for ( int ind = previous.x; ind < tip.x; ind++ )
194: + {
195: + allPoints.add( new Cpoint( ind, previous.y ) );
196: + // System.out.println( "\t\t"+ ind +" : "+ previous.y );
197: + }
198: + break;
199: + }
200: + default :
201: + {
202: + break;
203: + }
204: + }
205: + // System.out.println( "\t"+ here + tip );
206: + previous.setLocation( tip );
207: + }
208: + /*
209: + for ( Cpoint buh : allPoints )
210: + {
211: + System.out.println( "\t"+ here + buh );
212: + }
213: + */
214: + return allPoints;
215: + }
216: +
217: +
218: + private void render( Set<Cpoint> toShow )
219: + {
220: + int minXx = 0;
221: + int maxXx = 0;
222: + int minYy = 0;
223: + int maxYy = 0;
224: + for ( Cpoint candidate : toShow )
225: + {
226: + if ( candidate.x < minXx )
227: + minXx = candidate.x;
228: + if ( candidate.x > maxXx )
229: + maxXx = candidate.x;
230: + if ( candidate.y < minYy )
231: + minYy = candidate.y;
232: + if ( candidate.y > maxYy )
233: + maxYy = candidate.y;
234: + }
235: + Cpoint probe = new Cpoint( 0, 0 );
236: + for ( int indXx = minXx; indXx <= maxXx; indXx += 1 )
237: + {
238: + for ( int indYy = minYy; indYy <= maxYy; indYy += 1 )
239: + {
240: + probe.setLocation( indXx, indYy );
241: + if ( toShow.contains( probe ) )
242: + System.out.print( "x " );
243: + else
244: + System.out.print( "- " );
245: + }
246: + System.out.println();
247: + }
248: + }
249: +
250: +
251: + private void render( Set<Cpoint> first, Set<Cpoint> second )
252: + {
253: + int minXx = 0;
254: + int maxXx = 0;
255: + int minYy = 0;
256: + int maxYy = 0;
257: + for ( Cpoint candidate : first )
258: + {
259: + if ( candidate.x < minXx )
260: + minXx = candidate.x;
261: + if ( candidate.x > maxXx )
262: + maxXx = candidate.x;
263: + if ( candidate.y < minYy )
264: + minYy = candidate.y;
265: + if ( candidate.y > maxYy )
266: + maxYy = candidate.y;
267: + }
268: + for ( Cpoint candidate : second )
269: + {
270: + if ( candidate.x < minXx )
271: + minXx = candidate.x;
272: + if ( candidate.x > maxXx )
273: + maxXx = candidate.x;
274: + if ( candidate.y < minYy )
275: + minYy = candidate.y;
276: + if ( candidate.y > maxYy )
277: + maxYy = candidate.y;
278: + }
279: + Cpoint probe = new Cpoint( minXx, minYy );
280: + for ( int indXx = minXx; indXx <= maxXx; indXx += 1 )
281: + {
282: + for ( int indYy = minYy; indYy <= maxYy; indYy += 1 )
283: + {
284: + probe.setLocation( indXx, indYy );
285: + if ( first.contains( probe ) && second.contains( probe ) )
286: + System.out.print( "* " );
287: + else if ( first.contains( probe ) )
288: + System.out.print( "x " );
289: + else if ( second.contains( probe ) )
290: + System.out.print( "k " );
291: + else
292: + System.out.print( "- " );
293: + }
294: + System.out.println();
295: + }
296: + }
297: +
298: +
299: + private Set<Cpoint> intersectionsOf( Set<Cpoint> first, Set<Cpoint> second )
300: + {
301: + final String here = cl +"io ";
302: + Set<Cpoint> intersections = new HashSet<>( first.size() /10 );
303: + for ( Cpoint candidate : first )
304: + {
305: + if ( second.contains( candidate ) )
306: + {
307: + intersections.add( candidate );
308: + // System.out.println( here + candidate );
309: + }
310: + }
311: + return intersections;
312: + }
313: +
314: +
315: + // deprecated
316: + private Cpoint closestToOrigin( Set<Cpoint> somePoints )
317: + {
318: + Cpoint origin = new Cpoint( 0, 0 );
319: + Cpoint probe = new Cpoint( 0, 0 );
320: + double minDistance = Double.MAX_VALUE, currDistance = -1;
321: + for ( Cpoint candidate : somePoints )
322: + {
323: + if ( candidate.compareTo( origin ) == 0 )
324: + continue;
325: + currDistance = origin.distance( candidate );
326: + if ( currDistance < minDistance )
327: + {
328: + probe.setLocation( candidate );
329: + minDistance = currDistance;
330: + }
331: + }
332: + System.out.println( cl +"coo "+ minDistance );
333: + return probe;
334: + }
335: +
336: +
337: + private Cpoint closestToOriginManhattanwise( Set<Cpoint> somePoints )
338: + {
339: + Cpoint origin = new Cpoint( 0, 0 );
340: + Cpoint probe = new Cpoint( 0, 0 );
341: + int minDistance = Integer.MAX_VALUE, currDistance = -1;
342: + for ( Cpoint candidate : somePoints )
343: + {
344: + if ( candidate.compareTo( origin ) == 0 )
345: + continue;
346: + currDistance = Math.abs( candidate.x ) + Math.abs( candidate.y );
347: + if ( currDistance < minDistance )
348: + {
349: + probe.setLocation( candidate );
350: + minDistance = currDistance;
351: + }
352: + }
353: + System.out.println( cl +"coo "+ minDistance );
354: + return probe;
355: + }
356: +
357: +
358: + private class Vector
359: + {
360: + int magnitude = 0;
361: + CardinalDirection direction = CardinalDirection.UNKNOWN;
362: +
363: + @Override
364: + public String toString()
365: + {
366: + return direction.toString() + Integer.valueOf( magnitude ).toString();
367: + }
368: + }
369: +
370: +
371: + private enum CardinalDirection
372: + {
373: + UP( "U" ),
374: + DOWN( "D" ),
375: + LEFT( "L" ),
376: + RIGHT( "R" ),
377: + UNKNOWN( "" );
378: +
379: + public static CardinalDirection from( String candidate )
380: + {
381: + for ( CardinalDirection canon : CardinalDirection.values() )
382: + {
383: + if ( canon.toString().equals( candidate ) )
384: + return canon;
385: + }
386: + return CardinalDirection.UNKNOWN; // NOTE fallback
387: + }
388: +
389: + private String equivalent;
390: +
391: + private CardinalDirection( String code )
392: + {
393: + equivalent = code;
394: + }
395: +
396: + @Override
397: + public String toString()
398: + {
399: + return equivalent;
400: + }
401: + }
402: +
403: +
404: + private class Cpoint extends Point implements Comparable<Cpoint>
405: + {
406: + public Cpoint( int xx, int yy )
407: + {
408: + super( xx, yy );
409: + }
410: +
411: + @Override
412: + public int compareTo( Cpoint another )
413: + {
414: + if ( this.x == another.x )
415: + {
416: + if ( this.y == another.y )
417: + return 0;
418: + else if ( this.y < another.y )
419: + return -1;
420: + else
421: + return 1;
422: + }
423: + else if ( this.x < another.x )
424: + return -1;
425: + else
426: + return 1;
427: + }
428: +
429: + @Override
430: + public String toString()
431: + {
432: + return "C"+ x +","+ y;
433: + }
434: + }
435: +
436: +}
437: +
438: +
439: +
440: +
441: +
442: +
443: +
444: +
445: +
446: +
447: +
448: +
449: +
450: +
451: +
452: +
453: +
454: +
455: +
456: +
457: +
458: +
459: +
460: +
461: +
462: +
463: +
464: diff --git a/src/res/19_03_input.txt b/src/res/19_03_input.txt
465: new file mode 100644
466: index 0000000..d8ad6bf
467: --- /dev/null
468: +++ b/src/res/19_03_input.txt
469: @@ -0,0 +1,2 @@
470: +R992,U284,L447,D597,R888,D327,R949,U520,R27,U555,L144,D284,R538,U249,R323,U297,R136,U838,L704,D621,R488,U856,R301,U539,L701,U363,R611,D94,L734,D560,L414,U890,R236,D699,L384,D452,R702,D637,L164,U410,R649,U901,L910,D595,R339,D346,R959,U777,R218,D667,R534,D762,R484,D914,L25,U959,R984,D922,R612,U999,L169,D599,L604,D357,L217,D327,L730,D949,L565,D332,L114,D512,R460,D495,L187,D697,R313,U319,L8,D915,L518,D513,R738,U9,R137,U542,L188,U440,R576,D307,R734,U58,R285,D401,R166,U156,L859,U132,L10,U753,L933,U915,R459,D50,R231,D166,L253,U844,R585,D871,L799,U53,R785,U336,R622,D108,R555,D918,L217,D668,L220,U738,L997,D998,R964,D456,L54,U930,R985,D244,L613,D116,L994,D20,R949,D245,L704,D564,L210,D13,R998,U951,L482,U579,L793,U680,L285,U770,L975,D54,R79,U613,L907,U467,L256,D783,R883,U810,R409,D508,L898,D286,L40,U741,L759,D549,R210,U411,R638,D643,L784,U538,L739,U771,L773,U491,L303,D425,L891,U182,R412,U951,L381,U501,R482,D625,R870,D320,L464,U555,R566,D781,L540,D754,L211,U73,L321,D869,R994,D177,R496,U383,R911,U819,L651,D774,L591,U666,L883,U767,R232,U822,L499,U44,L45,U873,L98,D487,L47,U803,R855,U256,R567,D88,R138,D678,L37,U38,R783,U569,L646,D261,L597,U275,L527,U48,R433,D324,L631,D160,L145,D128,R894,U223,R664,U510,R756,D700,R297,D361,R837,U996,L769,U813,L477,U420,L172,U482,R891,D379,L329,U55,R284,U155,L816,U659,L671,U996,R997,U252,R514,D718,L661,D625,R910,D960,L39,U610,R853,U859,R174,U215,L603,U745,L587,D736,R365,U78,R306,U158,L813,U885,R558,U631,L110,D232,L519,D366,R909,D10,R294
471: +L1001,D833,L855,D123,R36,U295,L319,D700,L164,U576,L68,D757,R192,D738,L640,D660,R940,D778,R888,U772,R771,U900,L188,D464,L572,U184,R889,D991,L961,U751,R560,D490,L887,D748,R37,U910,L424,D401,L385,U415,L929,U193,R710,D855,L596,D323,L966,D505,L422,D139,L108,D135,R737,U176,R538,D173,R21,D951,R949,D61,L343,U704,R127,U468,L240,D834,L858,D127,R328,D863,R329,U477,R131,U864,R997,D38,R418,U611,R28,U705,R148,D414,R786,U264,L785,D650,R201,D250,R528,D910,R670,U309,L658,U190,R704,U21,R288,D7,R930,U62,R782,U621,R328,D725,R305,U700,R494,D137,R969,U142,L867,U577,R300,U162,L13,D698,R333,U865,R941,U796,L60,U902,L784,U832,R78,D578,R196,D390,R728,D922,R858,D994,L457,U547,R238,D345,R329,D498,R873,D212,R501,U474,L657,U910,L335,U133,R213,U417,R698,U829,L2,U704,L273,D83,R231,D247,R675,D23,L692,D472,L325,D659,L408,U746,L715,U395,L596,U296,R52,D849,L713,U815,R684,D551,L319,U768,R176,D182,R557,U731,R314,D543,L9,D256,R38,D809,L567,D332,R375,D572,R81,D479,L71,U968,L831,D247,R989,U390,R463,D576,R740,D539,R488,U367,L596,U375,L763,D824,R70,U448,R979,D977,L744,D379,R488,D671,L516,D334,L542,U517,L488,D390,L713,D932,L28,U924,L448,D229,L488,D501,R19,D910,L979,D411,R711,D824,L973,U291,R794,D485,R208,U370,R655,U450,L40,D804,L374,D671,R962,D829,L209,U111,L84,D876,L832,D747,L733,D560,L702,D972,R188,U817,L111,U26,L492,U485,L71,D59,L269,D870,L152,U539,R65,D918,L932,D260,L485,U77,L699,U254,R924,U643,L264,U96,R395,D917,R360,U354,R101,D682,R854,U450,L376,D378,R872,D311,L881,U630,R77,D766,R672
472: diff --git a/src/res/19_03_input_easy_135.txt b/src/res/19_03_input_easy_135.txt
473: new file mode 100644
474: index 0000000..4f3a2a4
475: --- /dev/null
476: +++ b/src/res/19_03_input_easy_135.txt
477: @@ -0,0 +1,2 @@
478: +R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
479: +U98,R91,D20,R16,D67,R40,U7,R15,U6,R7
480: diff --git a/src/res/19_03_input_easy_159.txt b/src/res/19_03_input_easy_159.txt
481: new file mode 100644
482: index 0000000..620a05e
483: --- /dev/null
484: +++ b/src/res/19_03_input_easy_159.txt
485: @@ -0,0 +1,2 @@
486: +R75,D30,R83,U83,L12,D49,R71,U7,L72
487: +U62,R66,U55,R34,D71,R55,D58,R83
488: diff --git a/src/res/19_03_input_trivial_6.txt b/src/res/19_03_input_trivial_6.txt
489: new file mode 100644
490: index 0000000..73b95a1
491: --- /dev/null
492: +++ b/src/res/19_03_input_trivial_6.txt
493: @@ -0,0 +1,2 @@
494: +R8,U5,L5,D3
495: +U7,R6,D4,L4