Advent of Code 2015 Day 13
Part 1
 Another combination puzzle?!
 How many possible combinations?
 Leveraging that combogenerator library
 Creating each person's happiness dictionary
 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 combogenerator library
 In an earlier combothemed puzzle, I resorted to browsing the reddit Solution Megathread for help
 In one JavaScript solver's post, they referenced a handy library,
jscombinatorics
 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('jscombinatorics')
// 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
orlose
 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 dictionarycreation 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 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
 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('jscombinatorics')
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 combinationgenerating 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 madefromscratch combinationgeneration algorithms?
Regardless, this was another fun combothemed puzzle!
Top comments (0)