#define SIZE_EDGE (3)
#define SIZE_ROT (2)
#define PROGRESS 5000
#define ROT_ONEKEY 1
/*
#define DEBUG 1
 */
#define NDEBUG 1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <assert.h>

#define SIZE_TOT (SIZE_EDGE*SIZE_EDGE)

typedef unsigned char num;
typedef unsigned int pos;
typedef num field[SIZE_TOT];

#define INVALID_POS ((pos)-1)

#define RC_ENTRY(x,y) ((y)*SIZE_EDGE+(x))

#if SIZE_EDGE==3
#define STATES_TOT (362880)
#define FILENAME_23 "Nokia61_23.cache"
#define ROUNDCYCLE_TOT (sizeof(roundcycle)/sizeof(*roundcycle))
static const unsigned char roundcycle[]={
	RC_ENTRY(0,0),
	RC_ENTRY(1,0),
	RC_ENTRY(1,1),
	RC_ENTRY(0,1),
	};
#else
#error "STATES_TOT not known!"
#endif

struct state {
	pos todo_next;
	pos parent;
	pos depth;
	} states[STATES_TOT];
pos todo=INVALID_POS;
pos *todo_tail=&todo;

#ifdef PROGRESS
pos states_touched=0,states_retouched=0,states_done=0;
pos maxdepth=0;
#endif

static const num ascending[25]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24};

static int check_field(const field fld)
{
unsigned char used[SIZE_TOT];
int i;

	memset(used,0,sizeof(used));
	for (i=0;i<SIZE_TOT;i++) {
		if (fld[i]>=SIZE_TOT || used[fld[i]])
			return(0);
		used[fld[i]]=1;
		}
	return(1);
}

#define assert_field(fld) assert(check_field(fld))

static void dump_field(const field fld)
{
unsigned char y,x;

	for (y=0;y<SIZE_EDGE;y++) {
		fputs("  ",stdout);
		for (x=0;x<SIZE_EDGE;x++)
			printf(" %2u",fld[y*SIZE_EDGE+x]+1);
		putchar('\n');
		}
}

static pos field_to_pos(const field fld)
{
num points[SIZE_TOT],remains;
pos r=0;

#ifdef DEBUG
	puts("field_to_pos(");
	dump_field(fld);
#endif

	assert_field(fld);
	memcpy(points,ascending,sizeof(points));
	for (remains=SIZE_TOT;remains;remains--) {
num n=*fld++;

		n=(num *)memchr(points,n,remains)-points;
		r*=remains;
		r+=n;
		memmove(points+n,points+n+1,remains-n-1);
		}

#ifdef DEBUG
	printf("  )=%u\n",r);
#endif

	return(r);
}

static void pos_to_field(field fld,pos p)
{
num points[SIZE_TOT],expanded[SIZE_TOT],remains;
#if defined(DEBUG) || !defined(NDEBUG)
num *fld_orig=fld;
#endif
#ifndef NDEBUG
pos p_orig=p;
#endif

#ifdef DEBUG
	printf("pos_to_field(%u)=\n",p);
#endif

	for (remains=1;remains<=SIZE_TOT;remains++) {
num n=p%remains;

		p/=remains;
		expanded[SIZE_TOT-remains]=n;
		}
	memcpy(points,ascending,sizeof(points));
	for (remains=SIZE_TOT;remains;remains--) {
num n=expanded[SIZE_TOT-remains];

		p/=remains;
		*fld++=points[n];
		memmove(points+n,points+n+1,remains-n-1);
		}

#ifdef DEBUG
	dump_field(fld_orig);
#endif

	assert(!p);
	assert(p_orig==field_to_pos(fld_orig));
}

static void mark(pos p,pos parent,pos depth)
{
struct state *state;

	assert(p>=0 && p<STATES_TOT);
	state=states+p;
	if (!(state->parent==INVALID_POS || state->depth>depth))
		return;
#ifdef PROGRESS
	if (maxdepth<depth)
		maxdepth=depth;
#endif
	state->parent=parent;
	state->depth=depth;
	if (state->todo_next==INVALID_POS) {
		*todo_tail=p;
		todo_tail=&state->todo_next;
#ifdef PROGRESS
		states_touched++;
#endif
		}
	else {
#ifdef PROGRESS
		states_retouched++;
#endif
		}
}

static void progress_dump(void)
{
#ifdef PROGRESS
	printf("TOUCHED=%6u (RETOUCHED %6u), DONE=%6u, KNOWN TODO=%6u, UNTOUCHED=%6u, MAXDEPTH=%6u\n",
			states_touched,states_retouched,states_done,states_touched-states_done,STATES_TOT-states_touched,maxdepth);
#endif
}

#ifdef PROGRESS
static void states_progress(void)
{
static unsigned period=0;
static time_t time_last=0;
time_t time_new;

	if (period++<PROGRESS)
		return;
	period=0;
	if (time(&time_new)<5+time_last)
		return;
	time_last=time_new;
	progress_dump();
}
#endif

