Advent of Code 2015 Day 9
Part 1
- A walk in the park
- 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 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.
Top comments (0)