Knights of the Dinner Table

Advent of Code 2015 Day 13

Part 1

1. Another combination puzzle?!
2. How many possible combinations?
3. Leveraging that combo-generator library
4. Creating each person's happiness dictionary
5. Look right, look left, then add

Another combination puzzle?!

• You'd think I'd be sick of them by now
• But this one seems equally as intriguing as the others thus far this year!

How many possible combinations?

The example input features four people:

First chair: 4 options
Second chair: 3 options
Third chair: 2 options
Fourth chair: 1 option

4 * 3 * 2 * 1
4!
24 combinations

My puzzle input features eight people:

8!
40,320 combinations

Thus, I'll have to determine the happiness scores of over 40K combinations to find the optimal seating arrangement.

Leveraging that combo-generator library

• In an earlier combo-themed puzzle, I resorted to browsing the reddit Solution Megathread for help
• In one JavaScript solver's post, they referenced a handy library, js-combinatorics
• I intend to use it to make solving this puzzle a bit easier

The library has a method, Permutation, that accepts a string of characters and returns a collection of all the ways those characters could be arranged.

I'll take the first initial of each person from my input and concatenate them into a string:

const C = require('js-combinatorics')

// Example input: Alice, Bob, Carol, David
const arrangements = [...new C.Permutation('ABCD')]
console.log(arrangements.length) // 24

// Example input: Alice, Bob, Carol, David, Eric, Frank, George, Mallory
const arrangements = [...new C.Permutation('ABCDEFGM')]
console.log(arrangements.length) // 40320

Fantastic! Each collection includes the expected factorial amount.

Now, how do I perform my calculations on these collections?

Creating each person's happiness dictionary

In the example input, these are Alice's scores:

Alice would gain 54 happiness units by sitting next to Bob.
Alice would lose 79 happiness units by sitting next to Carol.
Alice would lose 2 happiness units by sitting next to David.

From this, I want to craft this dictionary:

{
  'A': {
    'B': 54,
    'C': -79,
    'D': -2
  }
}

From each line, I need to extract four parts:

• Family member's first initial
• gain or lose
• Amount of happiness units
• Adjacent family member's first initial

I could use a regular expression, but since each line is the same number of words, I'll just use split() and access the relevant items:

let [X, , sign, amount, , , , , , , Y] = line.split(' ')
X = X[0]
Y = Y[0]
sign = sign == 'gain' ? '+' : '-'
amount = Number(sign + amount)

Then, I need to create the appropriate keys if they don't already exist, and set the appropriate amount.

My full dictionary-creation algorithm in JavaScript:

input.reduce((dict, line) => {
  let [X, , sign, amount, , , , , , , Y] = line.split(' ')
  X = X[0]
  Y = Y[0]
  sign = sign == 'gain' ? '+' : '-'
  amount = Number(sign + amount)
  if (!(X in dict)) dict[X] = {}
  dict[X][Y] = amount
  return dict
}, {})

The algorithm generates this dictionary for the example input:

{
  A: { B: 54, C: -79, D: -2 },
  B: { A: 83, C: -7, D: -63 },
  C: { A: -62, B: 60, D: 55 },
  D: { A: 46, B: -7, C: 41 }
}

Look right, look left, then add

By now I have:

• Each permutation of seating arrangements
• The happiness units of each family member's adjacent family member

Time to do some math!

Using the first permutation of the example input:

['A','B','C','D']

Look right:

A -> B: +54
B -> C: -7
C -> D: +55
D -> A: +46
-----------
        148

Look left:

D <- A: -2
A <- B: +83
B <- C: +60
C <- D: +41
-----------
        182

Then add:

        182
       +148
-----------
Total:  330 -> Optimal arrangement!

My algorithm, animated:

My algorithm in JavaScript:

arrangements.reduce(
  (optimal, permutation) => 
    Math.max(
      optimal,
      permutation.reduce(
        (sum, seat, index, RA) => 
          sum += happiness[seat][RA[(index + 1) % RA.length]]
        , 0)
    + permutation.reverse().reduce(
        (sum, seat, index, RA) => 
          sum += happiness[seat][RA[(index + 1) % RA.length]]
        , 0)
    )
  , 0)

It generated the correct answer!

Part 2

1. Inserting myself into the puzzle

Inserting myself into the puzzle

• I could manipulate the input, but that feels taboo
• I'll add myself programmatically, instead

happiness['R'] = {}
for (let seat in happiness) {
  // Adding other family members' happiness units toward me
  happiness[seat]['R'] = 0
  // Adding my happiness units toward them
  happiness['R'][seat] = 0
}

Generating 9! combinations instead of 8!:

const C = require('js-combinatorics')
const arrangements = [...new C.Permutation('ABCDEFGMR')]

Running the program again...

...and it generates the correct answer again!

I did it!!

• I solved both parts!
• Leveraging a combination-generating library I used previously!
• And my knack for treating arrays like circular lists!

I was a bit disappointed in how little increase of difficulty Part 2 was from Part 1.

Maybe it was intended to be a stress test for made-from-scratch combination-generation algorithms?

Regardless, this was another fun combo-themed puzzle!