Robert Mion

Posted on Sep 14, 2022

No Such Thing as Too Much

#adventofcode #algorithms #programming #javascript

Advent of Code 2015 Day 17

Part 1

Another combination puzzle?
Visually exploring potential algorithms
Writing my second idea
Accounting for duplicate amounts
Falling short
Celebrating my accomplishments
Discovering the answer, and a new library!
I should have waited...a lot longer

Another combination puzzle?

Much like Day 24, today's puzzle requires identifying combinations of integers that amass to a prescribed sum
Except, today seems more difficult because it's not about finding the shortest path so to speak
Rather, it requires I find every possible combination
That may mean I need to actually write an algorithm to solve this puzzle...instead of using my console to do some manual arithmetic

Visually exploring potential algorithms

My first idea is to:

Sort the list in ascending order
Set count to 0
For each number
  Accumulate an array of numbers
    If the sum is less than the target amount
      Continue with the following amount
    Else If the sum is greater than the target amount
      Backtrack by removing the last number
      Mark it as visited
      Continue with the following number
    Else If the sum is equal to the target amount
      Increment count by 1
Return count

This animation shows such an algorithm working on the first number in a sorted list:

My second idea is to:

Sort the list in descending order
Set count to 0

Recursive function: combos
  Accept three parameters
    1. A sum of the values visited thus far
    2. A list containing the visited values thus far
    3. A list containing the unvisited values thus far
  If sum is less than the target amount
    For each number in the list of unvisited values
      Call combos, passing as arguments:
        1. The sum incremented by the current number
        2. The list of visited values with the current number added
        2. The list of unvisited values with the current number removed
  Else if sum is greater than the target amount
    Do not proceed
  Else if sum is equal to the target amount
    Increment count by 1

This animation shows such an algorithm working on the first number in a sorted list:

Writing my second idea

Parsing the input and sorting the numbers in descending order:

let containers = input.split('\n').map(Number).sort((a, b) => b - a)

Setting my target number and initial empty set of matches:

let target = 150
let matches = new Set()

The recursive function:

function combos(sum, visited, unvisited) {
  if (sum < target) {
    unvisited.forEach((num, i) => {
      combos(
        sum + num, 
        visited.concat(containers.indexOf(num)), 
        unvisited
          .slice(i + 1)
          .filter((el, i) => !visited.includes(i))
      )
    })
  } else if (sum == target) {
    count.add(
      visited.map(el => containers[el])
       .sort((a, b) => a - b)
       .join('|')
    )
    return false
  } else if (sum > target) {
    return false
  }
}

Calling the function:

combos(0, [], containers.slice())

Accounting for duplicate amounts

My input of container amounts contains three pair of duplicate amounts
My algorithm is designed to only capture one occurrence of a possibly repeated combination
I have to handle the arithmetic for counting the actual number of ways to achieve any matching combination

Programmatically identifying which numbers in my input are part of a pair:

let duplicates = Object.entries(
  containers.reduce((counts, amount) => {
    counts[amount] = (counts[amount] || 0) + 1
    return counts
  }, {})
).filter(el => el[1] > 1).map(el => el[0])

A walkthrough using the example input of 20,15,10,5,5:

{ 20: 1, 15: 1, 10: 1, 5: 2 }
[['20',1],['15',2],['10',1],['5',2]]
['5',2]
['5']

Next, pseudocode for how I will account for each combination variant:

For each unique combination of amounts that equals the target
  Accumulate a sum of all variations of those combinations, starting at 0
    Generate an object storing tallies of each number's occurrences within a combination
    For each identified pair from the input
      Change the amount to 1 or 0 depending on whether that pair's value is a key in the object with a tally of 1
    For each modified pair value - now either 1 or 0
      Accumulate a product, starting at 1
        If the value is 1, multiply the accumulator by 2
        Else, multiply the accumulator by 1
    Increment the accumulating sum by the final product
      A number no smaller than 1 and no larger than 2 to the power of the amount of pairs in the input

Return the accumulated sum

