Your car only turns right!
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
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.
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))