advent-of-code/2024/day15/day15.py at master · buckley-w-david/advent-of-code · GitHub

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
from aoc_utils import *  # type: ignore
from aocd import get_data

data = get_data(year=2024, day=15, block=True)


def to_direction(c):
    if c == "^":
        return Direction.NORTH
    elif c == ">":
        return Direction.EAST
    elif c == "v":
        return Direction.SOUTH
    elif c == "<":
        return Direction.WEST
    assert False


def gps_sum(grid, char="O"):
    s = 0
    for (y, x), c in grid.row_major_with_index():
        if c == char:
            s += 100 * y + x
    return s


def parse(data):
    map, instructions = data.split("\n\n")
    instructions = [to_direction(c) for line in instructions.splitlines() for c in line]
    grid = Grid.parse(map)
    robot = None
    for yx, c in grid.row_major_with_index():
        if c == "@":
            grid[yx] = "."
            robot = yx
            break
    assert robot
    return grid, instructions, robot


def part_one(data):
    grid, instructions, robot = parse(data)

    for direction in instructions:
        dy, dx = direction.value
        ry, rx = robot
        next_position = (ry + dy, rx + dx)
        for yx, c in grid.ray_from_with_index(robot, direction):
            if c == ".":
                grid[yx] = grid[next_position]
                grid[next_position] = "."
                robot = next_position
                break
            elif c == "#":
                break

    return gps_sum(grid)


def part_two(data):
    d = data.replace("#", "##").replace("O", "[]").replace(".", "..").replace("@", "@.")

    grid, instructions, robot = parse(d)

    for direction in instructions:
        dy, dx = direction.value
        ry, rx = robot
        next_position = (ry + dy, rx + dx)

        if grid[next_position] == ".":
            robot = next_position
        elif grid[next_position] == "#":
            continue
        elif direction is Direction.WEST or direction is direction.EAST:
            target = None
            for yx, c in grid.ray_from_with_index(robot, direction):
                if c == ".":
                    target = yx
                    break
                elif c == "#":
                    break
            else:
                # The board is surrounded by #
                # This should be impossible
                assert False

            if not target:
                continue

            rd = direction.reverse()
            rdy, rdx = rd.value

            grid[target] = grid[(target[0] + rdy, target[1] + rdx)]
            for yx, c in grid.ray_from_with_index(target, direction.reverse()):
                if yx == robot:
                    break

                ny, nx = yx
                grid[yx] = grid[(ny + rdy, nx + rdx)]
            robot = next_position
        else:
            front = {next_position: robot}
            next_front = {}
            if grid[next_position] == "[":
                front[(next_position[0], next_position[1] + 1)] = robot
            elif grid[next_position] == "]":
                front[(next_position[0], next_position[1] - 1)] = robot

            layers = [front]

            blocked = False
            while True:
                clear = True
                for yx in front.keys():
                    if grid[yx] == ".":
                        continue

                    y, x = yx
                    np = (y + dy, x + dx)
                    next_front[np] = yx

                    if grid[np] != ".":
                        clear = False

                    if grid[np] == "#":
                        blocked = True
                        break
                    elif grid[np] == "[":
                        if (y, x + 1) in front.keys():
                            next_front[(y + dy, x + 1)] = (y, x + 1)
                        else:
                            next_front[(y + dy, x + 1)] = robot
                    elif grid[np] == "]":
                        if (y, x - 1) in front.keys():
                            next_front[(y + dy, x - 1)] = (y, x - 1)
                        else:
                            next_front[(y + dy, x - 1)] = robot
                    else:
                        pass
                front = next_front
                next_front = {}
                layers.append(front)
                if clear or blocked:
                    break

            if blocked:
                continue

            for layer in reversed(layers):
                for a, b in layer.items():
                    grid[a] = grid[b]
            robot = next_position

    return gps_sum(grid, char="[")


print(part_one(data))
print(part_two(data))