//	pentaminos
//	Patrice Torchet
//	Borland C++ 3.1

//	D‚sol‚ pour les comentaires, j'ai fait ce programme … la va vite
//	Mais ce coup ci il est structur‚.

//	version avec encodage du motif

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

//	affiche le tableau r‚sultat sur une ligne
#define	EN_LIGNE

//	calcul avec F pour filtrer les symtriques
//	pas defini pour un filtrage partiel avec X qui est un cas sp‚cial
// simplifiant les traitements
//	#define	SYM_F

	//	tableau de r‚f‚rence des pentaminos
	//	contient la lettre de r‚f‚rence et les coordonn‚es des cases
char	penta_ref [12][12] = {
#ifdef	SYM_F
			{'F',0,1,0,2,1,0,1,1,2,1},
			{'I',0,0,1,0,2,0,3,0,4,0},
			{'L',0,0,1,0,2,0,3,0,3,1},
			{'N',0,1,1,0,1,1,2,0,3,0},
			{'P',0,0,0,1,1,0,1,1,2,0},
			{'T',0,0,0,1,0,2,1,1,2,1},
			{'U',0,0,0,1,1,0,2,0,2,1},
			{'V',0,0,1,0,2,0,2,1,2,2},
			{'W',0,0,1,0,1,1,2,1,2,2},
			{'X',0,1,1,0,1,1,1,2,2,1},
			{'Y',0,1,1,0,1,1,2,1,3,1},
			{'Z',0,0,0,1,1,1,2,1,2,2}};
#else
			{'X',0,1,1,0,1,1,1,2,2,1},
			{'F',0,1,0,2,1,0,1,1,2,1},
			{'I',0,0,1,0,2,0,3,0,4,0},
			{'L',0,0,1,0,2,0,3,0,3,1},
			{'N',0,1,1,0,1,1,2,0,3,0},
			{'P',0,0,0,1,1,0,1,1,2,0},
			{'T',0,0,0,1,0,2,1,1,2,1},
			{'U',0,0,0,1,1,0,2,0,2,1},
			{'V',0,0,1,0,2,0,2,1,2,2},
			{'W',0,0,1,0,1,1,2,1,2,2},
			{'Y',0,1,1,0,1,1,2,1,3,1},
			{'Z',0,0,0,1,1,1,2,1,2,2}};
#endif

typedef	struct	{char	car[22];} ligne;
ligne	penta_map [6];

typedef	struct	{int	larg;
						int	haut;
						int	prem;
						int	dummy;
						long	motif;} p_sym ;

typedef	struct	{int	lettre;
						int	dispo;
						int	col;
						int	row;
						long	motif;
						long	masq;
						p_sym	sym [9];} p_dev ;
p_dev	penta_dev [12];

int	pntr_sol;

int	haut, larg, vertical;
int	penta_sym_l_max, penta_sym_c_max, penta_sym_lr_max, penta_sym_cr_max;

	//************************************************************
	//	affichage des pi‚ces de base pour contr“le visuel
void penta_ctrl ()
	{
	int	scan, scan2;

	for (scan=0; scan<12; scan++)
		{
		gotoxy(scan*6+1,1);cprintf("%c", penta_ref[scan][0]);
		for (scan2=1; scan2<11; scan2 +=2)
			{
			gotoxy(scan*6+1+penta_ref[scan][scan2+1],3+penta_ref[scan][scan2]);
			cprintf("%c", penta_ref[scan][0]);
			}
		}
	}

	//************************************************************
	//	affichage d'un tableau r‚sultat

