Advent of Code 2015 Day 20
Part 1
- Another fun arithmetic puzzle!
- Attempting to write a working algorithm
- House 10 reveals an oversight in my logic
- 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
- Now...this...seems tricky
-
filter()
for the win! - 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 alsoequal to
? - I don't think so
Oh. My. Word.
- I forgot to update the
10
in my loop to11
! - 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!
Top comments (0)