Created
March 13, 2018 04:38
-
-
Save MingweiSamuel/d86e1e20fe88150fabd2b081adbe66d0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment