Module aoc::year2018::day09

source ·
Expand description

§Marble Mania

Efficient solution using an append only vec and generating only the minimum number of marbles needed to play the game.

First let’s consider some other slower approaches:

We could store marbles in a vec, inserting and removing elements to make room. Each of these operations takes O(n) complexity. For part two if number of marbles is 100,000 then the total complexity is 100,000 * 100 * 100,000 = 10¹² which is infeasible.

A better approach is a linked list. Insert and remove operations are now O(1) for a total part two complexity of 100,000 * 1 * 100 = 10⁷. This is slow but practical. However linked lists have a number of drawbacks:

  1. Poor cache locality
  2. Allocation per element
  3. Ownership issues complex enough to inspire an entire blog post series.

§First optimization

The first key insight is that we can generate the marble sequence by only appending to a vec. We keep track of the head () and tail <> of the circle. Each turn adds two marbles to the head and removes one from the tail, growing the circle by one each time. For example the first 4 marbles look like:

   <0>
    0  <0> (1)
    0   0  <1>  0  (2)
    0   0   1  <0>  2  1  (3)
    0   0   1   0  <2>  1  3  0  (4)

Things start to get interesting at the 19th marble. When we pick the 23rd marble this will be 7 places counter clockwise, so we can optimize by not adding it at all the the circle. Instead we save the value for later.

    18th marble
    ...<9>  2  10   5  11   1  12   6  13   3  14   7  15   0  16   8  17   4  (18)

    19th marble, saving value of previous tail 9.
    ...<2> 10   5  11   1  12   6  13   3  14   7  15   0  16   8  17   4  18  (19)

For the 20th, 21st and 22nd marbles we re-write the history of the tail then move it backwards.

    20th marble
    ... 2  20   9  <2> 10   5  11   1  12   6  13   3  14   7  15   0  16   8  17   4  18  (19)
        ^  ^^

    21st marble
    ... 2  20  10 <21> 10   5  11   1  12   6  13   3  14   7  15   0  16   8  17   4  18  (19)
               ^^  ^^

    22nd marble (move tail)
    ...<2> 20  10  21   5  22  11   1  12   6  13   3  14   7  15   0  16   8  17   4  18  (19)
                        ^  ^^

The 23rd marble is never added to the circle instead increasing the current player’s score. The cycle then begins again, handling the next 18 marbles normally, then the next 19th to 22nd marbles specially.

§Second optimization

It may seem that we need to generate (last marble / 23) blocks. However in each block we add 37 marbles (2 each for the first 18 marbles and 1 for the 19th) while the marble added to each player’s score advances 23 - 7 = 16 marbles. This means we only need to generate about 16/37 or 44% of the total blocks to solve the game deterministcally. This saves both processing time and memory storage proportionally.

Functions§

Type Aliases§