Re: 四則演算で10を作る

//
// TP.c  ( Ver. 1.5.4 )
// Ten Puzzle
// by ADUMA Haruka
//
// % gcc -o TP TP.c
// % ./TP | sort > RESULT.txt
//
// 1.5s @ Core i5-4200 ( 2.2GHz )
//

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

char *OPS[6] = { " +", "i-", "r-", " *", "i/", "r/" } ;

typedef struct { int n ; int d ; } FRACTION ;
FRACTION fA, fB, fC, fD, fT, fU, fV ;

char SORT_BUFFER[10] ;

#define START 0

int main ( int ARGC, char **ARGV, char **ENVV ) {
  int A, B, C, D, O, P, Q, R ;
  int REQUIRE = 10 ;
  char *s = "|>%d,%d,%d,%d |%s,%s,%s| <= %d %d %d : %d,%d,%d\n" ;
  for ( A = START ; A < 10 ; A++ ) {
    for ( B = START ; B < 10 ; B++ ) {
      for ( C = START ; C < 10 ; C++ ) {
        for ( D = START ; D < 10 ; D++ ) {
          for ( O = 0 ; O < 6 ; O++ ) {             
            for ( P = 0 ; P < 6 ; P++ ) {   
              for ( Q = 0 ; Q < 6 ; Q++ ) {
                if ( 0 ) printf ( s, A,B,C,D,OPS[O],OPS[P],OPS[Q],O,P,Q,0,0,0 ) ;
                R = calc_exp_1 (A,B,C,D,O,P,Q,REQUIRE) ; /* A B C D + - / */
                R = calc_exp_2 (A,B,C,D,O,P,Q,REQUIRE) ; /* A B C + D - / */
                R = calc_exp_3 (A,B,C,D,O,P,Q,REQUIRE) ; /* A B + C D - / */
                R = calc_exp_4 (A,B,C,D,O,P,Q,REQUIRE) ; /* A B + C - D / */
  } } } } } } }
  return 0 ;
}

char * sort_set ( int A, int B, int C, int D ) {
  int i ; char *p = SORT_BUFFER ; /* force to be A <= B<= C <= D */
  if ( A > B ) { i=A; A=B; B=i; }  if ( B > C ) { i=B; B=C; C=i; }
  if ( C > D ) { i=C; C=D; D=i; }  if ( B > C ) { i=B; B=C; C=i; }
  if ( A > B ) { i=A; A=B; B=i; }  if ( B > C ) { i=B; B=C; C=i; }
  sprintf ( p, "%1d%1d%1d%1d", A, B, C, D ) ;
  return p ;
}

int operate_one ( FRACTION *A, FRACTION *B, FRACTION *X, int O ) {
  int f = 1 ;    /* operand A,   operand B,    result X, operation type O */
  switch ( O ) { /* case 0: X=A+B; case 1:X=A-B; case 2:X=B-A; case 3:X=A*B; */ 
    case 0: X->n = (A->n * B->d)+(B->n * A->d); X->d = A->d * B->d; break;
    case 1: X->n = (A->n * B->d)-(B->n * A->d); X->d = A->d * B->d; break;
    case 2: X->n = (B->n * A->d)-(A->n * B->d); X->d = A->d * B->d; break;
    case 3: X->n = A->n * B->n ; X->d = A->d * B->d ; break ;
    case 4: if (B->n !=0) X->n= A->n * B->d, X->d= A->d * B->n; else f=0; break;
    case 5: if (A->n !=0) X->n= B->n * A->d, X->d= B->d * A->n; else f=0; break;
  } /* case 4:  X = A / B  ;  case 5:  X = B / A   */
  if ( f ) reduce ( X ) ;
  return f ; /* 1: Valid Value, 0: Invalid Value, denominator = 0 */
}

int reduce ( FRACTION *X ) { /* EX.  24 / 9 --> 8 / 3  */ 
  int tN, tD, iM, iN, iR, f = 0 ; /* if ( f ) it is minus */
  tN = X->n, tD = X->d ;
  if ( tD <  0 ) tN = -tN, tD = -tD ; 
  if ( tN <  0 ) tN = -tN,  f =  1 ;
  if ( tN < tD ) iM =  tD, iN = tN ; else iM = tN, iN = tD ;
  while ( iN ) iR = iM % iN, iM = iN, iN = iR ; /* EUCLID */ 
  tN = tN / iM, tD = tD / iM ;
  if ( f ) tN = -tN ;
  X->n = tN, X->d = tD ;
  return f ;
}

