49
\$\begingroup\$

Introduction

You have the misfortune of being stuck in a runaway car on an obstacle course. All of the car's features are non-responsive, save for the steering system, which is damaged. It can drive straight, or it can turn right. Can the car be guided to safety?

Mechanics

Your car begins in the upper-left corner of an 8x8 map, and is trying to get to safety in the lower-right corner. The car has an orientation (initially to the right), measured in 90-degree increments. The car can perform one of two actions:

  1. Drive one square forward, or
  2. Turn 90 degrees clockwise, then drive one square forward

Note that the car is unable to turn sharply enough to perform a 180-degree turn on a single square.

Some of the squares are obstacles. If the car enters an obstacle square, it crashes. Everything outside the 8x8 course is assumed to be obstacles, so driving off the course is equivalent to crashing.

The lower-right square is the safe square, which allows the car to escape the obstacle course. The starting square and safe square are assumed not to be obstacles.

Task

You must write a program or function which takes as its input an 8x8 array (matrix, list of lists, etc.), representing the obstacle course. The program returns or prints a Boolean, or something similarly truthy. If it's possible for the car to make it to the safe square without crashing (i.e., if the map is solvable), the output is True, otherwise, it's False.

Scoring

Standard code golf rules - the winner is the code with the fewest bytes.

Bonuses:

  • If, for a solvable map, your code outputs a valid series of driver inputs which guide the car to the safe square, deduct 10 percentage points from your score. An example output format might be SRSSR (indicating Straight, Right, Straight, Straight, Right). This output would replace the standard True output.

  • If, for an unsolvable map, your code's output distinguishes between situations where a crash is unavoidable, and situations where it's possible to drive around the obstacle course forever, deduct 10 percentage points from your score. An example output might be Crash if a crash is unavoidable, or Stuck if the car is stuck in the obstacle course forever. These outputs would replace the standard False output for an unsolvable map.

Example

If the program is given an 8x8 array such as this:

[[0, 0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0], 
 [1, 1, 0, 0, 0, 0, 0, 0], 
 [0, 1, 0, 1, 0, 0, 0, 0], 
 [0, 0, 1, 1, 0, 0, 0, 0], 
 [0, 0, 0, 0, 1, 0, 1, 0], 
 [0, 0, 0, 0, 0, 0, 1, 0], 
 [0, 1, 1, 0, 0, 0, 1, 0]]

It would be interpreted as a map like this, with black squares indicating obstacles:

enter image description here

And a possible solution might be:

enter image description here

Since a solution exists, the program should return/print True for this map. The sequence of moves shown here is SSSSRSRRRSRSSRRRSSRSSS.

\$\endgroup\$
  • 2
    \$\begingroup\$ I wrote some incredibly simple test cases for Crash and Stuck. They're here because of how long they are. Row 2 filled, everything else empty -> Crash. Row 7 filled, everything else empty -> Stuck \$\endgroup\$ – undergroundmonorail Oct 3 '14 at 14:31
  • 3
    \$\begingroup\$ I'm confused about percentage points (as opposed to percentages). Getting either bonus multiplies your score by 0.9. Does getting both multiply it by 0.8 or 0.9^2? \$\endgroup\$ – undergroundmonorail Oct 3 '14 at 14:35
  • 3
    \$\begingroup\$ Sure, S and C are fine. My outputs were only suggestions. \$\endgroup\$ – phosgene Oct 3 '14 at 17:01
  • 13
    \$\begingroup\$ "Two wrongs don't make a right, but three lefts do." - Dad. \$\endgroup\$ – hoosierEE Oct 3 '14 at 21:07
  • 2
    \$\begingroup\$ "Your car can make only zero or three lefts!" \$\endgroup\$ – feersum Oct 4 '14 at 16:14
17
\$\begingroup\$

JavaScript (ES6) - 122 124 148 162 172 178 187 190 193 208 bytes

Many thanks to Optimizer and DocMax for helpful suggestions on how to improve this code:

F=a=>(D=(x,y,d)=>!D[i=[x,y,d]]&&(D[i]=1,x-=~d%2,y-=~-~d%2,x*y==49||!((x|y)&8||a[y][x])&&(D(x,y,d)||D(x,y,~-d%4))),D(-1,0))

Returns true (truthy) for solvable and false (falsy) for unsolvable.

Works only in Firefox as of today becasue of JavaScript 1.7 features.

Test Board

