#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "dllist.h"

typedef struct state_s {
	int v, w, r;
} state_t;

int compare_states(state_t *a, state_t *b) {
	assert(a);
	assert(b);
	if (a->v == b->v) {
		if (a->w == b->w) {
			if (a->r == b->r) return 0;
			else if (a->r > b->r) return 1;
			else return -1;
		} else if (a->w > b->w) return 1;
		else return -1;
	} else if (a->v > b->v) return 1;
	else return -1;
}

typedef enum {
	S, A, B, C, K, L, M
} pos_t;

typedef struct decoded_state_s {
	int x, y;  // coordinates on the board
	int f;     // f = 0 \/ (down) f = 1  /\ (up)
	pos_t p;
	int r;
} decoded_state_t;

void mirror_decoded_state(decoded_state_t *out, decoded_state_t *in) {
 	int inx2 = 2*in->x;
	int iny2 = 2*in->y;
	int outx2 = -(inx2 - 5)+5;
	int outy2 = -(iny2 - 5)+5;
 	out->x = outx2/2;
	out->y = outy2/2;
	out->f = 1 - in->f;
	out->r = in->r;
	out->p = in->p;
}

#if 1
/*
 *       ____________________
 *  0 __ \XX/\XX/\XX/\XX/\A /\
 *        \/XX\/XX\/XX\/__\/B_\
 *    1 __ \XX/\XX/\XX/\  /\D /\
 *          \/XX\/XX\/__\/__\/C_\
 *      2 __ \XX/\XX/\  /\  /\  /\
 *            \/XX\/C_\/__\/__\/__\
 *        3 __ \XX/\D /\  /\  /\  /\
 *              \/B_\/__\/__\/__\/__\
 *          4 __ \A /\  /\  /\D /\A /\
 *                \/__\/__\/C_\/B_\/XX\
 *                   0   1   2   3   4
 *
 */

// rotating around (2.5, 2.5) 120 degrees in positive direction
// (x, y) -> (x - 2.5, y - 2.5) -> 
// (4, 4) -> (1.5, 1.5) 
// 4d4 -> 4d0 -> 0d4
// 3u4 -> 4u0 -> 0u3
// 2u4 -> 4u1 -> 1u2
// 4d3 -> 4d1 -> 1d3

// disallowed connections
//
// n3u1M0 (7, 13, 0) [Sw] n2u2M1 (5, 20, 1)
// n3u1M1 (7, 13, 1) [Sw] n2u2M2 (5, 20, 2)
// n3u1M2 (7, 13, 2) [Sw] n2u2M0 (5, 20, 0)
//
// n2u3K0 (5, 25, 0) [Ww] n1u3K2 (3, 25, 2)
// n2u3K1 (5, 25, 1) [Ww] n1u3K0 (3, 25, 0)
// n2u3K2 (5, 25, 2) [Ww] n1u3K1 (3, 25, 1)
//
// n3u3L0 (7, 26, 0) [Nw] n3u2L1 (7, 19, 1)
// n3u3L1 (7, 26, 1) [Nw] n3u2L2 (7, 19, 2)
// n3u3L2 (7, 26, 2) [Nw] n3u2L0 (7, 19, 0)
//
// n3u0M2 (7, 6, 2) [Sw] n2u1M0 (5, 13, 0)
// n3u0M0 (7, 6, 0) [Sw] n2u1M1 (5, 13, 1)
// n3u0M1 (7, 6, 1) [Sw] n2u1M2 (5, 13, 2)
//
// n3d2L1 (6, 19, 1) [Nw] n3d1L0 (6, 12, 0)
// n3d2L2 (6, 19, 2) [Nw] n3d1L1 (6, 12, 1)
// n3d2L0 (6, 19, 0) [Nw] n3d1L2 (6, 12, 2)
//
// n3d3K1 (6, 25, 1) [Ee] n4d3K0 (8, 25, 0) [allowed]
// n3d3K2 (6, 25, 2) [Ee] n4d3K1 (8, 25, 1)
// n3d3K0 (6, 25, 0) [Ee] n4d3K2 (8, 25, 2)
//
// n4u3L1 (9, 26, 1) [Nw] n4u2L2 (9, 19, 2)
// n4u3L2 (9, 26, 2) [Nw] n4u2L0 (9, 19, 0)
// n4u3L0 (9, 26, 0) [Nw] n4u2L1 (9, 19, 1)
//
// n1u4K1 (3, 32, 1) [Ww] n0u4K0 (1, 32, 0)
// n1u4K2 (3, 32, 2) [Ww] n0u4K1 (1, 32, 1)
// n1u4K0 (3, 32, 0) [Ww] n0u4K2 (1, 32, 2) [allowed]
//
// n2d3M1 (4, 27, 1) [Sw] n1d4M0 (2, 34, 0)
// n2d3M2 (4, 27, 2) [Sw] n1d4M1 (2, 34, 1)
// n2d3M0 (4, 27, 0) [Sw] n1d4M2 (2, 34, 2)
#define SIZE_Y 5
#define SIZE_X 5

int grid[SIZE_Y][SIZE_X][2] = {
	{ { 0, 0 }, { 0, 0 }, { 0, 0 }, { 0, 1 }, { 1, 1 } },
	{ { 0, 0 }, { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 1 } },
	{ { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 1 }, { 1, 1 } },
	{ { 0, 1 }, { 1, 1 }, { 1, 1 }, { 1, 1 }, { 1, 1 } },
	{ { 1, 1 }, { 1, 1 }, { 1, 1 }, { 1, 1 }, { 1, 0 } }
};
#endif
#if 0
/* hexagon with size 2
 *
 *       ________________
 *  0 __ \XX/\XX/\  /\  /\
 *        \/XX\/__\/__\/__\
 *    1 __ \XX/\  /\  /\  /\
 *          \/__\/__\/__\/__\
 *      2 __ \  /\  /\  /\  /\
 *            \/__\/__\/__\/XX\
 *        3 __ \  /\  /\  /\XX/\
 *              \/__\/__\/XX\/XX\
 *                 \   \   \   \
 *                  0   1   2   3
 */


