diff options
Diffstat (limited to 'scratch/advent-of-code-2019/day_3.py')
| -rw-r--r-- | scratch/advent-of-code-2019/day_3.py | 137 |
1 files changed, 137 insertions, 0 deletions
diff --git a/scratch/advent-of-code-2019/day_3.py b/scratch/advent-of-code-2019/day_3.py new file mode 100644 index 000000000000..6dd863528c1c --- /dev/null +++ b/scratch/advent-of-code-2019/day_3.py @@ -0,0 +1,137 @@ +from math import floor +from heapq import heappush, heappop + +xs = [ + "R1009", "U993", "L383", "D725", "R163", "D312", "R339", "U650", "R558", + "U384", "R329", "D61", "L172", "D555", "R160", "D972", "L550", "D801", + "L965", "U818", "L123", "D530", "R176", "D353", "L25", "U694", "L339", + "U600", "L681", "D37", "R149", "D742", "R762", "U869", "R826", "U300", + "L949", "U978", "L303", "U361", "R136", "D343", "L909", "U551", "R745", + "U913", "L566", "D292", "R820", "U886", "R205", "D431", "L93", "D71", + "R577", "U872", "L705", "U510", "L698", "U963", "R607", "U527", "L669", + "D543", "R690", "U954", "L929", "D218", "R490", "U500", "L589", "D332", + "R949", "D538", "R696", "U659", "L188", "U468", "L939", "U833", "L445", + "D430", "R78", "D303", "R130", "D649", "R849", "D712", "L511", "U745", + "R51", "U973", "R799", "U829", "R605", "D771", "L837", "U204", "L414", + "D427", "R538", "U116", "R540", "D168", "R493", "U900", "L679", "U431", + "L521", "D500", "L428", "U332", "L954", "U717", "L853", "D339", "L88", + "U807", "L607", "D496", "L163", "U468", "L25", "U267", "L759", "D898", + "L591", "U445", "L469", "U531", "R596", "D486", "L728", "D677", "R350", + "D429", "R39", "U568", "R92", "D875", "L835", "D841", "R877", "U178", + "L221", "U88", "R592", "U692", "R455", "U693", "L419", "U90", "R609", + "U672", "L293", "U168", "R175", "D456", "R319", "D570", "R504", "D165", + "L232", "D624", "L604", "D68", "R807", "D59", "R320", "D281", "L371", + "U956", "L788", "D897", "L231", "D829", "R287", "D798", "L443", "U194", + "R513", "D925", "L232", "U225", "L919", "U563", "R448", "D889", "R661", + "U852", "L950", "D558", "L269", "U186", "L625", "U673", "L995", "U732", + "R435", "U849", "L413", "D690", "L158", "D234", "R361", "D458", "L271", + "U90", "L781", "U754", "R256", "U162", "L842", "U927", "L144", "D62", + "R928", "D238", "R473", "U97", "L745", "U303", "L487", "D349", "L520", + "D31", "L825", "U385", "L133", "D948", "L39", "U62", "R801", "D664", + "L333", "U134", "R692", "U385", "L658", "U202", "L279", "D374", "R489", + "D686", "L182", "U222", "R733", "U177", "R94", "D603", "L376", "U901", + "R216", "D851", "L155", "D214", "L460", "U758", "R121", "D746", "L180", + "U175", "L943", "U146", "L166", "D251", "L238", "U168", "L642", "D341", + "R281", "U182", "R539", "D416", "R553", "D67", "L748", "U272", "R257", + "D869", "L340", "U180", "R791", "U138", "L755", "D976", "R731", "U713", + "R602", "D284", "L258", "U176", "R509", "U46", "R935", "U576", "R96", + "U89", "L913", "U703", "R833" +] +ys = [ + "L1006", "D998", "R94", "D841", "R911", "D381", "R532", "U836", "L299", + "U237", "R781", "D597", "L399", "D800", "L775", "D405", "L485", "U636", + "R589", "D942", "L878", "D779", "L751", "U711", "L973", "U410", "L151", + "U15", "L685", "U417", "L106", "D648", "L105", "D461", "R448", "D743", + "L589", "D430", "R883", "U37", "R155", "U350", "L421", "U23", "R337", + "U816", "R384", "D671", "R615", "D410", "L910", "U914", "L579", "U385", + "R916", "U13", "R268", "D519", "R289", "U410", "L389", "D885", "L894", + "U734", "L474", "U707", "L72", "U155", "L237", "U760", "L127", "U806", + "L15", "U381", "L557", "D727", "L569", "U320", "L985", "D452", "L8", + "D884", "R356", "U732", "L672", "D458", "L485", "U402", "L238", "D30", + "R644", "U125", "R753", "U183", "L773", "U487", "R849", "U210", "L164", + "D808", "L595", "D668", "L340", "U785", "R313", "D72", "L76", "D263", + "R689", "U604", "R471", "U688", "R462", "D915", "R106", "D335", "R869", + "U499", "R190", "D916", "R468", "D882", "R56", "D858", "L143", "D741", + "L386", "U856", "R50", "U853", "R151", "D114", "L773", "U854", "L290", + "D344", "L23", "U796", "L531", "D932", "R314", "U960", "R643", "D303", + "L661", "D493", "L82", "D491", "L722", "U848", "L686", "U4", "L985", + "D509", "L135", "D452", "R500", "U105", "L326", "D101", "R222", "D944", + "L645", "D362", "L628", "U305", "L965", "U356", "L358", "D137", "R787", + "U728", "R967", "U404", "R18", "D928", "L695", "D965", "R281", "D597", + "L791", "U731", "R746", "U163", "L780", "U41", "L255", "U81", "L530", + "D964", "R921", "D297", "R475", "U663", "L226", "U623", "L984", "U943", + "L143", "U201", "R926", "U572", "R343", "U839", "R764", "U751", "R128", + "U939", "R987", "D108", "R474", "U599", "R412", "D248", "R125", "U797", + "L91", "D761", "L840", "U290", "L281", "U779", "R650", "D797", "R185", + "D320", "L25", "U378", "L696", "U332", "R75", "D620", "L213", "D667", + "R558", "U267", "L846", "U306", "R939", "D220", "R311", "U827", "R345", + "U534", "R56", "D679", "R48", "D845", "R898", "U8", "R862", "D960", "R753", + "U319", "L886", "D795", "R805", "D265", "R876", "U729", "R894", "D368", + "R858", "U744", "R506", "D327", "L903", "U919", "L721", "U507", "L463", + "U753", "R775", "D719", "R315", "U128", "R17", "D376", "R999", "D386", + "L259", "U181", "L162", "U605", "L265", "D430", "R35", "D968", "R207", + "U466", "R796", "D667", "R93", "U749", "L315", "D410", "R312", "U929", + "L923", "U260", "R638" +] + + +def to_coords(xs): + row, col = 0, 0 + coords = [] + for x in xs: + d, amt = x[0], int(x[1:]) + if d == 'U': + for i in range(1, amt + 1): + coords.append((row + i, col)) + row += amt + elif d == 'D': + for i in range(1, amt + 1): + coords.append((row - i, col)) + row -= amt + elif d == 'L': + for i in range(1, amt + 1): + coords.append((row, col - i)) + col -= amt + elif d == 'R': + for i in range(1, amt + 1): + coords.append((row, col + i)) + col += i + return coords + + +def contains(row, col, d): + if row not in d: + return False + return col in d[row] + + +def intersections(xs, ys): + d = {} + ints = set() + for row, col in to_coords(xs): + if row in d: + d[row].add(col) + else: + d[row] = {col} + for row, col in to_coords(ys): + if contains(row, col, d): + ints.add((row, col)) + return ints + + +def trace_to(coord, xs): + count = 0 + for coord_x in to_coords(xs): + count += 1 + if coord_x == coord: + return count + raise Exception("Intersection doesn't exist") + + +answer = [] +for coord in intersections(xs, ys): + x = trace_to(coord, xs) + y = trace_to(coord, ys) + heappush(answer, x + y) + +print(heappop(answer)) |