some messy tinkering around "optimizing" a graph-traversal question found on stack overflow by caching sub-paths

rook traversal.js

"use strict";

function memoize(f) {
    const cache = {};
    const ret = function (a) {
        return (a in cache) ?
                cache[a] :
                (cache[a] = f(a));
    }
    ret.cache = cache; // expose cache for debugging
    return ret;
}

const grid = [
[1,2,3],
[4,5,6],
[7,8,9]
];

const neighborhood = memoize(function (src) {
    const row = grid.find(r=>r.includes(src));
    const col = row.indexOf(src);

    const horizNeighborhood = row;
    const vertNeighborhood = grid.map(r=>r[col]);
    
    return horizNeighborhood.concat(vertNeighborhood).filter(e=>e!=src);;
});

// pre-populate cache
for(let i = 1; i <= 9; ++i) void neighborhood(i);

function walkAll(maxLen,/*startAt=1,*/ver=1) {
    const startAt = 1;

    function walk(loc,history="",maxHist=maxLen){
        history += ""+loc;
        if(history.length == maxHist)
            return history;
        return neighborhood(loc).flatMap(n=>walk(n,history))
    }

    // consistently goes 1 layer too deep, never actually uses cache
    const walk2_cache = {};
    const walk2_cache_length = 2;
    function walk2(loc,history="",maxHist=maxLen) {
        history += ""+loc;
        if(history.length >= maxHist)
            return history.substr(0,maxHist);
        if(loc in walk2_cache)
            return walk2_cache[loc].map(ce=>history+ce); // need to recurse here too!

        const newSubpath = neighborhood(loc).flatMap(n=>walk(n,"",walk2_cache_length));
        walk2_cache[loc] = newSubpath;
        return newSubpath.map(sp=>history+sp);
    }

    // congruent with v1
    function walk3(loc,history="",lifetime=maxLen-1) {
        history += ""+loc;
        if(lifetime <= 0)
            return history;
        return neighborhood(loc).flatMap(n=>walk3(n,history,lifetime-1))
    }

    const walk4_cache = {};
//     const walk4_cache_length = 1;
    const walk4_cache_length = Math.floor(maxLen/3); // len/2 might be better?
    function walk4(loc,history="",lifetime=maxLen-1) {
        history += ""+loc;
        if(lifetime == 0)
            return history;
        if(lifetime < 0)
            //throw new Error(`lifetime ${lifetime} < 0 with ${JSON.stringify({loc,history})}`);
            return []; // should work once passed through flatMap?

        if(lifetime > walk4_cache_length) {
            if(loc in walk4_cache)
                return walk4_cache[loc].flatMap(ce=> {
                    const newHist = history + (ce.slice(0,-1));
                    const newLoc = ce.slice(-1);
                    return walk4(newLoc,newHist,lifetime-(1+walk4_cache_length)); //maybe off-by-one?
                });
            // else populate cache
            const newSubpath = neighborhood(loc).flatMap(n=>walk4(n,"",walk4_cache_length))
            walk4_cache[loc] = newSubpath;
            // lazy impl: re-call self
            return walk4(loc,history.slice(0,-1),lifetime);
        }
        // lifetime < cache length, fallback to non-cache algo
        return neighborhood(loc).flatMap(n=>walk3(n,history,lifetime-1))
    }

    let ret;
    if (ver == 1)
        ret = walk(startAt);
    else if (ver == 2)
        //return walk2(startAt);
        throw "v2 broken"
    else if (ver == 3)
        ret = walk3(startAt);
    else if (ver == 4)
        ret = walk4(startAt);
    else
        throw "unkown version"
    return ret;
}

function benchmark(test_depth=10){
    let one = `algo 1 at depth ${test_depth}`;
    console.time(one);
    walkAll(test_depth,1);
    console.timeEnd(one);

    let two = `algo 4 at depth ${test_depth}`;
    console.time(two);
    walkAll(test_depth,4);
    console.timeEnd(two);
}