void	penta_list ()
	{
	int	x;
	long	tmp;
	char	l;
	p_dev	*dev;
	ligne *str;

#ifndef	SYM_F
	//	post filtrage des sym‚triques
	// quand X est sur une ligne ou colonne m‚diane
	//	j'utilise l'orientation de F pour lever le doute
	if ((penta_sym_lr_max==1) && (penta_dev[0].row == penta_sym_l_max) &&
		( (penta_dev[1].motif==penta_dev[1].sym[2].motif) || (penta_dev[1].motif==penta_dev[1].sym[3].motif) ||
		  (penta_dev[1].motif==penta_dev[1].sym[6].motif) || (penta_dev[1].motif==penta_dev[1].sym[7].motif) ))
		{return;}

	if ((penta_sym_cr_max==1) && (penta_dev[0].col == penta_sym_c_max) &&
		( (penta_dev[1].motif==penta_dev[1].sym[1].motif) || (penta_dev[1].motif==penta_dev[1].sym[3].motif) ||
		  (penta_dev[1].motif==penta_dev[1].sym[5].motif) || (penta_dev[1].motif==penta_dev[1].sym[7].motif) ))
		{return;}
#endif
	//	compter la solution
	pntr_sol ++;

	//	remplissage du tableau r‚sultat
	for (dev=&penta_dev[0]; dev < &penta_dev[12]; dev++)
		{
		x= larg- (*dev).col;
		l= (*dev).lettre;	//	lettre
		str=&penta_map[(*dev).row];

		for (tmp= (*dev).motif; tmp != 0; tmp = tmp>>1)
			{
			if (tmp&1)	{ (*str).car[x]= l; }
			str++;
			if (str == &penta_map[6])
				{ str=&penta_map[0]; x++; }
			}
		}

	//	pas de compteur, c'est une course de vitesse
	// gotoxy(5,12);
	// cprintf("%d", pntr_sol);

	//	affichage tableau r‚sultat
	for (str=&penta_map[haut-1]; str>&penta_map[0]; str--)
#ifdef	EN_LIGNE
		{ printf("%s ", str); }
	printf("%s\n", str);
#else
		{ printf("%s\n", str); }
	printf("%s\n\n", str);
#endif
	}

	//************************************************************
	//	calcul remplissage
void	penta_calc (p_dev *piece, int col, int cel)
	{
#ifdef	SYM_F
	int	scan_o;
#endif
	int	col_new, cel_new;
	long	dummy;
	p_dev	*dev;
	p_sym	*sym;

	//	c'est avec F que je g‚re les sym‚tries
	//	chercher	'F' en tant que cas sp‚cial
	if (penta_dev[0].dispo==0)	//	pi‚ce disponible
		{
		//	shunter si 'F' pas … gauche
		if (col < penta_sym_c_max) {return;}

#ifdef	SYM_F
		for (scan_o=0, sym=&penta_dev[0].sym[0]; scan_o<8; scan_o++, sym++)
#else
		sym=&penta_dev[0].sym[0];
#endif
			{
			if ( (cel-(*sym).prem >= 0) && (cel-(*sym).prem <= penta_sym_l_max))
				{
#ifdef	SYM_F
				//	shunter les retournements sur ligne et colone m‚diane (dimension impaire)
				if (((penta_sym_lr_max==0) || (cel-(*sym).prem < penta_sym_l_max) || ((scan_o & 2)==0 )) &&
					 ((penta_sym_cr_max==0) || (col             > penta_sym_c_max) || ((scan_o & 1)==0 )))
#endif
					{
					//	dimension acceptable
					if (((*piece).masq & ((*sym).motif << (cel-(*sym).prem)))==0)
						{
						(*(piece+1)).masq = (*piece).masq | ((*sym).motif << (cel-(*sym).prem));

						penta_dev[0].col= col;
						penta_dev[0].row= cel- (*sym).prem;
						penta_dev[0].motif= (*sym).motif;

						penta_dev[0].dispo= 1;

						cel_new= cel+1;
						col_new= col;
						while (((*(piece+1)).masq & vertical) == vertical)
							{
							(*(piece+1)).masq= (*(piece+1)).masq >> 6;
							cel_new= 0;
							col_new --;
							}
						for (dummy= ((*(piece+1)).masq >> cel_new); (dummy & 1); dummy= dummy >> 1, cel_new++) {}

						penta_calc(piece+1, col_new, cel_new);

						penta_dev[0].dispo=0;
						}
					}
				}
			}
		}

	//	chercher	autres lettres
	for (dev=&penta_dev[1]; dev < &penta_dev[12]; dev++)
		{
		if ((*dev).dispo==0)	//	pi‚ce disponible
			{
			for (sym=&((*dev).sym[0]); (col > (*sym).larg); sym++)
				{
				if ((cel- (*sym).prem >= 0) && (cel- (*sym).prem+ (*sym).haut < haut))
					{
					if (((*piece).masq & ((*sym).motif << (cel-(*sym).prem)))==0)
						{
						//	dimension acceptable
						(*dev).col= col;
						(*dev).row= cel- (*sym).prem;
						(*dev).motif= (*sym).motif;
						(*dev).dispo= 1;

						if (piece ==&penta_dev[11])
							{ penta_list(); }
						else
							{

							(*(piece+1)).masq = (*piece).masq | ((*sym).motif << (cel-(*sym).prem));

							cel_new= cel+1;
							col_new= col;
							while (((*(piece+1)).masq & vertical) == vertical)
								{
								(*(piece+1)).masq= (*(piece+1)).masq >> 6;
								cel_new= 0;
								col_new --;
								}
							for (dummy= ((*(piece+1)).masq >> cel_new); (dummy & 1); dummy= dummy >> 1, cel_new++) {}

							penta_calc(piece+1, col_new, cel_new);

							}
						(*dev).dispo=0;
						}
					}
				}
			}
		}
	}

	//************************************************************
	//	calcul remplissage
