Diagonal traverse

diagonal-traverse.js

// Initial test data
var data = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
];

// First time this function is executed with just the input argument
// The input argument always has the test data and it doesn't change
// 
// The x and y are the current location coordinates
// 
// The acc is the array where we accumulate the result
function findDiagonalOrder(input, x, y, acc) {

    // One of the autmated tests provided an empty array as input
    // had to add this check for that.
    // Basically if the test data is an empty array, don't do
    // anything and just return the empty string as the result.
    if (!input.length) return [];

    // When x, y and acc are not defined as arguments,
    // let's set some default values.
    // 
    // For example let's set "x = x" when x is defined,
    // otherwise let's set "x = 0".
    // 
    // Default for x and y is 0, because that's the starting point.
    // 
    // Also when the accumulator array isn't defined, we can't push
    // values to it, so we set it to an empty array.
    x   = x   || 0;
    y   = y   || 0;
    acc = acc || [];

    // This is a map of current direction to next direction.
    // If you take a look at the provided example image, it shows
    // how you should find the next number.
    // 
    // Usually you traverse the matrix in a diagonal line,
    // but when you reach the edge, you need to pick a new direction.
    // 
    // The key in the map is the initial direction - dx:dy.
    // Here are all the possible directions:
    // 
    //     [-1, -1]   [ 0, -1]   [ 1, -1]   |  In this direction
    //                                      |  Y increases
    //     [-1,  0]   [ 0,  0]   [ 1,  0]   |
    //                                      |
    //     [-1,  1]   [ 0,  1]   [ 1,  1]   ▼
    //     
    //     -------------------------------▶
    //     And in this direction
    //     X increases
    //
    // But when moving diagonally upwards, we need to check only 2.
    // And when moving downwards, we need to check the other 2.
    // So in total only 4 locations to check.
    // 
    // Let's take the example data:
    //     [1, 2, 3]
    //     [4, 5, 6]
    //     [7, 8, 9]
    //     
    // When you're on number 1, the direction is to north-east or 1:-1.
    // The we want to continue from number 2,
    // so the direction needs to be just east of number 1 or direction 1:0.
    // 
    // Another example, when you're on number 3, also moving upwards,
    // so the direction is 1:-1 again, so we try east again or 1:0.
    // But there's actually nothing to the east of number 3,
    // so in the FOR loop below, we actually retry.
    // If the direction now is 1:1, we check if maybe the next direction
    // should be at south instead of east - 1:0 -> [0, 1] and
    // that's where we find the next number, number 6.
    // 
    // The other two directions, -1:1 and 0:1 follow the same logic,
    // but used when going downward in the matrix.
    const nextDirMap = {
        '1:-1': [1, 0],
        '1:0':  [0, 1],
        '-1:1': [0, 1],
        '0:1':  [1, 0]
    }

    // Here we just push the number to the result array
    // and we use the coordinates form the function arguments.
    // Initially we set the coordinates to 0, so first entry would
    // always be what ever is at coordinates 0:0.
    acc.push(input[y][x]);

    // Here we define the movement direction
    // If the X + Y coordinate give an odd number,
    // then the direction is diagonally upward.
    // Because the movement is diagonally up or down,
    // we can just find the X direction first and derive the Y
    // direction by switching it's sign.
    // Unless we are at a turning point, the direction is always
    // either upward with 1:-1 or downward -1:1.
    let dx = (x + y) % 2 ? -1 : 1;
    let dy = dx * -1;

    // Here we try guess the next X and Y position and check
    // if something exists there.
    // We have 3 directions to test so we run it in a loop.
    // 
    // When going upwards the loop checks if we find something if we...
    // 1. Continue diagonally upward?
    // 2. Go east?
    // 3. Go south?
    // 
    // When going downward the loop checks...
    // 1. Continue diagonally downward?
    // 2. Go south?
    // 3. Go east?
    for (var i = 0; i < 3; i++) {

        // The next position is current position + movement direction
        const nextX = x + dx;
        const nextY = y + dy;

        // Here we check if we guessed the next position right
        if (input[nextY] && input[nextY][nextX] != null) {

            // If we guessed it right, we execute the function again
            // Now the nextX and nextY will be given as coordinates
            // and when the function runs the code...
            //    acc.push(input[y][x])
            // ...will store the value as result.
            // 
            // We also pass on the accumulator array which holds
            // all the previously found numbers.
            // 
            // What ever the function returns will be returned.
            return findDiagonalOrder(input, nextX, nextY, acc);
        }

        // If we didn't find the position for the next number
        // we still have a few tries, so based on the current
        // direction, we replace the current direction with
        // a new one from the nextDirMap object.
        const nextDir = nextDirMap[`${dx}:${dy}`];
        dx = nextDir[0];
        dy = nextDir[1];
    }

    // If we didn't return inside the for loop and we arrived here
    // that means there is no where else to go in the matrix,
    // so we finally return the accumulated result array.
    // 
    // So the call stack looks something like this:
    //   findDiagonalOrder(input)
    //    findDiagonalOrder(input, 0, 0, [])
    //     findDiagonalOrder(input, 1, 0, [1])
    //      findDiagonalOrder(input, 0, 1, [1, 2])
    //       findDiagonalOrder(input, 0, 2, [1, 2, 4])
    //        ...
    //         ...
    //          ... until eventually the function doesn't
    //           ... return the result of itself anymore
    //            ...
    //             [1, 2, 4, 7, 5, 3, 6, 8, 9]
    //    
    return acc;
};

console.log(findDiagonalOrder(data));