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
- Understanding the rules
- Correctly adjusting the array at each turn
- 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?
- The current player keeps the marble they would have placed, adding it to their score
- The marble 7 marbles counter-clockwise from the current marble is removed from the circle and also added to the current player's score
- 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:
- Wrapping back around the list of players
- 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:
- Correct answer!
- Correct answer!
- Correct answer!
- Correct answer!
- Correct answer!
- Correct answer!
And using my puzzle input...
Correct answer!
Part 2
- As anticipated, an algorithmic stress test
- 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 themodulo
operator - I recognized my algorithm's performance deficiencies (
O(n)
array vsO(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
Top comments (0)