void	penta_calc_init ()
	{
	int	scan, scan_m, scan_l, ht, lr, x, y;
	p_dev	*dev;

	//	calcul des clef d'‚limination des sym‚triques
	penta_sym_lr_max = haut & 1;
	penta_sym_l_max  = (haut+ penta_sym_lr_max) / 2 - 2;
	penta_sym_cr_max = larg & 1;
	penta_sym_c_max  = (larg- penta_sym_cr_max) / 2 + 2;

	vertical= ((1<<haut)-1);

	//	init des fins de chaines pour les tableaux r‚sultat
	for (scan_l=0; scan_l<haut; scan_l++)
		{
		penta_map[scan_l].car[larg]=0;
		}

	pntr_sol=0;

	for (scan=0, dev=&penta_dev[0]; scan<12; scan++, dev++)
		{
		(*dev).lettre=penta_ref[scan][0];
		(*dev).dispo=0;
		(*dev).masq=0;
		for (scan_l=0; scan_l <8; scan_l ++)
			{
			(*dev).sym[scan_l].motif=0;
			(*dev).sym[scan_l].prem=6;
			}

		//	calcul dimension figure
		lr=0; ht=0;
		for (scan_m=1; scan_m <11; scan_m +=2)
			{
			if (ht < penta_ref[scan][scan_m  ]) {ht = penta_ref[scan][scan_m  ];}
			if (lr < penta_ref[scan][scan_m+1]) {lr = penta_ref[scan][scan_m+1];}
			}
		for (scan_m=0; scan_m <4; scan_m++)
			{ (*dev).sym[scan_m].haut=ht; (*dev).sym[scan_m].larg=lr; }
		for (        ; scan_m <8; scan_m++)
			{ (*dev).sym[scan_m].haut=lr; (*dev).sym[scan_m].larg=ht; }

		//	construire dessin de la pi‚ce et sym‚tries
		for (scan_m=1; scan_m <11; scan_m +=2)
			{
			x=	penta_ref[scan][scan_m  ];
			y= penta_ref[scan][scan_m+1];

			(*dev).sym[0].motif |= 1L << (x    +y*6);
			(*dev).sym[2].motif |= 1L << (ht- x+y*6);

			(*dev).sym[1].motif |= 1L << (x    +(lr- y)*6);
			(*dev).sym[3].motif |= 1L << (ht- x+(lr- y)*6);

			//	appliquer sym‚trie diagonale sur les quatres premiŠres
			(*dev).sym[4].motif |= 1L << (y    +x*6);
			(*dev).sym[6].motif |= 1L << (lr- y+x*6);

			(*dev).sym[5].motif |= 1L << (y    +(ht- x)*6);
			(*dev).sym[7].motif |= 1L << (lr- y+(ht- x)*6);

			if (y == 0)
				{
				if ((*dev).sym[0].prem > x)		{(*dev).sym[0].prem= x;}
				if ((*dev).sym[2].prem > ht-x)	{(*dev).sym[2].prem= ht- x;}
				}
			if (y == lr)
				{
				if ((*dev).sym[1].prem > x)		{(*dev).sym[1].prem= x;}
				if ((*dev).sym[3].prem > ht-x)	{(*dev).sym[3].prem= ht- x;}
				}
			if (x == 0)
				{
				if ((*dev).sym[4].prem > y)		{(*dev).sym[4].prem= y;}
				if ((*dev).sym[6].prem > lr-y)	{(*dev).sym[6].prem= lr- y;}
				}
			if (x == ht)
				{
				if ((*dev).sym[5].prem > y)		{(*dev).sym[5].prem= y;}
				if ((*dev).sym[7].prem > lr-y)	{(*dev).sym[7].prem= lr- y;}
				}
			}
		//	‚liminer les doublons
		for (scan_m=0; scan_m <7; scan_m ++)
			{
			if ((*dev).sym[scan_m].larg != 30)
				{
				for (scan_l=scan_m+1; scan_l <8; scan_l ++)
					{
					if(((*dev).sym[scan_m].motif == (*dev).sym[scan_l].motif))
						{
						(*dev).sym[scan_l].larg=30;
						}
					}
				}
			}
		//	condenser les figures utilisables
		for (scan_l=0, scan_m=0; scan_l <8; scan_l ++)
			{
			if ((scan_l != scan_m) && ((*dev).sym[scan_l].larg != 30))
				{
				(*dev).sym[scan_m].larg     = (*dev).sym[scan_l].larg;
				(*dev).sym[scan_m].haut     = (*dev).sym[scan_l].haut;
				(*dev).sym[scan_m].prem     = (*dev).sym[scan_l].prem;
				(*dev).sym[scan_m].motif    = (*dev).sym[scan_l].motif;
				(*dev).sym[scan_l].larg     = 30;
				}
			if ((*dev).sym[scan_m].larg != 30) { scan_m++; }
			}
	 	(*dev).sym[8].larg     = 30;
		}
	}

	//************************************************************
	//	c'est supos‚ permettre le CTRL-C pendant l'‚x‚cution
