It Hangs in the Balance

Advent of Code 2015 Day 24

Part 1

1. Solving seems highly unlikely
2. New computer science theory!
3. Watching my understanding grow
4. 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 to Group 1 and its quantum 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

1. Now...this...seems tougher
2. 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!