オフラインリアルタイムどう書く E10 「塗って繋ぐ」をRubyで塗る

  • 0
    いいね
  • 0
    コメント

    当日は時間内に書きあがりませんでした。
    その後同じアイディアで動くものを書いたのですが、時間がかかりすぎですべての問題を解く前に Ctrl+C 。
    で。あくまで塗るというアイディアはそのままにできるだけ早いコードを探しました。三日ほどさまよいました。

    結果、私の Mac でおよそ 10 秒で全問解き終わるぐらいのコードになりました。
    そのうち解説を、描きたい。

    問題はこちら http://mtsmfm.github.io/2016/12/03/doukaku-e10.html
    みなさんの解答はこちら http://qiita.com/mtsmfm/items/8a78b895910a89e3012d

    orde10.rb
    require 'benchmark'
    require 'set'
    
    PATTERNS = {
      'X' => [[1, 0], [0, 1], [2, 1], [1, 2]],
      'O' => [[0, 0], [2, 0], [1, 1], [0, 2], [2, 2]]
    }
    
    def filled_area_count(size, blocks)
      block_set = blocks.map {|x, y| y * size + x }.to_set
      sentinel_index = size ** 2
      board = Array.new(sentinel_index) { sentinel_index }
    
      transform_table = {}
    
      next_index = 1
      sentinel_index.times do |i|
        next if block_set.include?(i)
        left_index  = (i % size == 0) ? sentinel_index : board[i - 1]
        upper_index = (i / size == 0) ? sentinel_index : board[i - size]
    
        if (left_index == sentinel_index) && (upper_index == sentinel_index)
          board[i] = next_index
          next_index += 1
        elsif left_index == upper_index
          board[i] = left_index
        else
          actual_index, alias_index = (left_index < upper_index) ? [left_index, upper_index] : [upper_index, left_index]
          transform_table[alias_index] = actual_index
          board[i] = actual_index
        end
      end
    
      filled_indices = board.flatten.to_set.delete(sentinel_index)
    
      transform_table.sort.reverse.each do |alias_index, actual_index|
        filled_indices.delete(alias_index)
        filled_indices.add(actual_index)
      end
    
      filled_indices.size
    end
    
    def solve(input)
      size = 
      blacks = input.chars.reduce([[0, 0]]) {|blacks, c|
        blacks.map {|cell|
          PATTERNS[c].map {|x, y| [cell[0] * 3 + x, cell[1] * 3 + y] }
        }.flatten(1)
      }
    
      filled_area_count(3 ** input.length, blacks).to_s
    end
    
    def test(input, expected)
      actual = solve(input)
      if actual == expected
        print "\x1b[1m\x1b[32m.\x1b[0m"
      else
        puts(<<~EOS)
          \x1b[1m\x1b[31m
          input:    #{input}
          expected: #{expected}
          actual:   #{actual}\x1b[0m
        EOS
      end
    end
    
    def test_all(data)
      data.each do |line|
        input, expected = line.split
        test(input, expected)
      end
    
      puts
    end
    
    time = Benchmark.realtime { test_all(DATA) }
    
    puts format('%8.3f sec', time)
    
    __END__
    X 5
    O 4
    XX 5
    OX 10
    XO 9
    XOO 17
    OXX 21
    OXO 18
    OOOX 130
    OXXO 29
    XXOX 81
    XOXXO 89
    OOOOX 630
    OXOOO 66
    OXOXOX 2001
    OXOXXO 417
    OXXOXX 1601
    XXXOXOO 345
    OOOOOXO 3258
    OXXOXXX 6401