Knights of the Dinner Table
Tags: adventofcode, algorithms, programming, javascript
Published: 2022-09-18 23:42:48

## [Advent of Code 2015 Day 13](https://adventofcode.com/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`](https://github.com/dankogai/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:
```js
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:
```js
{
  '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:
```js
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:
```js
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:
```js
{
  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:
![Animation of my algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sqnraqxln5v3zwej29s7.gif)

My algorithm in JavaScript:
```js
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

```js
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!`:
```js
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!