#define SIZE_Y 4
#define SIZE_X 4

int grid[SIZE_Y][SIZE_X][2] = {
/*
	{ { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 1 } },
	{ { 0, 1 }, { 1, 1 }, { 1, 1 }, { 1, 1 } },
	{ { 1, 1 }, { 1, 1 }, { 1, 1 }, { 1, 0 } },
	{ { 1, 1 }, { 1, 1 }, { 1, 0 }, { 0, 0 } } */

	{ { 1, 1 }, { 1, 1 }, { 1, 1 }, { 1, 1 } },
	{ { 1, 1 }, { 1, 1 }, { 1, 1 }, { 1, 1 } },
	{ { 1, 1 }, { 1, 1 }, { 1, 1 }, { 1, 1 } },
	{ { 1, 1 }, { 1, 1 }, { 1, 1 }, { 1, 1 } }

};

#endif
#if 0

/*         ______            ______
 *        /\    /\    /\     \    /
 * 0 _   /--\--/--\  /--\     \--/
 *      /____\/____\/____\_____\/
 *      \    /\    /\    /\    /\  \
 * 1 _   \--/  \--/--\  /--\--/--\  \
 *        \/____\/____\/____\/____\  \
 *        /\    /\    /\     \    /   \
 * 2 _   /--\--/  \--/--\     \--/     \
 *      /____\/    \/____\     \/       \
 *                                 \     \
 *          \     \     \     \     \     \
 *           0     1     2     3     4     5
 */

#define SIZE_Y 3
#define SIZE_X 6

int grid[SIZE_Y][SIZE_X][2] = {
	{ { 0, 0 }, { 0, 1 }, { 1, 1 }, { 0, 1 }, { 0, 0 }, { 1, 0 } },
	{ { 0, 0 }, { 1, 0 }, { 1, 1 }, { 0, 1 }, { 1, 1 }, { 0, 0 } },
	{ { 0, 1 }, { 1, 0 }, { 1, 1 }, { 0, 0 }, { 1, 0 }, { 0, 0 } }
};
#endif

int no_allowed = 0;
int allowed[SIZE_Y*7][SIZE_X*2][3] = { };

int no_connections[SIZE_Y*7][SIZE_X*2][3] = { };
state_t cons[SIZE_Y*7][SIZE_X*2][3][12] = { };

int no_visited = 0;
int visited[SIZE_Y*7][SIZE_X*2][3] = { };

int depth = 0;

// safe read from allowed
int sa(state_t *s) {
	assert(s);
	assert(s->w >= -1 || s->w <= SIZE_Y*7);
	assert(s->v >= -1 || s->v <= SIZE_X*2);
	assert(s->r >= 0 || s->r <= 2);

	if (s->w < 0 || s->w >= SIZE_Y*7) return 0;
	if (s->v < 0 || s->v >= SIZE_X*2) return 0;

	return allowed[s->w][s->v][s->r];
}

// safe read from grid
int sg(int y, int x, int f) {
	assert(y >= -1 || y <= SIZE_Y);
	assert(x >= -1 || x <= SIZE_X);

	if (y < 0 || y >= SIZE_Y || x < 0 || x >= SIZE_X) return 0;

	assert(f == 0 || f == 1);

	return grid[y][x][f];
}

char *draw_down[3][2] = {
	{ "    ", "    " },
	{ "  "  , "%.*s" },
	{ ""    , ""     }
};

char *draw_up[3][2][2] = {
	{ { ""    , ""     }, { ""    , ""     } },
	{ { "  "  , "  "   }, { "%.*s", "%.*s" } },
        { { "    ", "____" }, { "____", "____" } }
};

/*
 *        Nn
 *    Nw\ | /Ne
 *   Wn  \|/   En
 *  Ww --- ---- Ew
 *   Ws  /|\   Es
 *    Sw/ | \Se
 *        Ss
 *
 */
typedef enum {
	Nn, Ne, En, Ee, Es, Se, Ss, Sw, Ws, Ww, Wn, Nw
} dir_t;

char *trans_dir[12] = {
	"Nn", "Ne", "En", "Ee", "Es", "Se", "Ss", "Sw", "Ws", "Ww", "Wn", "Nw"
};

typedef struct {
	dllist_elt_t elt;
	dir_t dir;
} move_t;

typedef struct {
	dllist_elt_t elt;
	state_t from, to;
	int count;
	dllist_t route;
} connection_t;

dllist_t connections;

typedef enum {
	Dn, Up
} flip_t;

char trans_pos[7] = {
	'S', 'A', 'B', 'C', 'K', 'L', 'M'
};

typedef struct translation_s {
	int dx, dy, df;
} translation_t;

/*  y            Down                  Up
 *           ____________            ______
 *          /\    /\    /\          /\    /\
 * -1 ---- /Wn\Nw/Nn\Ne/En\ ------ /Nw\Nn/Ne\
 *        /____\/____\/____\      /____\/____\
 *        \    /\    /\    /     /\    /\    /\
 *  0 ---- \Ww/Ws\--/Es\Ee/ --- /Ww\Wn/--\En/Ee\
 *          \/____\/____\/ \   /____\/____\/____\
 *           \    /\    /   \  \    /\    /\    /
 *  1 ------- \Sw/Ss\Se/ --- \  \Ws/Sw\Ss/Se\Es/
 *             \/____\/ \     \  \/____\/____\/ \
 *                 \     \     \     \     \     \
 *                 -1     0     1     -1     0     1     x
 */
