Chocolate Charts

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

1. Another growing array puzzle?
2. Understanding this puzzle's arithmetic logic
3. Thinking out load before I write an algorithm
4. A written description of my working algorithm
5. 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

1. An interesting twist
2. My strategic approach
3. 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