/******************************************************************************
 * 神経衰弱の先手・後手の勝率をを調べるプログラム                             *
 *                                                                            *
 * ver 0.10 とりあえず思いついたままのコーディング    2001.12.12. H.Hasegawa  *
 ******************************************************************************/

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

#define		MAX_PAIR_NUM	26

#ifndef	TRUE
#define	TRUE	(1==1)
#endif
	
#ifndef	FALSE
#define	FALSE	!(1==1)
#endif

#define	STATE_UNKNOWN	(1)
#define	STATE_KNOWN		(2)
#define	STATE_FIRST		(4)
#define	STATE_SECOND	(8)

/*
 *
 * 【方針】
 *  カードのすべての配列を考える。
 *  先手，後手ともに戦略は
 *		・オープンされたカードの中にペアがあればそれを開いて取る
 *		・ペアがなければ新たに１枚開く
 *			開けたものが、過去にオープンされたものと同じならばそれをとる
 *			開けたものが、今まで知っているリストになければ、もう１枚新たにあける
 *	これを繰り返す。
 *	すべてのカードがとられたら終わり
 *
 * 【データ構造】
 *  ・カード：No.0〜No.2N-1 までの 2N枚。
 *		最後のビットをマスクしたパターンが同じならばペアであるとみなす。
 *
 *  ・リスト
 *		シャッフルされた（順列として生成された）カード配列。
 *
 *	・状態
 *		STATE_UNKNOWN		カードの数値を知らない
 *		STATE_KNOWN			カードの数値は既知である（オープンしたが取られていないカード）
 *		STATE_FIRST			先手が取ったカードである
 *		STATE_SECOND		後手が取ったカードである
 */

/**************************************************************************
 *	a と b がペアなら TRUE を返す
 **************************************************************************/
int is_pair(int a, int b)
{
	if ( (a&0xfffe)	== (b&0xfffe) )
		return TRUE;
	return  FALSE;
}


/**************************************************************************
 *	state 配列を調べて、known & unknown の数（取られていない数）を数える
 **************************************************************************/
int count_not_taken_num(int *state, int length)
{
	int num;
	int i;

	num=0;
	for ( i=0 ; i < length ; i++ )
	{
		if ( state[i] == STATE_KNOWN )
			num++;
		if ( state[i] == STATE_UNKNOWN )
			num++;
	}
	return num;
}

/**************************************************************************
 *	state 配列を調べて、statevalue の数を数える
 **************************************************************************/
int count_statevalue_num(int *state, int length, int statevalue)
{
	int num;
	int i;

	num=0;
	for ( i=0 ; i < length ; i++ )
	{
		if ( state[i] == statevalue )
			num++;
	}
	return num;
}




/*********************************************************************************************
 *	STATE_KNOWN の中に、value とペアになるカードがあれば、その位置（配列のオフセット）を返す。
 *  なければ　-1 を返す。
 *********************************************************************************************/
int search_pair_pos(int *list, int *state, int length, int value)
{
	int i;

	for ( i=0 ; i < length ; i++ ) {
		if ( state[i] != STATE_KNOWN ) continue;
		if ( list[i] == value ) continue;
		if ( is_pair( value, list[i] ) )
			return i;
	}
	return -1;
}



/*********************************************************************************************
 *	このアルゴリズムでは、手番がきたときに既知のペアがあるとすれば、それは配列の位置が
 *  一番後ろのものである。そこで、known のもので一番後ろの位置を返す
 *********************************************************************************************/
int search_last_known_pos(int *state, int length)
{
	int i;

	for ( i=length-1 ; i >=0 ; i-- )
	{
		if ( state[i] == STATE_KNOWN )
			return i;
	}
	return -1;
}

/*********************************************************************************************
 * 上記の逆：まだオープンしていない最初のカードを探す
 *********************************************************************************************/
int search_first_unknown_pos(int *state, int length)
{
	int i;

	for ( i=0 ; i < length ; i++ )
	{
		if ( state[i] == STATE_UNKNOWN )
			return i;
	}
	return -1;
}


/*********************************************************************************************
 * 自分の手番のときの処理
 *********************************************************************************************/