int setup_numbers ( int A, int B, int C, int D ) {
  fA.n = A ; fB.n = B ; fC.n = C ; fD.n = D ; /* numerator = given value */
  fA.d = 1 ; fB.d = 1 ; fC.d = 1 ; fD.d = 1 ; /* denominator = 1 */
  return 1 ;
}

int calc_exp_1 ( int A, int B, int C, int D, int O, int P, int Q, int R ) {
  char *p, *s="%s :EQ1: %2d %2d %2d %2d %s %s %s : %d\n" ; 
  int f = 1 ; setup_numbers ( A, B, C, D ) ;
  /**/     f = operate_one ( &fC, &fD, &fT, O ) ;   /* A B C D op/ op/ op/ */
  if ( f ) f = operate_one ( &fB, &fT, &fU, P ) ;   /*          O   P   Q  */
  if ( f ) f = operate_one ( &fA, &fU, &fV, Q ) ;   /*          T   U   V  */
  if ( f ) if ( ( fV.d == 1 ) && ( fV.n == R ) ) {
    p = sort_set ( A, B, C, D ) ;
    printf ( s, p, A, B, C, D, OPS[O], OPS[P], OPS[Q], fV. n ) ;
  }
  return f ;
} 

int calc_exp_2 ( int A, int B, int C, int D, int O, int P, int Q, int R ) {
  char *p, *s="%s :EQ2: %2d %2d %2d %s %2d %s %s : %d\n" ; 
  int f = 1 ; setup_numbers ( A, B, C, D ) ;
  /**/     f = operate_one ( &fB, &fC, &fT, O ) ;   /* A B C op/ D op/ op/ */
  if ( f ) f = operate_one ( &fT, &fD, &fU, P ) ;   /*        O     P   Q  */
  if ( f ) f = operate_one ( &fA, &fU, &fV, Q ) ;   /*        T     U   V  */
  if ( f ) if ( ( fV.d == 1 ) && ( fV.n == R ) ) {
    p = sort_set ( A, B, C, D ) ;
    printf ( s, p, A, B, C, OPS[O], D, OPS[P], OPS[Q], fV. n ) ;
  }
  return f ;
} 

int calc_exp_3 ( int A, int B, int C, int D, int O, int P, int Q, int R ) {
  char *p, *s="%s :EQ3: %2d %2d %s %2d %2d %s %s : %d\n" ; 
  int f = 1 ; setup_numbers ( A, B, C, D ) ;
  /**/     f = operate_one ( &fA, &fB, &fT, O ) ;   /* A B op/ C D op/ op/ */
  if ( f ) f = operate_one ( &fC, &fD, &fU, P ) ;   /*      O       P   Q  */
  if ( f ) f = operate_one ( &fT, &fU, &fV, Q ) ;   /*      T       U   V  */
  if ( f ) if ( ( fV.d == 1 ) && ( fV.n == R ) ) {
    p = sort_set ( A, B, C, D ) ;
    printf ( s, p, A, B, OPS[O], C, D, OPS[P], OPS[Q], fV. n ) ;
  }
  return f ;
} 

int calc_exp_4 ( int A, int B, int C, int D, int O, int P, int Q, int R ) {
  char *p, *s="%s :EQ4: %2d %2d %s %2d %s %2d %s : %d\n" ; 
  int f = 1 ; setup_numbers ( A, B, C, D ) ;
  /**/     f = operate_one ( &fA, &fB, &fT, O ) ;   /* A B op/ C op/ D op/ */
  if ( f ) f = operate_one ( &fT, &fC, &fU, P ) ;   /*      O     P     Q  */
  if ( f ) f = operate_one ( &fU, &fD, &fV, Q ) ;   /*      T     U     V  */
  if ( f ) if ( ( fV.d == 1 ) && ( fV.n == R ) ) {
    p = sort_set ( A, B, C, D ) ;
    printf ( s, p, A, B, OPS[O], C, OPS[P], D, OPS[Q], fV. n ) ;
  }
  return f ;
}