読者です 読者をやめる 読者になる 読者になる

Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

CodeIQ に出した「テトロミノ+ビンゴ!」の解説・解題

CodeIQ に「テトロミノ+ビンゴ!」( https://codeiq.jp/ace/nabetani_takenori/q524 )という問題を出した。
挑戦の募集はすでに締めきっている。
この記事は、「テトロミノ+ビンゴ!」という問題の解説・解題である。

まず。

前回の「カードゲームの役を判定する」とくらべて、難易度も高く、分量も多かったと思う。前回の「カードゲームの役を判定する」は、いつものオフラインリアルタイムどう書くに出してもいいかなと思うぐらいの問題だったんだけど、今回の「テトロミノ+ビンゴ!」は、ちょっとこれを出したら大不評に違いないと思う。

とはいえ、そんなに難しいってことはない。

問題を
http://nabetani.sakura.ne.jp/codeiq/tetromino_bingo/
においてみた。
未挑戦の方はこの先を読まずに挑戦するのも一興だと思う。

で。

解けなかった人のために

まずは、解けなかった人のためのアドバイス。

たぶんだけど、

  • 小さな手順に分解する
  • 分解したそれぞれの手順について、ちゃんと書いてから結合する
  • わからなかったら、プログラムではなく、紙とペンで解いてみる

という作業を行うと、難易度が下がると思う。
「ちゃんと書いてから結合する」を実現するためには、テストを書く。

それと。エレガントだけど惜しいところで間違えるコードよりも、無様で繰り返しが多くて計算量に無駄があるけど正しい結果を出すコードのほうがずっと優れている。
だから、スマートにすることよりも正しくすることに注力する。「なんかもっといい方法があると思うんだけどなぁ」と思っていても、そのちょっとかっこ悪い方法でうまくいきそうなら、その方向で書いてみる。
正しく動くようになったら、そこからスマートにしていけばいい。

そんな風に考えると解けるんじゃないかと思うんだけど、どうだろう。

問題を作るときに考えたこと

「ゲーム」というジャンルをせっかく作ってくださったのでゲームにしようということでなんかいいゲームないかなぁと考えて、ビンゴゲームに到達。
当初は普通のビンゴにしようと思っていて、テストデータを用意するところまで準備していた。
のだけれど。
普通のビンゴだとすでにどこかで出てるよなぁ、と思い、ちょっとひねる必要を感じ、テトロミノを導入した。という経緯になっている。
難易度が上がるなあとは思ったけど、面白味も増えるのでまあいいかと。制限時間ないし。

締めきってみて感じていること

ちょっと難しすぎたのかもしれないと思っている。
手順をちゃんと分解できればさほど難しくないとは依然として思っているものの、手数はちょっと多いと思う。人によってはだいぶ苦しんでしまったようで、ちょっと反省している。

解説

順当な手順だと私が思っているもの

ぱっと書ける人はまあぱっと書けばいいんだけど、そうでない人はまず、人間が手で解決する方法をそのままなぞる方向で考えるのがいい。と思っている。

最初にやるべきことは、1行目の、数を読み上げる順序を手に入れることだ。C言語方面の人は若干字句解析が面倒かもしれないけど、それは宿命として受け入れるか、ruby のような言語に鞍替えするのがよいと思う。

次はやはり、2行目以降を字句解析して盤面を手に入れる。
C言語以外なら、「/」で区切ったものを「,」で区切るのが順当なストーリーだけど、どうせ 5×5 だとわかっているので「数値以外」で区切って25要素の列を手に入れるのも悪くない。

盤面が手に入ったら、運営者の読み上げ順に従ってマス目を埋めていく。
ひとマス埋めるごとにテトロミノができているのかどうか判断し、できていたら、できているテトロミノの種別を返して終了。
最後の数まで読んだら「出来なかったよ」という趣旨の値を返して終了。

  • テトロミノができているのかどうか判断
  • テトロミノの種別を返す

の2つが引っかかるところだと思う。

人間の場合、テトロミノの成立判断と種別の判断は、同時に、直感的に出来てしまう。直感的に出来てしまっていることをソースコードに表現するのは、一般的に難しいと思う。

どうするか。

いろいろな方法があるんだけれど、まずは、テトロミノの成立のみを判断することにしよう。

手作業でやってみると(あるいはやってみるまでもなく)分かる通り、

  • 盤面にある数字が読まれた場合のみ判断すれば良い。
  • 新たに成立したテトロミノは、読まれたばかりの数字が書かれているマスを含む。

ということになっている。

したがって、読まれたばかりの数字が書かれているマスがテトロミノの一部になっているかどうかを調べれば良い。
というわけで、

  • 読まれたばかりの数字が書かれているマスから、上下左右に塗られているマスをたどる
  • たどることができたマスの数が(起点である読まれたばかりの数字が書かれているマスを含めて)4マスならテトロミノ成立

という処理を書けば良い。
この「たどる」という処理は、今回の場合、最大4回でよいので4重ループで書けないことはないんだけど、再帰で書いたほうが見通しがいい。幅優先にしてループにしても良い。

テトロミノが見つかると、テトロミノに含まれる4つのマスの座標が手に入る。
手に入った座標を評価して、I, L, O, S, T のいずれになるのかを決める必要がある。
どうするか。
鏡像と回転があるので、全パターンを調べると19種類になる。平行移動(同じことだけど、辞書順で最小となる座標からのオフセット)によって正規化し、そこから19種類のいずれに該当するのかを調査するのももちろん悪くないけれど、そうするのであれば、それが正しく書けていることを確認するためのテストパターンを自分で用意すべきだと思う。テストパターンが40しかないので、そこに必要なパターンが網羅されているとは考えないほうがいい。
とはいえ、もう少し簡単に書くことができる。

で。
興味のない情報を捨てることを考える。
今回の場合、興味のない情報は、テトロミノの向きと位置。興味のある情報は、テトロミノの種別。
テトロミノの向きや位置には関係ないけどテトロミノの種別の判定には使える情報を収集したい。どんな情報がいいか、候補を挙げてみる:

  • マス目とマス目の距離
  • マス目に隣接するマス目の数
  • マス目の斜め方向にあるマス目の数
  • x座標またはy座標が同じであるマス目の数
  • マス目の中心をつないでできる図形の、頂点数、面積、周長
  • 重心からの距離
  • 外接矩形の高さと幅を整列したもの

このなかで、テトロミノの種別を同定することができ、計算が簡単なのはどれかを考えてみると、マス目とマス目の距離や、重心からの距離が有望だとわかると思う。それ以外のものでも、複数組み合わせるとうまくいくようにすることはできる。

最初にお見せするのは、長いんだけど、C言語

// compiled with "clang -std=c99 -Wall"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>

#define COUNTOF(x) ( sizeof(x) / sizeof(*(x)) )
#define OUT // 引数が出力用だと示す
#define IN // 引数が入力用でもあると示す

enum{
  NUMBER_COUNT_TO_CALL = 99,
  BOARD_W = 5,
  BOARD_H = 5,

  PRIZ_I = 0,
  PRIZ_L = 1,
  PRIZ_O = 2,
  PRIZ_S = 3,
  PRIZ_T = 4,
  PRIZ_NONE = 5,
  PRIZ_COUNT = 6,

  TETROMINO_SIZE = 4,
};

struct numbers_to_call{
  char m[NUMBER_COUNT_TO_CALL];
};

struct board{
  char m[BOARD_W * BOARD_H];
};

struct holes{
  // 穴が開いていたら true
  bool m[BOARD_W * BOARD_H];
};

struct positions{
  int size;
  int m[TETROMINO_SIZE+1];
};

char const * next_digit( char const * p )
{
  for( ; isdigit(*p) ; ++p ){ /* nothing to do */ }
  for( ; ! isdigit(*p) ; ++p ){ /* nothing to do */ }
  return p;
}

bool read_digits( FILE * fp, OUT char * dest, int dest_count )
{
  enum{ ITEM_SIZE = 4 }; // "99, " の長さ。
  size_t buffer_size = dest_count*ITEM_SIZE + 3; // 3 は、ターミネータなどのために。
  char buffer[ buffer_size ]; // C99 の、可変長配列。
  if ( ! fgets( buffer, sizeof( buffer ), fp ) ){
    return false;
  }
  char const * src = buffer;
  for( int i=0 ; i<dest_count ; ++i ){
    assert( src && *src );
    dest[i] = atoi( src );
    src = next_digit( src );
  }
  return true;
}

bool is_checked( struct positions const * poss, int pos )
{
  for( int i=0 ; i<poss->size ; ++i ){
    if ( poss->m[i] == pos ){
      return true;
    }
  }
  return false;
}

void take_group( IN OUT struct positions * poss, struct  holes const * ho, int pos )
{
  if ( COUNTOF( poss->m )<poss->size || ! ho->m[ pos ] || is_checked( poss, pos ) ){
    return;
  }
  poss->m[ poss->size ] = pos;
  ++poss->size;
  if ( 0 < pos % BOARD_W ){
    take_group( poss, ho, pos-1 );
  }
  if ( pos % BOARD_W < BOARD_W-1 ){
    take_group( poss, ho, pos+1 );
  }
  if ( BOARD_W <= pos ){
    take_group( poss, ho, pos-BOARD_W );
  }
  if ( pos < BOARD_W*(BOARD_H-1) ){
    take_group( poss, ho, pos+BOARD_W );
  }
}

// 距離の自乗
int distance_sq( div_t a, div_t b )
{
  int dx = a.rem - b.rem;
  int dy = a.quot - b.quot;
  return dx*dx + dy*dy;
}

// 距離の自乗の合計
int sum_of_distance_sq( struct positions const * poss )
{
  int sum=0;
  for( int ia=0 ; ia<TETROMINO_SIZE ; ++ia ){
    div_t a = div( poss->m[ ia ], BOARD_W );
    for( int ib=0 ; ib<ia ; ++ib ){
      div_t b = div( poss->m[ ib ], BOARD_W );
      sum += distance_sq( a, b );
    }
  }
  return sum;
}

int sum_to_tetname( int sum )
{
  switch( sum ){
  case 1+1+1+4+4+9: return PRIZ_I;
  case 1+1+1+2+4+5: return PRIZ_L;
  case 1+1+1+1+2+2: return PRIZ_O;
  case 1+1+1+2+2+5: return PRIZ_S;
  case 1+1+1+2+2+4: return PRIZ_T;
  default:
    assert( false );
    return PRIZ_NONE;
  }
}

int tet_name( struct positions const * poss )
{
  int sum = sum_of_distance_sq( poss );
  return sum_to_tetname( sum );
}

int eval_filled_board( struct holes const * ho, int pos )
{
  struct positions poss= {0};
  take_group( &poss, ho, pos );
  if ( poss.size==4 ){
    return tet_name( &poss );
  } else {
    return PRIZ_NONE;
  }
}

int eval_board( struct board const * bo )
{
  struct holes ho = {{0}};
  for( int num=0 ; num<COUNTOF(bo->m) ; ++num ){
    int pos = bo->m[num];
    ho.m[pos] = true;
    int pri = eval_filled_board( &ho, pos );
    if ( pri != PRIZ_NONE ){
      assert( PRIZ_I<=pri && pri<=PRIZ_T );
      return pri;
    }
  }
  return PRIZ_NONE;
}

struct board
map_order_to_pos( struct board const * bo, struct numbers_to_call const * nums )
{
  struct numbers_to_call num_to_pos;
  memset( num_to_pos.m, -1, sizeof( num_to_pos.m ) );
  for( int pos=0 ; pos<COUNTOF( bo->m ) ; ++pos ){
    assert( 0<=bo->m[ pos ]-1 && bo->m[ pos ]-1 < COUNTOF( num_to_pos.m ) );
    num_to_pos.m[ bo->m[ pos ]-1 ] = pos;
  }
  struct board order_to_pos;
  memset( order_to_pos.m, -1, sizeof( order_to_pos.m ) );
  int ix=0;
  for( int order=0 ; order<COUNTOF( nums->m ) ; ++order ){
    int pos = num_to_pos.m[ nums->m[ order ]-1 ];
    if ( 0<=pos ){
      assert( ix<COUNTOF( order_to_pos.m ) );
      order_to_pos.m[ ix ] = pos;
      ++ix;
    }
  }
  return order_to_pos;
}

void process_all( FILE * fp )
{
  struct numbers_to_call n2call;
  read_digits( fp , n2call.m, COUNTOF( n2call.m ) );
  int prizes[ PRIZ_COUNT ] = {0};
  while( ! feof( fp ) ){
    struct board bo={{0}};
    if ( ! read_digits( fp , bo.m, COUNTOF( bo.m ) ) ){
      break;
    }
    struct board o2pos=map_order_to_pos( &bo, &n2call );
    ++prizes[ eval_board( &o2pos ) ];
  }
  printf( "I:%d,L:%d,O:%d,S:%d,T:%d",
    prizes[ PRIZ_I], prizes[ PRIZ_L], prizes[ PRIZ_O], prizes[ PRIZ_S], prizes[ PRIZ_T] );
  printf( "    none : %d", prizes[ PRIZ_NONE ] );
}

int main( int argc, char const * argv[] )
{
  if ( argc != 2 ){
    puts( "one file name should be specified in the command line option." );
    exit(1);
  }
  FILE * fp = fopen( argv[1], "r" );
  assert( fp );
  process_all( fp );
  fclose( fp );
  return EXIT_SUCCESS;
}

マス目をたどるのは、take_group という関数。再帰呼び出しをしている。
C言語なので可変長のバッファを避けるという意味もあり、5つ目が見つかった時点で終了している。
tet_name という関数でテトロミノの種別を判定している。
テトロミノが成立していることはわかっているので、マス目は4つ。4つから2つ選ぶと6通りなので、2点間の距離が6つある。この6つの距離の自乗を合計すると、テトロミノが判別できる。
例えば、L なら、距離1(つまり、隣接)が3組。距離 sqrt(2)、2、sqrt(5) がそれぞれひと組ずつ。距離の自乗は小さい順に 1, 1, 1, 2, 4, 5 となる。
この「1,1,2,4,5」という情報、つまり、収集した2点間の距離6件をソートしたものをキーとしてテトロミノの判定をするのが素直な流れなんだけど、C言語なのでソートがめんどくさい。
そもそも、ソートしたかったのは順序という情報を捨てるためだった。順序が失われる計算はソート以外にもたくさんある。例えば足し算。
というわけで、試しに足し算してみたところ、これがあっさりうまくいく。
以上の内容を私なりに綺麗に書いたのが上記の実装になる。
とはいえ、この読みやすさのままでももう 50行ぐらい短く書けるはずだと思っていて、悔しい感じではある。

もう一つの戦略は、ひとマス塗るごとに何マスの塊になったのかを把握していくというもの。
盤面の更新のためにコンテナ操作が先ほどと比べるとだいぶ複雑なので、C言語ではちょっとつらい感じになると思う。

rubyで書くとこんな感じ。

#!ruby
# tested with "ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-darwin12.4.0]"
class TetrominoBingo
  def initialize( nums )
    @numbers = nums
  end

  def tetname( positions )
    # 重心からの距離の自乗の合計でテトロミノの種別を判定する
    xys=positions.map{ |pos| pos.divmod(5) }
    gx,gy=xys.inject([0,0]){ |(ax,ay),(bx,by)| [ ax+bx, ay+by ] }
    key = xys.inject(0){ |a,(x,y)|
      a+(gx-x*4)**2+(gy-y*4)**2
    }
    { 80=>"I",56=>"L",32=>"O",48=>"S",44=>"T" }[key]
  end

  def neibours( pos )
    y,x=pos.divmod(5)
    [
       [x+1, y], [x-1, y], [x, y+1], [x, y-1],
    ].select{ |xy| 0<=xy.min && xy.max<5 }.map{ |xy| xy[0]+xy[1]*5 }
  end

  def merge( bo, positions )
    s=positions.map{ |x| bo[x] }.compact.inject( &:| )
    s.each{ |x|  bo[x]=s }
  end

  def solve( src )
    (@numbers & src).each_with_object([]) do |n,bo|
      pos = src.index(n)
      bo[pos]=[pos]
      merge( bo, [pos]+neibours(pos) )
      return tetname( bo[ pos ] ) if bo[pos].size==4
    end
    "-"
  end
end

open( "data.txt" ) do |f|
  tebi = TetrominoBingo.new( f.gets.split(",").map( &:to_i ) )
  result = f.each_with_object( Hash.new(0) ){ |line,o|
    o[ tebi.solve( line.scan( /\d+/ ).map( &:to_i ) ) ]+=1
  }
  puts %w( I L O S T ).map{ |k| [k,result[k]].join(":") }.join(",")
end

「マス目の座標から、そのマス目と連結しているマス目のリストへの写像」というものを維持することで、テトロミノの成立を判断している。
更新のタイミングで新たに出来た塊のサイズが 4 ならテトロミノ成立。
成立したら種別を判断するんだけど、こちらでは「重心からの距離の自乗の合計の、16倍」というものをキーにしてみた。16倍しているのは、整数にするため。

順当じゃないかもしれないと思っている実装

実は、最初に書いたのは上記のようなものではなかった。
言葉で書くとやや不鮮明だけどこんな感じ:

  • 盤面の周囲に1マス「塗ってない」マークのマスを付加する。
  • 読まれた数字のマスを塗る
  • 塗ってないマークを v、塗ってあるマークを O として、都合 7×7 のマス目を一列に並べて 49文字の文字列にする。
  • /vv....vOOv...vOOv....vv/ という正規表現とマッチしたら、"O"。
  • L などについては、マス目をぐるぐる回したり鏡に写したりしてから繰り返し正規表現とマッチする

まあまあ短く書けるんだけれども、意図が不明瞭だしひどく遅いのでここには載せなかった。

挑戦者の中にも正規表現(のようなもの)で解いた方がいらっしゃったので、順当じゃないってほどでもないかもしれない。

補足

計算時間

私自身は実行速度はまあどうでもいいと思って問題を出しているんだけど、今回はちょっと計算量が多くなってしまった。

上記の実装は、手元の環境でいずれも1秒以下で計算が終わるんだけど、数字が読まれるたびに全面を調査するという選択をするとだいぶ時間がかかると思う。

4000 は多すぎたかもとちょっと思っている。(ちょっとしか思っていない)。