DFS & Hill Climb in NodeJS

dfs-hill-climb.js

/*
    Evan Wieland
    12/7/2022

    Usage:

    $ node dfs-hill-climb.js

    > Would you like to run the tests or supply your own graph (y/n)?
    > n
    >
    > Please supply the weighted graph to be searched, as an adjacency list:
    > a b 8 c 4
    > b c 2 d 7
    > c b 2 d 1
    > d b 1 c 5 g 3
    > g c 4 d 3
    >
    > Please supply the start node:
    > a
    >
    > Please supply the goal node:
    > g
    >
    > DFS: a -> c -> d -> g
    > Hill climb: a -> c -> d -> g

 */

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const dfs = (graph, start, goal) => {
    const stack = [start];
    const visited = new Set();
    const path = [];

    while (stack.length > 0) {
        const node = stack.pop();
        if (node === goal) {
            path.push(node);
            break;
        }
        if (!visited.has(node)) {
            visited.add(node);
            path.push(node);
            for (const child in graph[node]) {
                stack.push(child);
            }
        }
    }

    return pathToString(path);
};

const hillClimb = (graph, start, goal) => {
    const stack = [start];
    const visited = new Set();
    const path = [];

    while (stack.length > 0) {
        const node = stack.pop();
        if (node === goal) {
            path.push(node);
            break;
        }
        if (!visited.has(node)) {
            visited.add(node);
            path.push(node);
            const children = Object.entries(graph[node]);

            // Find if children contains goal
            const goalChild = children.find(([child]) => child === goal);
            if (goalChild) {
                path.push(goal);
                break;
            }

            // Sort children by weight
            const sorted = children.sort((a, b) => a[1] - b[1]);

            const child = sorted[0][0];
            stack.push(child);
        }
    }

    return pathToString(path);
};

const pathToString = (path) => {
    return path.join(' -> ');
};

const runTests = () => {
    const graph = {
        a: {b: 8, c: 4},
        b: {c: 2, d: 7},
        c: {b: 2, d: 1},
        d: {b: 1, c: 5, g: 3},
        g: {c: 4, d: 3},
    };

    const testCases = [
        ['a', 'g'],
        ['a', 'b'],
        ['b', 'g'],
        ['b', 'c'],
        ['c', 'g'],
        ['c', 'b'],
        ['d', 'c'],
        ['d', 'b'],
    ];

    testCases.forEach(([start, goal]) => {
        console.log('Start', start, ', Goal', goal);
        console.log('DFS:', dfs(graph, start, goal));
        console.log('Hill climb:', hillClimb(graph, start, goal), '\n');
    });

    rl.close();
};

const runUserInput = () => {
    const graph = {};

    console.log('Please supply the weighted graph to be searched, as an adjacency list:');
    rl.on('line', (input) => {
        input = input.trim();
        if (input === '') {
            rl.question('Please supply the start node:\n', (start) => {
                rl.question('\nPlease supply the goal node:\n', (goal) => {
                    console.log('\nDFS:', dfs(graph, start, goal));
                    console.log('Hill climb:', hillClimb(graph, start, goal));
                    rl.close();
                });
            });
        } else {
            const [node, ...adj] = input.split(' ');
            graph[node] = {};
            for (let i = 0; i < adj.length; i += 2) {
                graph[node][adj[i]] = parseInt(adj[i + 1]);
            }
        }
    });
};

rl.question('Would you like to run the tests or supply your own graph (y/n)?', (input) => {
    if (input === 'y') {
        runTests();
    } else {
        runUserInput();
    }
});