DEV Community

Cover image for Knights of the Dinner Table
Robert Mion
Robert Mion

Posted on

Knights of the Dinner Table

#adventofcode #algorithms #programming #javascript

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
Enter fullscreen mode Exit fullscreen mode

My puzzle input features eight people:

8! 40,320 combinations
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

From this, I want to craft this dictionary:

{ 'A': { 'B': 54, 'C': -79, 'D': -2 } }
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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 }, {})
Enter fullscreen mode Exit fullscreen mode

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 } }
Enter fullscreen mode Exit fullscreen mode

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']
Enter fullscreen mode Exit fullscreen mode

Look right:

A -> B: +54 B -> C: -7 C -> D: +55 D -> A: +46 ----------- 148
Enter fullscreen mode Exit fullscreen mode

Look left:

D <- A: -2 A <- B: +83 B <- C: +60 C <- D: +41 ----------- 182
Enter fullscreen mode Exit fullscreen mode

Then add:

 182 +148 ----------- Total: 330 -> Optimal arrangement!
Enter fullscreen mode Exit fullscreen mode

My algorithm, animated:
Animation of my algorithm

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)
Enter fullscreen mode Exit fullscreen mode

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 }
Enter fullscreen mode Exit fullscreen mode

Generating 9! combinations instead of 8!:

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

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)