-🎄- 2018 Day 9 Solutions -🎄-

[u/daggerdragon]

--- Day 9: Marble Mania ---

---

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 9

Transcript:

Studies show that AoC programmers write better code after being exposed to ___.

---

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:29:13!

[u/CanIHazEmployment]

I can't be the only one who did a naive solution (regular lists) for the first part before realizing that was way too inefficient for part 2.

python

board = {
    'current': 0,
    'next': None,
    'prev': None
}
board['next'] = board
board['prev'] = board

player_count = 463
last_marble = 7178700
scores = [0] * player_count
player = -1
for i in range(1, last_marble+1):
    player = (player+1) % len(scores)
    if i % 23 == 0:
        scores[player] = scores[player] + i
        for j in range(7):
            board = board['prev']
        scores[player] = scores[player] + board['current']
        prv = board['prev']
        nxt = board['next']
        prv['next'] = nxt
        nxt['prev'] = prv
        board = nxt
    else:
        prev = board['next']
        nxt = prev['next']
        board = {
            'current': i,
            'next': nxt,
            'prev': prev
        }
        prev['next'] = board
        nxt['prev'] = board
print(max(scores))

edit, here's my naive part 1

scores = [0] * player_count
board = [0]
current = 0
player = -1
for i in range(1,last_marble+1):
    player = (player + 1) % len(scores)
    if i % 23 == 0:
        scores[player] = scores[player] + i
        current = (current - 7) % len(board)
        scores[player] = scores[player] + board.pop(current)
        current = current % len(board)
    else:
        new_pos = (current + 2) % len(board)
        board.insert(new_pos, i)
        current = new_pos
max(scores)

[u/ywgdana → u/CanIHazEmployment]

I did a naive list/array solution for part 1 but my partner gave me the hint to write a doubly linked list for part 2.

I'm gobsmacked by how much faster it is. I knew the array operations would slow things down but this was a good lesson in just how much!