No Such Thing as Too Much

Advent of Code 2015 Day 17

Part 1

1. Another combination puzzle?
2. Visually exploring potential algorithms
3. Writing my second idea
4. Accounting for duplicate amounts
5. Falling short
6. Celebrating my accomplishments
7. Discovering the answer, and a new library!
8. 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

1. More waiting, but for what I'm sure will be a correct answer
2. 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.