DEV Community

Cover image for All in a Single Night
Robert Mion
Robert Mion

Posted on

All in a Single Night

#adventofcode #algorithms #programming #javascript

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

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

let [A, ,B, ,C] = flight.split(' ')
Enter fullscreen mode Exit fullscreen mode

Creating the dictionary of places and scores

For the example input:

London to Dublin = 464 London to Belfast = 518 Dublin to Belfast = 141
Enter fullscreen mode Exit fullscreen mode

I want a dictionary like this:

{ London: { Dublin: 464, Belfast: 518 }, Dublin: { London: 464, Belfast: 141 }, Belfast: { London: 518, Dublin: 141 } }
Enter fullscreen mode Exit fullscreen mode

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

dict[A][B] = +C dict[B][A] = +C
Enter fullscreen mode Exit fullscreen mode

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

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

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

My algorithm, animated:
Algorithm animation

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

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.

Top comments (0)