オフラインリアルタイムどう書くE14 の問題の実装例

  • 0
    Like
  • 0
    Comment

    オフラインリアルタイムどう書くE14 の問題の実装例です。

    問題 : http://mtsmfm.github.io/2017/06/03/doukaku-e14.html
    解答リンク集 : http://qiita.com/mtsmfm/items/89b6634f363bbf5b47f5
    イベント : https://yhpg.doorkeeper.jp/events/59397

    def rot( f )
      f.transpose.reverse
    end
    
    # 横に4マス続くパターンを含む展開図
    def solve1(m)
      (1..m.size-2).each do |y|
        (0..m[0].size-4).each do |x|
          a=m[y][x]
          b=m[y][x+1]
          next if a==b
          next unless 7-a==m[y][x+2]
          next unless 7-b==m[y][x+3]
          rest = [*1..6] - [a, 7-a, b, 7-b]
          return true if [0,1].any?{ |ix| m[y-1][x,4].include?(rest[ix] ) && m[y+1][x,4].include?(rest[1-ix] ) }
        end
      end
      false
    end
    
    # 3×1 が2つという形の展開図
    def solve2(m)
      (0..m.size-2).each do |y|
        (0..m[0].size-5).each do |x|
          a,b,c =[0,1,2].map{ |ix| m[y][x+ix] }
          d,e,f =[0,1,2].map{ |ix| m[y+1][x+ix+2] }
          return true if a+c==7 && d+f==7 && b+e==7 && [a,b,c,d,e,f].uniq.size==6
        end
      end
      false
    end
    
    # 階段状の展開図
    def solve3(m)
      (0..m.size-3).each do |y|
        (0..m[0].size-4).each do |x|
          a,b =[0,1].map{ |ix| m[y][x+ix] }
          c,d =[0,1].map{ |ix| m[y+1][x+ix+1] }
          e,f =[0,1].map{ |ix| m[y+2][x+ix+2] }
          return true if a+d==7 && b+e==7 && c+f==7 && [a,b,c,d,e,f].uniq.size==6
        end
      end
      false
    end
    
    # それ以外の展開図
    def solve4(m)
      (0..m.size-3).each do |y|
        (0..m[0].size-4).each do |x|
          b,c,d =[0,1,2].map{ |ix| m[y+1][x+ix+1] }
          e,f =[0,1].map{ |ix| m[y+2][x+ix] }
          a, = [*1..6] - [ b, c, d, e, f ]
          next unless m[y][x+1,3].include?(a)
          return true if a+f==7 && b+d==7 && c+e==7 && [a,b,c,d,e,f].uniq.size==6
        end
      end
      false
    end
    
    def solve_impl( src )
      field = src.split(",").map{ |x| x.chars.map(&:to_i) }
      2.times do
        4.times do |r|
          return "1" if solve1(field)
          return "2" if solve2(field)
          return "3" if solve3(field)
          return "4" if solve4(field)
          field = rot( field )
        end
        field = field.reverse
      end
      false
    end
    
    def solve( src )
      (!!solve_impl(src)).to_s
    end
    
    if $0==__FILE__
      okays = DATA.map do |line|
        num, src, expected = line.split(/\s+/)
        actual = solve( src )
        ok = actual==expected
        p [ ok ? "ok" : "**NG**", num, src, actual, expected ]
        ok
      end
      p [ okays.count{ |x| x }, okays.size ]
    end
    
    __END__
    0 44165,44516 false 状況
    1 26265,31436 true  状況
    2 46345,54215 true  状況
    3 62143,11152 false 状況
    4 4242,4314,1562  false 状況
    5 5612,3656,4523  false 状況
    136 5545354,6566343,3525411,5356165,4625265,1535435,5522665 false 状況
    

    いつもどおり、テストケースの大半は省略。

    45分ぐらいで解けた気がするけど、苦しい感じだった。
    解けてほっとした。

    展開図を4種類に分けて、それぞれベタに書くという戦略
    手数が多いので書ききれるかどうか心配だったけどなんとかなった。

    想定解がどうなっているのかはまだわからないんだけど、どうなんだろ。