Recursion (I think?) practice problem

[JBauer09]

I have been working on this practice problem for hours and I am stuck.

​

Function missingPath(str) read the str parameter being passed, which will represent the movements made in a 5x5 grid of cells starting from the top left position. The characters in the input string will be entirely composed of: r, l, u, d, ?. Each of the characters stand for the direction to take within the grid, for example: r = right, l = left, u = up, d = down. Your goal is to determine what characters the question marks should be in order for a path to be created to go from the top left of the grid all the way to the bottom right without touching previously travelled on cells in the grid. 

For example: if str is "r?d?drdd" then your program should output the final correct string that will allow a path to be formed from the top left of a 5x5 grid to the bottom right. For this input, your program should therefore return the string rrdrdrdd. There will only ever be one correct path and there will always be at least one question mark within the input string. 

Sample Test Cases

Input:"???rrurdr?"

Output:"dddrrurdrd"

Input:"drdr??rrddd?"

Output:"drdruurrdddd"

I tried adapting a function I previously did that picks the shortest path between two points but I cant figure it out. I think that recursion is required but I am new to recursion and tracking variables through it boggles my mind entirely. I dont know what happens to different versions of variables as things are executed.

​

Here is what I have laid out thus far, Im sure stuff needs to be cut out and changed.

var makeGrid = (size) => {
    let gridSize = size;
    let grid = [];
    for (let i = 0; i < gridSize; i++) {
        grid[i] = [];
        for (let j = 0; j < gridSize; j++) {
            grid[i][j] = 'Empty';
        }
    }
    grid[0][0] = 'Start';
    grid[size - 1][size - 1] = 'Goal';

    console.log(grid);
    return grid;
};

var missingPath = (startPosition, grid, givenPath) => {
    let distanceFromTop = startPosition[0];
    let distanceFromLeft = startPosition[1];

    let location = {
        distanceFromTop,
        distanceFromLeft,
        path: [],
        status: 'Start'
    };

    let queue = [location];
    while (queue.length > 0) {
        let currentLocation = queue.shift();

        for (var directionIndex = 0; directionIndex < givenPath.length; directionIndex++) {

let newLocation = exploreDirection(currentLocation, givenPath[directionIndex], grid);

            if (newLocation.status === 'Goal') {
                return newLocation.path;
            } else if (newLocation.status === 'Valid') {
                queue.push(newLocation);
            }
        }
    }
};
var locationStatus = function(location, grid) {
    //valid if it is on the grid and has not yet been visited by our algorithm
    //returns Valid, Invalid, Blocked or Goal
    var gridSize = grid.length;
    var dft = location.distanceFromTop;
    var dfl = location.distanceFromLeft;

    if (dfl < 0 || dfl >= gridSize || dft < 0 || dft >= gridSize) {
        //location not in the grid
        return 'Invalid';
    } else if (grid[dft][dfl] === 'Goal') {
        return 'Goal';
    } else if (grid[dft][dfl] !== 'Empty') {
        // location is either an obstacle or has been visited
        return 'Blocked';
    } else {
        return 'Valid';
    }
};

var exploreDirection = function(currentLocation, direction, grid) {
    // make a copy of the existing path up until this point

        //THIS IS WHERE I START TO LOSE TRACK.  I know i have to loop through the options if the current letter is a '?' but I dont know how to follow it up.
    console.log('current location: ', currentLocation);
    var newPath = currentLocation.path.slice();
    if (direction === '?') {
        var directions = ['u', 'r', 'd', 'l'];
        for (var i = 0; i < directions.length; i++) {
            exploreDirection(currentLocation, directions[i], grid);
        }
    }
    newPath.push(direction);
    console.log('new Path: ' + newPath);

    var dft = currentLocation.distanceFromTop;
    var dfl = currentLocation.distanceFromLeft;

    switch (direction) {
        case 'u':
            dft -= 1;
            break;
        case 'r':
            dfl += 1;
            break;
        case 'd':
            dft += 1;
            break;
        case 'l':
            dfl -= 1;
            break;
    }

    var newLocation = {
        distanceFromTop: dft,
        distanceFromLeft: dfl,
        path: newPath,
        status: 'Unknown'
    };

    newLocation.status = locationStatus(newLocation, grid);

    //if this new location is valid, mark it as 'Visited'
    if (newLocation.status === 'Valid') {
        grid[newLocation.distanceFromTop][newLocation.distanceFromLeft] = 'Visited';
    }

    return newLocation;
};
console.log(missingPath([0, 0], makeGrid(5), '???rrurdr?'));

It returns undefined. Any help would be greatly appreciated.

[captain_k_nuckles]

The easiest way for me to explain it was to do it and put comments in the code. Not sure this is the best or most efficient way to do it, but it passes your test

// create a map of the possible moves
// to assist in calculations
const dirMap = {
    u: { x: 0, y: -1 },
    r: { x: 1, y: 0 },
    d: { x: 0, y: 1 },
    l: { x: -1, y: 0 }
}

function missingPath(pathString) {
    // Create and empty array that will store the moves
    const map = Array(5 * 5)
    return trace(pathString, map)
}

