Grid Paths

Number of Paths through a grid.

by mslocum

HTML

<h2>Find The Number of Shortest Paths Through a Grid</h2>
<div>
    <label>Width: <input type="number" id="width" value="17"/></label>
    <label>Height: <input type="number" id="height" value="15"/></label>
</div>
<div>
    <button id="recursion">Recursion</button>
    <button id="factoral">factoral</button>
</div>
<div id="log"></div>

JavaScript

$(function() {
    $('#recursion').click(function() {
        var width = parseInt($('#width').val(), 10), 
            height = parseInt($('#height').val(), 10),
            dStart = new Date(),
            iFound,
            dEnd;
        iFound = recursion(width, height);
        dEnd = new Date();
        log('Recursion(' + width + ', ' + height + '): ' + iFound + ' time: ' + (dEnd - dStart));
    });
    $('#factoral').click(function(e) {
        var width = parseInt($('#width').val(), 10), 
            height = parseInt($('#height').val(), 10),
            dStart = new Date(),
            iFound,
            dEnd;
        iFound = factoral(width, height);
        dEnd = new Date();
        log('Factoral: ' + iFound + ' time: ' + (dEnd - dStart));
    });
});

function log(strLog) {
    $('#log').append(strLog + '<br/>');
}

function recursion(width, height) {
    if (width == 1 && height == 1) {
        return 1;
    }
    var count = 0;
    if (width > 1) {
        count += recursion(width - 1, height);
    }
    if (height > 1) {
        count += recursion(width, height -1);
    }
    return count;
}

/**
  The grid grows identical to Pascal's Triangle. 
  http://en.wikipedia.org/wiki/Pascal%27s_triangle
  
  It can also be thought of as a combination equation,
  where it always takes width-1 steps to move to the vertical
  edge and height-1 to move to the destination. These can be
  done in any order. Therefore, it fits the combination 
  equation nCr. For example: a 4 x 3 grid would take 3 steps
  and 2 steps (5 steps total). So there are 
  5 pick 3 (or 5 pick 2) combinations.
*/
function factoral(width, height) {
    var n = width - 1 + height - 1,
        r = width - 1;
    // Lets do nCr 
    return Math.round(fact(n) / (fact(r) * fact(n - r)));
}

function fact(num) {
    var fact = num
    while (--num) {
        fact *= num;
    }
    return fact;
}