My algorithm in JavaScript:

Array.from(matches).reduce((sum, combo) => {
  let tallies = combo.split('|').reduce((dictionary, num) => {
    dictionary[num] = (dictionary[num] || 0) + 1
    return dictionary
  }, {})
  let variations = duplicates.map(dupe => {
    return (tallies[dupe] && tallies[dupe] == 1) ? 1 : 0
  }).reduce(
    (product, multiple) => product *= multiple == 1 ? 2 : 1, 1)
  return sum += variations
}, 0)

Falling short

My algorithm generated the correct answer for the example input
But an answer Too Low for my puzzle input
I thought I nailed it, too!

Celebrating my accomplishments

I made a couple of GIFs as a way to brainstorm an algorithmic approach to solving today's puzzle
I wrote a few complex algorithms that seemed to work as intended
I practiced a ton of my accrued skills involving Arrays and Sets

I almost pushed Publish!

Discovering the answer, and a new library!

I really wanted to know whether I was off by 1, 10, 100 or even 1000
So I turned to the reddit Solution Megathread for today's puzzle
And searched for JavaScript solutions
Luckily, I found one that I could re-create!
The solver used a library called js-combinatorics
After some reading and trial and error, I discovered the correct answer for my puzzle input

I was off by over 1000!

Yikes!

I should have waited...a lot longer

The algorithm I included as my second idea features this snippet of code:

unvisited
  .slice(i + 1)
  .filter((el, i) => !visited.includes(i))

It mistakenly generates a list of only the numbers after the number being removed from the unvisited list and added to the sum, and the numbers not in the list of visited numbers
Instead, I should have expanded it to include all numbers in the unvisited list...except the current one and the ones in the visited list
Ironically, that's how I wrote it originally
But when I ran the program with only a logging statement to show the next number in the first call of the recursive function, the program seemed to hang after just the first number!
I assumed my algorithm was broken
As it turns out, it was just extremely slow...at processing millions of combinations

The original snippet in my algorithm:

unvisited
  .slice(0, i)
  .concat(unvisited.slice(i + 1))
  .filter((el, i) => !visited.includes(i)))

I added a logging statement any time a new combination tries to get added to the unique set of combinations
Then I ran the program
Earlier, my set included 116 unique stringified combinations
This time, my set quickly surpasses that amount
Reaching over 500 unique combinations in about a minute of running
And over 700 unique combinations in about 10 minutes of running
Eventually, the program terminates, having collected all the unique combinations and accounted for each one's pairs
And the amount it generated matched the amount generated by the reddit solver's algorithm
Proof that my hand-written algorithm - albeit terribly slow - works as intended!

Part 2

More waiting, but for what I'm sure will be a correct answer
The correct answer...twice!

More waiting, but for what I'm sure will be a correct answer

I know that my algorithm generates a list of every possible combination and accounts for each one's pairs
Now I need to filter the unique list a bit more to determine and keep the combinations with the fewest containers
Before proceeding to account for each one's pairs

The reddit solver uses reduce() in a very eloquent to accomplish this:

let fewest = combinations.reduce(
  (min, list) => list.length < min ? list.length : min, 999
)
let answer = combinations.filter(
  (list) => list.length == fewest
)

I'm going to write my own, longer algorithm
But it will be nice to have an answer with which to compare before submitting

The correct answer...twice!

First, I ran my re-creation of the reddit solver's code
After a few seconds, it generated a double-digit answer
Next, I added near-identical code to my algorithm
After about two minutes, it generated the same double-digit answer
Both were the correct answer!

I did it!!

I solved both parts!
I solved Part 1 without realizing it...my impatience got the best of me!
I didn't give up!
I technically cheated in order to see how far off I was from the correct answer!
But doing that just made me want to generate it with my code even more!

This year's first combination-theme puzzle was solvable manually, thankfully.

But today's required an algorithm.

I'm proud of myself for writing it from scratch - after a ton of troubleshooting and a lot of waiting while it ran.

DEV Community