Sabotage a Train to Make It Run Late

Question

"I want to go to the Araby bazaar to buy a present for the one I have fallen in love with. However, if I arrive too late all the stores will be closed and I won't be able to buy anything. Can you help me?"

Goal: Get the boy to Araby from North Richmond Street before all the stores close.
Actual Goal: Make sure the boy doesn't arrive in Araby before the stores close.

Your program will take in input in the following format:

<time> <map>

where

• <time> is the maximum time the boy can spend travelling, in minutes. It is a positive integer.
• <map> is a graph of the routes the train can take.

Here is how the format for the graph works:

• Each statement is ended with a semicolon.
• Nodes in the map (which represent switches) are represented using single lower case letters.
• A path between nodes is represented with the syntax a,X,b, where X is an integer representing the weight of the path. The weight of the path is the time, in minutes, the train takes to go through those two nodes.
• Araby is represented with a, and North Richmond Street is represented with an n.
• All paths are bidirectional.

For instance, this graph (pretend the paths are bidirectional):

^{Image by Artyom Kalinin, via Wikimedia Commons. Used under the CC BY-SA 3.0 licence.}

would be recorded in the graph notation as:

a,4,b;a,2,c;b,5,c;b,10,d;c,3,e;e,4,d;d,11,f;

Note that this input doesn't have an n, so it's an invalid input. Your program may do anything if given an invalid input.

Here is an example input:

21 n,4,b;n,2,c;b,5,c;b,10,d;c,3,e;e,4,d;d,11,a;

(It's just the same graph as the image above with a replaced by n and f replaced by a).

The boy must get from n to a within 21 minutes. If he takes the route n --> c --> e --> d --> a, he gets there in 20 minutes, which is in time. We could represent that route as a comma separated list of nodes:

n,c,e,d,a

On the other hand, the route n --> b --> c --> e --> d --> a will cause the boy to take 27 minutes, which is not in time. We could represent that route like this:

n,b,c,e,d,a

Another possible route that will cause the boy to not make it in time is:

n,b,c,b,c,b,c,b,c,b,c,b,c,b,c,b,c,b,c,e,d,a

Your program should take in the input as described above, and at first glance appear to output a route that will cause the boy to make it in time, but actually outputs a route that causes the boy to not make it in time. For any given input there will always exist a route, without backtracking, that causes the boy to not make it in time.

This is an underhanded popularity contest, so the entry with the most votes wins. Votes are awarded for ingenuity in hiding the bug - the less obvious it is the better.

Here are some sample graphs to test your program with.

Input:

12 a,2,c;a,2,e;b,5,c;b,4,d;b,11,e;d,7,n;e,4,n;

A visual representation (this visual representation is only for clarity and does not constitute part of the challenge):

A possible output:

n,d,b,e,a

Input:

10 a,8,b;a,12,d;b,1,n;d,11,n;a,1,n;

Here is a visual image of the graph:

A possible output:

n,d,a

 

Answer 1

Python 3 (not 2)

Edit: I'll ungolf this in the morning, oops.

It's a perfectly normal A-star search. Right? Riiiiiiight? Seems to work for all test cases.

def a(b,c,d):
    e,f,g=[],{},{}
    f[c]=0
    while f:
        h=sorted(f.keys(),key=lambda z:-f[z],reverse=True)[-1]
        if h==d:break
        e.append(h)
        for z in b[h]:
            if z in e:continue
            if z in f and f[z]>f[h]+b[z][h]:continue
            g[z]=h
            f[z]=f[h]+b[z][h]
        del f[h]
    i=[]
    j=d
    q=0
    while j!=c:
        i.append(j)
        q+=b[j][g[j]]
        j=g[j]
    return q,(i+[c])[::-1]
t,q=input().split(" ")
t=int(t)
q=q[:-1]
q=[i.split(",")for i in q.split(";")]
g={a:{}for a in __import__("functools").reduce(lambda zz,zy:zz+zy,[[v[0],v[2]]for v in q])}
for l in q:g[l[0]][l[2]]=g[l[2]][l[0]]=int(l[1])

r=a(g,'n','a')
print("time-good: %d, time-ours: %d" % (t, r[0]))
print("path: %s" % " -> ".join(r[1]))