Calculate the total number of paths

Description

There will be a grid of 9x9, where there will be placed 12 rocks.

You will start at a starting-rock and walking with a starting-direction (north, south, west or east), whenever you see a rock, you have two options:

• Climb over the rock and continue in the same direction
• Change direction to your *left

*NOT to the west, you change to your left as if you were walking and you take your own left.

So the flow of the paths will always be counter-clockwise. Here is an example that illustrates the flow:

Note: In this case, the starting-rock is the yellow (X) and the starting-direction is to the south

Rules

• The code must be able to solve it for any rock (if it doesn't have complete paths, then is 0)
• You can NOT memorize anything different than the rocks used
• The rocks must be included on the code (so you can't pass them by input)
• We will use the above's rock placement in the competition
• You chose how you will pick the starting-rock (Example: passing an array index or giving a xy location, etc) and how you chose the starting-direction (Example: 1=north, 2=south or etc)
• It must return, print or otherwise make us know the total number of paths somehow for that given rock
• Counted by characters used

Just to immortalize the grid and rock placements in case the image dies for unknown reasons, I will put it in plain text:

100100000
100100010
000000000
000000000
000000000
010010000
000000000
010100000
100010010

//rocks = 1, empty = 0


Clarifications

• You can't walk on the same part twice on the same path (crossing ways are allowed)
• We need to be able to set on the input: a) the starting-rock and b) the starting-direction
• The complete paths must end on the starting-rock
• Note that it shouldn't be a problem whether we can climb over a starting rock or not, because it is impossible to this to happen with the current map and rules (we do have a four-path rock where this could happen, but after analysing it, this can't happen)
• You are allowed to compress the 9x9 grid. (the most it can be compressed is to a 5x5 I think)
• How do paths end? Do they have to end at a rock? The starting point? – Keith Randall Mar 1 '12 at 4:37
• @KeithRandall yes, to the starting point. <updating my post> – ajax333221 Mar 1 '12 at 4:44
• One more nitpick: can the path cross the starting rock before ending up at it? – Keith Randall Mar 1 '12 at 20:55
• @KeithRandall I didn't see any case that this will affect us. We only have one rock where theoretically this could happen because it have (+) formation, but I revised it and it is impossible to bother us except if a) we allow to walk twice on the same part on the same path or b) modify the map. But as it is now, it shouldn't be a problem – ajax333221 Mar 1 '12 at 21:23
• I have a map where it can happen. If you're going to restrict the program to just the given map, then print 3 is a pretty good program... – Keith Randall Mar 1 '12 at 22:08

Python, 274 chars

S=7
D=-1j

R=[0,4,7,1+1j,3+1j,1+3j,4+3j,7j,3+7j,7+7j,8j,3+8j]
Z={}
for i in range(4096):
d=D;p=R[S];L=[]
while len(L)<12:
p+=d;P=[(abs(r-p),r)for r in R if r-p==abs(r-p)*d]
if not P:break
p=min(P)[1];d*=1j**(i>>R.index(p)&1);L+=[p]
if p==R[S]:Z[tuple(L)]=1;break
print len(Z)


The code I'm counting starts at the R=[..., the initial two lines are "input" which I didn't count.

R is the set of rock coordinates, listed using complex number coordinates. S is the starting rock. D is the starting direction, again using complex numbers (1=right,-1=left,1j=up,-1j=down).

The code tries all of the 2^12=4096 possibilities for go straight/turn left for each rock, then walks from the starting rock until it gets back to the starting rock, or there is no more rock on the path, or the path gets too long (it loops). It saves the path in Z if it is successful.

• very interesting way. Just remember that the rock placements can't be passed by input – ajax333221 Mar 2 '12 at 16:45
• @ajax333221: fixed – Keith Randall Mar 2 '12 at 16:54

ASM - WinXP Command shell .COM 128 bytes, source = 607 characters

To run, provide the rock id and the direction, e.g.

program c1


where the letter is the rock (top left = a, bottom right = l) and the number is the direction: up = 3, left = 2, down = 1, right = 0

   mov bp,1000h
mov di,bp
mov cx,bp
xor ax,ax
rep stosw
mov bl,b[82h]
sub bl,'a'-1
mov bh,ch
mov cl,b[83h]
sub cl,48
shl cl,2
mov di,bx
call l2
mov dx,bp
mov b[bp+1],'\$'
mov ah,9
int 21h
ret
l1:inc b[bp]
cmp di,bx
je ret
dec b[bp]
cmp b[di+bp],0
jne ret
call l2
sub cl,4
l2:mov dx,[di+l3-2]
ror dx,cl
and dx,15
jz ret
mov b[di+bp],1
pusha
mov di,dx
call l1
popa
mov b[di+bp],0
ret
l3:xor al,b[bx+si]
inc ax
and ax,ax
pusha
xor b[si],cl
jpe l4
l4:pop bx


JavaScript, 466 chars

• Starting-direction is equal to: North=1, West=2, South=3, East=4
• The starting-rock is in row/column notation, where the upper-left is 11. (the grid was compressed to a 5x5)

The first two lines are input and aren't included in the count of characters, also I added some break lines to wrap the code.

D=3;//starting direction
C=21;//starting rock

function a(a){return a+="",(a[0]-1)*5+(a[1]-1)}
function b(a){var b=!1,c=C+"";a==4?(h=c[0]+(c[1]-1))[1]>0&&(b=!0):a==3?(h=-(-c[0]-1)+c[1]+"")[0]<6&&(b=!0):a==2?(h=c[0]+ -(-c[1]-1))[1]<6&&(b=!0):(h=c[0]-1+c[1])[0]>0&&(b=!0);if(b)return C=h*1,!0}
function c(){var c=C;while(b(D)&&F[a(C)]==0);if(C!=c&&F[a(C)]==1)return!0}
function d(){if(c()){F[C]++;var a=D,b=C;C!=B?(d(),C=b,D=a,D==1?D=4:D--,d()):(A++,F=E)}}


Uncompressed and explained code:

dir=3;
start=21;

//transforms row-column notation to array index
function toAV(a){
return a+="",(a[0]-1)*5+(a[1]-1);
}

//advance one square on the current direction
//returns true when it succeed
function walk(num){
var walkbol=false,str=xy+"";
if(num==4){
if((wal_rec=str[0]+(str[1]-1))[1]>0){
walkbol=true;
}
}else if(num==3){
if((wal_rec=-(-str[0]-1)+str[1]+"")[0]<6){
walkbol=true;
}
}else if(num==2){
if((wal_rec=str[0]+-(-str[1]-1))[1]<6){
walkbol=true;
}
}else{
if((wal_rec=(str[0]-1)+str[1])[0]>0){
walkbol=true;
}
}
if(walkbol){
xy=wal_rec*1;
return true;
}
}

//start walking on the current dir until a)didn't succeed walking or b)step on a rock
//returns true when it moved at least once and it ended above a rock
function nextRock(){
var str1=xy;
while(walk(dir)&&map[toAV(xy)]==0){}

if(xy!=str1&&map[toAV(xy)]==1){
return true;
}
}

//if it finds a rock, it calls itself twice
//one with the current direction and one with the direction to its left
function splitways(){
if(nextRock()){
map[xy]++;
var cc=dir,dd=xy;
if(xy!=start){
splitways();
//--
xy=dd;
dir=cc;
dir==1?dir=4:dir--;
splitways();
}else{
count++;
map=xmap;
}
}
}

//globals
count=0,xy=start,xmap=map="1010010101010100110010011".split("");

//start
splitways();