-
hangs during Run, same tests pass in Check
This is weird. My code hangs for > 30 minutes in Extra Test 1 when I click Check. However, if I copy all the extra tests (from git) into the global.is_checking section and click Run, they all pass in < 1 minute.
Is there something different about the Check environment vs the Run environment that would cause this? I don't have any global vars.
My code, including the extra assertion:
"use strict";
const OFFSETS = [[0,1],[0,-1],[1,0],[-1,0]]
function climbingRoute(map){
//build up adjacency map of neighbors
let neighbors = new OMap()
let [nr, nc] = [map.length, map[0].length]
let source = [0,0]
let dest = [nr-1,nc-1]
for (let r=0;r<nr;r++) {
for (let c=0;c<nc;c++) {
let v = parseInt(map[r][c])
for (let o of OFFSETS) {
let [ro, co] = [r+o[0], c+o[1]]
if (0<=ro&&ro<nr && 0<=co&&co<nc) {
let vo = parseInt(map[ro][co])
if (Math.abs(v-vo)<=1) {
if (neighbors.has([r,c])) {
neighbors.get([r,c]).add([ro,co])
} else {
neighbors.set([r,c], new OSet([ro,co]))
}
}
}
}
}
}
//build up mountains
let mountains = []
for (let r=0;r<nr;r++) {
for (let c=0;c<nc;c++) {
let v = parseInt(map[r][c])
if (v>0 && !mountains.some(m=>m.has([r,c]))) {
let m = new OSet()
grow(r,c,map,m,new OSet())
mountains.push(m)
}
}
}
//ind set of tops from mountains
let tops = []
for (let m of mountains) {
m=[...m]
if (m.length>1) {
m.sort((x,y)=> map[x[0]][x[1]]-map[y[0]][y[1]])
tops.push(m[m.length-1])
}
}
//find min distances between source, tops, and dest
let dist = new OMap()
dist.set(source, dijkstra(neighbors, source))
for (let t of tops) {
dist.set(t, dijkstra(neighbors, t))
}
//loop through all possible orders of tops, and find the minimum total
let min = Infinity
for (let p of permutations(tops)) {
let t = totaldist(dist, source, p, dest)
if (t<min) min=t
}
return min
}
//build up mountain recursively
function grow(r,c, map, mountain, visited) {
if (visited.has([r,c])) return
visited.add([r,c])
let v = parseInt(map[r][c])
if (v>0) {
mountain.add([r,c])
let [nr, nc] = [map.length, map[0].length]
for (let o of OFFSETS) {
let [ro, co] = [r+o[0], c+o[1]]
if (0<=ro&&ro<nr && 0<=co&&co<nc) {
grow(ro,co,map,mountain,visited)
}
}
}
}
//find distance from source to all locations, using dijkstra
function dijkstra(neighbors, source) {
let q = [...neighbors.keys()]
let dist = new OMap()
for (let n of q) {
dist.set(n, Infinity)
}
dist.set(source, 0)
while (q.length > 0) {
q.sort((x,y)=>dist.get(x)-dist.get(y))
let u=q.shift()
for (let v of neighbors.get(u)) {
let alt = dist.get(u) + 1
if (alt < dist.get(v)) {
dist.set(v, alt)
}
}
}
return dist
}
//total dist from source, through path, to dest
function totaldist(dist, source, path, dest) {
if (path.length==0) {
return dist.get(source).get(dest)
}
let d = dist.get(source).get(path[0])
for (let i=0; i<path.length-1; i++) {
d+=dist.get(path[i]).get(path[i+1])
}
d+=dist.get(path[path.length-1]).get(dest)
return d
}
function permutations(array) {
if ((array.length)<=1) return [array]
let result = []
for (let i=0; i<array.length; i++) {
let head=array[i]
let tail=array.slice(0,i).concat(array.slice(i+1))
for (let p of permutations(tail)) {
result.push([head].concat(p))
}
}
return result
}
//set with items that are unique based on toString()
class OSet {
constructor() {
this.map = new Map();
for (let a of arguments) {
this.add(a)
}
this[Symbol.iterator] = this.values;
}
add(item) {
this.map.set(item.toString(), item);
}
has(item) {
return this.map.has(item.toString());
}
values() {
return this.map.values();
}
}
//map with keys that are unique based on toString()
class OMap {
constructor() {
this.keyMap = new Map();
this.valMap = new Map();
this[Symbol.iterator] = this.keys;
}
set(key, value) {
this.keyMap.set(key.toString(), key);
this.valMap.set(key.toString(), value);
}
get(key) {
return this.valMap.get(key.toString());
}
has(key) {
return this.keyMap.has(key.toString());
}
keys(key) {
return this.keyMap.values();
}
values() {
return this.valMap.values();
}
}
let assert = require('assert');
if (!global.is_checking) {
assert.equal(climbingRoute([
'000',
'210',
'000']), 6, 'basic')
assert.equal(climbingRoute([
'00000',
'05670',
'04980',
'03210',
'00000']), 26, 'spiral')
assert.equal(climbingRoute([
'000000001',
'222322222',
'100000000']), 26, 'bridge')
assert.equal(climbingRoute([
'000000002110',
'011100002310',
'012100002220',
'011100000000']), 26, 'two top')
assert.equal(climbingRoute([
'000000120000',
'001002432100',
'012111211000',
'001000000000']), 16, 'one top')
assert.equal(climbingRoute([
'00000000111111100',
'00000000122222100',
'00000000123332100',
'00000000123432100',
'00000000123332100',
'00000000122222100',
'00000000111111100',
'00011111000000000',
'00012221000000000',
'00012321000000000',
'00012221000000012',
'00011111000000000',
'11100000000000000',
'12100000000000000',
'11100000000000000']), 52, 'pyramids')
console.log("regular tests done");
assert.equal(climbingRoute(['0000000000000',
'0232021202320',
'0222022202220',
'0212023202120',
'0000000000000',
'0232021202320',
'0222022202220',
'0212023202120',
'0000000000000',
'0232021202320',
'0222022202220',
'0212023202120',
'0000000000000']), 110, 'e1')
assert.equal(climbingRoute(['000002000000',
'000001000000',
'000000000000',
'000001002220',
'000001012320',
'000001002220',
'000001000000',
'000001000000',
'000001000000',
'000001022220',
'000001120320',
'000001120020',
'000001022220',
'000001000000',
'000001000000']), 43, 'e2')
assert.equal(climbingRoute(['01220000122332332',
'12343000023443211',
'11232100000232100',
'11110000001223121',
'11011002223333443',
'21002023334454564',
'10000234556678752',
'10000046778898531',
'10000004555677642',
'11000000001234532',
'22112211000123421',
'11234432210002321',
'22345443321012210',
'33456554332111210']), 37, 'e3')
assert.equal(climbingRoute(['01020',
'00304',
'05060',
'00708',
'00000']), 8, 'e4')
console.log("Coding complete? Click 'Check' to review your tests and earn cool rewards!");
}
