15
\$\begingroup\$

"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):

graph
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):

Input 1

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:

Input 2

A possible output:

n,d,a

 

\$\endgroup\$

closed as off-topic by Rohan Jhunjhunwala, mbomb007, GamrCorps, NoOneIsHere, absinthe Aug 15 '16 at 3:39

  • This question does not appear to be about programming puzzles or code golf within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Can we write a function (instead of a stand-alone program)? \$\endgroup\$ – golfer9338 Oct 11 '14 at 13:28
  • \$\begingroup\$ @golfer9338 Yes. I'd prefer a program if possible, but if the underhanded part relies on it being a function then a function is allowed.​​​​​​​​​​​​ \$\endgroup\$ – absinthe Oct 12 '14 at 5:49
  • \$\begingroup\$ I'm asking because I plan to do this in Javascript. \$\endgroup\$ – golfer9338 Oct 12 '14 at 5:55
  • 3
    \$\begingroup\$ The real question is, why are we out to spite this love-struck boy? Perhaps he insulted our family? Do we ourselves have designs on the object of his affection? We must know! \$\endgroup\$ – Claudiu Oct 14 '14 at 3:04
  • 3
    \$\begingroup\$ I'm voting to close this question as off-topic because Underhanded challenges are off topic on this sight \$\endgroup\$ – Rohan Jhunjhunwala Aug 12 '16 at 11:46
2
\$\begingroup\$

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]))
\$\endgroup\$

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