Your car only turns right!

Question

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:

And a possible solution might be:

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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