• hangs during Run, same tests pass in Check

Question related to mission Climbing Route

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!");
}