Enumeration of Self-Avoiding Walks

up.c

#include <stdio.h>
#include <stdlib.h>

#define DIM 2
// square lattice
#define NDIR (2*DIM) 
int L; // grid size
int nsite; // = (L+1)^2
int *f_visited; // 0/1 = un/occupied
int *nnp; // neighbour index
int drvec[NDIR][DIM] = {
    {-1,0},
    {0,-1},
    {1,0},
    {0,1}
};
#define DIR_L 0
#define DIR_U 1
#define DIR_R 2
#define DIR_D 3

#define xy2idx(x, y) ((x)+(L+1)*(y))
void idx2xy(int idx, int *x, int *y)
{
    *x = idx % (L+1);
    *y = idx / (L+1);
}

void init_misc(int L0)
{
    L=L0;
    nsite = (L+1)*(L+1);
    f_visited = (int *)malloc(sizeof(int)*nsite);
    nnp = (int *)malloc(sizeof(int)*nsite*NDIR);
    int i,dir;
    for(i=0;i<nsite;i++)
    {
	f_visited[i]=0;
	int x,y;
	idx2xy(i, &x, &y);
	for(dir=0;dir<NDIR;dir++)
	{
	    int xx= x+drvec[dir][0];
	    int yy= y+drvec[dir][1];
	    if(xx<0 || xx>L || yy<0 || yy>L)
		nnp[i*NDIR+dir] = -1;
	    else
		nnp[i*NDIR+dir] = xy2idx(xx,yy);
#ifdef DEBUG
	    printf("# site %d,%d dir %d pos %d %d nnp=%d\n",x,y,dir,xx,yy,nnp[i*NDIR+dir] );
#endif
	}//dir
    }//i
}

int npath=0;
int pos_start, pos_goal;


// recursive routine for one step move
void proceed(int pos0, int dir_p)
{
    int dir;
    int dir_ban2=-1;
    int x,y;
    idx2xy(pos0, &x,&y);
    if(dir_p!=-1) dir_ban2 = (dir_p+2)&3;

    if(pos0 == pos_goal)
    {
#ifdef DEBUG
	printf("# Goal!\n");
#endif
	int i;

	npath++;
	return;
    }

    f_visited[pos0]=1;

#ifdef DEBUG
    printf("Now %d,%d \n", x,y);
#endif

#ifdef HIT_WALL_MOD
    int ban_dir = -1;
    if(x==0) ban_dir = DIR_U;
    if(x==L) ban_dir = DIR_U;
    if(y==0) ban_dir = DIR_L;
    if(y==L) ban_dir = DIR_L;
#endif
    for(dir=0;dir<NDIR;dir++)
    {
	if(dir==dir_ban2)continue;
#ifdef HIT_WALL_MOD
	if(dir==ban_dir)continue;
#endif
	int newpos= nnp[pos0*NDIR+dir];
#ifdef DEBUG
	int xx,yy;
	if(newpos==-1)printf("# dir %d Newpos out of bound\n",dir);
	else
	{
	    idx2xy(newpos, &xx,&yy);
	    printf("# dir %d New %d,%d F=%d\n", dir,xx,yy,f_visited[newpos]);
	}
#endif
	if(newpos==-1)continue;
	if(f_visited[newpos]==1)
	{
	    continue;
	}
	else
	{
	    proceed(newpos, dir);
	}
    }
    f_visited[pos0]=0;
}

int main(int argc, char **argv)
{
    int ll=atoi(argv[1]);
    init_misc(ll);


    pos_goal = xy2idx(L,L);
#ifdef HIT_WALL_MOD
    f_visited[xy2idx(0,0)]=1;
    pos_start= xy2idx(1,0);
    proceed(pos_start, 2);
#else
    pos_start= xy2idx(0,0);
    proceed(pos_start, -1);
#endif


#ifdef HIT_WALL_MOD
    npath *= 2;
#endif
    printf("L=%d N=%d\n",L, npath);

}