\$\endgroup\$
  • 1
    \$\begingroup\$ This is 193 bytes : D=(x,y,d,t,a)=>!t[i=x+y*8+d*64]&&(t[i]=1,x+=d==0?1:d==2?-1:0,y+=d==1?1:d==3?-1:0,x==7&&y==7||!((x|y)&~7||a[y][x])&&G(x,y,d,t,a));G=(x,y,d,t,a)=>D(x,y,d,t,a)||D(x,y,d+1&3,t,a);F=a=>G(0,0,0,[],a) . \$\endgroup\$ – Optimizer Oct 3 '14 at 14:56
  • 1
    \$\begingroup\$ 172 : D=d=>!t[i=x+y*8+d/4]&&(t[i]=1,x+=d?d^2?0:-1:1,y+=d^1?d^3?0:-1:1,x==7&&y==7||!((x|y)&~7||b[y][x])&&G(x,y,d));G=(X,Y,d)=>D(d,x=X,y=Y)||D(d+1&3,x=X,y=Y);F=a=>G(0,0,0,b=a,t={}) - Tested. \$\endgroup\$ – Optimizer Oct 3 '14 at 15:52
  • 1
    \$\begingroup\$ @Optimizer I'm still getting true for the second test case [[0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]. That should give false. \$\endgroup\$ – me and my cat Oct 3 '14 at 15:57
  • 2
    \$\begingroup\$ That is because since x and y are both globals, you cannot run two testcases before reloading the page... \$\endgroup\$ – Optimizer Oct 3 '14 at 16:00
  • 1
    \$\begingroup\$ You can save a total of 9 more by replacing x+=d?d^2?0:-1:1 with x+=d&1?0:1-d and y+=d^1?d^3?0:-1:1 with y+=d&1&&2-d. \$\endgroup\$ – DocMax Oct 4 '14 at 5:34
10
\$\begingroup\$

Python 2 - 123 125 133 146 148 150 154 160

True on success, False on failure.

def f(h=1,v=0,b=0,x=0,y=0,c=[]):s=x,y,h,v;a=b,x+h,y+v,c+[s];return(s in c)==(x|y)&8==b[y][x]<(x&y>6or f(h,v,*a)|f(-v,h,*a))

You must supply input like f(b=var_containing_board).

Lambda version - 154

Returns 0 (falsy) for failure, True for success.

F=lambda b,x=0,y=0,h=1,v=0,c=[]:0if[x,y,h,v]in c or x|y>7or x|y<0 or b[y][x]else x&y==7or F(b,x+h,y+v,h,v,c+[[x,y,h,v]])or F(b,x+h,y+v,-v,h,c+[[x,y,h,v]])

Thanks to Will and Brandon for making the function shorter than the lambda. Also for adding more horizontal scrolling :D

Thanks to xnor for superior bit-bashing and logic!

Edit note: I am reasonably confident that b[y][x] will never be executed when going out of range. Since we are outside of the board, the history check s in c will be False. Then the boundary check (x|y)&8 will be 8. Then python will not even check the last value of == because the first two are already different.

\$\endgroup\$
  • 1
    \$\begingroup\$ The functional version can combine the two ifs which both return; as return alone returns None which is falsy, you also don't need to return 0. .just returning the favour ;) \$\endgroup\$ – Will Oct 3 '14 at 17:00
  • \$\begingroup\$ If you flip the checks you can combine both ifs too \$\endgroup\$ – Will Oct 3 '14 at 17:36
  • \$\begingroup\$ Can you combine both return statements? \$\endgroup\$ – Brandon Oct 3 '14 at 18:02
  • 1
    \$\begingroup\$ @Will Thanks, I knew there was a better way to do that :D Um, I couldn't find any spaces to remove that don't cause me syntax error. I don't really get why x|y>7or works but x|y<0or doesn't... \$\endgroup\$ – FryAmTheEggman Oct 4 '14 at 15:31
  • 1
    \$\begingroup\$ You can make an octal literal beginning with 0o. \$\endgroup\$ – feersum Oct 4 '14 at 18:04
9
\$\begingroup\$

C (GNU-C), 163 bytes * 0.9 = 146.7

#C (GNU-C), 186 bytes * 0.9 = 167.4

My new version uses a signed rather than unsigned integer. Earlier I was afraid of signed right shift, but I realized since the sign bit is the goal square, it doesn't matter what happens after that.

The function takes an array of bits (ones represent blocked squares) in the form of a 64-bit integer. The bits are arranged least to most significant in the same way you would read a book. It returns -1 for a crash, 0 for driving forever, or 1 for escaping to the bottom right corner.

g(long long o) {
    typeof(o) a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;
    for( ;i--;d = D<<8&~o)
        a |= D = d|r,
        r = (r|u)*2&~M&~o,
        u = (u|l)>>8&~o,
        l = ((l|d)&~M)/2&~o;
    return a<0?:-!(d|r|u|l);
}

Test program

