Discussion on: Advent of Code 2019 Solution Megathread - Day 6: Universal Orbit Map

View post
Javascript solution w/ Graph implementation
Map.prototype.reduce = function(reducer, initialState) {
  let state = initialState
  for (entry of this.entries()) {
    state = reducer(state, entry)
  }
  return state
}

Map.prototype.map = function(fn) {
  return this.reduce((p, [key, value]) => {
    p.set(key, fn(value))
    return p
  }, new Map())
}

class Graph {
  constructor() {
    this.adjacencyList = new Map()
  }

  addDirectedEdge(v, w) {
    if (!this.adjacencyList.get(v)) this.adjacencyList.set(v, [])
    if (!this.adjacencyList.get(w)) this.adjacencyList.set(w, [])
    this.adjacencyList.get(v).push(w)
  }
  addEdge(v, w) {
    if (!this.adjacencyList.get(v)) this.adjacencyList.set(v, [])
    if (!this.adjacencyList.get(w)) this.adjacencyList.set(w, [])
    this.adjacencyList.get(v).push(w)
    this.adjacencyList.get(w).push(v)
  }
  toString() {
    return this.adjacencyList.reduce(
      (p, [vertex, neighbors]) =>
        p + '\n' + `${vertex} -> ${neighbors.join(' ')}`
    )
  }

  dfs(startingNode, reducer, initialState) {
    const visited = this.adjacencyList.map(() => false)
    return this.DFSUtil(startingNode, visited, reducer, initialState)
  }

  DFSUtil(vert, visited, reducer, state) {
    state = reducer(state, vert)
    visited.set(vert, true)

    const neighbors = this.adjacencyList.get(vert)

    for (const neighbor of neighbors) {
      if (!visited.get(neighbor))
        state = this.DFSUtil(neighbor, visited, reducer, state)
    }

    return state
  }

  bfs(from, to, reducer, state) {
    const queue = []
    const visited = this.adjacencyList.map(() => false)

    queue.push(from)
    while (queue.length) {
      const vertex = queue.shift()
      const neighbors = this.adjacencyList.get(vertex)
      for (const neighbor of neighbors) {
        if (!visited.get(neighbor)) {
          visited.set(neighbor, true)
          state = reducer(state, neighbor, vertex)
          queue.push(neighbor)

          if (neighbor === to) {
            return state
          }
        }
      }
    }
    return false
  }

  shortestPath(from, to) {
    const initialState = this.adjacencyList.map(() => ({
      distance: Infinity,
      predecessor: null
    }))
    initialState.get(from).distance = 0

    const result = this.bfs(
      from,
      to,
      (p, v, vertex) => {
        const val = p.get(v)
        val.distance = p.get(vertex).distance + 1
        val.predecessor = vertex
        return p
      },
      initialState
    )

    return result.get(to).distance
  }

  countIndirectOrbits() {
    return this.adjacencyList.reduce(
      (sum, [key]) => sum + this.dfs(key, (a, b) => a + 1, -1),
      0
    )
  }
}

const input = require('fs')
  .readFileSync(0)
  .toString()

const map = input.split('\n')
const orbits = map.map(x => x.split(')'))

const graph = new Graph()
const directedGraph = new Graph()

orbits.forEach(([orbitee, orbiter]) => {
  graph.addEdge(orbiter, orbitee)
  directedGraph.addDirectedEdge(orbiter, orbitee)
})

console.log(directedGraph.toString())
console.log(directedGraph.countIndirectOrbits())
console.log(graph.shortestPath('YOU', 'SAN') - 2)