/*
    dbox - Sokoban level solver

    Copyright (C) 2001-2009  Ian Cowburn (ianc@noddybox.demon.co.uk)

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    -------------------------------------------------------------------------

*/
static const char cvs_id[]="$Id$";

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <time.h>

#if (USECURSES == ncurses)
#include <ncurses.h>
#else
#include <curses.h>
#endif

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif

static const int DEBUG=TRUE;
static char *name;

/* Stop the program once this much memory is allocated.
   Set to -1 to disable the check
*/
#define MAXMB		-1

#define MEGABYTE	(1024*1024)

/* ---------------------------------------- TYPES
*/
typedef signed char	PosInt;
typedef unsigned char	Byte;
typedef Byte		Bool;

typedef char		Route[1024];

typedef enum {SPACE_GL=' ',
	      WALL_GL='#',
	      PLAYER_GL='@',
	      BOX_GL='B',
	      TARGET_GL='.',
	      BOX_TARGET_GL='X'} Glyph;

typedef enum {SPACE, WALL} MapChar;

typedef enum {QUIET,CSV,VERBOSE} LogMode;

#define DIR_NONE	-1
#define DIR_LEFT	0
#define DIR_UP		1
#define DIR_RIGHT	2
#define DIR_DOWN	3

typedef struct
{
    PosInt		x;
    PosInt		y;
} Pos;

static const Pos move_dir[4]={{-1,0},{0,-1},{1,0},{0,1}};

typedef struct State
{
    Pos			player;
    Pos			*box;
    Bool		path;
    Byte		dir;
    Bool		pushed;
    int			hash;
    struct State	*left;
    struct State	*right;
    struct State	*up;
    struct State	*down;
    struct State	*parent;
    struct State	*next;
} State;

typedef struct
{
    char		*name;
    int			width;
    int			height;
    int			no;
    Pos			*target;
    MapChar		*map;
    State		*state;
} Level;

#define STATE_HASH	0x10000

typedef struct StateMap
{
    State		*s;
    struct StateMap	*next;
} StateMap;

static StateMap		*state_map[STATE_HASH]={NULL};
static int		state_map_no=0;

#define AT(l,x,y)	((l)->map[(l)->width*(y)+(x)])


/* ---------------------------------------- PROTOS
*/
static void	*Grab(size_t l);

static void	Interactive(Level *l, int play);

static Level	*Load(const char *path);
static void	FreeLevel(Level *l);
static void	Display(Level *level, State *state);
static char	GetGlyph(Level *level, State *state, int x, int y);
static State	*CreateState(Byte dir, Bool must_push, Level *l, State *s,
			     Bool check_possible);
static void	Solve(Level *level, Route route, int max_depth, LogMode log);


/* ---------------------------------------- MAIN
*/
int main(int argc, char *argv[])
{
    int interact=FALSE;
    int play=FALSE;
    int base;
    int f;
    LogMode mode=VERBOSE;

    name=argv[0];

    if (argc<2)
    {
	fprintf(stderr,"%s: usage %s [-i|-p] file [file2 ...]\n",name,name);
	return EXIT_FAILURE;
    }

    if (strcmp(argv[1],"-i")==0)
    {
	interact=TRUE;
	base=2;
    }
    else if (strcmp(argv[1],"-p")==0)
    {
	interact=TRUE;
	play=TRUE;
	base=2;
    }
    else if (strcmp(argv[1],"-c")==0)
    {
	interact=FALSE;
	mode=CSV;
	base=2;
    }
    else
    {
    	base=1;
    }

    if (argc<=base)
    {
	fprintf(stderr,"%s: usage %s [-c|-i|-p] file [file2 ...]\n",name,name);
	return EXIT_FAILURE;
    }

    for(f=base;f<argc;f++)
    {
	Route route;
	Level *level;

	if (!(level=Load(argv[f])))
	{
	    fprintf(stderr,"%s: %s could not be read\n",name,argv[f]);
	}
	else
	{
	    if (interact)
	    {
	    	Interactive(level,play);
	    }
	    else
	    {
		printf("Solving %s\n\n",level->name);

		Display(level,level->state);

		Solve(level,route,999,mode);

		printf("\nRoute = '%s'\n",route);
	    }

	    FreeLevel(level);
	}
    }

    return EXIT_SUCCESS;
}


