about summary refs log tree commit diff
path: root/advent-of-code/day_3.py
blob: 6dd863528c1c19a53c0179d0dc68245970bba94e (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
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))