translation_t translations[12][2] = {
	{ {  0, -1, 1 }, {  1, -1, 1 } }, /* Nn */
	{ {  1, -1, 0 }, {  1, -1, 0 } }, /* Ne */
	{ {  1, -1, 1 }, {  1,  0, 1 } }, /* En */
	{ {  1,  0, 0 }, {  1,  0, 0 } }, /* Ee */
	{ {  0,  0, 1 }, {  1,  1, 1 } }, /* Es */
	{ {  0,  1, 0 }, {  0,  1, 0 } }, /* Se */
	{ { -1,  1, 1 }, {  0,  1, 1 } }, /* Ss */
	{ { -1,  1, 0 }, { -1,  1, 0 } }, /* Sw */
	{ { -1,  0, 1 }, { -1,  1, 1 } }, /* Ws */
	{ { -1,  0, 0 }, { -1,  0, 0 } }, /* Ww */
	{ { -1, -1, 1 }, {  0,  0, 1 } }, /* Wn */
	{ {  0, -1, 0 }, {  0, -1, 0 } }  /* Nw */
};

void check_translations() {
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 2; j++) {
			assert(translations[i][j].df == 1 - (i%2));
		}
	}
	for (int i = 0; i < 12; i+=2) {
		assert(translations[i][0].dx == -translations[(i+6)%12][1].dx);
		assert(translations[i][0].dy == -translations[(i+6)%12][1].dy);
		assert(translations[i][1].dx == -translations[(i+6)%12][0].dx);
		assert(translations[i][1].dy == -translations[(i+6)%12][0].dy);
	}
	for (int i = 1; i < 12; i+=2) {
		assert(translations[i][0].dx == translations[i][1].dx);
		assert(translations[i][0].dy == translations[i][1].dy);
		assert(translations[i][0].dx == -translations[(i+6)%12][1].dx);
		assert(translations[i][0].dy == -translations[(i+6)%12][1].dy);
	}

}

/*
 * View from the top
 *
 *       /\
 *  2   /  \   1
 *     / <> \
 *    /______\
 *
 *        0
 */

typedef struct dst_s {
	int dist, dr, p;
} dst_t;

#define DST(a,b,c) &((dst_t){ a, b, c })

/*
 *        _________________________
 *       /C\B   K   A/C\B   K   A/C\
 *      /   \       /   \       /   \
 * 0 - /M S L\L S M/M S L\L S M/M S L\
 *    /       \   /       \   /       \
 *   /A___K___B\C/A___K___B\C/A___K___B\
 *   \B   K   A/C\B   K   A/C\B   K   A/
 *    \       /  \        /   \       /
 * 1 - \L S M/M S L\L S M/M S L\L S M/
 *      \   /       \   /       \   / \
 *       \C/A___K___B\C/A___K___B\C/   \
 *         \B   K   A/C\B   K   A/      \
 *          \       /   \       /        \
 * 2 -----   \L S M/M S L\L S M/          \
 *            \   /       \   / \          \
 *             \C/A___K___B\C/   \          \
 *                     \          \          \
 *                      0          1          2
 */
dst_t *dsts[7][2][12] = { {            /* S */
	{       /* Dn */
		DST(2, 0, K), NULL, NULL, NULL,
		DST(2, 2, M), NULL, NULL, NULL,
		DST(2, 1, L), NULL, NULL, NULL
	}, {    /* Up */
		NULL, NULL, DST(2, 1, L), NULL,
		NULL, NULL, DST(2, 0, K), NULL,
		NULL, NULL, DST(2, 2, M), NULL
	}
}, {                                   /* A */
	{ 	/* Dn */
		DST(1, 1, B), NULL, NULL, NULL,
		DST(1, 2, C), NULL, NULL, NULL,
		DST(1, 0, L), NULL, NULL, NULL
	}, {    /* Up */
		NULL, NULL, DST(1, 0, L), NULL,
		NULL, NULL, DST(1, 1, B), NULL,
		NULL, NULL, DST(1, 2, C), NULL
	}
}, {                                    /* B */
	{ 	/* Dn */
		DST(1, 2, A), NULL, NULL, NULL,
		DST(1, 0, M), NULL, NULL, NULL,
		DST(1, 1, C), NULL, NULL, NULL
	}, { 	/* Up */
		NULL, NULL, DST(1, 1, C), NULL,
		NULL, NULL, DST(1, 2, A), NULL,
		NULL, NULL, DST(1, 0, M), NULL
	}
}, {                                    /* C */
	{ 	/* Dn */
		DST(1, 0, K), NULL, NULL, NULL,
		DST(1, 1, A), NULL, NULL, NULL,
		DST(1, 2, B), NULL, NULL, NULL
	}, {    /* Up */
		NULL, NULL, DST(1, 2, B), NULL,
		NULL, NULL, DST(1, 0, K), NULL,
		NULL, NULL, DST(1, 1, A), NULL
	}
}, {                             /* K */
	{       /* Dn */
		DST(1, 0, C), NULL, NULL,
		DST(1, 2, K), NULL, NULL,
		DST(2, 0, S), NULL, NULL,
		DST(1, 1, K), NULL, NULL
	}, { 	/* Up */
		DST(2, 0, S), NULL, NULL,
		DST(1, 1, K), NULL, NULL,
		DST(1, 0, C), NULL, NULL,
		DST(1, 2, K), NULL, NULL
	}
}, { 			          /* L */
	{ 	/* Dn */
		NULL, NULL, DST(2, 2, S),
		NULL, NULL, DST(1, 1, L),
		NULL, NULL, DST(1, 0, A),
		NULL, NULL, DST(1, 2, L)
	}, { 	/* Up */
		NULL, NULL, DST(1, 0, A),
		NULL, NULL, DST(1, 2, L),
		NULL, NULL, DST(2, 2, S),
		NULL, NULL, DST(1, 1, L)
	}
}, {                              /* M */
	{ 	/* Dn */
		NULL, DST(1, 1, M), NULL,
		NULL, DST(1, 0, B), NULL,
		NULL, DST(1, 2, M), NULL,
		NULL, DST(2, 1, S), NULL
	}, { 	/* Up */
		NULL, DST(1, 2, M), NULL,
		NULL, DST(2, 1, S), NULL,
		NULL, DST(1, 1, M), NULL,
		NULL, DST(1, 0, B), NULL
	}
} };

/*
 * blocking mehod
 *
 *  *--X--X--X--X--X--X--X--X--*
 */
void show_dst(dst_t *d) {
	assert(d);
	printf("dist=%d, dr=%d -> %c\n", d->dist, d->dr, trans_pos[d->p]);
}

