An Elephant Named Joseph
Tags: adventofcode, algorithms, programming, computerscience
Published: 2022-08-19 01:24:56

## [Advent of Code 2016 Day 19](https://adventofcode.com/2016/day/19)

## Part 1
1. Going in circles, again!
2. This is making my head spin!
3. Writing an algorithm that works on my examples
4. A pattern emerges!
5. 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!
![Manually solving several circle sizes](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3ma475fhpetrxf4kir8h.gif)

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:
![Animation revealing the puzzle's pattern](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uidpegu9fa623swb40vv.gif)

- 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
1. Ugh, more example GIFs
2. Writing the algorithm that I animated
3. A pattern emerges again!
4. 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:
![Animating 10 circles](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/k735w57a2nh1zy1fdrsb.gif)

Sadly, `10` circles isn't enough to reveal a pattern:
![Pattern unidentified](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lyr7jmg5xvr0q257s321.gif)

### 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:
![Revealing the pattern of winners](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/somfn0505h1qqivh1sly.gif)

- 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?