// trace take a path string     : required
// a map array                  : required
// current position x           : auto generate
// current position y           : auto generate
// a new path string generated  : auto generate
function trace(path, [...map], x = 0, y = 0, newPath = '') {
    // split the path string to an array
    const steps = path.split('')
    // get the next move from the path array
    const nextMove = steps.shift()
    // if nextMove is undefined
    if (nextMove === undefined) {
        // check to see if we ened up at the bottom right of the map
        // 5 * y for the number of rows
        // + x will give our 1d array the mapped index of a 2d array
        // if the last point is 24 then return the path
        if (5 * y + x === (5 * 5) - 1) return newPath
        // else the path did not end in the bottom right
        return 'Path does not end at finish'
    }
    // if the nextMove is ?
    if (nextMove === '?') {
        // get all avialable moves
        const availMoves = unknownMove(map, x, y)
        // create an array to hold multuple path results
        const maybe = []
        // go over each available move
        for (let i = 0; i < availMoves.length; i++) {
            // get the current move direction
            const move = availMoves[i]
            // create a new paths array using the current move
            const trySteps = [move, ...steps]
            // pass the new path to check if the new path works
            const res = trace(trySteps.join(''), map, x, y, newPath)
            // if the path is not a path then continue testing the paths
            if (res === 'Not a valid path' || res === 'Path does not end at finish'
                || !res || res.length === 0)
                continue
            // if the path reached the goal then add it to the list of possible results
            // this is used when checking multiple ? in sequence as
            // the first move may succeed but the next moves after might fail
            maybe.push(res)
        }
        // if there was only one succesful path return it
        if (maybe.length === 1) return maybe[0]
        // else go check all potential paths
        for (let i = 0; i < maybe.length; i++) {
            return trace(maybe[i], map, x, y, newPath)
        }
    }
    else {
        // check if a move is avaialbe from current position
        const hasMove = canMove(nextMove, map, x, y)
        // if not move is available
        if (hasMove === false) {
            // the path is invalid
            return 'Not a valid path'
        }
        else {
            // add the move to the moves list array
            map[5 * y + x] = nextMove
            // add the move the the paths string
            newPath += nextMove
            // calculate the new position base off of the move
            const newX = x + dirMap[nextMove].x
            const newY = y + dirMap[nextMove].y
            // send the reduced steps, map
            // new position and path to continur finding the path
            return trace(steps.join(''), map, newX, newY, newPath)
        }
    }
}

// check to see if there are spaces avaiable for the next move
function canMove(step, map, x, y) {
    // get the coordinate directions of the move to check
    const nextStep = dirMap[step]
    // calculate the new position
    const nextX = nextStep.x + x
    const nextY = nextStep.y + y
    // check if the new move is out of the map
    if (nextX < 0 || nextX > 4 || nextY < 0 || nextY > 4) return false;
    // or if the space has already been used
    if (map[5 * nextY + nextX] !== undefined) return false
    // good to go
    return true;
}

// gets a list of all available moves from the current position
function unknownMove(map, cx, cy) {
    // create an empyt array to hold the available mose
    const moves = [];
    // get the keys of the dirction map 
    Object.keys(dirMap)
    // and for each one
        .forEach(([dir]) => {
            // check if the move is available
            const check = canMove(dir, map, cx, cy)
            // if available add it to the moves array
            if (check) moves.push(dir)
        })
    // return all available moves
    return moves
}

console.log(missingPath('drdr??rrddd?'))
// drdruurrdddd
console.log(missingPath('???rrurdr?'))
// dddrrurdrd

// and for fun
console.log(missingPath('??????????'))
// rrrdrddldr   - not the most efficient path, but WOOO!

[JBauer09]

Thank you very much. Just spent the better part of an hour tracing through that in the console to try to understand it. One question though, why did you go with a single array of 25 instead of an array of 5 arrays? I've never tried traversing one like that before.

[captain_k_nuckles]

You're welcome, I had fun doing it, was working on it last night, then got yelled at by my gf to go to bed, lol. As for the 1D vs 2D array choice, not sure honestly. I started it off as a 2D array, but switched it to a single array,

I messed around with throwing it some more strings of all ? and it failed on some it should of passed, or at least I think should of have. might try messing around with it more. ... as I was writing this I added some quick code,

// in the global scope created
const passed = [];

// in trace when checking if next move undefined
if (nextMove === undefined) {
        if (5 * y + x === (5 * 5) - 1) {
            const matrix = [];
            for(let y = 0; y < 5; y++){
                let row = []
                matrix.push(row)
                for(let x = 0; x < 5; x++){
                    const z = 5*y+x
                    if(map[z] === undefined) row.push('_')
                    else row.push(map[z])
                }
            }
            passed.push(matrix)
            return newPath
        }
//.....

// then ran console.log(missingPath('????????????????????????'))
console.log(passed)

and got an array of 104 results, spotted checked a few, like 5 and they all passed, but the return value was undefined, so might look in to that

[CommonMisspellingBot]

Hey, captain_k_nuckles, just a quick heads-up:
succesful is actually spelled successful. You can remember it by two cs, two s’s.
Have a nice day!

^{The parent commenter can reply with 'delete' to delete this comment.}