Calculate the total number of paths

Question

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)

Answer 1

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.

Answer 2

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
   add bx,bx
   mov cl,b[83h]
   sub cl,48
   shl cl,2
   mov di,bx
   call l2
   mov dx,bp
   add b[bp],48
   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
   add di,di
   call l1
   popa
   mov b[di+bp],0
   ret
l3:xor al,b[bx+si]
   inc ax
   add w[si+09510],sp
   and ax,ax
   add al,087
   add b[bx+si+0906],dh
   pusha
   add b[bx+si+0b],cl
   xor b[si],cl
   jpe l4
l4:pop bx

Answer 3

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)}}
A=0,B=C,E=F="1010010101010100110010011".split(""),d(),alert(A)

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();
alert(count);