/*
 * S: standing on the base of the cage on associated vertex
 *
 * A, B, C: standing on the top of the cage with tip in associated vertex
 *
 * K, L, M: laying on the side with top horizontal bar on associated edge,
 * trangle must have a mirror image in the vertex accross
 */

void decode_state(decoded_state_t *d, state_t *s) {
	assert(d);
	assert(s);
	d->p = s->w%7;
	d->f = s->v%2;
	d->y = s->w/7;
	d->x = s->v/2;
	d->r = s->r;
}

state_t Start = { .v = 9, .w = 0, .r = 0 };
state_t Finish = { .v = 8, .w = 3, .r = 2 };

void encode_state(state_t *s, decoded_state_t *d) {
	assert(d);
	assert(s);
	s->v = 2*d->x + d->f;
	s->w = 7*d->y + d->p;
	s->r = d->r;
}

void apply_translation(decoded_state_t *d, translation_t *t) {
	assert(d);
	assert(t);
	d->x += t->dx;
	d->y += t->dy;
	d->f = (d->f + t->df)%2;
}

void verbose_decoded_state(decoded_state_t *d) {
	printf("n%d%c%d%c%d", d->x, (d->f == 0)?'d':'u', d->y, trans_pos[d->p], d->r);
}

void verbose_state(state_t *s) {
	decoded_state_t d;
	decode_state(&d, s);
	verbose_decoded_state(&d);
}

void print_board(state_t *s) {
	decoded_state_t d;
	if (s) {
		decode_state(&d, s);
		// don't print the board if the state is not allowed
		if (!sa(s)) return;
		verbose_decoded_state(&d);
		printf("\n");
	}
	char s_down[2], s_up[2];
	for (int x = 0; x < SIZE_X; x++) {
		if (grid[0][x][0]) printf("______");
		else printf("      ");
	}
	printf("\n");
	for (int y = 0; y < SIZE_Y; y++) {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3*y + i; j++) {
				putchar(' ');
			}
			for (int x = 0; x < SIZE_X; x++) {
				if (i == 1) {
					s_down[0] = s_down[1] = s_up[0] = s_up[1] = '-';
					if (s && d.x == x && d.y == y) {
						if (d.f == 0) {
							s_down[0] = trans_pos[d.p];
							s_down[1] = '0' + d.r;
						} else {
							s_up[0] = trans_pos[d.p];
							s_up[1] = '0' + d.r;
						}
					}
				}
				if (sg(y, x - 1, 1) || grid[y][x][0]) putchar('\\');
				else if (i == 2 && sg(y+1, x-1, 0)) putchar('_');
				else putchar(' ');
				printf(draw_down[i][grid[y][x][0]], 2, s_down);
				if (grid[y][x][0] || grid[y][x][1]) putchar('/');
				else if (i == 2 && sg(y+1, x, 0)) putchar('_');
				else putchar(' ');
				printf(draw_up[i][grid[y][x][1]][sg(y + 1, x, 0)], 2, s_up);
			}
			if (grid[y][SIZE_X-1][1]) printf("\\");
			printf("\n");
		}
	}
}

void *count_allowed(state_t *s) {
	no_allowed += allowed[s->w][s->v][s->r];
	return NULL;
}

void *initialize_visited(state_t *s) {
	visited[s->w][s->v][s->r] = -1;
	return NULL;
}

void *check_allowed(state_t *s) {
	decoded_state_t d;
	decode_state(&d, s);

	if (!grid[d.y][d.x][d.f]) return NULL;

	//disallow n1u2L1
	//if (d.x == 1 && d.y == 2 && d.p == L && d.f == 1 && d.r == 1) return;

	//disallow n2d2A1
	//if (d.x == 2 && d.y == 2 && d.p == A && d.f == 0 && d.r == 1) return;

	if (d.p == K) {
		if (d.f == 0) {
			if (!sg(d.y + 1, d.x - 1, 1)) return NULL;
		} else { /* d.f == 1 */
			if (!sg(d.y - 1, d.x + 1, 0)) return NULL;
		}
	} else if (d.p == L) {
		if (d.f == 0) {
			if (!sg(d.y - 1, d.x + 1, 1)) return NULL;
		} else { /* d.f == 1 */
			if (!sg(d.y + 1, d.x - 1, 0)) return NULL;
		}
	} else if (d.p == M) {
		if (d.f == 0) {
			if (!sg(d.y - 1, d.x - 1, 1)) return NULL;
		} else { /* d.f == 1 */
			if (!sg(d.y + 1, d.x + 1, 0)) return NULL;
		}
	}

	allowed[s->w][s->v][s->r] = 1;

	return NULL;
}

connection_t *append_connection(state_t *from, state_t *to, int count) {
        connection_t *c;
        c = calloc(1, sizeof(connection_t));
        assert(c);

        c->from = *from;
        c->to = *to;
        c->count = count;
        dllist_init(&c->route);
        no_connections[from->w][from->v][from->r]++;
        no_connections[to->w][to->v][to->r]++;
        dllist_append(&connections, (dllist_elt_t*)c);
        return c;
}

connection_t *find_same() {
        int visit(connection_t *c, state_t *p) {
                if (!compare_states(&c->to, &c->from)) return 0;
                return 1;
        }
        return dllist_iterate(&connections, (int (*)(dllist_elt_t*, void*))visit, NULL);
}

connection_t *find(state_t *A) {
        int visit(connection_t *c, state_t *p) {
                if (!compare_states(p, &c->from)) return 0;
                if (!compare_states(p, &c->to)) return 0;
                return 1;
        }
        return dllist_iterate(&connections, (int (*)(dllist_elt_t*, void*))visit, A);
}

connection_t *find2(state_t *A, state_t *B, connection_t *wrong) {
        int visit(connection_t *c, state_t *p) {
		if (c == wrong) return 1;
                if (!compare_states(A, &c->from) && !compare_states(B, &c->to)) return 0;
                if (!compare_states(B, &c->from) && !compare_states(A, &c->to)) return 0;
                return 1;
        }
        return dllist_iterate(&connections, (int (*)(dllist_elt_t*, void*))visit, A);
}

