Advent of Code 2024 - Day 14: Restroom Redoubt

:: programming, python, puzzle

 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
 
from advent import parse, ints, iterate, count_from

robots        = parse(14, ints)
width, height = 101, 103
tick          = lambda r: [ ((x + vx) % width, (y + vy) % height, vx, vy) for x, y, vx, vy in r ]

def part1(n=100):
    bots           = iterate(tick, robots, 100)
    ul, ur, ll, lr = 0, 0, 0, 0
    xmid, ymid     = width // 2, height // 2

    for x, y, _, _ in bots:
        if x < xmid:
            if y < ymid:
                ul += 1
            elif y > ymid:
                ll += 1
        elif x > xmid:
            if y < ymid:
                ur += 1
            elif y > ymid:
                lr += 1

    return ul * ur * ll * lr

def mostly_symmetric(s, xmid):
    good, bad = 0, 0

    for x, y in s:
        if x < xmid:
            if (xmid + xmid - x, y) in s:
                good += 1
            else:
                bad += 1

    return good > bad

def part2():
    r = robots

    for seconds in count_from(1):
        r = tick(r)
        s = { (x,y) for x, y, _, _ in r }

        for xmid in range(30, width-30):
            if mostly_symmetric(s, xmid):
                return seconds

# ---------------------------------------------------------------------------------------------

assert part1() == 224969976
assert part2() == 7892

Parsing

We’re given input of the form:

p=1,65 v=-5,-84
p=14,63 v=-85,6
p=49,81 v=71,14
p=61,77 v=85,67
p=58,37 v=42,47
...

We just want a tuple of numbers, so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
robots = parse(14, ints)

----------------------------------------------------------------------------------------------------
day14.txt ➜ 8330 chars, 500 lines; first 3 lines:
----------------------------------------------------------------------------------------------------
p=1,65 v=-5,-84
p=14,63 v=-85,6
p=49,81 v=71,14
----------------------------------------------------------------------------------------------------
parse(14) ➜ 500 entries:
----------------------------------------------------------------------------------------------------
((1, 65, -5, -84), (14, 63, -85, 6), (49, 81, 71, 14), (61, 77, 85, 67 ... 9, 53), (31, 39, 16, 34))
----------------------------------------------------------------------------------------------------

Part 1

For part 1, we perform 100 iterations of robot movement, and then return the product of the count of robots in each of four quadrants. First, we’ll create a function to perform a single iteration of robot movement:

1
 
tick = lambda r: [ ((x + vx) % width, (y + vy) % height, vx, vy) for x, y, vx, vy in r ]

Then, in part1(), we’ll iterate() that tick() function 100 times.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
 
def part1(n=100):
    bots           = iterate(tick, robots, 100)
    ul, ur, ll, lr = 0, 0, 0, 0
    xmid, ymid     = width // 2, height // 2

    for x, y, _, _ in bots:
        if x < xmid:
            if y < ymid:
                ul += 1
            elif y > ymid:
                ll += 1
        elif x > xmid:
            if y < ymid:
                ur += 1
            elif y > ymid:
                lr += 1

    return ul * ur * ll * lr

Part 2

Part 2 gave me a lot of trouble initially, because I wrongly assumed the tree would be symmetrical about the midpoint of the grid. A second attempt was to assume there would be a picture frame (turns out to be correct), but I assumed it would be around the border of the grid. After a few false starts, I decided to look for symmetry around an (almost) arbitrary midpoint, and that solved the puzzle.

My solution is very inefficient, but after burning too much time on the puzzle, I wasn’t motivated to tune the performance. I may come back to that after seeing other solutions, to see how Python compares on the same algorithm.

Here is the function to indicate whether the grid has enough symmetry:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
def mostly_symmetric(s, xmid):
    good, bad = 0, 0

    for x, y in s:
        if x < xmid:
            if (xmid + xmid - x, y) in s:
                good += 1
            else:
                bad += 1

    return good > bad

What remains is to iterate robot movement, and then scan across the mid-point values to see if there is sufficient symmetry:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
def part2():
    r = robots

    for seconds in count_from(1):
        r = tick(r)
        s = { (x,y) for x, y, _, _ in r }

        for xmid in range(30, width-30):
            if mostly_symmetric(s, xmid):
                return seconds

