/* Very compact tic-tac-toe program.
   Written by: Frans Faase for comp.programming.contests

   Original contest description by John Tromp:

     I wonder how long a program has to be in order to play a perfect game
     of tic-tac-toe. To fix matters, let's assume the program always goes
     second. The human inputs are simply a single digit (1-9) followed by enter,
     while the program's response should also be a single digit followed by
     newline. The 9th move, which gets to be played by the human, is fixed,
     and simply omitted from input. The program should never let the human
     win, of course.
     For simplicity we'll only require the program to assure a draw.
     In fact, it may continue playing after getting 3 in a row of its own,
     ignoring this if it manages to make for a smaller program.

     So we want a program that does 4 rounds of
       reading an input digit followed by enter
       writing an output digit
     which, including the forced 9th move, represents all 9 different
     moves in which the human has no three in a row.

     If you want to detect computer wins and stop the game, that's fine too,
     but I suspect that lenghtens the source.


  Select version, by adding/removing NO_: */

#define NO_COMPACT            
#define PRINT_BOARD     
#define PRINT_OUTCOME
#define NO_DEBUG           /* Only for NO_COMPACT */ 



#ifdef COMPACT
#ifndef PRINT_BOARD
#ifndef PRINT_OUTCOME

/* Most compact version: only asks for input 4 times, and only prints reply. */

w(b){return!(b&7&&b&56&&b&448&&b&73&&b&146&&b&292&&b&273&&b&84);}v(int a,int b,
int *m){int i=0,e,k,c=5,n;if(w(~a))c=4;else{for(;i<9;i++)if(!(a&(k=1<<i)||b&k)
&&c>(e=5-v(b|k,a,&n)))c=e,*m=i;if(c>4)c=3;c-=(c>1);}return c;}main(){int a=0,b=
0,d,l=0;for(;l<4;l++){a|=1<<(getchar()-'1');getchar();if(w(~a))break;v(a,b,&d);
printf("%d\n",d+1);b|=1<<d;if(w(~b))break;}} 

#else /* PRINT_OUTCOME */

/* Prints the outcome of the game (asks 5 times for input) */

w(b){return!(b&7&&b&56&&b&448&&b&73&&b&146&&b&292&&b&273&&b&84);}v(int a,int b,
int *m){int i=0,e,k,c=5,n;if(w(~a))c=4;else{for(;i<9;i++)if(!(a&(k=1<<i)||b&k)
&&c>(e=5-v(b|k,a,&n)))c=e,*m=i;if(c>4)c=3;c-=(c>1);}return c;}main(){int a=0,b=
0,d,l=0;for(;l<5;l++){a|=1<<(getchar()-'1');getchar();if(w(~a)){printf("You wi"
"n!\n");return;}if(l<4){v(a,b,&d);printf("%d\n",d+1);b|=1<<d;}if(w(~b)){printf(
"I win!\n");return;}}printf("A draw\n");} 


#endif 
#else /* PRINT_BOARD */
#ifndef PRINT_OUTCOME

/* Prints only the board, not the outcome of the game (asks 5 times for input) */

#define s(i) ,a&(1<<i)?'x':b&(1<<i)?'o':' '
w(b){return!(b&7&&b&56&&b&448&&b&73&&b&146&&b&292&&b&273&&b&84);}v(int a,int b,
int *m){int i=0,e,k,c=5,n;if(w(~a))c=4;else{for(;i<9;i++)if(!(a&(k=1<<i)||b&k)
&&c>(e=5-v(b|k,a,&n)))c=e,*m=i;if(c>4)c=3;c-=(c>1);}return c;}main(){int a=0,b=
0,d,l=0;for(;l<5;l++){a|=1<<(getchar()-'1');getchar();if(w(~a))break;if(l<4){v(
a,b,&d);printf("%d\n",d+1);b|=1<<d;}printf("+---+\n|%c%c%c|\n|%c%c%c|\n|%c%c%c"
"|\n+---+\n"s(0)s(1)s(2)s(3)s(4)s(5)s(6)s(7)s(8));if(w(~b))break;}} 

#else /* PRINT_OUTCOME */

/* Prints the outcome of the game (asks 5 times for input), and prints board */

#define s(i) ,a&(1<<i)?'x':b&(1<<i)?'o':' '
w(b){return!(b&7&&b&56&&b&448&&b&73&&b&146&&b&292&&b&273&&b&84);}v(int a,int b,
int *m){int i=0,e,k,c=5,n;if(w(~a))c=4;else{for(;i<9;i++)if(!(a&(k=1<<i)||b&k)
&&c>(e=5-v(b|k,a,&n)))c=e,*m=i;if(c>4)c=3;c-=(c>1);}return c;}main(){int a=0,b=
0,d,l=0;for(;l<5;l++){a|=1<<(getchar()-'1');getchar();if(w(~a)){printf(
"You win!\n");return;}if(l<4){v(a,b,&d);printf("%d\n",d+1);b|=1<<d;}printf(
"+---+\n|%c%c%c|\n|%c%c%c|\n|%c%c%c|\n+---+\n"s(0)s(1)s(2)s(3)s(4)s(5)s(6)s(7)
s(8));if(w(~b)){printf("I win!\n");return;}}printf("A draw\n");} 

#endif
#endif
#else /*  NOT_COMPACT */

/* This is a normal spaced version of the program */

#include <stdio.h>
#define s(i) ,a&(1<<i)?'x':b&(1<<i)?'o':' '

int w(int b){return!(b&7&&b&56&&b&448&&b&73&&b&146&&b&292&&b&273&&b&84);}

int v(int a,int b,int *m, int dept)
{int i=0,e,k,c=5,n;

    if (w(~a))
        c=4;
    else 
    {   
        for (;i<9;i++)
            if (   !(a&(k=1<<i)||b&k)
                && c>(e=5-v(b|k,a,&n,dept+1)))c=e,*m=i;
        
        if (c>4)
            c=3;
        c-=(c>1);
   }

#ifdef DEBUG
   printf("%*.*s|%c%c%c %c%c%c %c%c%c| gives %d\n", dept,dept,""
          s(0)s(1)s(2)s(3)s(4)s(5)s(6)s(7)s(8),c);
#endif

   return c;
}


void main()
{   int a=0,b=0,d,l=0;

    for (;l<5;l++)
    {   a|=1<<(getchar()-'1');
        getchar();

        if (w(~a))
        {   
#ifdef PRINT_OUTCOME
            printf("You win!\n");
#endif
            return;
        }
        if(l<4)
        {v(a,b,&d,1);
         printf("%d\n",d+1);b|=1<<d;}
#ifdef PRINT_BOARD
        printf("+---+\n|%c%c%c|\n|%c%c%c|\n|%c%c%c|\n+---+\n"
               s(0)s(1)s(2)s(3)s(4)s(5)s(6)s(7)s(8));
#endif
        if(w(~b))
        {   
#ifdef PRINT_OUTCOME
            printf("I win!\n");
#endif
            return;
        }
   }
#ifdef PRINT_OUTCOME
   printf("A draw\n");
#endif
} 
#endif