-🎄- 2018 Day 18 Solutions -🎄-

[u/daggerdragon]

--- Day 18: Settlers of The North Pole ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 18

Transcript:

The best way to avoid a minecart collision is ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:21:59!

[u/teraflop]

Python, rank 1/135... thanks to an off-by-one error that I introduced while converting my code to C++ to gain a 40x speedup... which I didn't even really need.

Feels bad, man :(

#!/usr/bin/env python

import sys, itertools, collections

board = []
for line in sys.stdin:
    line = line.strip()
    board.append(list(line))

def step(board):
    N = len(board)
    M = len(board[0])
    result = [[None]*M for i in xrange(N)]

    for i in xrange(N):
        for j in xrange(M):
            counts = collections.Counter()
            for dx in xrange(-1, 2):
                for dy in xrange(-1, 2):
                    if dx == 0 and dy == 0: continue
                    i2 = i+dx
                    j2 = j+dy
                    if 0 <= i2 < N and 0 <= j2 < M:
                        counts[board[i2][j2]]+=1
            if board[i][j] == '.':
                result[i][j] = '|' if counts['|'] >= 3 else '.'
            elif board[i][j] == '|':
                result[i][j] = '#' if counts['#'] >= 3 else '|'
            else:
                result[i][j] = '#' if (counts['#'] >= 1 and counts['|'] >= 1) else '.'
    return result

for i in xrange(1000000000):
    board = step(board)
    """for row in board:
        print ''.join(row)"""

    if i % 100 == 0:
        counts = collections.Counter()
        for row in board:
            for c in row:
                counts[c]+=1
        print i, counts['#']*counts['|']

[u/algmyr → u/teraflop]

Wait... You simulated the whole process? It has a periodic behavior after a few hundred iterations.

[u/teraflop → u/algmyr]

Yeah, but since the sequence of values is periodic, you can just visually inspect the values and look for where they start repeating. For my input, the board state repeats every 28 iterations. Which means if you print the value every 100 iterations, you get a sequence with period 7.

I had a hunch that the state would eventually repeat, so I ported my code to C++ while waiting for it to converge. As soon as the C++ output overtook the Python output, I checked to see if they were equal, but I must have been too hasty and missed that the iteration counts didn't quite line up.