All in a Single Night

Advent of Code 2015 Day 9

Part 1

1. A walk in the park
2. Writing a working algorithm

A walk in the park

Today's puzzle feels like Day 13 in Easy mode!

• Generate the list of permutations
• Sum up each A to B score
• Identify the lowest score

Writing a working algorithm

Extracting the places and score

Each line of the input follows this pattern:

A to B = C

I'll forego using regex and instead extract the three parts using split() and array destructuring:

let [A, ,B, ,C] = flight.split(' ')

Creating the dictionary of places and scores

For the example input:

London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141

I want a dictionary like this:

{
  London: { Dublin: 464, Belfast: 518 },
  Dublin: { London: 464, Belfast: 141 },
  Belfast: { London: 518, Dublin: 141 }
}

Thus, for each line, I need to set two keys and the same value to each:

dict[A][B] = +C
dict[B][A] = +C

Altogether, my reduce() looks like this:

const scores = input.reduce((dict, flight) => {
  let [A, ,B, ,C] = flight.split(' ')
  if (!(A in dict)) dict[A] = {}
  if (!(B in dict)) dict[B] = {}
  dict[A][B] = +score
  dict[B][A] = +score
  return dict
}, {})

Generating the list of possible routes

• I'll again use the very handy JavaScript library, js-combinatorics
• I need to pass the list of all possible destinations
• I'll use Object.keys() to generate that list

const C = require('js-combinatorics')
const routes = [...new C.Permutation(Object.keys(scores))]

Finding the shortest route

My algorithm in pseudocode:

For each possible route
  Accumulate a number - starting at Infinity - that should get smaller and smaller
  Set score to 0
  For each destination in the route, except the last
    Increment score by the value associated with the key corresponding to the next item that is a key inside the dictionary corresponding to the current item
  Return the smaller number between the accumulated number and score
Return the accumulated number

My algorithm, animated:

My algorithm in JavaScript:

routes.reduce((shortest, route) => {
  let score = 0
  for (let i = 0; i < route.length - 1; i++) {
    score += scores[route[i]][route[i + 1]]
  }
  return Math.min(shortest, score)
}, Infinity)

It generated the correct answer!

Part 2

Swapping Math.min() for Math.max() and Infinity for 0

• Two simple changes
• And another correct answer!

I did it!!

• I solved both parts!
• In record time, given my familiarity with the combination-generating library and reduce()!

The only problem with solving these puzzles backwards is that combination-themed ones become decreasingly fun to solve.

Since I'm only at Day 9, I feel like there's at least one more waiting for me before the end of the year.