Advent of Code 2015 Day 13
Part 1
- Another combination puzzle?!
- How many possible combinations?
- Leveraging that combo-generator 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 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
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 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 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('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!
Top comments (0)