## DEV Community # All in a Single Night

## 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 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)
``````

## Part 2

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

• Two simple changes
• In record time, given my familiarity with the combination-generating library and `reduce()`!