f(long long o){typeof(o)a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;for(;i--;d=D<<8&~o)a|=D=d|r,r=(r|u)*2&~M&~o,u=(u|l)>>8&~o,l=((l|d)&~M)/2&~o;return a<0?:-!(d|r|u|l);}
{
    char* s[] = {"Crash", "Stuck", "Escape"};
    #define P(x) puts(s[f(x)+1])
    L ex = 0x4640500C0A034020;
    P(ex);
    L blocked = 0x4040404040404040;
    P(blocked);

    L dead = 0x10002;
    P(dead);

    return 0;
}

Output

Escape
Stuck
Crash

Python array-to-hex converter:

a2b=lambda(A):"0x%X"%sum(A[i/8][i%8]<<i for i in range(64))
\$\endgroup\$
  • 1
    \$\begingroup\$ Replace memset(&M,~1,8) (15 chars) with M=~(-1ULL/255) (14 chars). \$\endgroup\$ – R.. Oct 5 '14 at 3:50
  • \$\begingroup\$ @R.. Nice one! -4 bytes from that. \$\endgroup\$ – feersum Oct 5 '14 at 4:50
  • 2
    \$\begingroup\$ I like the input format - very cool! \$\endgroup\$ – phosgene Oct 5 '14 at 5:53
  • \$\begingroup\$ I'm getting 'crash' for P(0x00fefefefefefefe); =( Should be straight shot to upper right, one turn, straight to corner. Same for P(0x00eeeeeeeeeeeeee); (dead end on 4th col). I don't think you need to assign a initially. \$\endgroup\$ – user21677 Oct 8 '14 at 20:22
  • \$\begingroup\$ @tolos You've got the row/column-major order transposed. To have the top row and right column open, it should be 0x7f7f7f7f7f7f7f00. Also it is necessary to initialize a because later it is only modified by ORing in additional bits, so I can't afford to have an unwanted bit set initially. \$\endgroup\$ – feersum Oct 9 '14 at 8:00
6
\$\begingroup\$

Python, 187 213

207 chars, 10% bonus for printing path

b=map(ord," "*9+" ".join("".join("o "[i]for i in j)for j in input())+" "*9)
def r(p,d,s):
 p+=(1,9,-1,-9)[d]
 if b[p]&1<<d:b[p]^=1<<d;return(s+"S")*(p==79)or r(p,d,s+"S")or r(p,(d+1)%4,s+"R")
print r(8,0,"")

On the test input it finds a slightly different path: SSSSRSRSRRSSRSSRRSRSSRSSSSS

The general approach is to first turn the input into a spaces and os. Spaces have a hex of 20, so all four lower bits are unset. o has a hex of 6F, so the low four bits are all set.

A border of os is placed around the board so we don't have to worry about bad indices.

As we walk over the board, we use the bits in each tile to see if we are allowed to pass when coming from that side. In this way, we avoid infinite loops. Its not enough to have a single boolean per tile, as your exit direction depends on your entry direction, so tiles can be visited twice.

We then do a recursive search for a safe path.

\$\endgroup\$
  • 3
    \$\begingroup\$ "Your car begins in the upper-left corner of an 8x8 map" - can't you hardcode 9 in place of w=len(b[0])+1, etc? \$\endgroup\$ – FryAmTheEggman Oct 3 '14 at 15:00
  • \$\begingroup\$ @FryAmTheEggman thank you, how could I have overlooked that? :D \$\endgroup\$ – Will Oct 3 '14 at 15:11
  • \$\begingroup\$ You can reverse your ternary statement and replace p==79 with p-79. I got a syntax error doing this both ways without a space before the else. I think that trick only works with if. \$\endgroup\$ – FryAmTheEggman Oct 3 '14 at 15:23
  • \$\begingroup\$ @FryAmTheEggman I think the depth test has to before the recurse? I've been playing with a multiplication by boolean instead. \$\endgroup\$ – Will Oct 3 '14 at 15:32
  • 7
    \$\begingroup\$ I just found a really neat trick. You probably know that -~x == x+1 but both unary operators have higher precedence than multiplication, division and modulus! So (d+1)%4 could be -~d%4! This also would work with x-1 but just use ~-x instead. \$\endgroup\$ – FryAmTheEggman Oct 4 '14 at 3:38
6
\$\begingroup\$

Javascript - 270 - 20% = 216 262 - 20% = 210 bytes

Since there ought to be at least one solution that earns both bonuses (and doesn't lead to a ridiculous stack depth ;)...

Minified:

V=I=>{n=[N=[0,0,0]];v={};v[N]='';O='C';for(S='';n[0];){m=[];n.map(h=>{[x,y,d]=h;D=i=>[1,0,-1,0][d+i&3];p=v[h];for(j=2;j--;){O=v[c=[X=x+D(j),Y=y+D(3-3*j)),d+j&3]]?'K':O;J=X|Y;J<0||J>7||I[Y][X]||v[c]?O:(m.push(c),v[c]=p+'SR'[j])}S=(x&y)>6?p:S});n=m;}return S||O;};

