cheapest_combo.js

const _ = require('lodash')
const Graph = require('node-dijkstra')


/*

problem: 
  we want to paint a series of buildings
  each building can be one of 3 colors (red, green, blue)
  each building has its own cost per color
  two neighbor houses can't have the same color
  find the cheapest way to paint the street


proposed solution:
  build a graph where each house has 3 nodes, one per color
  for each building Bn -> exists BRn BGn BBn 
  such as 
    BRn -> connected to BGn+1 and BBn+1
    BGn -> connected to BRn+1 and BBn+1
    BBn -> connected to BRn+1 and BGn+1
  and the weight of each edge is the cost of the color for building n

  then find shortest path from first house to last house
*/

const mapRange = (n, f)  => _.range(n).reduce((acc, i) => { acc.push(f(i)); return acc }, [])

function link(graph, src, dst, weight) {
  if (!graph[src]) {
    graph[src] = []
  }

  graph[src].push([dst, weight])
}

function main() {
  const n = 10
  const houses = mapRange(n, () => mapRange(3, () => _.random(1, 100)))
  const graph = {}
  const nodeToWeight = {}

  for (let i = 0; i < houses.length; i++) {
    const h = houses[i]

    nodeToWeight['r' + i] = h[0]
    nodeToWeight['g' + i] = h[1]
    nodeToWeight['b' + i] = h[2]

    if (i == 0) {

      link(graph, 'start', 'r0', h[0])
      link(graph, 'start', 'g0', h[1])
      link(graph, 'start', 'b0', h[2])

    } else if (i < houses.length) {

      link(graph, 'r' + (i-1), 'g' + i, h[1])
      link(graph, 'r' + (i-1), 'b' + i, h[2])

      link(graph, 'g' + (i-1), 'r' + i, h[0])
      link(graph, 'g' + (i-1), 'b' + i, h[2])

      link(graph, 'b' + (i-1), 'r' + i, h[0])
      link(graph, 'b' + (i-1), 'g' + i, h[1])
    } 
  }

  link(graph, 'r' + (n-1), 'end', 1)
  link(graph, 'g' + (n-1), 'end', 1)
  link(graph, 'b' + (n-1), 'end', 1)

  const route = new Graph()

  for (const node of Object.keys(graph)) {
    const edges = {}
    for (const edge of graph[node]) {
      edges[edge[0]] = edge[1]
    }

    route.addNode(node, edges)
  }

  console.log(houses)
  console.log(route.path('start', 'end'))
}

main()