void remove_connection(connection_t *c) {
        assert(c);
        assert(no_connections[c->from.w][c->from.v] [c->from.r]> 0);
        assert(no_connections[c->to.w][c->to.v][c->to.r] > 0);
        no_connections[c->from.w][c->from.v][c->from.r]--;
        no_connections[c->to.w][c->to.v][c->to.r]--;
	move_t *m = dllist_get_head(&c->route);
	cons[c->from.w][c->from.v][c->from.r][m->dir].r = -1;
	m = dllist_get_tail(&c->route);
	cons[c->to.w][c->to.v][c->to.r][(m->dir+6)%12].r = -1;
        dllist_remove(&c->elt);
}

void *iterate_states(void *(*func)(state_t*)) {
	state_t s;
	void *p;

	for (s.w = 0; s.w < SIZE_Y*7; s.w++) {
		for (s.v = 0; s.v < SIZE_X*2; s.v++) {
			for (s.r = 0; s.r < 3; s.r++) {
				if ((p = func(&s))) return p;
			}
		}
	}

	return NULL;
}

void *show_last(state_t *s) {
	if (visited[s->w][s->v][s->r] == depth - 1) {
		printf("found end state at depth=%d ", depth);
		verbose_state(s);
		printf("\n");
	}
	return NULL;
}

void *visit_next(state_t *s) {
	if (visited[s->w][s->v][s->r] == depth - 1) {
		assert(sa(s));
		printf("found state at depth=%d ", depth - 1);
		verbose_state(s);
		printf("\n");
		for (int i = 0; i < 12; i++) {
			state_t *n = &cons[s->w][s->v][s->r][i];
			if (n->r == -1) continue;
			if (visited[n->w][n->v][n->r] == -1) {
				visited[n->w][n->v][n->r] = depth;
				no_visited++;
				printf("- visited dir %d: ", i);
				verbose_state(n);
				printf("\n");
			}
		}
	}
	return NULL;
}

void *start_state(state_t *s) {
	// if the start state should be allowed
	if (!sa(s)) return NULL;
	iterate_states(initialize_visited);
	visited[s->w][s->v][s->r] = 0;
	int old_no_visited = no_visited = 1;
	printf("starting at ");
	verbose_state(s);
	printf("\n");
	depth = 0;
	do {
		depth++;
		old_no_visited = no_visited;
		iterate_states(visit_next);
	} while (no_visited > old_no_visited);

//	if (depth == 25) {
//		iterate_states(show_last);

		printf("maxdepth=%d\n", depth);
//	}
	return NULL;
}

void *remove_tofro(state_t *s) {
	void *helper(state_t *t) {
		if (compare_states(s, t) <= 0) return NULL;
		connection_t *c1 = find2(s, t, NULL);
		if (!c1) return NULL;
		connection_t *c2 = find2(s, t, c1);
		if (c1 && c2) {
			remove_connection(c2);
			free(c2);
		}
		return NULL;
	};
	return iterate_states(helper);
}

connection_t *find_and_remove_connection(state_t *A) {
        connection_t *c = find(A);
        if (!c) return NULL;

        remove_connection(c);

        return c;
}

void *remove_loops() {
	connection_t *c;

	while ((c = find_same())) {
		remove_connection(c);
		free(c);
	}
	return NULL;
}

void add_connection(state_t *from, state_t *to, dir_t dir) {
        move_t *m = calloc(1, sizeof(move_t));
        assert(m);
        connection_t *c;
	c = append_connection(from, to, 1);
        m->dir = dir;
        dllist_append(&c->route, &m->elt);
}

void remove_state(state_t *s) {
        connection_t *old = find_and_remove_connection(s);
        move_t *m;

        assert(old);
        assert(no_connections[s->w][s->v][s->r] == 0);
        assert(!find(s));

        while ((m = dllist_get_head(&old->route))) {
                dllist_remove(&m->elt);
                free(m);
        }

        free(old);
}
void route_append(dllist_t *d, dllist_t *s) {
        dllist_elt_t *elt;

        while ((elt = dllist_get_head(s)))
                dllist_append(d, dllist_remove(elt));
}

void route_append_reverse(dllist_t *d, dllist_t *s) {
        move_t *m;

        while ((m = dllist_get_tail(s))) {
                m->dir = (m->dir + 6)%12;
                dllist_append(d, dllist_remove(&m->elt));
        }
}

void reverse_connection(connection_t *c) {
        state_t P;
        P = c->from;
        c->from = c->to;
        c->to = P;
}

void merge_connections_at(state_t *P) {
        state_t A, B;
        int rev1, rev2;

        connection_t *old1 = find_and_remove_connection(P);
	if (!compare_states(&old1->to, &old1->from)) {
		free(old1);
		return;
	}
        connection_t *old2 = find_and_remove_connection(P);
        connection_t *new;

        assert(no_connections[P->w][P->v][P->r] == 0);
        assert(old1 && old2);

        // er mag geen derde weg zijn...
        assert(!find(P));

        if (!compare_states(&old1->from, P)) {
                rev1 = 1;
                A = old1->to;
        } else {
                rev1 = 0;
                A = old1->from;
        }
        if (!compare_states(&old2->from, P)) {
                rev2 = 0;
                B = old2->to;
        } else {
                rev2 = 1;
                B = old2->from;
        }

        new = append_connection(&A, &B, old1->count + old2->count);

        if (rev1) route_append_reverse(&new->route, &old1->route);
        else route_append(&new->route, &old1->route);

        if (rev2) route_append_reverse(&new->route, &old2->route);
        else route_append(&new->route, &old2->route);

        free(old1);
        free(old2);
}

void *remove_if_dead_end(state_t *P) {
        if (no_connections[P->w][P->v][P->r] == 1 /*&& compare_states(P, &Start) && compare_states(P, &Finish)*/)
                remove_state(P);

	return NULL;
}

