Advent of Code 2018 Day 14
Task: Solve for X where...
Part 1
X = the scores of the ten recipes immediately after N number of recipes, where N is my puzzle input
Part 2
X = the number of recipes that appear on the scoreboard to the left of N, where N is the score sequence in my puzzle input
Example input
9
It represents:
- The number of recipes made by two Elves
Part 1
- Another growing array puzzle?
- Understanding this puzzle's arithmetic logic
- Thinking out load before I write an algorithm
- A written description of my working algorithm
- A visual depiction of changing current recipe
Another growing array puzzle?
- This puzzle and its illustrated example reminds me of 2021 Day 6: Lanternfish
- I learned from inspecting another solver's solution a very elegant and performant way to solve that puzzle that used an array whose length didn't change
- I'm not sure if I could devise a similar solution for this puzzle at first glance
- Instead, I think I'll attempt a straightforward solution and hope my algorithm doesn't buckle under the pressure of increasing the size of an array from two values to nearly 1 million
Understanding this puzzle's arithmetic-based logic
- Two elves
- Each one making a recipe
- Tracking a scoreboard that logs their score
0-9
of each recipe
The initial state is:
scoreboard = [3,7]
elf1 = scoreboard[0] -> 3
elf2 = scoreboard[1] -> 7
One or two new recipes are created:
new_score = elf1 + elf2
3 + 7
-----------------------
10
new recipes = 1,0
scoreboard = [3,7,1,0]
Elf 1's new current
recipe:
steps_forward = 1 + elf1 -> 1 + 3 -> 4
[3,7,1,0]
*
[3,7,1,0]
1 2 3
[3,7,1,0]
4
elf1 = scoreboard[0] -> 3
Elf 2's new current
recipe:
steps_forward = 1 + elf2 -> 1 + 7 -> 8
[3,7,1,0]
*
[3,7,1,0]
1 2
[3,7,1,0]
3 4 5 6
[3,7,1,0]
7 8
elf1 = scoreboard[1] -> 8
Thinking out load before I write an algorithm
I feel like I understand this enough to write an algorithm inside of a for
loop that would run N + 10 times - where N is my nearly-1-million-number puzzle input.
I also feel like that loop may take several seconds - if not minutes - to finish, especially if it has to continually re-allocate memory for an increasingly large array.
I guess I know exactly what the array's length will eventually be, so I could create one that big, with initial values 3 and 7 at indices 0 and 1.
But that would mess up how I track the steps forward, unless I also track how many values it contains at any given point and use that as the simulated length
.
I wonder...if that algorithm would work.
What if...I tried writing it?
Let's try!
A written description of my working algorithm
- The toughest part was identifying the equation for updating the
current recipe
for each elf - It took a long walk with my dog to work it out in my head, but I eventually thought of an algorithm that works
Set several variables:
1. My puzzle input as an integer
2. The scoreboard as an array containing as many empty slots as the sum of my puzzle input and 10
3. Elf 1's current recipe as 0
4. Elf 2's current recipe as 1
5. The number of scores on the scoreboard as 2
Set 3 and 7 as the first two values in scoreboard
Do as many times as the sum of my puzzle input and 10
Set new_recipe as the sum of the values in scoreboard at the positions indicated by both Elves current recipes
For each digit in new_recipe
Insert the digit at the next empty slot in scoreboard
Update the number of scores to reflect the sum of the current value of scores and the number of digits in new_recipe
Update both Elves' current recipes to the result of the following equation:
The remainder after dividing these two values
1. The sum of: a) the current position of this Elf; b) 1; c) the value in scoreboard at the current position of this Elf;
2. The number of scores on the scoreboard
Return as a 10-digit integer the 10 scores after the score at the location indicated by my puzzle input
It worked!
And it ran in under a second!
A visual depiction of changing current recipe
The formula:
(current + (1 + score of current)) % number of scores
Part 2
- An interesting twist
- My strategic approach
- A written description of my working algorithm
An interesting twist
- Part 1 seemed to dictate the number of iterations to generate recipes
- Part 2 is more of a scavenger hunt, treating the puzzle input as an ordered list of scores that I need to find while generating recipe scores
My strategic approach
- As long as there are N scores in the scoreboard, check the last N scores in the scoreboard, where N is the number of digits in my puzzle input
- Turns out, I needed an extra variable to track where I started checking from - that's because the number of scores could grow by 1 or 2, and I didn't want to risk skipping any scores
A written description of my working algorithm
Set several variables:
1. My puzzle input as a string
2. The scoreboard as an array containing as many empty slots as my puzzle input as an integer
3. Elf 1's current recipe as 0
4. Elf 2's current recipe as 1
5. The number of scores on the scoreboard as 2
6. The address of the first score to check as 0
Set 3 and 7 as the first two values in scoreboard
Do until manually escaped
If there are more than 5 scores in scoreboard
If the N scores starting from the score at address - when combined - are equivalent to my puzzle input
Break out of the loop
Else
Increment address by 1
Set new_recipe as the sum of the values in scoreboard at the positions indicated by both Elves current recipes
For each digit in new_recipe
Insert the digit at the next empty slot in scoreboard
Update the number of scores to reflect the sum of the current value of scores and the number of digits in new_recipe
Update both Elves' current recipes to the result of the following equation:
The remainder after dividing these two values
1. The sum of: a) the current position of this Elf; b) 1; c) the value in scoreboard at the current position of this Elf;
2. The number of scores on the scoreboard
Return address
My algorithm took several seconds to run.
That may be because the scoreboard array eventually became magnitudes larger than the one I created.
Oh, well. It generated the correct answer!
I did it!!
- I solved both parts!
- I like to think I accounted for performance - at least in Part 1 - with my array being the exact length needed from the start
- I made a GIF that depicts how I update the current recipes
Top comments (0)