static void cycle(void)
{
pos p;

	while ((p=todo)!=INVALID_POS) {
struct state *state=states+p;
field fld;
unsigned char y,x,cyc;

		pos_to_field(fld,p);
#ifdef DEBUG
		printf("START: %u\n",p);
#endif
		for (y=0;y<=SIZE_EDGE-SIZE_ROT;y++)
		for (x=0;x<=SIZE_EDGE-SIZE_ROT;x++)
		for (cyc=0;cyc<ROUNDCYCLE_TOT;cyc++) {
num swap,*base;
unsigned char cyci;

			base=fld+y*SIZE_EDGE+x;
			for (cyci=0;cyci<ROUNDCYCLE_TOT-1;cyci++) {
				swap=base[roundcycle[cyci]];
				base[roundcycle[cyci]]=base[roundcycle[cyci+1]];
				base[roundcycle[cyci+1]]=swap;
				}
#ifdef ROT_ONEKEY
			if (!(cyc&1))
#endif
				mark(field_to_pos(fld),p,state->depth+1);
			}
		todo=state->todo_next;
		state->todo_next=INVALID_POS;
#ifdef PROGRESS
		states_done++;
		states_progress();
#endif
		}
}

static void final(void)
{
#ifdef PROGRESS
pos *maxes,p;
int maxi;
#endif

	puts("FINAL:");
	progress_dump();
#ifdef PROGRESS
	fputs("Depth distribution:",stdout);
	maxes=malloc(sizeof(*maxes)*(maxdepth+1));
	memset(maxes,0,sizeof(maxes));
	for (p=0;p<STATES_TOT;p++)
		maxes[states[p].depth]++;
	for (maxi=0;maxi<=maxdepth;maxi++)
		printf(" %d(=%d)",maxi,maxes[maxi]);
	free(maxes);
	putchar('\n');
#endif
	putchar('\n');
}

#if SIZE_EDGE==3

static struct item_23 {
	unsigned char a[3];
	} *states_23;
#define STATES_23_SIZEOF (sizeof(*states_23)*STATES_TOT)

static int read_23(void)
{
FILE *f;
pos p;
unsigned char eof_mark;

	if (!(f=fopen(FILENAME_23,"rb")))
		return(1);
	if (!(states_23=malloc(STATES_23_SIZEOF))) {
fail_fclose:
		fclose(f);
		return(1);
		}
	if (fread(states_23,1,STATES_23_SIZEOF,f)!=STATES_23_SIZEOF) {
fail_free:
		free(states_23);
		goto fail_fclose;
		}
	if (fread(&eof_mark,1,1,f))
		goto fail_free;
	for (p=0;p<STATES_TOT;p++) {
		states[p].depth=0;
		states[p].parent=(states_23[p].a[0]<<16)
		               | (states_23[p].a[1]<< 8)
									 | (states_23[p].a[2]<< 0);
		}
	fclose(f);
	free(states_23);
#ifdef PROGRESS
	printf("Cache read from \"%s\".\n",FILENAME_23);
#endif
	return(0);
}

static void write_23(void)
{
FILE *f;
pos p;

	if (!(f=fopen(FILENAME_23,"wb"))) {
fail:
#ifdef PROGRESS
		printf("Failed to write cache to \"%s\"!\n",FILENAME_23);
#endif
		return;
		}
	if (!(states_23=malloc(STATES_23_SIZEOF))) {
fail_unlink:
		fclose(f);
		unlink(FILENAME_23);
		goto fail;
		}
	for (p=0;p<STATES_TOT;p++) {
		states_23[p].a[0]=(states[p].parent>>16);
		states_23[p].a[1]=(states[p].parent>> 8);
		states_23[p].a[2]=(states[p].parent>> 0);
		}
	if (fwrite(states_23,1,STATES_23_SIZEOF,f)!=STATES_23_SIZEOF) {
fail_free:
		free(states_23);
		goto fail_unlink;
		}
	if (fclose(f))
		goto fail_free;
	free(states_23);
#ifdef PROGRESS
		printf("Cache written to \"%s\".\n",FILENAME_23);
#endif
}

#endif /* SIZE_EDGE==3 */

static void input(void)
{
field fld;
int x,y,i;
pos p;
struct state *state;

	for (;;) {
restart:
		for (y=0;y<SIZE_EDGE;y++) {
			printf("Enter line #%d/%d: ",y+1,SIZE_EDGE); fflush(stdout);
			for (x=0;x<SIZE_EDGE;x++) {
				if (1!=scanf("%d",&i)) {
					if (!y && !x)
						return;
					puts("Error reading input, restarting!");
					goto restart;
					}
				fld[y*SIZE_EDGE+x]=i-1;
				}
			}
		if (!check_field(fld)) {
			puts("Field not valid!");
			continue;
			}
		puts("-->");
		p=field_to_pos(fld);
		do {
			state=states+p;
			printf("STATE %6u: DEPTH=%6u, PARENT=%6u\n",p,state->depth,state->parent);
			pos_to_field(fld,p);
			dump_field(fld);
			puts("----------");
			p=state->parent;
			} while (state!=states+0);
		putchar('\n');
		}
}

int main(void)
{
#if SIZE_EDGE==3
	if (read_23())	
#endif
	{
		memset(states,-1,sizeof(states));
		mark(0,0,0);
		cycle();
		final();
#if SIZE_EDGE==3
		write_23();
#endif
		}
	input();
	return(EXIT_SUCCESS);
}