## DEV Community # It Hangs in the Balance

## 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!

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...?

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.

#### 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!