/* ---------------------------------------- UTIL
*/
static size_t grab_tot=0;
static int grab_last_mb=0;
static int grab_mb=0;

static void *Grab(size_t l)
{
    size_t *p;

    p=malloc(l+sizeof(size_t));

    if (!p)
    {
	fprintf(stderr,"%s: malloc(%d) failed\n",name,l);
	exit(EXIT_FAILURE);
    }

    *p=l;

    grab_tot+=l;

    grab_mb=grab_tot/MEGABYTE;

    if (grab_last_mb!=grab_mb)
    {
	grab_last_mb=grab_mb;

#if MAXMB != -1
	if (grab_mb>=MAXMB)
	{
	    fprintf(stderr,"Quitting: Allocated %d Mb\n",grab_mb);
	    exit(EXIT_FAILURE);
	}
#endif
    }

    return p+1;
}


static void Release(void *p)
{
    size_t *pp;

    pp=p;

    pp--;

    grab_tot-=*pp;

    free(pp);
}


static int GrabSize(void)
{
    return grab_mb;
}


static Pos *FindPos(Pos *p, int no, int x, int y)
{
    int f;

    for (f=0;f<no;f++)
    {
	if (p[f].x==x && p[f].y==y)
	{
	    return p+f;
	}
    }

    return NULL;
}


/* ---------------------------------------- LEVEL LOADING
*/
static char *GetLine(FILE *fp)
{
    static char s[1024];
    size_t l;

    fgets(s,sizeof s,fp);

    if (feof(fp))
    {
	return NULL;
    }

    l = strlen(s);

    if (l && s[l-1]=='\n')
    {
	s[l-1]=0;
    }

    return s;
}

static Level *Load(const char *path)
{
    FILE *fp;
    char *line;
    Level *new;
    int x,y;
    int tno,bno;
    int pno;

    if (!(fp=fopen(path,"r")))
    {
    	return NULL;
    }

    new=Grab(sizeof *new);

    line=GetLine(fp);
    new->name=Grab(strlen(line)+1);
    strcpy(new->name,line);

    new->no=atoi(GetLine(fp));

    /* Calc sizes
    */
    new->width=strlen(GetLine(fp));
    new->height=1;

    while((line=GetLine(fp)))
    {
	new->height++;

	if (strlen(line)!=new->width)
	{
	    fprintf(stderr,"%s: '%s' (line %d) too short "
			    "(should be %d wide)\n",
			    	name,line,new->height,new->width);
	    exit(EXIT_FAILURE);
	}
    }

    /* Rewind file and skip first two lines
    */
    rewind(fp);
    GetLine(fp);
    GetLine(fp);

    new->target=Grab(sizeof(Pos)*new->no);
    new->map=Grab(sizeof(MapChar)*(new->width*new->height));

    new->state=Grab(sizeof(State));
    new->state->parent=NULL;
    new->state->next=NULL;
    new->state->box=Grab(sizeof(Pos)*new->no);
    new->state->left=new->state->right=new->state->up=new->state->down=NULL;
    new->state->dir=DIR_NONE;

    tno=0;
    bno=0;
    pno=0;

    for(y=0;y<new->height;y++)
    {
	line=GetLine(fp);

	if (strlen(line)<new->width)
	{
	    fprintf(stderr,"%s: line '%s' too short "
			    "(should be %d wide)\n",name,line,new->width);
	    exit(EXIT_FAILURE);
	}

	for(x=0;x<new->width;x++)
	{
	    switch(line[x])
	    {
		case WALL_GL:
		    AT(new,x,y)=WALL;
		    break;

		case SPACE_GL:
		    AT(new,x,y)=SPACE;
		    break;

		case BOX_TARGET_GL:
		case TARGET_GL:
		    if (tno==new->no)
		    {
			fprintf(stderr,"%s: too many "
					"targets in %s\n",name,path);

			exit(EXIT_FAILURE);
		    }

		    AT(new,x,y)=SPACE;
		    new->target[tno].x=x;
		    new->target[tno].y=y;
		    tno++;

		    /* NOTE: Runs into following case
		    */
		    if (line[x]==TARGET_GL)
		    {
			break;
		    }

		case BOX_GL:
		    if (bno==new->no)
		    {
			fprintf(stderr,"%s: too many "
					"boxes in %s\n",name,path);

			exit(EXIT_FAILURE);
		    }

		    AT(new,x,y)=SPACE;
		    new->state->box[bno].x=x;
		    new->state->box[bno].y=y;
		    bno++;
		    break;

		case PLAYER_GL:
		    if (pno++==1)
		    {
			fprintf(stderr,"%s: too many "
					"players in %s\n",name,path);

			exit(EXIT_FAILURE);
		    }

		    AT(new,x,y)=SPACE;
		    new->state->player.x=x;
		    new->state->player.y=y;
		    break;
	    }
	}
    }

    fclose(fp);

    if (pno==0)
    {
	fprintf(stderr,"%s: no player definied in %s\n",name,path);

	exit(EXIT_FAILURE);
    }

    return new;
}