void *merge_if_two(state_t *P) {
	decoded_state_t d;
	decode_state(&d, P);
	//if (d.x == 2 && d.y == 0 && d.p == M && d.f == 1) return NULL;
	//if (d.p == S) return;
        if (no_connections[P->w][P->v][P->r] == 2 /*&& compare_states(P, &Start) && compare_states(P, &Finish)*/)
                merge_connections_at(P);

	return NULL;
}

void *analyze_possible_moves(state_t *s) {
	int verbose = 0;
	state_t new;
	decoded_state_t d;
	if (!allowed[s->w][s->v][s->r]) {
		for (int i = 0; i < 12; i++) {
			cons[s->w][s->v][s->r][i].r = -1;
		}
		return NULL;
	}
	decode_state(&d, s);
	//if (d.x == 3 && d.y == 0 && d.p == S && d.f == 1) verbose = 1;
	//if (d.x == 2 && d.y == 0 && d.p == M && d.f == 1) verbose = 1;
	//if (d.x == 1 && d.y == 3 && d.p == M && d.f == 1) verbose = 1;
	if (verbose == 1) {
		printf("current state:");
		verbose_decoded_state(&d);
		printf("\n");
	}
	for (int i = 0; i < 12; i++) {
		dst_t *dst = dsts[d.p][d.f][i];
		if (!dst) {
			cons[s->w][s->v][s->r][i].r = -1;
			continue;
		}
		if (verbose == 1) {
			printf("proposed move %s: ", trans_dir[i]);
			show_dst(dst);
		}
		for (int j = dst->dist; j > 0; j--) {
			//printf("applying translation dx=%d, dy=%d, df=%d\n", translations[i][d.f].dx, translations[i][d.f].dy, translations[i][d.f].df);
			apply_translation(&d, &translations[i][d.f]);
		}
		d.p = dst->p;
		d.r = (d.r + dst->dr)%3;
		if (verbose == 1) {
			printf("proposed new state: ");
			verbose_decoded_state(&d);
		}
		encode_state(&new, &d);
		if (sa(&new)) {
			cons[s->w][s->v][s->r][i] = new;
			if (verbose == 1)printf(" ALLOWED\n");
			if (compare_states(s, &new) > 0) add_connection(s, &new, i);
		} else {
			cons[s->w][s->v][s->r][i].r = -1;
			if (verbose == 1) printf(" DISALLOWED\n");
		}
		decode_state(&d, s);
	}
	return NULL;
}

void color_node(int x, int y, int f, int p, int r, int c) {
	decoded_state_t d;
	state_t s;
	d.x = x;
	d.y = y;
	d.f = f;
	d.p = p;
	d.r = r;
	encode_state(&s, &d);
	verbose_state(&s);
        printf(" [style=filled,colorscheme=paired12,fillcolor=%d]\n", c);
}

void color_mirror(int x, int y, int f, int p, int r, int c1, int c2) {
	decoded_state_t org, mirror;
	org.x = x;
        org.y = y;
        org.f = f;
        org.p = p;
        org.r = r;
	verbose_decoded_state(&org);
        printf(" [style=filled,colorscheme=paired12,fillcolor=%d]\n", c1);
	mirror_decoded_state(&mirror, &org);
	verbose_decoded_state(&mirror);
        printf(" [style=filled,colorscheme=paired12,fillcolor=%d]\n", c2);
}

pos_t rotate_pos(pos_t p, int n) {
	assert(n >= 0 && n < 3);
	if (p == 0) return p;
	if (p < 4) {
		return (p - 1 + n)%3 + 1;
	}
	return (p - 4 + n)%3 + 4;
}

void color_all(int x, int y, int f, int p, int c) {
	color_node(x, y, f, p, 0, c);
	color_node(x, y, f, p, 1, c);
	color_node(x, y, f, p, 2, c);

// 4d4 -> 4d0 -> 0d4
// 4d3 -> 4d1 -> 1d3
#if 0

	if (f == 1) {
		// 3u4 -> 4u0 -> 0u3
		// 2u4 -> 4u1 -> 1u2
		// 1u4 -> 4u2 
		color_node(y, y - x - 1, f, rotate_pos(p, 1), 0, c);
		color_node(y, y - x - 1, f, rotate_pos(p, 1), 1, c);
		color_node(y, y - x - 1, f, rotate_pos(p, 1), 2, c);
		color_node(y - x - 1, x, f, rotate_pos(p, 2), 0, c);
		color_node(y - x - 1, x, f, rotate_pos(p, 2), 1, c);
		color_node(y - x - 1, x, f, rotate_pos(p, 2), 2, c);
	} else {
		color_node(y, y - x, f, rotate_pos(p, 1), 0, c);
		color_node(y, y - x, f, rotate_pos(p, 1), 1, c);
		color_node(y, y - x, f, rotate_pos(p, 1), 2, c);
		color_node(y - x, x, f, rotate_pos(p, 2), 0, c);
		color_node(y - x, x, f, rotate_pos(p, 2), 1, c);
		color_node(y - x, x, f, rotate_pos(p, 2), 2, c);
	}
#endif
}

void color_sym(int x, int y, int f, int p, int r, int c1, int c2, int c3) {
	color_node(x, y, f, p, r, c1);
	color_node(x, y, f, p, (r+1)%3, c2);
	color_node(x, y, f, p, (r+2)%3, c3);
}

