Robert Mion

Posted on Aug 19, 2022

An Elephant Named Joseph

#adventofcode #algorithms #programming #computerscience

Advent of Code 2016 Day 19

Part 1

Going in circles, again!
This is making my head spin!
Writing an algorithm that works on my examples
A pattern emerges!
Simulating the pattern with an algorithm

Going in circles, again!

The example is wonderfully explanatory
My puzzle input is an integer over 3M
I want to explore more example circle sizes before writing an algorithm
Because I anticipate a pattern emerging

This is making my head spin!

Good news:

I now have several unit tests
I feel comfortable writing a brute-force algorithm that will definitely finish quickly on circles with up to 100K Elves probably

Bad news:

I don't think I found a faithful pattern for identifying the winning Elf based on the number of Elves in the circle
I'm not sure the brute-force algorithm I intend to write will work for circles with millions of Elves

Writing an algorithm that works on my examples

For i from 1 to 20, inclusive
  Create an array called circle of length i where each value is 1
  Set pointer to 0
  Set next to 0
  Do as long as circle does not include i
    Increment next, wrapping when appropriate
    Continue incrementing next until the value in circle at next is not 0
    Update the value in circle at pointer to the sum of the current value in circle at pointer and the current value in circle at next
    Set the value in circle at next to 0
    Increment next until the value in circle at next is not 0
    Set pointer to the value stored in next
  Log the number one greater than the location of i in circle

I spent quite some time fiddling with this algorithm
I was either forgetting to update next or incorrectly updating it
For a while, I was logging circle after each iteration of the inner while loop to confirm whether it was working as intended
Thankfully, I eventually worked out all the kinks and got it to print the values I was expecting

A pattern emerges!

I ran the loop above for Elven circles up to 99 in size.

This animation shows circles up to 26, which is enough to demonstrate the pattern:

I was almost certain there would be a pattern!
Unsurprisingly, I missed it by skipping 6-9, 11-14, and 16-19 in my initial GIF
Now that I see and understand it, I need to re-create it with a different algorithm!

Simulating the pattern with an algorithm

Set circle to 0
Set multiple to 1
Set answer to null
Do as long as circle is less than the puzzle input
  Set winner to -1
  For i from 1 up to and including multiple
    Increment winner by 2
    Increment circle by 1
    If circle is the puzzle input
      Set answer to winner
  Double multiple

This also took some fiddling to get right
At first I had two for loops, then realized I didn't need both
The outer loop condition causes this algorithm to overextend itself a bit, unfortunately
And I'm not sure how to achieve the same result without starting winner at a value two less than my first desired value of 1, since I increment it by 2 each time

Regardless, this algorithm terminates near-instantly!

And it generates the correct answer for every example and my puzzle input!

That's wonderful, especially since my brute-force algorithm outlined earlier seemingly never finishes when run on my 3M+ puzzle input number!

Part 2

Ugh, more example GIFs
Writing the algorithm that I animated
A pattern emerges again!
Simulating the pattern with a similar algorithm

Ugh, more example GIFs

Seeing a 5-Elf circle demonstrated is nice
But I need to find another pattern
So, I need to play out at least circle sizes 1-10

It took a long time, but it helped prepare me to write the algorithm...I hope:

Sadly, 10 circles isn't enough to reveal a pattern:

Writing the algorithm that I animated

For i from 1 to 10, inclusive
  Create an array called circle of length i where each value is one greater than its index
  Set pointer to 0
  Do until circle contains one item
    Set removed as the remainder resulting from:
      The sum of pointer and the length of circle divided by two, rounded down to the nearest whole number
      Divided by the length of circle
    Delete the item at the location stored in removed
    Update pointer based on the value of removed
      If removed is less than pointer
        Set pointer to the remainder after dividing pointer by the length of circle
      Else
        Set pointer to the remainder after dividing one greater than pointer by the length of circle
  Log the single value remaining in circle

I had the most trouble fiddling with updating pointer correctly
Thankfully, this algorithm generated the same winners as in my animation, so I could trust my work and the computer's!
Next, I ran it on numbers up to 100
I was delighted by what I saw!

A pattern emerges again!

I ran the loop above for Elven circles up to 99 in size.

This animation shows circles up to 28, which is enough to demonstrate the pattern:

I was almost certain there would be a similar pattern!
Unsurprisingly, I couldn't see it clearly with just 10 circles
Now that I see and understand it, I need to re-create it with a similar algorithm!

Simulating the pattern with a similar algorithm

Set circle to 1
Set multiple to 3
Set answer to null
Do as long as circle is less than the puzzle input
  Set winner to 0
  Set counter to 1
  Do as long as counter is less than or equal to multiple
    If counter is less than or equal to multiple divided by 3
      Increment counter by 1
      Increment winner by 1
    Else
      Increment counter by 2
      Increment winner by 2
    Increment circle by 1
    If circle is the puzzle input
      Set answer to winner
  Triple multiple

This also took some fiddling to get right
I had a lot of trial and error getting counter to increment the correct amount based on the condition
And I still don't know how to start this algorithm from a circle of size 1 - my divide by 3 rule makes that impossible

Regardless, this algorithm terminates near-instantly, too!

And it generates the correct answer for every example and my puzzle input!

I did it!!

I solved both parts!
Through a journey of animation, brute-force algorithm as pattern-identification, then number-processing algorithm for a near-instant answer!
I made so many slides as part of several GIFs!
And I'm glad I did, as it helped me understand the many algorithms I would have to write!

This may be my favorite puzzle of all of Advent of Code thus far!

With the exception of building a simulator - which I can't reliably use to visualize a circle with over 3 million Elves - I got to use all of my design and developer skills to solve it...and I succeeded!

Who knew circular data structures could be this fun?

DEV Community