void play(int *list, int *state, int length, int statevalue)
{
	int pos, new_pos;
	int value;
	int pair_pos;

	/* step 1 : 既知のpair があるか？ */
	pos = search_last_known_pos(state, length);
	if ( pos > 0 ) {
		value = list[pos];
		pair_pos = search_pair_pos(list, state, length, value);
		if ( pair_pos >= 0 ) {
			state[pos] = state[pair_pos] = statevalue;
		}
	}

	/* step 2 : 未知の１枚目を開ける。*/
	for (;;) {
		pos = search_first_unknown_pos(state, length);
		if ( pos < 0 ) break;	/* もう未知のカードはないなら脱出 */

		value = list[pos];
		pair_pos = search_pair_pos(list, state, length, value);
		if ( pair_pos >= 0 ) {	/* １枚目に開けたカードのペアを知っている */
			state[pos] = state[pair_pos] = statevalue;
		}
		else {					/* １枚目のペアをしらないので、もう１枚開ける */
			state[pos]=STATE_KNOWN;
			new_pos = search_first_unknown_pos(state, length);
			if ( is_pair( list[pos], list[new_pos] ) ) {
				state[pos] = state[new_pos] = statevalue;
			}
			else {
				state[pos] = state[new_pos] = STATE_KNOWN;
				return;
			}
		}
	}
}


/*********************************************************************************************
 *	リストの評価。length はリストの長さ。（Ｎペアあったとき、length は２Ｎになる。）
 *  result には、先手、後手が取ったペアの数を入れる
 *********************************************************************************************/
int eval_list(int *list, int length, int *result)
{
	static int state[MAX_PAIR_NUM*2];
	int i;

	for ( i=0 ; i < length ; i++ )
		state[i] = STATE_UNKNOWN;

	for ( i=0 ;; i++ ){
		play(list, state, length, STATE_FIRST);
		if ( count_not_taken_num( state, length ) == 0 )
			break;
		play(list, state, length, STATE_SECOND);
		if ( count_not_taken_num( state, length ) == 0 )
			break;
	}

	result[0] = count_statevalue_num(state, length, STATE_FIRST) / 2;
	result[1] = count_statevalue_num(state, length, STATE_SECOND) / 2;

	return i;
}

/*********************************************************************************************
 * 以下は、カードの順列をグローバル配列に生成する処理。
 *********************************************************************************************/
int Counter;
int Length;
int List[MAX_PAIR_NUM*2];
int OK_flg[MAX_PAIR_NUM*2];
int Win1st, Win2nd, Even;

void init()
{
	Counter=0;
	Win1st = Win2nd = Even = 0;
}


void check()
{
	int result[2];

	Counter++;
	eval_list( List, Length, result);
	if ( result[0] > result[1] )
		Win1st++;
	else if ( result[0] < result[1] )
		Win2nd++;
	else
		Even++;
}

void show()
{
	int i;
	Counter++;
	printf("%5d: ",Counter);
	for ( i=0 ; i < Length ; i++ ) {
		printf(" %d",List[i]);
	}
	printf("\n");
}


void gen(int pos, int val)
{
	int j;

	List[pos] = val;
	if ( pos == (Length-1) ) {
//		show();
		check();
	}
	else {
		OK_flg[val] = -1;
		for ( j=0 ; j < Length ; j++ ) {
			if ( OK_flg[j] > 0 ) {
				gen( pos+1, j);
			}
		}
		OK_flg[val] = 1;
	}
}


void eval(int length)
{
	int i;

	Length = length;
	for ( i=0 ; i < length ; i++ )
		OK_flg[i] = 1;
	for ( i=0 ; i < length ; i++ )
		gen(0,i);
}

void result()
{
	printf(" Win1st=%d, Win2nd=%d, Even=%d\n",Win1st, Win2nd, Even);
}

/*********************************************************************************************
 *
 *********************************************************************************************/
int main(int argc, char **argv)
{
	int pair;

	if ( argc != 2 ) {
		printf(" usage : test1 pair-num(< %d)\n", MAX_PAIR_NUM);
		return 1;
	}

	pair = atoi( argv[1] );
	if ( pair < 1 || MAX_PAIR_NUM < pair ) {
		printf(" pair num must be lower than %d\n",MAX_PAIR_NUM);
		return 1;
	}
	init();
	eval( pair*2 );
	result();

	return 0;
}