## DEV Community # Knights of the Dinner Table

## 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
Y = Y
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
Y = Y
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
``````

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

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)
``````

## Part 2

1. Inserting myself into the puzzle

### Inserting myself into the puzzle

• I could manipulate the input, but that feels taboo
``````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!