オフラインリアルタイムどう書くF01の問題の rubyとC99 による実装例 #Ruby

問題 : http://nabetani.sakura.ne.jp/hena/ordf01_twicel/
実装リンク集 : http://qiita.com/Nabetani/items/8e02ede04315b4eadd6d

まずは、ruby による実装例。

WX=WY=8

def at( m, x, y, t )
  if t
    (0...WX)===x && (0...WY)===y ? m[y][x] : nil
  else
    at( m, y, x, true )
  end
end

def solve( src )
  m=src.split("/").map{ |x| x.to_i(16) }
  r=[0,0]
  WY.times do |y|
    WX.times do |x|
      [true, false].each do |t|
        c=at( m, x, y, t )
        if c==at( m, x+1,y, t )
          r[c]+=1 if [
            [x-1,y], [x+2,y], [x,y-1], [x,y+1], [x+1,y-1], [x+1,y+1]
          ].all?{ |pos| at(m, *pos, t)!=c }
        end
      end
    end
  end
  r.join(",")
end

DATA.map{ |line|
  num, src, expected = line.split( /\s+/ )
  p src
  actual = solve( src )
  ok = actual==expected
  puts [ num, ( ok ? "ok" : "**NG**" ), src, actual, expected ].join( " " )
  ok
}.all?.tap{ |x| p( x ? "all okay!" : "something wrong!!" ) }

__END__
0 dc/bc/a7/59/03/d5/d4/ea 2,3
1 ff/ff/ff/ff/ff/ff/ff/ff 0,0
2 00/00/00/00/00/00/00/00 0,0
3 cc/33/cc/33/cc/33/cc/33 16,16
4 aa/aa/55/55/aa/aa/55/55 16,16
5 ac/a3/5c/53/ca/3a/c5/35 8,8

そして、上記の ruby を C99 に移植したもの：

C99

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

struct result
{
  int success;
  int testcount;
};

enum{ WX=8, WY=8 };

int at( uint64_t m, int x, int y, _Bool t )
{
  if ( t ){
    if ( 0<=x && x<WX && 0<=y && y<WY ){
      return ( m & (1ULL<<(x+y*8) ) ) ? 1 : 0;
    } else {
      return -1;
    }
  }
  return at( m, y, x, 1 );
}

struct wb{ int m[2]; };
struct xy{ int x, y; };
const struct xy P[6] = {
  {-1, 0},  {2, 0},
  {0, -1},  {0, 1},
  {1, -1},  {1, 1},
};

#define COUNTOF(x) (sizeof(x) / sizeof(*(x)))
struct wb solve_impl( uint64_t num )
{
  struct wb r={{0}};
  for( int y=0 ; y<WY ; ++y ){
    for( int x=0 ; x<WX ; ++x ){
      for( int t=0 ; t<2 ; ++t ){
        int c=at( num, x, y, !!t );
        if ( c==at( num, x+1,y, !!t ) ){
          _Bool all=1;
          for( int pos=0 ; pos<COUNTOF(P) ; ++pos ){
            all = ( all && c!=at( num, x+P[pos].x, y+P[pos].y, !!t ) );
          }
          if ( all ){
            ++r.m[c];
          }
        }
      }
    }
  }
  return r;
}

// caller should free return value memory.
char const * solve( char const * src )
{
  uint64_t num=0;
  for( int i=0 ; i<8 ; ++i ){
    num*=256;
    num += strtoul( src+3*i, 0, 16 );
  }
  struct wb a = solve_impl( num );
  char buffer[ 10 ] = {0};
  sprintf( buffer, "%d,%d", a.m[0], a.m[1] );
  return strdup(buffer);
}

void test_( struct result * r, char const * src, char const * expected )
{
  char const * actual = solve( src );
  int okay = 0==strcmp(actual, expected );
  if ( okay ){
    ++r->success;
  }
  ++r->testcount;
  printf( "%s : %s->%s(%s)\n", (okay?"ok" : "**NG**"), src, actual, expected );
  free( (void*)actual );
}

int main(void)
{
  struct result r={0};
  #define test(src, expected) test_( &r, src, expected )
  /*0*/ test( "dc/bc/a7/59/03/d5/d4/ea", "2,3" );
  /*1*/ test( "ff/ff/ff/ff/ff/ff/ff/ff", "0,0" );
  /*2*/ test( "00/00/00/00/00/00/00/00", "0,0" );
  /*3*/ test( "cc/33/cc/33/cc/33/cc/33", "16,16" );
  /*4*/ test( "aa/aa/55/55/aa/aa/55/55", "16,16" );
  /*5*/ test( "ac/a3/5c/53/ca/3a/c5/35", "8,8" );
  #undef test
  printf( "%d / %d\n", r.success, r.testcount );
  return r.testcount==r.success ? 0 : 1;
}

実装方針は、いくつかあるけど

深さ優先探索などで、連結しているマス目の数を数える。
2マス限定であることを利用して数える

のどちらかになると思う。ciel さんの実装( https://github.com/cielavenir/procon/blob/f807cc5ae792801e452ee94d1f6661e993590668/hena/tyama_henaf01.rb )は前者。これは後者になる。

あと、端っこの処理としては、

不等号などで何とかする
番兵を置く

の2種類がある。この実装は前者。

ruby と C99 で書いたけど、いずれもネストが深すぎてよろしくないね。

問題としては簡単気味だと思っているんだけど、どう？