朝日新聞2005年9月2日パズル横丁解答

プログラムの実行結果は以下の通り。

102/34+56/7+89 =  23800 /    238 =  100

プログラムのソースは以下の通り。

上の方はパズルパーク2004年12月11日の問題からの拝借。

#include "puzutl.h"

struct struct_number {          // 数字を通分して記録する
  int m;                        // 分子
  int n;                        // 分母
  struct_number() { m=n=0;}
  struct_number( int x) { m=x; n=1;}
} dig[9];
int idig = 0;
int op[8];                      // 0:+, 1:-, 2:*, 3:/
int iop = 0;
void push( int n)
{
  dig[idig++] = n;
}
void calc( int p) {
  if( idig < 2) { pe( "Stack short\n"); exit(16);}
  int m1 = dig[idig-2].m, n1 = dig[idig-2].n;
  int m2 = dig[idig-1].m, n2 = dig[idig-1].n;
  idig--;
  int m, n;
  switch( p) {
  case 0:                       // +
    n = n1*n2; m = m1*n2 + n1*m2;
    dig[idig-1].m = m; dig[idig-1].n = n;
    //ps( "%d/%d + %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
    break;
  case 1:                       // −
    n = n1*n2; m = m1*n2 - n1*m2;
    dig[idig-1].m = m; dig[idig-1].n = n;
    //ps( "%d/%d - %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
    break;
  case 2:                       // ×
    n = n1*n2; m = m1*m2;
    dig[idig-1].m = m; dig[idig-1].n = n;
    //ps( "%d/%d * %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
    break;
  case 3:                       // ÷
    n = n1*m2; m = m1*n2;
    dig[idig-1].m = m; dig[idig-1].n = n;
    //ps( "%d/%d / %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
    break;
  default:
    pe( "unknown calc(%d)\n", p);
    exit(16);
  }
}
void ope( int p) {
  if( p == 2 || p == 3) {
    // ×,÷は出現したら即実行する
    calc( p);
  }
  else {
    // +または−は計算せずに取っておく
    if( p == 1) { dig[idig-1].m = -dig[idig-1].m; p = 0;}// −は+負数に変換する
    op[iop++] = p;
  }
} 
cstring opestr( int o) {
  cstring s[] = { "+", "-", "*", "/" };
  if( o >= 0 && o <= 3) return s[o];
  return "?";
}

void eval( cstring s)
{
  cstring ss = s;
  iop = idig = 0;
  int n = 0;
  int num[10], o[10];
  int inum = 0;
  while( *s) {
    if( *s == '+') {
      num[inum] = n;
      o[inum] = 0;
      inum++;
      n = 0;
    }
    else if( *s == '/') {
      num[inum] = n;
      o[inum] = 3;
      inum++;
      n = 0;
    }
    else {
      n *= 10; n += *s - '0';
    }
    s++;
  }
  num[inum] = n;
  push(num[0]);
  for( int i=0; i< 4; i++) {
    push(num[i+1]);
    ope(o[i]);
  }
  while( iop--> 0) {
    calc(op[iop]);
  }
  if( dig[0].n != 0 && (dig[0].m / dig[0].n) == 100 && (dig[0].m % dig[0].n) == 0) { 
    ps( "%s = %6d / %6d = %4d\n", ss, dig[0].m, dig[0].n, dig[0].m/dig[0].n);
  }
}

int cnt[10];
int main( int argc, cstring argv[])
{
  for( int a=0; a<= 2; a++) {
    cnt[a]++;
    for( int b=0; b<= 2; b++) {
      if( b && cnt[b] >= 2) continue;
      cnt[b]++;
      for( int c=0; c<= 2; c++) {
        if( c && cnt[c] >= 2) continue;
        cnt[c]++;
        for( int d=0; d<= 2; d++) {
          if( d && cnt[d] >= 2) continue;
          cnt[d]++;
          for( int e=0; e<= 2; e++) {
            if( e && cnt[e] >= 2) continue;
            cnt[e]++;
            for( int f=0; f<= 2; f++) {
              if( f && cnt[f] >= 2) continue;
              cnt[f]++;
              for( int g=0; g<= 2; g++) {
                if( g && cnt[g] >= 2) continue;
                cnt[g]++;
                for( int h=0; h<= 2; h++) {
                  if( h && cnt[h] >= 2) continue;
                  cnt[h]++;
                  for( int i=0; i<= 2; i++) {
                    if( i && cnt[i] >= 2) continue;
                    cnt[i]++;
                    if( cnt[1] == 2 && cnt[2] == 2) { // 「+」が2個,「÷」が2個使用しているか?
                      int pos[] = {a,b,c,d,e,f,g,h,i};
                      char buf[128]; astring s = buf;
                      cstring ns = "1023456789";
                      for( int k=0; k< 9; k++) { // 文字列の間に「+」と「÷」を入れて計算式を作成する
                        *s++ = ns[k];
                        if( pos[k] == 1) *s++= '+';
                        else if( pos[k] == 2) *s++ = '/';
                      }
                      *s++ = ns[k];
                      *s = NIL;
                      eval( buf); // 作成した計算式を評価する
                    }
                    cnt[i]--;
                  }
                  cnt[h]--;
                }
                cnt[g]--;
              }
              cnt[f]--;
            }
            cnt[e]--;
          }
          cnt[d]--;
        }
        cnt[c]--;
      }
      cnt[b]--;
    }
    cnt[a]--;
  }
  return    0;
}