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

  • 0
    いいね
  • 0
    コメント

    問題 : http://mtsmfm.github.io/2016/12/03/doukaku-e10.html
    実装リンク集 : http://qiita.com/mtsmfm/items/8a78b895910a89e3012d

    時間内に書いたのはスタッオーバーフローするので、スタックサイズを調整して無理やり実行するという酷いものだった。
    ここに載せるにあたってそれはあんまりだと思うので、スタックオーバーフローを回避したものを:

    require "pp"
    require "benchmark"
    
    def docmd( o, cmd )
      r=o.size*3
      Array.new(r){ |y|
        Array.new(r){ |x|
          if o[y/3][x/3]==1
            (cmd=="X") == ((x%3+y%3)%2==0) ? 0 : 1
          else
            0
          end
        }
      }
    end
    
    def paint( f, x, y )
      s=[[x,y]]
      loop do
        x,y=s.pop
        if (0...f.size)===x && (0...f.size)===y && f[y][x]==0
          f[y][x]=1
          s.push( [x, y+1] )
          s.push( [x, y-1] )
          s.push( [x+1,y] )
          s.push( [x-1 ,y] )
        end
        return if s.empty?
      end
    end
    
    def count(f)
      r=0
      f.size.times do |y|
        f.size.times do |x|
          if f[y][x]==0
            r+=1
            paint( f, x, y )
          end
        end
      end
      r
    end
    
    def solve( src )
      field = src.chars.inject( [[1]] ){ |acc, cmd|
        acc = docmd( acc, cmd )
      }
      count(field)
    end
    
    $stdout.sync=true
    
    DATA.map do |line|
      /(?<num>\w+)\s+(?<src>[XO]+)\s+(?<expected>\S+)/=~line
      actual = nil
      tick = Benchmark.realtime{  actual = solve( src ).to_s }
      okay = actual==expected
      puts( "%s %s %s->%s ( e:%s ) tick=%.3f" % [ ( okay ? "ok" : "**NG**" ), num, src[0,70], actual, expected, tick] )
      okay
    end.all?.tap{|x| puts( x ? "everything is ok" : "something wrong" ) }
    
    __END__
    0 X 5 
    1 O 4 
    2 XX  5 
    

    手元のマシンで、テストをすべて通すのに1分ぐらい。
    もっと素晴らしい実装が公開されているけど、私は 1時間ではこれ(の、スタックオーバーフローするバージョン)が限界。

    会場では、
    ・00〜01分→上記の実装のアイディア浮かぶ。
    ・01〜15分→よりよい実装があるはずだと思い、迷走する。
    ・15〜50分→諦めて最初のアイディアで実装する。スタックサイズをいじればテストは通った。
    ・50〜60分→よりよい実装があるはずだと思い、迷走する。
    という感じだった(時間は記録していないので適当です)。

    解けたか解けなかったでいえば解けてはいるものの、敗北感がある。ぐぬぬ。