int c_break(void)
	{
	gotoxy(1,20); cprintf("Abandon ...\n");
	return (0);
	}

	//************************************************************
void	main (int argc, char *argv[])
	{
	struct  time t_db, t_fn;	// pour le chronom‚trage
	char	*dummy;

	ctrlbrk(c_break);

	//	‚ffacer l'‚cran
	// clrscr();

	if (argc==1)
		{
		puts("exe hauteur \>soluces.txt\n");
		return;
		}
	haut=strtol(argv[1], &dummy, 10);
	if (haut<3 || haut>6)	{ haut=3; }
	larg= 60/haut;

	//	controle dessin des figures : facultatif
	// penta_ctrl();

	// top d‚but
	gettime(&t_db);

	//	initialisation
	penta_calc_init();
	//	remplissage rectangle
	penta_calc(&penta_dev[0], larg, 0);

	// top fin
	gettime(&t_fn);

	// calcul du temps d'‚x‚cution
	if ( t_fn.ti_hund < t_db.ti_hund ) { t_fn.ti_hund += 100; t_db.ti_sec++; }
	t_fn.ti_hund -= t_db.ti_hund;
	if ( t_fn.ti_sec  < t_db.ti_sec  ) { t_fn.ti_sec  +=  60; t_db.ti_min++; }
	t_fn.ti_sec  -= t_db.ti_sec ;
	if ( t_fn.ti_min  < t_db.ti_min  ) { t_fn.ti_min  +=  60; t_db.ti_hour++; }
	t_fn.ti_min  -= t_db.ti_min ;
	if ( t_fn.ti_hour < t_db.ti_hour ) { t_fn.ti_hour +=  24; }
	t_fn.ti_hour -= t_db.ti_hour;

	fprintf(stderr, "%d solutions en : %02d.%02d secondes\n", pntr_sol, t_fn.ti_sec, t_fn.ti_hund);
	}