Marble Mania

Advent of Code 2018 Day 9

Task: Solve for X where...

Part 1

X = the winning Elf's score

Part 2

X = the winning Elf's score be if the number of the last marble were 100 times larger

Example input

10 players; last marble is worth 1618 points

It represents:

• The parameters for playing and scoring a game of marbles

Part 1

1. Understanding the rules
2. Correctly adjusting the array at each turn
3. Writing what I hope is a working algorithm

Understanding the rules

Take turns arranging the marbles in a circle according to very particular rules

I interpret that as a growing array where the start and end must be programmatically viewed as adjacent cells

The marbles are numbered starting with 0 and increasing by 1 until every marble has a number

• The starting with 0 and increasing by 1 part makes sense
• But how do I know the number of marbles? Is that the number specified as the point value of the last marble?

First, the marble numbered 0 is placed in the circle. The marble is both clockwise from itself and counter-clockwise from itself. This marble is designated the current marble.

This is depicted as:

[-] (0)

Then, each Elf takes a turn placing the lowest-numbered remaining marble into the circle between the marbles that are 1 and 2 marbles clockwise of the current marble.

This is depicted as:

           (Current)
0  8  4  9  2(10) 5  1  6  3  7
                  1  2
                   ^^
                   || 
               11 goes here

                 (Current)
0  8  4  9  2 10  5(11) 1  6  3  7

However, if the marble that is about to be placed has a number which is a multiple of 23, something entirely different happens.

Of course it does.

What happens if the marble about to be placed has a number which is a multiple of 23?

1. The current player keeps the marble they would have placed, adding it to their score
2. The marble 7 marbles counter-clockwise from the current marble is removed from the circle and also added to the current player's score
3. The marble located immediately clockwise of the marble that was removed becomes the new current marble

This is depicted as:

Most recent turn
...18  9 19  2 20 10 21  5(22)11  1 12...

Coming up, marble number 23...

Current player keeps marble number 23; adds to their score.

Remove marble 7 marbles counter-clockwise from current marble:
...18  9 19  2 20 10 21  5(22)11  1 12...
       *  6  5  4  3  2  1  0

Current player removes marble 9; adds to their score.
...18    19  2 20 10 21  5(22)11  1 12...

The marble located immediately clockwise of the marble that was removed becomes the new current marble:
...18   (19) 2 20 10 21  5 22 11  1 12...

Correctly adjusting the array at each turn

• I understand the rules
• I intend to use an array as a data structure to store the ordered set of marbles
• How will I insert - and occasionally remove - marbles into/from the correct location?

I need to walk through a few scenarios from the example illustration.

First, an easy one:

0 (4) 2  1  3

Marble 5 goes between 2 and 1:

0  4  2 (5) 1  3

I could determine and execute that using the following logic:

current = 1 // the index of 4

// 1 marble clockwise
current + 1 == 2

// 2 marbles clockwise
current + 2 == 3

// Insert marble 5 before location 3
marbles.splice(current + 2, 0, 5)

Second, a wrapping one:

0  2  1 (3)

Marble 4 goes between 0 and 2:

0 (4) 2  1  3 

I could determine and execute that using the following logic:

current = 3 // the index of 3

// 1 marble clockwise
current + 1 == 4 // not a valid location
(current + 1) % marbles.length == 0 // correctly wrapping

// 2 marbles clockwise
current + 2 == 5 // not a valid location
(current + 2) % marbles.length == 1 // correctly wrapping

// Insert marble 4 before location 1
marbles.splice((current + 2) % marbles.length, 0, 4)

Third, another wrapping one:

0  4  2  5  1 (6) 3

Marble 7 goes between 3 and 0:

0  4  2  5  1  6  3 (7)

I could determine and execute that using the following logic:

current = 5 // the index of 6

// 1 marble clockwise
(current + 1) % marbles.length == 6

// 2 marbles clockwise
(current + 2) % marbles.length == 0 // correctly wrapping

// Insert marble 7 before location 0 (a.k.a. at the end)
marbles.splice(marbles.length, 0, 7)

A supposed winning formula for inserting marbles in normal circumstances:

marbles.splice(
  // where to insert
  (current + 2) % marbles.length == 0 ? // condition
    marbles.length // do if true
    : (current + 2) % marbles.length, // do if false
  0, // amount to delete
  next_number // number to insert
)

What about when the number is divisible by 23?

• In the example, the location is conveniently in the middle of all the marbles
• What if it is near the starting edge?
• Thus, the marbles 6 and 7 counter-clockwise away would be at the start or end

Create a temporary variable equal to the difference of current and 7
If that variable is less than 0
  Update it to the sum of itself and the length of marbles
