1
\$\begingroup\$

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.

\$\endgroup\$

closed as off-topic by Downgoat, mınxomaτ, Justin, feersum, Dennis Sep 20 '15 at 1:22

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Dennis
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    \$\begingroup\$ This is probably not a good challenge to be a [popularity-contest]; it works extremely well as a [code-golf]. It's not related to [sorting], either. \$\endgroup\$ – Justin Sep 19 '15 at 23:10
  • 1
    \$\begingroup\$ Note that this is a path-finding problem. It's a lot like this. \$\endgroup\$ – Justin Sep 19 '15 at 23:13
  • 1
    \$\begingroup\$ Also, while you mention Java and Python, their tags are not relevant to this question. \$\endgroup\$ – mınxomaτ Sep 19 '15 at 23:19
  • 2
    \$\begingroup\$ @tawilson You have added criteria, but they aren't objective. "Readable" and "Is mildly easy to understand" are identical and subjective. What if two answers are posted that both solve your problem? Then what? This site is a Q&A style, but the idea is to post challenges out there that people can solve whenever they come across it. Shortest code is a pretty good criteria, as it allows us to objectively find a winning answer. Most answerers have an un-minified version of their code as well, which they post along with an explanation. \$\endgroup\$ – Justin Sep 20 '15 at 3:41
  • 3
    \$\begingroup\$ I find it very hard to believe that a teacher for 10 years would take more than 5 minutes to solve this incredibly easy problem. I also find it incredibly worrying only 8 of your students managed to solve it. \$\endgroup\$ – orlp Sep 20 '15 at 11:00
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Could I see the decompressed version? \$\endgroup\$ – tawilson Sep 20 '15 at 2:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.