Eventually, I was able to find the following grid. In hindsight, it may have been simpler to look for a picture frame :)

........................xx............................................................x.............x
.......................xx............................................................................
...................................x.......................x......x............x.....................
......................................................................................x..............
.....................................................................................................
..x.............................................................x....................................
...............................x.....................................................................
...x..........................................x......................................................
x.........x..........................................x.........................................x.....
.....x......................................x.........x..............................................
.....x..............................................x................................................
.x...............................x...................................................................
.....................................................................................................
...................................................................x.................................
..............x................x.....................................................................
............x............................x..................................................x........
......x.............................x.......................................x........................
.............................................................x.............x.........................
...............................................................x.....................................
............................................x........................................................
....x.....................................................x.........................x................
....................................................................................x................
...........x...................................x.....................................................
..............................................x.............x........................................
...............................................................x.....................................
................................................................................................x....
.....................x.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...............................................
.......................x.............................x.....................................x.........
.......................x.............................x.....................x...........x.............
.......................x.............................x...............................................
.......................x.............................x...............................................
x......................x..............x..............x...............................................
.......................x.............xxx.............x............x..................................
.......................x............xxxxx............x...............................................
.......................x...........xxxxxxx...........x..x.........................................x..
............x..........x..........xxxxxxxxx..........x..................................x............
.......................x............xxxxx............x...........x................x...x..............
.....x.................x...........xxxxxxx...........x...............................................
....x..................x..........xxxxxxxxx..........x...............................................
...............x.......x.........xxxxxxxxxxx.........x..................x............................
.......................x........xxxxxxxxxxxxx........x...........................x.............x.....
..............x........x..........xxxxxxxxx..........x.....x............x............................
.......................x.........xxxxxxxxxxx.........x..............................x................
.......................x........xxxxxxxxxxxxx........x...............................................
....x.......x..........x.......xxxxxxxxxxxxxxx.......x...............................................
.......................x......xxxxxxxxxxxxxxxxx......x.......x.......................................
......x................x........xxxxxxxxxxxxx........x...............................................
.......................x.......xxxxxxxxxxxxxxx.......x.....x.........................................
.......................x......xxxxxxxxxxxxxxxxx......x....................................x..........
.......................x.....xxxxxxxxxxxxxxxxxxx.....x.........................................x.....
.......................x....xxxxxxxxxxxxxxxxxxxxx....x........................x...............x......
.......................x.............xxx.............x...............................................
.......................x.............xxx.............x...............................................
.......................x.............xxx.............x..........................x.......x............
.......................x.............................x.....................x......x..................
.......................x.............................x...............................................
..............x...x....x.............................x...............................................
.......................x.............................x......x....................x...................
.......................xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...............................................
.....................................................................................................
............................................................................................x........
..x....................x.............................................................................
..x....................x..............x..............................................................
.....................................................................................................
.....................................................................................................
.............................x.......................................................................
...................x.............................................................x...................
.........................................................x...........................................
..................x.....................x.......................................x....................
...............................................................................................x.....
....................................................................................x................
..........................................x..........................................................
..........x.......................x....................................................x.............
............................x................................................x.......................
............x........................................................................................
.......................................................................x..........................x..
.....................................................................................................
...................................................................................................x.
....x................................................................................................
...............................x......x...............x..............................................
.........................x...........................................................................
.............................................................................x.......................
.....................................................................................................
.....................................................................................................
.................................x.........x.........................................................
................................................................................................x....
............................x......x.................................................................
.....................................................................................................
.....................x............................................x..................................
...................x...........x.....................................................................
....................................................x................................................
...x.................................................................................................
........x...................x...............x........................................................
..............................................................................x......................
..x.......................................................................................x..........
...............x................................x.........................................x..........
.............................................x........x..............................................
.....................................................................................................
.....................................................................................................
..................................................................x..................................
......................................................................x...x..........................
........................................................................................x............
.....................................................................................................

New Python Concepts

  • itertools.count # renamed to count_from in my library

Conclusion

As I mentioned, this puzzle gave me more difficulty than it should have, but it was gratifying to solve it without help. If I felt it had more real world applicability, I’d probably be motivated to make it fast, but as it stands, I think I’ll move on.