- Solving seems highly unlikely
- New computer science theory!
- Watching my understanding grow
- Forget the algorithm: studying my puzzle input and submitting a few guesses
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 1has 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 to
Group 1and its
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!
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:
- Also, Bit Masking...?
There are several lengthy articles about this algorithm.
And tons of Youtube videos.
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!
- While walking my dog, I opted to try YouTube
- Searching for
partition to k equal sum subsetsresulting in a litany of videos, as expected
- I picked one of the first three in my results for no real reason
- 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
- 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:
- 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!
- 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
- How might I modify this algorithm to save each group's integers, instead of returning whether it can partition or not?
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.
- 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)
Each group's sum must be:
A few groups I could identify manually:
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
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
- Too high
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
- That was the correct answer!
Welp, so much for needing an algorithm to solve Part 1!
- Now...this...seems tougher
- But I gotta try...manually!
- Three groups seemed wonderfully constricting of the amounts
- But four groups...this may require some intense manual searching, or actually writing an algorithm
- The sum to match is now
- 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
1for the smallest quantum entanglement
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 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!