static void FreeLevel(Level *l)
{
}


static void Display(Level *level, State *state)
{
    int x,y;

    for(y=0;y<level->height;y++)
    {
	for(x=0;x<level->width;x++)
	{
	    putchar(GetGlyph(level,state,x,y));
	}

	putchar('\n');
    }
}


static char GetGlyph(Level *level, State *state, int x, int y)
{
    if (AT(level,x,y)==WALL)
    {
	return WALL_GL;
    }
    else if (FindPos(&state->player,1,x,y))
    {
	return PLAYER_GL;
    }
    else if (FindPos(state->box,level->no,x,y) &&
		FindPos(level->target,level->no,x,y))
    {
	return BOX_TARGET_GL;
    }
    else if (FindPos(state->box,level->no,x,y))
    {
	return BOX_GL;
    }
    else if (FindPos(level->target,level->no,x,y))
    {
	return TARGET_GL;
    }
    else
    {
	return SPACE_GL;
    }
}


/* ---------------------------------------- SOLVER
*/
static void FreeState(State *s)
{
    Release(s->box);
    Release(s);
}


static void ClearStates(void)
{
    int f;

    state_map_no=0;

    for(f=0;f<STATE_HASH;f++)
    {
	while(state_map[f])
	{
	    StateMap *p;
	    p=state_map[f]->next;
	    Release(state_map[f]);
	    state_map[f]=p;
	}
    }
}


static Bool AddNewState(Level *l, State *s)
{
    StateMap *p;
    int hash;

    hash=s->hash%STATE_HASH;

    p=state_map[hash];

    while(p)
    {
	if (s->player.x==p->s->player.x && s->player.y==p->s->player.y)
	{
	    int f;
	    int ok;

	    ok=FALSE;

	    for(f=0;f<l->no && !ok;f++)
	    {
	    	if (s->box[f].x!=p->s->box[f].x || s->box[f].y!=p->s->box[f].y)
		{
		    ok=TRUE;
		}
	    }

	    if (!ok)
	    {
	    	return FALSE;
	    }
	}

	p=p->next;
    }

    p=Grab(sizeof *p);

    p->s=s;
    p->next=state_map[hash];
    state_map[hash]=p;

    state_map_no++;

    return TRUE;
}


static int GetStateNum(void)
{
    return state_map_no;
}


