Infinite Elves and Infinite Houses

Advent of Code 2015 Day 20

Part 1

1. Another fun arithmetic puzzle!
2. Attempting to write a working algorithm
3. House 10 reveals an oversight in my logic
4. All numbers by which a given number is divisible

Another fun arithmetic puzzle!

It seems this puzzle plays with divisible by 2 and divisible by 3.

Analyzing the initial house numbers and present amounts:

House 1 got 10 presents.
House 2 got 30 presents.
House 3 got 40 presents.
House 4 got 70 presents.
House 5 got 60 presents.
House 6 got 120 presents.
House 7 got 80 presents.
House 8 got 150 presents.
House 9 got 130 presents.

Attempting to extrapolate each amount based on divisors:

1:10  -> 1: div 2? N div 3? N
2:30  -> 2: div 2? Y div 3? N 2 + 1
3:40  -> 3: div 2? N div 3? Y 3 + 1
4:70  -> 4: div 2? Y div 3? N 4 + 4/2 + 1
5:60  -> 5: div 2? N div 3? N 5 + 1
6:120 -> 6: div 2? Y div 3? Y 6 + 6/2 + 6/3 + 1
7:80  -> 7: div 2? N div 3? N 7 + 1
8:150 -> 8: div 2? Y div 3? N 8 + 8/2 + 8/2/2 + 1
9:130 -> 9: div 2? N div 3? Y 9 + 9/3 + 1

Hmm. Looks like my algorithm will require recursion and memoization to keep track of all previously calculated divisor amounts.

Attempting to write a working algorithm

My recursive function looked something like this:

Expect one parameter, a number
  Create a copy of the number
  If the number is 1
    Return 1
  Else
    If the number is divisible by 2
      Increment the copy by the result of calling this function with a number 1/2 the size of the input number
    If the number is divisible by 3
      Increment the copy by the result of calling this function with a number 1/3 the size of the input number
  Return the incremented copied number

It seemed to work on numbers 1-3.

But it failed to generate the same totals as in the example 9 houses for nearly all other houses.

I am definitely getting something wrong.

House 10 reveals an oversight in my logic

Recalling my formulas for a few houses:

4:70  -> 4: div 2? Y div 3? N 4 + 4/2 + 1
6:120 -> 6: div 2? Y div 3? Y 6 + 6/2 + 6/3 + 1
8:150 -> 8: div 2? Y div 3? N 8 + 8/2 + 8/2/2 + 1
9:130 -> 9: div 2? N div 3? Y 9 + 9/3 + 1

House 8 could be re-written as:

8:150 -> 8: div 2? Y div 3? N 8 + House 4

What about House 10?

10:160 -> 10: div 2? Y div 3? N 10 + 10/2 + 1

• That's not correct, though
• House 10 is visited by Elves 1, 2, 5 and 10
• My formula was missing Elf 2

10:160 -> 10: div 2? Y div 3? N div 5? Y 10 + 10/2 + 10/5 + 1

All numbers by which a given number is divisible

• 8: itself, 4, 2, 1
• 9: itself, 3, 1
• 10: itself, 5, 2, 1
• 15: itself, 5, 3, 1
• 20: itself, 10, 5, 4, 2, 1

I'm sure I could find an algorithm for this by searching online.

But could I write it myself?

The brute-force approach is:

For i from 1 to target
  If target % i == 0
    target is divisible by i!
  Else
    target is not divisible by i

• That algorithm checks every number between 1 and the target
• But I know that for any of my target house numbers, there will be no number greater than half the target number that the target number evenly divides by...because the biggest is the target number divided by 2
• I also know that if the target number is even, I have to check all numbers from 1 up to half the target number...and if the target number is odd, I can just check all odd numbers from 1 up to one less than half the target number
• These optimizations save a bit of time, but my algorithm still can't process more than 1000 house numbers every second or two

My slightly-optimized algorithm:

For any target number
  Create a unique set of numbers including 1 and the target number
  If the target number is even
    For i from 1 to half the target, incrementing by 1
      If target % i == 0
        Attempt to add the number to the unique set
  Else, if the target number is odd
    For i from 1 to one less than half the target, incrementing by 2
      If target % i == 0
        Attempt to add the number to the unique set
  Return the list of unique numbers

Multiply each unique number by 10
  Add all the resulting numbers together
    Return the sum

Set house number to 1
Set winner to empty

While there is no winner
  Calculate the sum of presents delivered to this house
  If sum >= puzzle input
    Set winner as the house number responsible for generating the sum
  Increment house number by 1

Return winner

• My puzzle input is 34M
• I arbitrarily decided to start at house number 1M
• The first winner was house number 1043460
• I continually lowered my starting house number by 100K, then by 10K
• I found smaller and smaller house numbers: 1000080, 900900, 892080, 882000, 873180, 819000
• I started from house number 700000
• And found a winner under 800K: 786240
• I started from house number 600000
• And found no winners below 700K

I think I found the correct answer: house number 786240

Indeed, that is the lowest house number using my input!

It may have taken a lot of guessing and waiting, but I did it!

Part 2

1. Now...this...seems tricky
2. filter() for the win!
3. Negligence bites hard

Now...this...seems tricky

• I barely squeezed out a star for Part 1
• Part 2 includes an easy update: multiply Elf numbers by 11 instead of 10
• But the far more difficult twist is: each Elf will stop after delivering presents to 50 houses

Wow. I'm not sure where to even begin.

After some time away, I think I know where to begin!

filter() for the win!

The easy update was this:

Multiply each unique number by 11 - not 10
  Add all the resulting numbers together
    Return the sum

The tougher update, though simple in hindsight - was this:

For any target number
  Create a unique set of numbers including 1 and the target number
  If the target number is even
    For i from 1 to half the target, incrementing by 1
      If target % i == 0
        Attempt to add the number to the unique set
  Else, if the target number is odd
    For i from 1 to one less than half the target, incrementing by 2
      If target % i == 0
        Attempt to add the number to the unique set
  Filter the list of unique numbers
    Keep only numbers that, when multiplied by 50, become a number greater than or equal to the target number
  Return the list of filtered, unique numbers

• An Elf could now only visit 50 houses
• Elf 1 could only visit houses 1-50
• Elf 2: 2-100
• Thus, each elf's last visit was their number times 50

It made my algorithm a bit slower, given the additional step of generating a new, filtered, list for each house.

But it ran at relatively the same speed: ~1000 house numbers processed per 1-2 seconds.

I again started arbitrarily at house number 1M:

• Match found just over 1M
• Using smaller and smaller starting house numbers...
• Match found at 990K, just over 900K, just under 890K
• No matches found between 700K and the recent match

I submitted my lowest house number.

Too high.

Negligence bites hard

Too high?! How?

• Was my filter() logic wrong?
• Should it be greater than and not also equal to?
• I don't think so

Oh. My. Word.

• I forgot to update the 10 in my loop to 11!
• What a terribly unfortunate oversight -I ran my program starting at house number 700K again
• It found a match at just over 830K
• That was the correct answer!

I did it!!

• I solved both parts!
• By tinkering with a poor-performing, divisor-collecting algorithm!
• And identifying the silly numerical oversight in my code!

Like with several puzzles in the past:

• I may not have solved this puzzle using 100% computer science
• But I did identify arithmetical calculations that helped me find the correct answers
• And I solved both parts nonetheless, albeit using process of elimination
• And that's what I set out to do!