void check_mirror(state_t *o) {
	decoded_state_t org, mirror;;
	int nco, ncm;
	state_t m;
	//if (!allowed[o->w][o->v][o->r]) return;
	decode_state(&org, o);

	mirror_decoded_state(&mirror, &org);

	encode_state(&m, &mirror);
	nco = no_connections[o->w][o->v][o->r];
	ncm = no_connections[m.w][m.v][m.r];

	if (nco != ncm) {
		printf("ASYMMETRY!: ");
		verbose_state(o); printf(" <-> "); verbose_state(&m); printf("\n");
	}
	for (int i = 0; i < 12; i++) {
		if (!dsts[org.p][org.f][i]) continue;
		state_t *odest = &cons[o->w][o->v][o->r][i];
		state_t *mdest = &cons[m.w][m.v][m.r][(i+6)%12];
		decoded_state_t od, md;
		state_t test;
		if (odest->r == -1 && mdest->r == -1) continue;
		if (odest->r == -1 || mdest->r == -1) {
			printf("%s ", trans_dir[i]);
			printf("Asymmetry\n");
			verbose_state(o); printf(" <-> "); verbose_state(&m); printf("\n");
		}
		//verbose_state(odest);
		//printf(" ");
		//verbose_state(mdest);
		decode_state(&md, mdest);
		mirror_decoded_state(&od, &md);
		//verbose_decoded_state(&od);
		encode_state(&test, &od);
		if (test.w != odest->w || test.v != odest->v /*|| test.r != odest->r*/) {
			printf("%s ", trans_dir[i]);
			printf("Asymmetry\n");
			verbose_state(o); printf(" <-> "); verbose_state(&m); printf("\n");
		}
	}
}


