朝日新聞2006年5月19日パズル横丁解答

プログラムの実行結果は以下の通り。'T'が立った状態で，'_'が座った状態。

Find
    一つ前の状態 T T T T _ T _ 
      新しい状態 _ _ _ _ _ T _ 
Find
    一つ前の状態 T _ T T T T _ 
      新しい状態 T _ _ _ _ _ _ 
Find
    一つ前の状態 T T T _ T _ T 
      新しい状態 _ _ _ _ T _ _ 
Find
    一つ前の状態 _ T T T T _ T 
      新しい状態 _ _ _ _ _ _ T 
Find
    一つ前の状態 T T _ T _ T T 
      新しい状態 _ _ _ T _ _ _ 
Find
    一つ前の状態 T _ T _ T T T 
      新しい状態 _ _ T _ _ _ _ 
Find
    一つ前の状態 _ T _ T T T T 
      新しい状態 _ T _ _ _ _ _ 

新しい状態で立っている人を基準に考えると実質1件。

判りやすい絵にすると以下の通り。

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

#include "puzutl.h"

void bit2array( int prev_st[], int n) // 7人の状態をビットから配列にする
{
  for( int i=0; i< 7; i++) {    // 7人分
    if( n&1) prev_st[i] = 1; else prev_st[i] = 0; // ビットがONなら配列の対応位置もON
    n           >>= 1;          // 次の人
  }
}
int pos( int i)                 // 配列を輪にみなす
{
  if( i >= 7) return    i-7;
  if( i <  0) return    i+7;
  return    i;
}

int countst( int st[])          // 立っている人の数を数える
{
  int           num_stand = 0;
  for( int i=0; i< 7; i++) {
    if( st[i]) num_stand++;
  }
  return    num_stand;
}

void prev_st2new_st( int st[], int prev_st[]) // 以前の状態を元に次の状態を求める
{
  int           num = 0;        // 立っている人の数
  for( int i=0; i< 7; i++) {    // 7人全てについて調べる
    num         = 0;
    if( prev_st[pos(i-1)]) num++; // 左の人は立っている?
    if( prev_st[pos(i+0)]) num++; // 自分は立っている?
    if( prev_st[pos(i+1)]) num++; // 右の人は立っている?
    // 左右両隣と自分の合計3人のうち，
    // 1.一人だけが立っている
    if( num == 1 ) {
      st[i] = 1;                // 次に自分が立つ
    }
    // 2.皆が座っているか2人や3人が立っているときは座る。
    else if( num == 0 || num == 2 || num == 3) {
      st[i]     = 0;            // 次に自分は座る
    }
    else {
      pe( "Error\n");           // 他の状態は無い
    }
  }
}

void dump( cstring msg, int st[]) // 7人の状態を出力する
{
  ps( "%16s ", msg);
  for( int i=0; i< 7; i++) {    // 7人分出力する
    if( st[i]) ps( "T ");       // 立っている
    else       ps( "_ ");       // 座っている
  }
  ps( "\n");
}

int main( int argc, cstring argv[])
{
  int           st[7], prev_st[7]; // 7人の次の状態，一つ前の状態
  int           istat;          // 7人の状態を数値化したもの
  for( int i=0; i<= 0x7F; i++) { // 7人が立ったり座ったりしている全ての状態を調べる
    bit2array( prev_st, i); // ビットで表現されている7人分の情報を配列に変換する
    prev_st2new_st( st, prev_st); // 以前の状態(prev_st)を元に次の状態(st)を決定する。
    if( countst(st) == 1) {   // 7人のうち一人だけが立っている。
      ps( "Find\n");          // prev_st[]が直前の状態。
      dump( "一つ前の状態", prev_st);
      dump( "新しい状態", st);
    }
  }
  return    0;
}