some-advent-of-code: 883baee32ed735b519879b1b0b7a0537d9801cc7
1:
2: import java.io.IOException;
3: import java.nio.file.Files;
4: import java.nio.file.InvalidPathException;
5: import java.nio.file.Path;
6: import java.nio.file.Paths;
7: import java.text.ParseException;
8: import java.util.LinkedList;
9: import java.util.List;
10: import java.util.Map;
11: import java.util.NavigableMap;
12: import java.util.Set;
13: import java.util.TreeSet;
14: import java.util.TreeMap;
15: import java.util.regex.Matcher;
16: import java.util.regex.Pattern;
17:
18: public class Exercise18031
19: {
20: private class Rectangle
21: {
22: String rectId = "";
23: int posX = 0;
24: int posY = 0;
25: int lenX = 0;
26: int lenY = 0;
27: boolean beenChecked = false;
28: public String toString()
29: {
30: return String.format( "id-%s px-%d py-%d lx-%d ly-%d",
31: rectId, posX, posY, lenX, lenY );
32: }
33: }
34: private static final String cl = "e18031.";
35:
36: public static void main( String args[] )
37: {
38: final String here = cl +"m ";
39: if ( args.length < 1 )
40: {
41: throw new RuntimeException( here +"add a filename argument" );
42: }
43: String userSaysFile = args[ 0 ];
44: List<String> fileLines = new LinkedList<>();
45: try
46: {
47: Path where = Paths.get( userSaysFile );
48: fileLines = Files.readAllLines( where );
49: }
50: catch ( IOException | InvalidPathException ie )
51: {
52: System.err.println( here +"couldn't read file "+ userSaysFile +" because "+ ie );
53: return;
54: }
55: Exercise18031 solvesTheProblem = new Exercise18031();
56: solvesTheProblem.with( fileLines );
57: }
58:
59:
60: void with( List<String> fileLines )
61: {
62: final String here = cl +"w ";
63: // 4TESTS
64: fileLines.clear();
65: fileLines.add( "#11 @ 1,1: 3x3" );
66: fileLines.add( "#22 @ 2,1: 3x3" );
67: fileLines.add( "#33 @ 1,2: 3x3" );
68: // fileLines.add( "#44 @ 5,4: 1x1" );
69: // fileLines.add( "#55 @ 1,6: 7x3" );
70: // 4TESTS
71: List<Rectangle> userRectangles = parse( fileLines );
72: Map<String, Rectangle> allRect = new TreeMap<>();
73: NavigableMap<Integer, List<String>> xxPositions = new TreeMap<>();
74: NavigableMap<Integer, List<String>> yyPositions = new TreeMap<>();
75: for ( Rectangle currRect : userRectangles )
76: {
77: allRect.put( currRect.rectId, currRect );
78: List<String> shapesAtXx = xxPositions.get( currRect.posX );
79: if ( shapesAtXx == null )
80: {
81: shapesAtXx = new LinkedList<>();
82: }
83: shapesAtXx.add( currRect.rectId );
84: xxPositions.put( currRect.posX, shapesAtXx );
85: List<String> shapesAtYy = yyPositions.get( currRect.posY );
86: if ( shapesAtYy == null )
87: {
88: shapesAtYy = new LinkedList<>();
89: }
90: shapesAtYy.add( currRect.rectId );
91: yyPositions.put( currRect.posY, shapesAtYy );
92: }
93: String delimiter = "@@", separator = "^^";
94: Set<String> bothOcclude = occlusionPairs(
95: userRectangles, xxPositions, yyPositions, delimiter );
96: // NOTE create new rectangles at the intersection
97: Map<String, Rectangle> allJoins = new TreeMap<>();
98: xxPositions.clear();
99: yyPositions.clear();
100: for ( String comboId : bothOcclude )
101: {
102: String[] pair = comboId.split( delimiter );
103: Rectangle first = allRect.get( pair[0 ] );
104: Rectangle last = allRect.get( pair[ 1 ] );
105: Rectangle intersect = intersectionOf( first, last, comboId );
106: System.out.println( here +"occluded at "+ intersect ); // 4TESTS
107: allJoins.put( comboId, intersect );
108: List<String> shapesAtXx = xxPositions.get( intersect.posX );
109: if ( shapesAtXx == null )
110: {
111: shapesAtXx = new LinkedList<>();
112: }
113: shapesAtXx.add( intersect.rectId );
114: xxPositions.put( intersect.posX, shapesAtXx );
115: List<String> shapesAtYy = yyPositions.get( intersect.posY );
116: if ( shapesAtYy == null )
117: {
118: shapesAtYy = new LinkedList<>();
119: }
120: shapesAtYy.add( intersect.rectId );
121: yyPositions.put( intersect.posY, shapesAtYy );
122: }
123: System.out.println( here +"combined area is "+ overlappingAreaOf( allJoins, xxPositions, yyPositions, separator ) );
124: }
125:
126:
127: /** format: #[[ number ]] @ [[ x ]],[[ y ]]: [[ width ]]x[[ height ]]
128: ex: #121 @ 55,2424: 224x2424 */
129: List<Rectangle> parse( List<String> rectangleDesc )
130: {
131: final String here = cl +"p ";
132: List<Rectangle> rectangles = new LinkedList<>();
133: int idInd = 1, xposInd = idInd +1, yposInd = xposInd +1,
134: xlenInd = yposInd +1, ylenInd = xlenInd +1; // one indexed because 0 is the whole thing
135: int currInd = 0;
136: String rectangleFormat = "#(\\d+) @ (\\d+),(\\d+): (\\d+)x(\\d+)";
137: String expression = "";
138: try
139: {
140: Pattern fsmSpec = Pattern.compile( rectangleFormat );
141: Matcher fsmRuntime;
142: for ( String currInput : rectangleDesc )
143: {
144: expression = currInput; // 4TESTS ensuring that I can get the problematic line, otherwise unnecessary
145: fsmRuntime = fsmSpec.matcher( currInput );
146: Rectangle currRect = new Rectangle();
147: if ( fsmRuntime.find( currInd ) )
148: {
149: currRect.rectId = fsmRuntime.group( idInd );
150: currRect.posX = Integer.valueOf( fsmRuntime.group( xposInd ) );
151: currRect.posY = Integer.valueOf( fsmRuntime.group( yposInd ) );
152: currRect.lenX = Integer.valueOf( fsmRuntime.group( xlenInd ) );
153: currRect.lenY = Integer.valueOf( fsmRuntime.group( ylenInd ) );
154: rectangles.add( currRect );
155: }
156: }
157: }
158: catch ( IllegalArgumentException | IllegalStateException iae )
159: {
160: System.err.println( here +"couldn't interpret "+ expression
161: +" as a rectangle "+ iae );
162: }
163: return rectangles;
164: }
165:
166:
167: Set<String> occlusionPairs( List<Rectangle> userRectangles,
168: NavigableMap<Integer, List<String>> xxPositions,
169: NavigableMap<Integer, List<String>> yyPositions,
170: String delimiter )
171: {
172: Set<String> bothOcclude = new TreeSet<>();
173: final boolean inclusive = true;
174: for ( Rectangle currRect : userRectangles )
175: {
176: NavigableMap<Integer, List<String>> xxOcclusions = xxPositions.subMap(
177: currRect.posX, inclusive, currRect.posX + currRect.lenX, ! inclusive );
178: NavigableMap<Integer, List<String>> yyOcclusions = yyPositions.subMap(
179: currRect.posY, inclusive, currRect.posY + currRect.lenY, ! inclusive );
180: Set<String> inXxShadow = new TreeSet<>();
181: Set<String> inYyShadow = new TreeSet<>();
182: for ( Integer currXx : xxOcclusions.keySet() )
183: {
184: List<String> idsAtXx = xxOcclusions.get( currXx );
185: for ( String idAt : idsAtXx )
186: {
187: if ( idAt.equals( currRect.rectId ) )
188: {
189: continue;
190: }
191: else
192: {
193: inXxShadow.add( idAt );
194: }
195: }
196: }
197: for ( Integer currYy : yyOcclusions.keySet() )
198: {
199: List<String> idsAtYy = yyOcclusions.get( currYy );
200: for ( String idAt : idsAtYy )
201: {
202: if ( idAt.equals( currRect.rectId ) )
203: {
204: continue;
205: }
206: else
207: {
208: inYyShadow.add( idAt );
209: }
210: }
211: }
212: // NOTE find the intersection of the two sets, these actually overlap the current rectangle
213: for ( String xxId : inXxShadow )
214: {
215: for ( String yyId : inYyShadow )
216: {
217: if ( xxId.equals( yyId )
218: && ! bothOcclude.contains( xxId + delimiter + currRect.rectId ) ) // avoiding inserting when we find the reverse of an existing pair
219: {
220: bothOcclude.add( currRect.rectId + delimiter + xxId );
221: }
222: }
223: }
224: }
225: return bothOcclude;
226: }
227:
228:
229: int overlappingAreaOf( Map<String, Rectangle> allJoins,
230: NavigableMap<Integer, List<String>> xxPositions,
231: NavigableMap<Integer, List<String>> yyPositions,
232: String delimiter )
233: {
234: int combinedArea = 0;
235: final boolean inclusive = true;
236: boolean multiOverlap;
237: for ( String pairId : allJoins.keySet() )
238: {
239: multiOverlap = false;
240: Rectangle currRect = allJoins.get( pairId );
241: NavigableMap<Integer, List<String>> xxOcclusions = xxPositions.subMap(
242: currRect.posX, inclusive, currRect.posX + currRect.lenX, ! inclusive );
243: NavigableMap<Integer, List<String>> yyOcclusions = yyPositions.subMap(
244: currRect.posY, inclusive, currRect.posY + currRect.lenY, ! inclusive );
245: Set<String> inXxShadow = new TreeSet<>();
246: Set<String> inYyShadow = new TreeSet<>();
247: for ( Integer currXx : xxOcclusions.keySet() )
248: {
249: List<String> idsAtXx = xxOcclusions.get( currXx );
250: for ( String idAt : idsAtXx )
251: {
252: if ( idAt.equals( currRect.rectId ) )
253: {
254: continue;
255: }
256: else
257: {
258: inXxShadow.add( idAt );
259: multiOverlap |= true;
260: }
261: }
262: }
263: for ( Integer currYy : yyOcclusions.keySet() )
264: {
265: List<String> idsAtYy = yyOcclusions.get( currYy );
266: for ( String idAt : idsAtYy )
267: {
268: if ( idAt.equals( currRect.rectId ) )
269: {
270: continue;
271: }
272: else
273: {
274: inYyShadow.add( idAt );
275: }
276: }
277: }
278: // NOTE find the intersection of the two sets, these actually overlap the current rectangle
279: for ( String xxId : inXxShadow )
280: {
281: for ( String yyId : inYyShadow )
282: {
283: if ( xxId.equals( yyId ) )
284: {
285: Rectangle first = allJoins.get( xxId );
286: Rectangle intersect = intersectionOf( first, currRect, delimiter );
287: if ( ! first.beenChecked || ! currRect.beenChecked )
288: {
289: // if they've both been checked, then this is a really multi overlap (3 pairs) avoiding overdraft
290: combinedArea -= intersect.lenX * intersect.lenY;
291: }
292: if ( ! first.beenChecked )
293: {
294: combinedArea += first.lenX * first.lenY;
295: first.beenChecked = true;
296: }
297: if ( ! currRect.beenChecked )
298: {
299: combinedArea += currRect.lenX * currRect.lenY;
300: currRect.beenChecked = true;
301: }
302: multiOverlap |= true;
303: }
304: }
305: }
306: if ( ! multiOverlap )
307: {
308: combinedArea += currRect.lenX * currRect.lenY;
309: currRect.beenChecked = true;
310: }
311: // else handled above
312: }
313: return combinedArea;
314: }
315:
316:
317: Rectangle intersectionOf( Rectangle some, Rectangle other, String idToUse )
318: {
319: Rectangle between = new Rectangle();
320: between.rectId = idToUse;
321: between.posX = Math.max( some.posX, other.posX );
322: between.posY = Math.max( some.posY, other.posY );
323: int endSome = some.posX + some.lenX;
324: int endOther = other.posX + other.lenX;
325: between.lenX = Math.min( endSome, endOther ) - between.posX;
326: endSome = some.posY + some.lenY;
327: endOther = other.posY + other.lenY;
328: between.lenY = Math.min( endSome, endOther ) - between.posY;
329: return between;
330: }
331:
332: }
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
Generated by git2html.