Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dynamic Programming solution in Clear category for [old] Fast Train by Sim0000
"use strict";
function fastTrain(numbers) {
let limit = [];
for(let n of numbers){
limit = limit.concat(Array(n[0]).fill(n[1]));
}
const goal = limit.length;
let q = [[1, 1, 1]];
let table = {};
while(q.length){
const [pos, speed, step] = q.shift();
if(pos == goal && speed == 1) return step; // found
// make next position and speed
for(let d of [-1, 0, 1]){
const speed_next = speed + d;
const pos_next = pos + speed_next;
if(speed_next <= 0) continue;
if(pos_next < 0 || goal < pos_next) continue;
if(table[[pos_next, speed_next]]) continue; // already search
if(!limit.slice(pos, pos_next).every(v => speed_next <= v)) continue;
table[[pos_next, speed_next]] = step + 1;
q.push([pos_next, speed_next, step + 1]);
}
}
// not found
}
// dynamic programming
var assert = require('assert');
if (!global.is_checking) {
console.log('Example:');
console.log(fastTrain([[4, 3]]));
assert.equal(fastTrain([[4, 3]]), 3);
assert.equal(fastTrain([[9, 10]]), 5);
assert.equal(fastTrain([[5, 5], [4, 2]]), 6);
console.log('"Run" is good. How is "Check"?');
}
Jan. 15, 2019