Remove the marbles at that location in marbles
Decrement current by 6
If current is now less than 0
  Update current to the sum of itself and the length of marbles

Writing what I hope is a working algorithm

Use a simple regular expression to extract both digits from the puzzle input: 1) player count; 2) highest numbered marble
Create an object, scores, to eventually store each player's score
Create an array, marbles, to eventually store the ordered list of marbles
  Set the first value as 0
Create a current marble tracker, starting at 0: the location of the only value in marbles
Create a player tracker, starting at 0
For each number from 1 up to and including the highest numbered marble
  If the number is divisible by 23
    Decrement current by 7
    If current is now negative
      Update current to the sum of current and the length of marbles
    If there is no score for the current player
      Create a key in scores using the current player's number
        Set its value to 0
    Update the current player's score to the sum of the current marbles number and the marble at the location stored in current
    Remove the marble at the location stored in current
  Else
    Insert the number in the appropriate spot based on the algorithm described in the section above
    Update current to the location of the just-added number
Update player such that it equals the remainder after dividing a number one greater than player by the player count

Generate a list of all the values stored in scores
  Return the largest number in that list

I struggled with two parts in particular:

1. Wrapping back around the list of players
2. Re-positioning the current marble when the number is a multiple of 23

Wrapping back around the list of players

• The instructions illustrate players numbered starting at 1
• But the answer only requires the winning score, not the player who has the winning score
• So I can number players starting at 0, instead
• This helps me avoid adding a few + 1 operations to my algorithm that would have otherwise helped me wrap from 1-9 instead of 0-8

Re-positioning the current marble when the number is a multiple of 23

The algorithm I wrote in the prior section didn't work as expected:

Create a temporary variable equal to the difference of current and 7
If that variable is less than 0
  Update it to the sum of itself and the length of marbles
Remove the marbles at that location in marbles
Decrement current by 6
If current is now less than 0
  Update current to the sum of itself and the length of marbles

It turns out:

• It was overly complicated
• It incorrectly moved the current marble location to a location that was one-off from the correct location

An algorithm that does work is this:

Decrement current by 7
If current is now negative
  Update current to the sum of current and the length of marbles
Remove the marble at the location stored in current

Testing the results on all six examples:

1. Correct answer!
2. Correct answer!
3. Correct answer!
4. Correct answer!
5. Correct answer!
6. Correct answer!

And using my puzzle input...

Correct answer!

Part 2

1. As anticipated, an algorithmic stress test
2. Doing a little research on linked lists

As anticipated, an algorithmic stress test

• The number of marbles is now in the millions instead of the 10s-of-thousands
• My algorithm took a few seconds to run for Part 1
• It would take, maybe, several hours - upwards of a day - to run Part 2, assuming the stack never overflowed and the processor never timed out

What makes my algorithm take so long to run?

• I use splice() a bunch
• But that manipulates the array in-place, so I'm not creating a new array each turn...am I?
• Well, my use of splice() is rarely deleting. Rather, it is almost always adding
• Therefore, more memory is being allocated, and perhaps the array is being implicitly re-created somewhere in memory on each turn

What could I do differently?

• I could initialize my array to a size greater than what it will eventually be, so I have allocated enough memory from the start
• But that would require a whole new approach to setting and updating existing values at their locations on each turn
• I could use a linked list
• That way, adding or removing values is a simple operation (e.g. O(1)), instead of requiring as many as all values in an array to be moved (e.g. O(n))
• But how would I re-create the sense of a wrapping list with a linked list? I guess each item could have a previous and next value. Since it starts with one item, that item's previous and next values would be itself? Hmm.
• I'm not sure of any other approaches to drastically improving the space- or time-complexity of my algorithm

Doing a little research on linked lists

After scouring the Solution Megathread and searching Google for linked list, I learned:

• There are several types: Singly, Doubly, Circular
• They differ in which directions the nodes point: Forward, Forward & Backward, Closed Loop (Start points to End)
• There is a type of 'collection' - akin to a list - called a Deque (short for Doubly Ended Queue)
• One Reddit solver used a deque in Python to write a wonderfully eloquent algorithm that solves each part in mere seconds
• The FreeCodeCamp tutorial group that I discovered recently features several modules on linked lists and circular queues. I'm excited to continue attempting those challenges.

Celebrating my accomplishments

• I solved Part 1!
• I practiced splice() and the modulo operator
• I recognized my algorithm's performance deficiencies (O(n) array vs O(1) linked list) and identifying a potentially viable alternative method...that I studied just enough to know I would need to study more before writing my own algorithm

Bummers:

• I didn't solve Part 2
• I didn't make any GIFs
• I didn't make a simulator - this puzzle didn't inspire any compelling interactivity or visuals