static const char *NoMoveReason(char *fmt,...)
{
    static char r[512];
    va_list va;

    va_start(va,fmt);

    if (fmt)
    {
	vsprintf(r,fmt,va);
    }

    va_end(va);

    return r;
}


static Bool CheckImpossible(Level *l, State *s)
{
    int f;

    for(f=0;f<l->no;f++)
    {
	int x,y;

	x=s->box[f].x;
	y=s->box[f].y;

	if (!FindPos(l->target,l->no,x,y))
	{
	    int d;
	    int any_move;

	    /* Check that the box can be pushed at all for the next go
	       (Simple wall based check)
	    */
	    any_move=FALSE;

	    for(d=0;d<4 && !any_move;d++)
	    {
		int nx,ny;

		nx=x+move_dir[d].x;
		ny=y+move_dir[d].y;

		if (AT(l,nx,ny)!=WALL)
		{
		    int ox,oy;

		    ox=x+move_dir[(d+2)%4].x;
		    oy=y+move_dir[(d+2)%4].y;

		    if (AT(l,ox,oy)!=WALL)
		    {
		    	any_move=TRUE;
		    }
		}
	    }

	    if (!any_move)
	    {
		NoMoveReason("Couldn't push block at %d,%d",x,y);
		return TRUE;
	    }

	    /* Four blocks together is impossible
	    */
	    if (FindPos(s->box,l->no,x+1,y) && FindPos(s->box,l->no,x,y+1) &&
	    					FindPos(s->box,l->no,x+1,y+1))
	    {
		NoMoveReason("Group of 4 boxes at %d,%d",x,y);
	    	return TRUE;
	    }
	}
    }

    return FALSE;
}


static State *CreateState(Byte dir, Bool must_push,
			  Level *l, State *s, Bool check_possible)
{
    State *new;
    Pos *p;
    int x,y;
    int push;
    int dx,dy;
    int f;

    dx=move_dir[dir].x;
    dy=move_dir[dir].y;

    push=FALSE;

    x=s->player.x+dx;
    y=s->player.y+dy;

    /* Check for walls
    */
    if (AT(l,x,y)==WALL)
    {
    	return NULL;
    }

    /* Check for boxes
    */
    if ((p=FindPos(s->box,l->no,x,y)))
    {
	int bx,by;

	/* Can the box be pushed?
	*/
	bx=p->x+dx;
	by=p->y+dy;

	if (AT(l,bx,by)==WALL)
	{
	    return NULL;
	}

	if (FindPos(s->box,l->no,bx,by))
	{
	    return NULL;
	}

	push=TRUE;
    }

    if (!push && must_push)
    {
    	return NULL;
    }

    new=Grab(sizeof *new);
    new->box=Grab(sizeof(Pos)*l->no);
    memcpy(new->box,s->box,sizeof(Pos)*l->no);

    new->player.x=x;
    new->player.y=y;

    if (push)
    {
	p=FindPos(new->box,l->no,x,y);

	p->x+=dx;
	p->y+=dy;

	/* (Very) basic checks to see if the move has made the level impossible
	*/
	if (check_possible && CheckImpossible(l,new))
	{
	    FreeState(new);
	    return NULL;
	}
    }


    new->left=NULL;
    new->right=NULL;
    new->up=NULL;
    new->down=NULL;

    new->parent=s;
    new->next=NULL;

    new->path=FALSE;
    new->pushed=push;
    new->dir=dir;

    /* Calculate a hash based on box and player positions 
    */
    new->hash=0;

    for(f=0;f<l->no;f++)
    {
	new->hash+=new->box[f].x+new->box[f].y*l->height;
    }

    new->hash+=(STATE_HASH>>2)+new->box[f].x+new->box[f].y*l->height;

    if (!AddNewState(l,new))
    {
	NoMoveReason("State matches previous");
	FreeState(new);
	return NULL;
    }

    return new;
}


