-
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!"); }
Created at: 2017/04/01 23:59; Updated at: 2017/04/02 17:55
The question is resolved.
The question is resolved.