Expanded:

V = I => {
    n = [N=[0,0,0]];
    v = {};
    v[N] = '';
    O = 'C';

    for( S = ''; n[0]; ) {
        m = [];
        n.map( h => {
            [x,y,d] = h;
            D = i => [1,0,-1,0][d+i&3];
            p = v[h];
            for( j = 2; j--; ) {
                O = v[c = [X = x+D(j),Y = y+D(3-3*j),d+j&3]] ? 'K' : O;
                J = X|Y;
                J<0 || J>7 || I[Y][X] || v[c] ? O : (
                    m.push( c ),
                    v[c] = p + 'SR'[j]
                );
            }

            S = (x&y) > 6 ? p : S;
        } );
        n = m;
    }
    return S || O;
};

v is a hashtable with keys that are state triples (x,y,d) corresponding to (x,y) coordinate and direction of entry d. Each key has an associated value that is the string of S (straight) and R (turn right) moves required to reach the state represented by the key.

The code also maintains a stack of triples (in variable n) that have not been processed yet. The stack initially contains only the triple (0,0,0), corresponding to the state where the car faces right in the (0,0) cell. In the outer loop, for( S = ... ), the routine checks if any unprocessed triples remain. If so, it runs each unprocessed triple through the inner loop, n.map( ....

The inner loop does five things:

  1. computes the two possible moves (driving straight, turning right) out of the current state
  2. if either of these moves leads to a state already registered in the hashtable, it is ignored for further processing. We flag the FALSE output as K (stuck), however, since we have found at least one loop where the car can continue to circle forever without crashing.
  3. if a state is legal and novel, it is added to the hashtable (v) and to the stack of unprocessed triples (m) for the next pass of the outer loop
  4. when the new state is registered in v, its value is set to the value of the originating state (the sequence of moves) plus R or S based on the current move
  5. if x and y are 7, the value of the originating state (the sequence of moves taken to reach the originating state) is copied to S, since this move sequence is a solution to the problem

After the inner loop terminates, n (the stack) is replaced by m (the new stack).

After the outer loop terminates (no new states were reached), the function returns its output. If the (7,7) cell was reached, S will contain a sequence of moves leading to this cell, and this is outputted. If the cell was not reached, S will be the empty string, and the routine falls through to outputting O, which will contain K (stuck) if and only if a loop was found, or C (crash) if the car will inevitably crash.

\$\endgroup\$
  • 1
    \$\begingroup\$ Got confirmation from OP, you can rename 'Crash' and 'Stuck' to 'C' and 'S'. \$\endgroup\$ – FryAmTheEggman Oct 3 '14 at 17:24
  • \$\begingroup\$ Ah. That saves a bit, then. Thanks. ;) \$\endgroup\$ – COTO Oct 3 '14 at 18:46
  • \$\begingroup\$ Can you explain what your code is doing? I can't make heads or tails of it. \$\endgroup\$ – phosgene Oct 3 '14 at 19:20
  • \$\begingroup\$ @phosgene: I've included a detailed explanation inline. \$\endgroup\$ – COTO Oct 3 '14 at 20:44
  • \$\begingroup\$ That's a clever procedure. Nothing is wasted. \$\endgroup\$ – phosgene Oct 4 '14 at 0:35
4
\$\begingroup\$

Python 339 - 10% = 305 bytes

I used a recursive depth-first search, which is terminated early on success via exit. Also printing path on success in the form of 00001010101010101010101110100111001000, 0 for straight, 1 for right. The answer will be longer than optimal, since it is depth-first. I'm sure some optimizations to the algorithm could bring the byte count down quite a bit.

b=input()
D=[(-1,0),(0,-1),(1,0),(0,1)]
def a(l):
 x,y=0,0
 v=2
 for d in l:
  if d=='1':v=(v+1) % 4
  x+=D[v][0]
  y+=D[v][1]
  if x<0 or x>7 or y<0 or y>7:return 0,x,y
  if b[y][x]:return -1,x,y
 return 1,x,y
def c(l):
 if len(l) < 39:
  t,x,y=a(l)
  if t==1:
   if (x,y)==(7,7):
    print l;exit(0)
   c(l+"0")
   c(l+"1")
c("")
print 0
\$\endgroup\$
  • 3
    \$\begingroup\$ Since this is Python 2, you can mix tabs and spaces for indents, like in a's for loop. You also don't need spaces around operators, e.g. (v+1) % 4 -> (v+1)%4. You can also join multiple statements onto one line by using ; if there is no if or for, etc on the line, e.g c(l+"0");c(l+"1"). Some other golfs: x,y,v=0,0,2, x|y>7 or x|y<0, x==y==7. Good luck :) \$\endgroup\$ – FryAmTheEggman Oct 3 '14 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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