static void SetChain(State **first, State **curr, State *new)
{
    if (new)
    {
	if (!*first)
	{
	    *first=new;
	    *curr=*first;
	}
	else
	{
	    (*curr)->next=new;
	    (*curr)=new;
	}
    }
}


static void SubSolve(Level *level, State *state,int depth,
		     int max_depth, LogMode log)
{
    static time_t last=0;
    State *first;
    State *curr;
    State *new;
    State *s;
    int ok;
    int f;

    if (depth>=max_depth)
    {
    	return;
    }

    if (depth==1)
    {
    	last=time(NULL);
    }

    switch(log)
    {
	case QUIET:
	    break;
	case VERBOSE:
	    printf("Searching %d moves deep "
			"(%ld secs, used %dMb - %d unique states)\n",
			    depth,time(NULL)-last,GrabSize(),GetStateNum());
	    break;
	case CSV:
	    printf("%d,%ld,%d,%d\n",
			    depth,time(NULL)-last,GrabSize(),GetStateNum());
	    break;
    }

    last=time(NULL);

    /* Loop across all states at this depth
    */
    s=state;
    first=NULL;
    curr=NULL;

    while(s)
    {
	/* Check to see whether the level is solved
	*/
	ok=TRUE;

	for(f=0;(f<level->no) && ok;f++)
	{
	    if (!FindPos(s->box,level->no,
	    		 level->target[f].x,level->target[f].y))
	    {
		ok=FALSE;
	    }
	}

	if (ok)
	{
	    s->path=TRUE;
	    s=s->parent;

	    while(s)
	    {
	    	s->path=TRUE;
		s=s->parent;
	    }
	    return;
	}

	/* Check moves
	*/
	if (s->dir==DIR_RIGHT)
	{
	    s->left=new=CreateState(DIR_LEFT,!s->pushed,level,s,TRUE);
	}
	else
	{
	    s->left=new=CreateState(DIR_LEFT,FALSE,level,s,TRUE);
	}

	SetChain(&first,&curr,new);

	if (s->dir==DIR_LEFT)
	{
	    s->right=new=CreateState(DIR_RIGHT,!s->pushed,level,s,TRUE);
	}
	else
	{
	    s->right=new=CreateState(DIR_RIGHT,FALSE,level,s,TRUE);
	}

	SetChain(&first,&curr,new);

	if (s->dir==DIR_DOWN)
	{
	    s->up=new=CreateState(DIR_UP,!s->pushed,level,s,TRUE);
	}
	else
	{
	    s->up=new=CreateState(DIR_UP,FALSE,level,s,TRUE);
	}

	SetChain(&first,&curr,new);

	if (s->dir==DIR_UP)
	{
	    s->down=new=CreateState(DIR_DOWN,!s->pushed,level,s,TRUE);
	}
	else
	{
	    s->down=new=CreateState(DIR_DOWN,FALSE,level,s,TRUE);
	}

	SetChain(&first,&curr,new);

	s=s->next;
    }

    if (first)
    {
	SubSolve(level,first,++depth,max_depth,log);
    }
}


static void Solve(Level *level, Route route, int max_depth, LogMode log)
{
    State *s;

    route[0]=0;
    ClearStates();

    SubSolve(level,level->state,1,max_depth,log);

    s=level->state;

    while(s)
    {
	if (s->left && s->left->path)
	{
	    strcat(route,"L");
	    s=s->left;
	}
	else if (s->right && s->right->path)
	{
	    strcat(route,"R");
	    s=s->right;
	}
	else if (s->up && s->up->path)
	{
	    strcat(route,"U");
	    s=s->up;
	}
	else if (s->down && s->down->path)
	{
	    strcat(route,"D");
	    s=s->down;
	}
	else
	{
	    s=NULL;
	}
    }
}


