Advent of Code 2015 Day 24
Part 1
- Solving seems highly unlikely
- New computer science theory!
- Watching my understanding grow
- Forget the algorithm: studying my puzzle input and submitting a few guesses
Solving seems highly unlikely
I need to identify a way to form three groups of weights where:
- Each group has the same sum across its included weights
- The group I arbitrarily dictate as
Group 1
has the fewest amount of weights across all three groups - For all combinations that satisfy the previous bullet for
Group 1
, I must find the one where the product of the included weights is the lowest
Based on that understanding:
- I sense there will be recursion
- I sense I'll need a tree data structure
- I sense the answer is ultimately the
shortest path
, at least related toGroup 1
and itsquantum entanglement
value
Outside of those intimidating hurdles:
- I have no idea how I'd even begin generating the possible combinations of weights that will form each group!
New computer science theory!
I did some Google'ing.
It seems like this puzzle involves a popular algorithm:
- Partition to K equal sum subsets
And that algorithm involves the use of a popular technique:
- Backtracking...?
- Also, Bit Masking...?
There are several lengthy articles about this algorithm.
And tons of Youtube videos.
Sadly, none of them appear to have solutions written in JavaScript.
Still, it's worth my time to attempt to understand how they work in hopes that I could attempt to at least make a GIF, and at most attempt to re-write them and solve this puzzle!
Watching my understanding grow
- While walking my dog, I opted to try YouTube
- Searching for
partition to k equal sum subsets
resulting in a litany of videos, as expected - I picked one of the first three in my results for no real reason
Some of my observations:
- Each of my groups had to sum to the same amount: the sum of all amounts divided by 3!
- Build each array by adding either another amount or no amount
- Each node is the sum of included amounts
- Stop creating branches if a sum is ever greater than the target amount: the sum of all amounts divided by 3
Some of my questions:
- If I found one group that matched the target sum, does that mean there must be a way to make the other two groups match?
- Or is it possible for one or two groups to match the target sum and the other(s) not?
- Am I ready this early to build a recursive algorithm that finds a single group among...say...the example amounts?
I don't think so. I owe it to myself to browse a couple more tutorials.
Next was this video:
Some of my observations:
- Interesting use of one function to check whether it's even possible for the remaining amounts to each total the required sums...once one target sum is reached
- That's a lot of arguments being passed to the recursive function!
- I feel like I could write both functions in JavaScript
- Though, it seems like this function is designed to answer whether an array of integers can be partitioned
- I know my array of integers can be partitioned into three groups
- What I need to find is each group's DNA
Some of my questions:
- How might I modify this algorithm to save each group's integers, instead of returning whether it can partition or not?
- Am I ready to attempt re-writing this algorithm in JavaScript?
Yes, I think I'll start with re-writing the Driver
function, which says whether the remaining integers can total to the remaining required sum.
Before that, I should analyze my puzzle input for a bit...just in case I can solve this part manually through trial and error.
Forget the algorithm: studying my puzzle input and submitting a few guesses
- Aside from
1
, all my weights are prime numbers - There are just under 30 weights
- Numbers range from low single-digits to just over 100
What's my total weight?
input.split('\n').map(Number).reduce((a,c) => a + c)
Total weight: 1524
Each group's sum must be: 508
A few groups I could identify manually:
Round 1
113,109,107,97,79,3
qe = 30297639891
113,109,107,97,29,53
qe = 196487225791
107,101,97,83,73,47
qe = 298521555667
101,109,107,97,79,11,3,1
qe = 297882105477
1,23,29,31,37,41,43,47,53,59,71,73
qe = 1027421174784893400
Feeling greedy, I had to try 30297639891
as a possible answer:
- Too high
Round 2
113,109,107,103,73,3
qe = 29728298883
113,109,103,101,79,3
qe = 30367698987
113,109,107,101,73,5
qe = 48585083935
113,109,101,97,83,5
qe = 50077904335
109,107,101,97,89,5
qe = 50846772895
113,109,107,97,71,11
qe = 99841589683
Then, I had to try 29728298883
:
- Too high
Round 3
101,107,103,113,83,1
qe = 10439961859
After more fiddling around in my console, I discovered a combination with 6 integers where one was 1
, in essence finding a combination where the product comprised only 5 integers instead of 6!
Crossing my fingers that I found the only combination with 1
in it...and a quantum entanglement value 1/3 that of the lowest one I'd found thus far...I had to try 10439961859
:
- That was the correct answer!
Welp, so much for needing an algorithm to solve Part 1!
Part 2
- Now...this...seems tougher
- But I gotta try...manually!
Now...this...seems tougher
- Three groups seemed wonderfully constricting of the amounts
- But four groups...this may require some intense manual searching, or actually writing an algorithm
But I gotta try...manually!
- The sum to match is now
381
- There seems like no way to achieve that with my puzzle input's three largest prime numbers
- So the minimum count of weights in a group must be 4
- However, since all weights are odd, there's no way to get an even number after adding four odd numbers together: two odds make an even, two pair of odds each make an even and those evens make an even, etc.
- So, it must be that the minimum count of weights is a group of 5...with the 5th weight being
1
for the smallest quantum entanglement
Round 1
113,107,101,59,1
qe = 72050269
109,103,101,67,1
qe = 75973109
113,103,97,67,1
qe = 75641861
107,103,97,73,1
qe = 78039701
113,109,103,53,3
qe = 201715509
I can't find a 5-weight combination that has a quantum entanglement amount smaller than 72M.
Can't hurt to try it:
- It was the correct answer!
I did it!!
- I solved both parts!
- Of a Day 24 puzzle!
- Without writing an algorithm!
- Rather, by just trying a bunch of combinations for Part 1!
- Then, using my understanding of odds and evens to narrow the search field for Part 2!
Wow. I was not expecting to solve either part of today's puzzle.
The algorithms referenced seemed intimidating.
Thankfully, with some trial and error, I pulled this one out using my browser's console and number swapping!
Top comments (0)