int main(int argc, char *argv[]) {
	dllist_init(&connections);

	// sanity check on translations
	check_translations();

	iterate_states(check_allowed);

	iterate_states(count_allowed);
	//printf("no_allowed=%d\n", no_allowed);
	//iterate_states(print_board);
	iterate_states(analyze_possible_moves);
	//iterate_states(start_state);
	//start_state(&Finish);
	//print_board(NULL);
	//exit(0);
	//
	//verbose_state(&s);
	//printf("allowed=%d %d\n", sa(s.w, s.v, s.r), allowed[s.w][s.v][s.r]);
	iterate_states(remove_if_dead_end);
	iterate_states(remove_if_dead_end);
	iterate_states(remove_if_dead_end);
	iterate_states(remove_if_dead_end);
	iterate_states(remove_if_dead_end);
        iterate_states(merge_if_two);
        iterate_states(merge_if_two);
	iterate_states(remove_tofro);
	iterate_states(remove_if_dead_end);
	iterate_states(remove_if_dead_end);
	iterate_states(remove_if_dead_end);
	iterate_states(remove_if_dead_end);
        iterate_states(merge_if_two);
        iterate_states(merge_if_two);
	iterate_states(remove_loops);
	iterate_states(remove_if_dead_end);
	iterate_states(remove_if_dead_end);
	iterate_states(remove_if_dead_end);
        iterate_states(merge_if_two);
	//iterate_states(check_mirror);
	//exit(0);
	//iterate_states(remove_if_dead_end);
        //iterate_states(merge_if_two);
	//iterate_states(remove_if_dead_end);
       // iterate_states(merge_if_two);

	//remove_loops();
//	iterate_states(remove_if_dead_end);
 //       iterate_states(merge_if_two);
//	iterate_states(remove_if_dead_end);
//	iterate_states(remove_tofro);
 //       iterate_states(merge_if_two);
 //       iterate_states(merge_if_two);
//	iterate_states(remove_if_dead_end);
      //  iterate_states(merge_if_two);

        int show(connection_t *c) {
		state_t curr;
                int showroute(move_t *m) {
                        printf("%s", trans_dir[m->dir]);
                        return 1;
                }
		curr = c->from;
		int showroute_verbose(move_t *m) {
                        printf(" [%s] ", trans_dir[m->dir]);
			decoded_state_t d;
			decode_state(&d, &curr);
			dst_t *dst = dsts[d.p][d.f][m->dir];
			for (int j = dst->dist; j > 0; j--) {
                        	apply_translation(&d, &translations[m->dir][d.f]);
                	}
                	d.p = dst->p;
                	d.r = (d.r + dst->dr)%3;
			encode_state(&curr, &d);
			verbose_state(&curr);
			printf(" (%d, %d, %d)", curr.v, curr.w, curr.r);
			return 1;
		}
		printf("// ");
                verbose_state(&c->from);
		printf(" (%d, %d, %d)", c->from.v, c->from.w, c->from.r);
                dllist_iterate(&c->route, (int (*)(dllist_elt_t*, void*))showroute_verbose, NULL);
		printf("\n");
                verbose_state(&c->from);
                printf(" -> ");
                verbose_state(&c->to);
                printf(" [label=");
                dllist_iterate(&c->route, (int (*)(dllist_elt_t*, void*))showroute, NULL);
                printf("]\n");
                return 1;
        }

        printf("digraph {\n");
	//state_t sym000;
	//decoded_state_t d;

/* hexagon with size 2
 *
 *       ________________
 *  0 __ \  /\  /\  /\  /\
 *        \/__\/__\/__\/__\
 *    1 __ \  /\  /\  /\  /\
 *          \/__\/__\/__\/__\
 *      2 __ \  /\  /\  /\  /\
 *            \/__\/__\/__\/__\
 *        3 __ \  /\  /\  /\  /\
 *              \/__\/__\/__\/__\
 *                 \   \   \   \
 *                  0   1   2   3
 */
#if 1
	/* 120 deg symmetry */
	color_all(2, 4, 1, K, 1);
	color_all(4, 1, 1, L, 1);
	color_all(1, 2, 1, M, 1);

	color_all(3, 1, 1, M, 2);
	color_all(1, 3, 1, K, 2);
	color_all(3, 3, 1, L, 2);

	color_all(2, 2, 1, M, 3);
	color_all(2, 3, 1, K, 3);
	color_all(3, 2, 1, L, 3);

	color_all(2, 2, 0, B, 4);
	color_all(2, 4, 0, C, 4);
	color_all(4, 2, 0, A, 4);

	color_all(3, 2, 0, L, 6);
	color_all(2, 3, 0, M, 6);
	color_all(3, 3, 0, K, 6);

	color_all(3, 3, 1, K, 7);
	color_all(3, 1, 1, L, 7);
	color_all(1, 3, 1, M, 7);

	color_all(3, 2, 0, M, 8);
	color_all(2, 3, 0, K, 8);
	color_all(3, 3, 0, L, 8);

	color_all(4, 2, 0, A, 9);
	color_all(2, 2, 0, B, 9);
	color_all(2, 4, 0, C, 9);

	color_all(4, 2, 1, L, 10);
	color_all(2, 1, 1, M, 10);
	color_all(1, 4, 1, K, 10);

	/*
	color_sym(2, 4, 1, K, 0, 1, 2, 3);
	color_sym(3, 1, 1, M, 0, 1, 2, 3);
	color_sym(2, 2, 1, M, 1, 1, 2, 3);
	color_sym(1, 3, 1, M, 2, 1, 2, 3);
	color_sym(2, 1, 1, M, 2, 1, 2, 3);
	color_sym(1, 4, 1, K, 2, 1, 2, 3);
	color_sym(4, 1, 1, L, 0, 1, 2, 3);
	color_sym(4, 2, 1, L, 2, 1, 2, 3);
	color_sym(1, 3, 1, K, 0, 1, 2, 3);
	color_sym(1, 2, 1, M, 0, 1, 2, 3);
	color_sym(2, 2, 0, B, 1, 1, 2, 3);
	color_sym(3, 2, 0, L, 1, 1, 2, 3);
	color_sym(2, 3, 0, K, 1, 1, 2, 3); //
	color_sym(2, 3, 1, K, 1, 1, 2, 3);
	color_sym(3, 3, 1, K, 2, 1, 2, 3);
	color_sym(3, 3, 0, L, 2, 1, 2, 3);
	color_sym(2, 4, 0, C, 1, 1, 2, 3);
	color_sym(3, 3, 1, L, 0, 1, 2, 3);
	color_sym(3, 1, 1, L, 2, 1, 2, 3);
	color_sym(3, 2, 1, L, 1, 1, 2, 3);
	color_sym(4, 2, 0, A, 1, 1, 2, 3);
	color_sym(3, 2, 0, M, 1, 1, 2, 3);
	color_sym(3, 3, 0, K, 0, 1, 2, 3);
	color_sym(2, 3, 0, M, 0, 1, 2, 3);
	*/
//	color_node(4, 0, 1, S, 0, 5);
//	color_node(4, 0, 0, C, 2, 5);
#else
	/* 180 deg symmetrie */
	//color_mirror(3, 5, 1, K, 0, 1, 2);

#endif

#if 0
        /* orientation symmetry */
	color_node(1, 1, 1, K, 0, 1);
	color_node(1, 2, 0, L, 0, 1);
	color_node(2, 2, 0, L, 1, 1);
	color_node(1, 2, 1, K, 1, 1);
	color_node(2, 2, 0, K, 2, 1);
	color_node(1, 3, 0, M, 1, 1);
	color_node(2, 1, 0, K, 0, 1);
	color_node(3, 1, 0, M, 0, 1);
	color_node(2, 0, 0, K, 0, 1);
	color_node(1, 1, 1, L, 0, 1);
	color_node(2, 1, 1, L, 1, 1);

	color_node(1, 1, 1, K, 1, 2);
	color_node(1, 2, 0, L, 1, 2);
	color_node(2, 2, 0, L, 2, 2);
	color_node(1, 2, 1, K, 2, 2);
	color_node(2, 2, 0, K, 0, 2);
	color_node(1, 3, 0, M, 2, 2);
	color_node(2, 1, 0, K, 1, 2);
	color_node(3, 1, 0, M, 1, 2);
	color_node(2, 0, 0, K, 1, 2);
	color_node(1, 1, 1, L, 1, 2);
	color_node(2, 1, 1, L, 2, 2);

	color_node(1, 1, 1, K, 2, 3);
	color_node(1, 2, 0, L, 2, 3);
	color_node(2, 2, 0, L, 0, 3);
	color_node(1, 2, 1, K, 0, 3);
	color_node(2, 2, 0, K, 1, 3);
	color_node(1, 3, 0, M, 0, 3);
	color_node(2, 1, 0, K, 2, 3);
	color_node(3, 1, 0, M, 2, 3);
	color_node(2, 0, 0, K, 2, 3);
	color_node(1, 1, 1, L, 2, 3);
	color_node(2, 1, 1, L, 0, 3);

	color_node(0, 2, 0, L, 0, 6);
	color_node(0, 2, 0, L, 1, 6);
	color_node(0, 2, 0, L, 2, 6);
#endif

/*	color_node(2, 2, 0, K, 0, 4);
	color_node(2, 1, 1, L, 0, 4);

	color_node(2, 2, 0, K, 1, 5);
	color_node(2, 2, 0, K, 2, 6);
	color_node(1, 1, 1, L, 0, 7);
	color_node(1, 1, 1, L, 1, 8);
	color_node(1, 1, 1, L, 2, 9);
	color_node(2, 2, 0, L, 0, 10);
	color_node(2, 2, 0, L, 1, 11);
	color_node(2, 2, 0, L, 2, 12);*/
/*
	d.x = 1;
	d.y = 1;
	d.f = 1;
	d.p = K;
	d.r = 0;
	encode_state(&sym000, &d);
	verbose_state(&sym000);
        printf(" [style=filled,colorscheme=paired12,fillcolor=1]\n");

	d.x = 1;
	d.y = 1;
	d.f = 1;
	d.p = K;
	d.r = 1;
	encode_state(&sym000, &d);
	verbose_state(&sym000);
        printf(" [style=filled,colorscheme=paired12,fillcolor=2]\n");

	d.x = 1;
	d.y = 1;
	d.f = 1;
	d.p = K;
	d.r = 2;
	encode_state(&sym000, &d);
	verbose_state(&sym000);
        printf(" [style=filled,colorscheme=paired12,fillcolor=3]\n");
	*/

	/*
	d.x = 2;
	d.y = 2;
	d.f = 0;
	d.p = K;
	d.r = 0;
	encode_state(&sym000, &d);
	verbose_state(&sym000);
        printf(" [style=filled,colorscheme=paired12,fillcolor=4]\n");
	*/

        //print_state(&F);
        //printf(" [style=filled,fillcolor=red]\n");
        dllist_iterate(&connections, (int (*)(dllist_elt_t*, void*))show, NULL);
        printf("}\n");

	exit(0);
}