/* $Id$ */

/*

"Quadrati magici" (IOI 1996)
Copyright (C) 2000 Massimo Santini

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

*/

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

#define CONFLEN   8
#define MAXCONF   40320

/* macro che scambia il valore dei suoi argomenti */
#define swap(a,b) { (a) ^= (b); (b) ^= (a); (a) ^= (b); }

typedef char conf[CONFLEN + 1];
typedef void (*transfun)( conf );

/* strutture dati che conservano le configurazioni ed il loro numero */
conf allconf[MAXCONF];
int confnum;

/* dati necessari alal generazione delle permutazioni */
char id, val[CONFLEN + 2];

void applyA( conf c )
{
	swap( c[0], c[7] );
	swap( c[1], c[6] );
	swap( c[2], c[5] );
	swap( c[3], c[4] );
}

void applyB( conf c )
{
	swap( c[0], c[1] );
	swap( c[2], c[3] );
	swap( c[0], c[2] );
	swap( c[4], c[5] );
	swap( c[6], c[7] );
	swap( c[5], c[7] );
}

void applyC( conf c )
{
	swap( c[1], c[6] );
	swap( c[2], c[6] );
	swap( c[6], c[5] );
}

transfun transf[3] = { applyA, applyB, applyC };

/* mette in c la configurazione iniziale */
void iniconf( conf c )
{
	int i;

	for ( i = 0; i < CONFLEN; i++ ) c[i]='1'+i;
	c[i] = '\0';
}

/* compara due configurazioni, serve per l'ordinamento e la ricerca*/
int cmpconf( const void *k, const void *c )
{
	return strncmp( *(conf *)k, *(conf *)c, CONFLEN );
}

/* dalla configurazione alla posizione nell'array, usando la ricerca dicotomica */
int conf2pos( conf c )
{
	return ((conf *)bsearch( c, allconf, confnum, sizeof(conf), cmpconf ) - (conf *)allconf);
}

/* generazione delle permutazioni, vedi "Algoritmi in C", pag. 657 */
void genperm( int k )
{
	int t;

	val[k] = ++id + '0';
	if ( id == CONFLEN ) strcpy( allconf[confnum++], &(val[1]) );
	for ( t = 1; t <= CONFLEN; t++ )
		if ( val[t] == '0' ) genperm( t );
	id--;
	val[k] = '0';
}

int main( void )
{
	conf t;
	int i;
	FILE *out;

	if ( (out = fopen( "auto.c", "w" )) == NULL ) {
		fprintf( stderr, "non posso aprire auto.c\n" );
		exit( EXIT_FAILURE );
	}

	/* genera il vettore ordinato di tutte le configurazioni */
	for ( i = 0; i <= CONFLEN; i++ ) val[i] = '0';
	confnum = 0;
	id = -1;
	genperm( 0 );
	qsort( allconf, confnum, sizeof( conf ), cmpconf );

	/* scrive il vettore delle configurazioni */ 
	fprintf( out, "#define CONFNUM %d\n\n", confnum );
	fprintf( out, "char *pos2conf[CONFNUM] = {\n" ); 
	for ( i = 0; i < confnum ; i++ )
		fprintf( out, "\t\"%s\"%s \n", allconf[i], i < confnum - 1 ? "," : ""  );
	fprintf( out, "};\n\n" );

	/* scrive la parte utile della matrice di adiacenza */ 
	fprintf( out, "int adj[CONFNUM][3] = {\n" ); 
	for ( i = 0; i < confnum ; i++ ) {
		strncpy( t, allconf[i], CONFLEN );
		applyA( t );
		fprintf( out, "\t{ %d, ", conf2pos( t ) );
		strncpy( t, allconf[i], CONFLEN );
		applyB( t );
		fprintf( out, "%d, ", conf2pos( t ) );
		strncpy( t, allconf[i], CONFLEN );
		applyC( t );
		fprintf( out, "%d }%s\n ", conf2pos( t ), i < confnum -1 ? "," : "" );
	}
	fprintf( out, "};\n" );

	fclose( out );

	printf( "ho generato il file 'auto.c' con %d configurazioni\n", confnum );

	return 0;
}