DEV Community

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

Posted on

1 1

Knights of the Dinner Table

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!

SurveyJS custom survey software

Simplify data collection in your JS app with a fully integrated form management platform. Includes support for custom question types, skip logic, integrated CCS editor, PDF export, real-time analytics & more. Integrates with any backend system, giving you full control over your data and no user limits.

Learn more

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay