The Truck Problem

Question

I am a teacher who was given a problem a few years ago. Every year since I have given it to my advanced students as a bonus assignment, but in ~10 years only 8 solved it, each with a slightly different approach. The problem is as follows:

You have some input (from stdin), in the following format (the //comments are not included in the input):

6      //Route Begin
1 2    //Route data...
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0    //Route end
4      //Route Begin
2 3    //Route Data...
3 4
5 1
1 6
7 8
8 9
2 5
5 7
3 1
1 8
4 6
6 9
0 0    //Route end
// continued...

The input begins with the destination, an integer. It is followed by a 'map' of all streets in the city. Each line represents a connection, so you can get from street 1 to street 2, and vice-versa. On every rout you start at street 1, then work your way to your destination.

The objective: List all possible routes, and tell the user the shortest one (least amount of street changes). Also, the code beads to be human readable. So you would wont to output something like:

Destination 1 (6):
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the truck station to street 6.
The shortest of these is the route "1 2 4 6", with 4 streets.

Destination 2 (4):
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the truck station to street 4.
The shortest of these is the route "1 3 4", with 3 streets.

Now personally, I rather java or python (and java is preferred more), but I leave this open ended to my students, so they can choose any language they like.

The original document is here

HOW TO WIN: Create the described program in a readable programming language, with the following criteria: - Readable - takes the input from the user(stdin/file) - Is mildly easy to understand.

Answer 1

Javascript (1159)

function h(g,e){var b=[],d=0,c=null,f=0;g.split("\n").forEach(function(a){a=a.replace(/\s*\/\/.*?$/,"");switch(d){case 0:c={};f=a;d++;break;case 1:a=a.split(" "),"0"===a[0]&&"0"===a[1]?(b.push(c),a=[],k(f,c,null,null,a),e.push([f,a]),d=0):(c[a[0]]||(c[a[0]]=[]),c[a[1]]||(c[a[1]]=[]),c[a[0]].push(a[1]),c[a[1]].push(a[0]))}})}
function k(g,e,b,d,c){b||(b="1",d=[]);d.push(b);var f=[];if(g!=b){if(e[b].forEach(function(a){-1==d.indexOf(a)&&(a=k(g,e,a,d.slice(),c))&&f.push(a)}),f.length)return f}else return c.push(d),d}
(function(g,z){var e=[];h(g,e);e.forEach(function(b){document.write("Destination "+b[0]+z);var d=99,c=-1;b[1].forEach(function(b,a){document.write(b.join(", ")+z);b.length<d&&(d=b.length,c=a)});document.write("There are "+b[1].length+" routes from the fire station to street "+b[0]+z);document.write('The shortest of these is the route "'+b[1][c].join(" ")+'", with '+d+" streets"+z)})})("6      //Route Begin\n1 2    //Route data...\n1 3\n3 4\n3 5\n4 6\n5 6\n2 3\n2 4\n0 0    //Route end\n4      //Route Begin\n2 3    //Route Data...\n3 4\n5 1\n1 6\n7 8\n8 9\n2 5\n5 7\n3 1\n1 8\n4 6\n6 9\n0 0    //Route end\n// continued...\n","<br>");

notes:

• Just used "regular" javascript code, then minified it using Closure Compiler
• Route data embedded, could have been alot shorter without a "parser". That would mean the data should be JSON encoded ..

Unminified version (added per request):

function parseInput(input, data)
{
    var output = [];
    var lines = input.split("\n");
    var state = 0;
    var route = null;
    var routeDest = 0;
    lines.forEach(function(val){
        val = val.replace(/\s*\/\/.*?$/, "");

        switch(state)
        {
            case 0:
                route = {};
                routeDest = val;
                state++
            break;
            case 1:
                var conn = val.split(" ");
                if (conn[0] === "0" && conn[1] === "0")
                {
                    output.push(route);
                    var innerData = [];
                    calculateRoutes(routeDest, route, null, null, innerData);
                    data.push([routeDest, innerData]);
                    state = 0;
                }
                else
                {
                    if (!route[conn[0]])
                    {
                        route[conn[0]]=[]
                    }
                    if (!route[conn[1]])
                    {
                        route[conn[1]]=[]
                    }

                    route[conn[0]].push(conn[1]);
                    route[conn[1]].push(conn[0]);
                }
            break;
        }
    });

    return output;
}

function calculateRoutes(dest, data, curr, from, returnData)
{
    if (!curr)
    {
        curr = "1";
        from = [];
    }

    from.push(curr);

    var routes = [];

    if (dest != curr)
    {
        data[curr].forEach(function(val){
            if (from.indexOf(val) == -1)
            {
                var route = calculateRoutes(dest, data, val, from.slice(), returnData);
                if (route)
                {
                    routes.push(route);
                }
            }
        });

        if (routes.length)
        {
            return routes;
        }
    }
    else
    {
        returnData.push(from);
        return from;
    }
}

function printRoutes(routeInfo)
{
    var data = [];
    parseInput(routeInfo, data);

    data.forEach(function(val){
        console.log("Destination " + val[0]);
        var shortLen = 99;
        var shortId = -1;
        val[1].forEach(function(ele, id){
            console.log(ele.join(", "));
            if (ele.length < shortLen)
            {
                shortLen = ele.length;
                shortId = id;
            }
        });
        console.log("There are " + val[1].length + " routes from the fire station to street " + val[0]);
        console.log("The shortest of these is the route \"" + val[1][shortId].join(" ") + "\", with " + shortLen + " streets");
    });
}

var nl = "\n"

printRoutes("6      //Route Begin" + nl +
    "1 2    //Route data..." + nl +
    "1 3" + nl +
    "3 4" + nl +
    "3 5" + nl +
    "4 6" + nl +
    "5 6" + nl +
    "2 3" + nl +
    "2 4" + nl +
    "0 0    //Route end" + nl +
    "4      //Route Begin" + nl +
    "2 3    //Route Data..." + nl +
    "3 4" + nl +
    "5 1" + nl +
    "1 6" + nl +
    "7 8" + nl +
    "8 9" + nl +
    "2 5" + nl +
    "5 7" + nl +
    "3 1" + nl +
    "1 8" + nl +
    "4 6" + nl +
    "6 9" + nl +
    "0 0    //Route end" + nl +
    "// continued..." + nl);

The unminified version uses console.log for output instead of document.write. Because document.write gives a better experience as a code snippet than console.log.