/* ---------------------------------------- INTERACTIVE MODE
*/
static void CursesDisplay(Level *l, State *s, int play)
{
    int x,y,f;
    char allow[80];

    for(x=0;x<l->width;x++)
    {
	char num[20];

	sprintf(num,"%d",x);

	f=0;

	while(num[f])
	{
	    mvaddch(3+f,3+x,num[f++]);
	}

	for(y=0;y<l->height;y++)
	{
	    if (x==0)
	    {
	    	mvprintw(6+y,0,"%d",y);
	    }

	    mvaddch(6+y,3+x,GetGlyph(l,s,x,y));
	}
    }

    strcpy(allow,"Moves: ");

    if (s->left)
    {
    	strcat(allow,"left ");
    }

    if (s->right)
    {
    	strcat(allow,"right ");
    }

    if (s->up)
    {
    	strcat(allow,"up ");
    }

    if (s->down)
    {
    	strcat(allow,"down ");
    }

    if (s->parent)
    {
    	strcat(allow,"back");
    }

    while(strlen(allow)<70)
    {
    	strcat(allow,"     ");
    }

    mvaddstr(l->height+11,0,allow);

    if (!play)
    {
	if (s->path)
	{
	    mvaddstr(l->height+10,0,"On solved path: YES");
	}
	else
	{
	    mvaddstr(l->height+10,0,"On solved path: NO ");
	}
    }
    else
    {
	int depth=0;

	while(s)
	{
	    depth++;
	    s=s->parent;
	}

	mvprintw(l->height+10,0,"Depth: %d ",depth);
    }

    mvprintw(LINES-3,0,"Last reason: %-40.40s",NoMoveReason(NULL));

    refresh();
}


static void Interactive(Level *l, int play)
{
    int quit;
    Route route;
    State *s;

    if (!play)
    {
	Solve(l,route,999,VERBOSE);
    }

    initscr();
    cbreak();
    noecho();
    nonl();
    intrflush(stdscr,FALSE);
    keypad(stdscr,TRUE);

    quit=FALSE;
    s=l->state;

    clear();
    mvaddstr(0,0,l->name);

    mvaddstr(LINES-1,0,"Cursors to move, P to follow path, "
    			"Q to quit, Backspace/B to step back");

    if (!play)
    {
	mvprintw(l->height+9,0,"Route:%s",route);
    }

    while(!quit)
    {
	int key;

	CursesDisplay(l,s,play);

	key=getch();

	if (key=='p' || key=='P')
	{
	    if (s->left && s->left->path)
	    {
	    	key=KEY_LEFT;
	    }

	    if (s->right && s->right->path)
	    {
	    	key=KEY_RIGHT;
	    }

	    if (s->up && s->up->path)
	    {
	    	key=KEY_UP;
	    }

	    if (s->down && s->down->path)
	    {
	    	key=KEY_DOWN;
	    }
	}

	switch(key)
	{
	    case KEY_BACKSPACE:
	    case 'b':
	    case 'B':
		if (s->parent)
		{
		    s=s->parent;
		}
	    	break;

	    case KEY_LEFT:
		if (play && !s->left)
		{
		    s->left=CreateState(DIR_LEFT,FALSE,l,s,TRUE);
		}

		if (s->left)
		{
		    s=s->left;
		}
	    	break;

	    case KEY_RIGHT:
		if (play && !s->right)
		{
		    s->right=CreateState(DIR_RIGHT,FALSE,l,s,TRUE);
		}

		if (s->right)
		{
		    s=s->right;
		}
	    	break;

	    case KEY_DOWN:
		if (play && !s->down)
		{
		    s->down=CreateState(DIR_DOWN,FALSE,l,s,TRUE);
		}

		if (s->down)
		{
		    s=s->down;
		}
	    	break;

	    case KEY_UP:
		if (play && !s->up)
		{
		    s->up=CreateState(DIR_UP,FALSE,l,s,TRUE);
		}

		if (s->up)
		{
		    s=s->up;
		}
	    	break;

	    case 'q':
	    case 'Q':
	    	quit=TRUE;
		break;

	    default:
	    	break;
	}
    }

    endwin();
}


/* END OF FILE */