roadtripBroken.js

function test() {
  for (let i = 0; i < 20; i++) {
    let problem = generateProblem();
    console.log('Problem:', problem);
    let ansFast = roadTripFast(...problem);
    let ansKey = roadTripKey(...problem);
    console.log(ansFast, ansKey);
    if (ansFast === ansKey)
      console.log('%cPASS', 'color: #0A0');
    else
      console.log('%cFAIL', 'color: #F00');
  }
}

function testProblem() {
  return [
    [1, 2, 3, 0],
    [0, 1, 2, 7],
    5
  ];
}

function generateProblem() {
  let c = []; // Costs (per gallon).
  let d = []; // Distances.
  let n = 2 + (Math.random() * Math.random() * 1000)|0;
  for (let i = 0; i < n; i++) {
    c[i] = 1 + (Math.random() * 50)|0;
    d[i] = i && (d[i - 1] + 100 + Math.random() * 100)|0;
  }
  let C = -1/0; // Gallons our tank can handle.
  for (let i = 1; i < n; i++) {
    if (d[i] - d[i - 1] > C)
      C = d[i] - d[i - 1];
  }
  C += (C * Math.random() * Math.random())|0; // Make our tank a bit larger, so there aren't always two stations C apart.
  return [ c, d, C ];
}

function roadTripFast(c, d, C) {
  let B = [ 0 ]; // Lowest bill.
  let P = [ 1/0 ]; // Previous station's price.
  let X = [ C ]; // Extra gallons we could've filled.
  let bestPrev = [ -1 ];
  for (let i = 1; i < c.length; i++) {
    let k; /* Best previous station. */
    let bestCost = 1/0;
    for (let j = i - 1; d[i] - d[j] <= C && j >= 0; j--) {
      let dist = d[i] - d[j];
      let cost;
      if (P[j] < c[j]) {
        if (X[j] >= dist)
          cost = dist * P[j];
        else
          cost = X[j] * P[j] + (dist - X[j]) * c[j];
      }
      else
        cost = dist * c[j];
      cost += B[j];
      if (cost <= bestCost) {
        bestCost = cost;
        k = j;
      }
    }
    B[i] = bestCost; // Best cost (from k).
    P[i] = c[k]; // Cost of previous station's gas.
    X[i] = C - (d[i] - d[k]); // Extra gallons we could've filled.
    bestPrev[i] = k;
  }
  // Reconstruct path.
  let path = [ c.length - 1 ];
  let i = bestPrev[c.length - 1];
  while (i >= 0) {
    path.unshift(i);
    let j = bestPrev[i];
    i = j;
  }
  console.log('My path:', path);
  console.log('B', B);
  console.log('P', P);
  console.log('X', X);
  console.log('b', bestPrev);
  // Return.
  return B[c.length - 1];
}

function roadTripKey(c, d, C) {
  let M = [];
  let N;
  let arr = [ M ];
  for (let g = 0; g <= C; g++)
    M[g] = c[0] * g; // Base case (js is zero-indexed).
  for (let i = 1; i < c.length; i++) {
    N = [];
    for (let g = 0; g <= C; g++) {
      N[g] = 1/0; // N is a temporary array.
      for (let h = d[i] - d[i-1]; h <= Math.min(C, d[i] - d[i - 1] + g); h++) {
        let cost = M[h] + (g + d[i] - d[i - 1] - h) * c[i];
        if (cost < N[g])
          N[g] = cost;
      }
    }
    M = arr[i] = N;
    if (i < c.length - 1)
      arr[i + 1] = M;
    // for (let g = 0; g <= C; g++)
    //   M[g] = N[g]
  }
  console.log(arr);
  // return M[0];
  return M[0]
}