Torn Programming Game

CHALLENGE #5

HTML

The shortest path from <span id="from"></span> to <span id="to"></span> is: <span id="path"></span>

JavaScript

var nodes= [
        { _id: 'A', connections: ['B', 'C', 'E'] },
        { _id: 'B', connections: ['A', 'C', 'D', 'E'] },
        { _id: 'C', connections: ['B', 'A', 'E'] },
        { _id: 'D', connections: ['B', 'F', 'G'] },
        { _id: 'E', connections: ['A', 'B', 'C', 'G', 'H'] },
        { _id: 'F', connections: ['D'] },
        { _id: 'G', connections: ['D', 'I', 'E'] },
        { _id: 'H', connections: ['I', 'E'] },
        { _id: 'I', connections: ['G', 'H'] }
    ];

var allPaths= [], traversed= [];
var origin= 'A', to= 'G';

function routes(from, traversed)
{
    var currNode;

    traversed.push(from);

    currNode= _.find(nodes, function(n){ return n._id === from; });

    if (currNode.connections.indexOf(to) > -1)
       allPaths.push(traversed.toString()+','+to);
    else
    {
    _.each(_.difference(currNode.connections, traversed),
           function(n)
           {
               routes(n, traversed);
           });
    }

    traversed.pop();
}

routes(origin, traversed);

document.getElementById('from').innerHTML = origin;
document.getElementById('to').innerHTML = to;
document.getElementById('path').innerHTML = allPaths.sort(function (a, b) { return a.length - b.length; })[0];