09.md

Day 09

Part 1

What is the distance of the shortest route?

const input = `London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141`

const roads = input.split('\n').reduce((roads, road) => {
  const [from, to, distance] = road.split(/ to | = /)

  roads.push(
    {
      from,
      to,
      distance: Number(distance),
    },
    {
      from: to,
      to: from,
      distance: Number(distance),
    }
  )

  return roads
}, [])

const getNextRoutes = (currentRoute) => {
  const previous = currentRoute.stops[currentRoute.stops.length - 1]

  const destinations = roads
    .filter((road) => road.from === previous)
    // Prevent loops:
    .filter((road) => !currentRoute.stops.includes(road.to))

  if (destinations.length === 0) return currentRoute

  const newRoutes = destinations.map((road) => ({
    distance: currentRoute.distance + road.distance,
    stops: currentRoute.stops.concat(road.to),
  }))

  return newRoutes.flatMap(getNextRoutes)
}

const startingPoints = [...new Set(roads.map((road) => road.from))]
const initialRoutes = startingPoints.map((startingPoint) => ({
  distance: 0,
  stops: [startingPoint],
}))
const finalRoutes = initialRoutes.flatMap(getNextRoutes)
const distances = finalRoutes.map((route) => route.distance)

const part1 = Math.min(...distances)
console.log('Part 1:', part1)

Flems link in Part 2.

Part 2

What is the distance of the longest route?

const part2 = Math.max(...distances)
console.log('Part 2:', part2)

Try out the final code on flems.io

What did I learn?

Nothing, but this puzzle was quite challenging, like most puzzles requiring recursive thinking.

It didn't even help that I had solved a very similar puzzle ~7 months ago. I didn't take a look at it before I had solved this puzzle because I didn't want any spoilers from the past me. Turns out that the past me is more clever than the current me because this new solution was initially more complex and less clear than the old solution. :man_shrugging: (I refactored this new solution to be more simpler before publishing it here, i.e. here you are seeing the simpler version inspired by the old solution.)