Solution for Advent of Code 2018 - Day 9: Marble Mania

Link to the puzzle text

Part 1

In this puzzle we have the instructions for a marble game. There is a fixed number of numbered marbles and a fixed number of players. We start with a single marble labeled 0 in a circle  During each players turn, the next marble is inserted into the circle at a position one to the left of the current marble. If the current marble is labeled as a multiple of 23, we use a different step. Both the current marble and the one 7 positions to the right are removed and their labels added as points for the current player. We are looking for the highest point score after all marbles have been placed.

 

We can simulate the rules as written. For the circle of marbles we used a dequeue so we can rotate the circle around later one. We always keep the current marble at the last position. In the normal case, we rotate the circle one position and insert the new marble at the last position. In every 23th step, we rotate first by 7 positions and remove the marble there before rotating back one position again. In this case we also update the current players points:

for marble in range(1, last_marble + 1):
    if marble % 23 == 0:
        marble_circle.rotate(7)
        points[current_player] += marble + marble_circle.pop()
        marble_circle.rotate(-1)
    else:
        marble_circle.rotate(-1)
        marble_circle.append(marble)
    current_player = (current_player + 1) % num_players 

Finally we return the highest of the players scores.

Part 2 

In part 2, we have to run the game longer. We should use 100 times the marbles and again report the highest player score.

We reused the previous code and updated the marble number before running the function again. This was quick enough.

If further optimization is needed, we could use the fact that the marble circle is independent of the number of players and find a structure in there to exploit.

Link to my solutions