http://nabetani.sakura.ne.jp/hena/orde32rects/

hoge.rb

require "pry"

# どう書く 2019-04-06
# http://nabetani.sakura.ne.jp/hena/orde32rects/
#
# 方針
# 1. 各入力矩形で塗ったかどうかを点ごとに記録する
# 2. 全体を舐めてその点がどの図形に属しているかを判定しつつ、面積と縦横別の面積を記録する
# 3. 各図形のうち長方形になっているものを選択して面積を返してソートする
#
# やらないこと
# * サイズが36x36と小さいのでそこを何か上手くやる工夫はしない、交点で計算すればもっと効率化できる

SIZE = 36

def init
  @points1 = Array.new(SIZE).map do
    Array.new(SIZE) do
      {
        ids: [],
      }
    end
  end
  @points2 = Array.new(SIZE).map do
    Array.new(SIZE) do
      {}
    end
  end
  @idcounter = Hash.new(0)
  @rects = {}
end

# 43gw/d7qq/mlop => [[L, U, R, D], ...]
def parse_input(str)
  str.split("/").map do |s|
    s.each_char.map do |x|
      x.to_i(36)
    end
  end
end

def perform_input_rect1(input_rect, id)
  (input_rect[0]...input_rect[2]).each do |w| # L => R
    (input_rect[1]...input_rect[3]).each do |h| # U => D
      @points1[w][h][:ids] << id
    end
  end
end

def get_exist_rect_id(key, prewid, prehid)
  return nil if prewid == nil && prehid == nil
  if prewid == nil
    return prehid if prehid.start_with?("#{key}-")
    return nil
  end
  if prehid == nil
    return prewid if prewid.start_with?("#{key}-")
    return nil
  end

  return prewid if prewid == prehid && prewid.start_with?("#{key}-")
  if prewid.split("-").first == prehid.split("-").first && prehid.start_with?("#{key}-")
    # conflict!!
    @rects[prewid][:dirty] = true
    @rects[prehid][:dirty] = true
    return prehid
  end
  return prehid if prehid.start_with?("#{key}-")
  return prewid if prewid.start_with?("#{key}-")
  return nil
end

def perform
  SIZE.times.each do |w| # L => R
    SIZE.times.each do |h| # U => D
      # next if @points1[w][h][:ids].empty?

      # rectのid決める
      prewid = w > 0 ? @points2[w-1][h][:id] : nil
      prehid = h > 0 ? @points2[w][h-1][:id] : nil

      key = @points1[w][h][:ids].join(",")

      rect_id = get_exist_rect_id key, prewid, prehid
      unless rect_id
        suffix = @idcounter[key]
        @idcounter[key] += 1
        rect_id = "#{key}-#{suffix}"
      end

      @points2[w][h][:id] = rect_id
      @rects[rect_id] ||= {
        area: 0,
        w: Hash.new(0),
        h: Hash.new(0),
      }

      @rects[rect_id][:area] += 1
      @rects[rect_id][:w][w] += 1
      @rects[rect_id][:h][h] += 1
    end
  end
end

def ok_rect?(id)
  rect = @rects[id]
  return false if rect[:dirty]
  # -始まりで隅まで塗っているのはダメ
  if id.start_with?("-")
    return false if rect[:w][0] > 0
    return false if rect[:w][SIZE-1] > 0
    return false if rect[:h][0] > 0
    return false if rect[:h][SIZE-1] > 0
  end
  rect[:w].values.uniq.size == 1 && rect[:h].values.uniq.size == 1
end

def solve(input)
  init
  parse_input(input).each_with_index { |rect, i| perform_input_rect1 rect, i }
  perform
  @rects.select { |k, _| ok_rect?(k) }.map { |_, v| v[:area] }.sort.join(",")
end

def test(input, result)
  res = solve(input)
  if res != result
    p ["NG!!", input, result, res, parse_input(input)]
    p @rects
    exit
  end
end

test( "43gw/d7qq/mlop", "8,57" )
test( "034a", "28" )
test( "06qr/8pnq", "15" )
test( "c1th/b2qy", "210" )
test( "c8wz/gbsg/i0xd", "20" )
test( "97uv/2g5x/eihv", "39,51" )
test( "254d/2jvu/mjvu", "16,99,220" )
test( "ggiu/ggzu/g5ig", "22,28,238" )
test( "jbnc/i7xe/i7je/icje", "2,4,5" )
test( "3cey/0fzo", "27,33,99,110,189" )
test( "00ab/p0zd/0ofz/87rs", "8,12,28" )
test( "1dsy/2d9s/2s9y", "21,42,105,399" )
test( "28db/d0lm/d1i8/l0w5", "33,35,55" )
test( "3aen/4fir/1lev", "2,20,40,48,60" )
test( "j7ou/3rms/m4vs", "3,10,16,42,60" )
test( "336a/3rkw/jlor/3akw", "6,21,24,85" )
test( "21om/87bv/67cv", "9,15,18,27,30,45" )
test( "4hhx/056u/4rvu", "6,20,33,39,42,110" )
test( "b0sh/pgxt/88lq/amux", "3,20,35,44,90" )
test( "c0hc/h6md/fdmk/4cfj", "2,35,49,60,77" )
test( "0liz/ilvz/0lvr/0rvz", "78,104,108,144" )
test( "81ib/q1zb/8cir/qczr", "90,100,135,150" )
test( "h7t8/t8ye/g8he/hetz", "6,12,30,72,252" )
test( "b5qy/o6qc/21tb/qoyu/b5eu", "2,10,18,48,57" )
test( "eajn/jkln/j8ua/nkun/u4wy", "6,21,22,60,65" )
test( "wwzz/nfuw/nfzz/41vw/l1r2/nfrg", "4,6,9,17" )
test( "46rb/t6xb/m7zk/4hrj/thxj", "4,8,10,16,20,36" )
test( "olwx/ogul/ogwx/ogux/agux", "10,24,30,72,238" )
test( "b7un/c3hv/fiyo/h6xm", "2,10,12,13,16,20,52,143" )
test( "d6qa/o4qr/tcur/9bto", "2,4,6,8,15,26,39,44,195" )
test( "2lsx/54hf/k3yi/8dhw/bhny", "3,12,18,24,33,60,66" )
test( "apcx/a8pv/7uwx/a2c8/c8pu", "2,4,9,10,12,13,34,286" )
test( "7yjz/jywz/7ejz/j5wy/bejz/jewy", "4,8,13,80,117,160,260" )
test( "d0wk/5dqu/6lqs/77ae/f4mq/56bm", "3,4,5,7,14,18,28,35,49,63" )
test( "d4gn/94in/d4rs/94xu/97xn", "6,9,12,18,27,32,48,64,70,96,144" )
test( "l5wh/wdxn/60xs/c5fd/jpwx/mgqx", "4,9,10,12,15,18,20,24,30,32" )
test( "5178/58xk/uixk/71u8/71uk/71ui/51ui", "4,6,14,20,30,46,161,230" )
test( "m8sp/mosp/2imp/i8sp/2isp/i8si/misp/iosp", "4,6,24,36,40,60,112" )
test( "34d5/253k/f4m5/m5rk/2o3u/3udy/fumy/moru", "6,7,10,15,28,30,40,75" )
test( "2ilw/mbnc/n9wj/9dmy/6qwy/2ekh/9dkh", "1,6,11,18,21,33,72,80,90,96" )
test( "j0le/10uo/q6ue/jeqt/jelf/l6xf", "2,4,5,27,28,32,35,36,40,54,63,432" )
test( "j4mu/31r5/qeyf/0f5h/r0v5/00qi/j5kf/jlru", "3,4,8,9,10,10,20,27,45,52" )
test( "g8kc/dbuv/gbkc/dbgv/evuw/dbui/d8kw", "1,4,6,9,10,12,21,24,39,52,70,130" )
test( "apry/a0ry/a0hx/60hp/6xhy/a0hp/a0hy/6phy/6phx", "4,7,32,56,90,100,175,250" )
test( "1eok/33by/d0kz/1rnw", "10,10,12,12,14,15,16,21,24,35,40,42,48,49,56,88,98" )
test( "0qbs/6cws/l6xj/659q/03lc/bclp/96dj/96wc", "10,12,13,14,14,21,24,42,48,66,77" )
test( "q8sr/98yu/clyn/s8yl/9lqr/0rsu/0l9m/0n9u", "4,8,9,12,26,27,28,36,42,57,78,221" )
test( "5sjy/jbsy/8dgp/gkvp/gdvh/jhvp/i2vk", "3,4,6,8,9,12,15,15,18,27,36,45,81,84,96" )
test( "42va/10nf/23l6/c2uw/3hpo/4ofu/m7sv", "3,5,6,8,8,15,18,20,21,24,27,32,48,50,63,70" )
test( "84lj/10j1/wcxd/ljnl/1njx/01xd/00x1/81wq/1c8q", "1,1,4,7,11,14,18,21,33,70,78,117,126" )
test( "kfvg/76vq/136d/6gvq/6g7q/137g/7dmz/63m6/m3vz", "2,3,9,10,27,45,50,81,81,90,105,135,150" )
test( "4eht/38jt/jeym/htjv/eeyv/eejt/3myv/h1jt/hejm", "4,6,7,12,14,14,16,21,22,24,70,80,120,135" )
test( "smuz/04c7/28zc/83ri/cihu/8flm/masw/8ivo", "2,4,6,8,10,10,12,16,16,20,22,24,24,30,30,36,39,48" )
test( "7fuu/17fd/6cpg/fghu/ahnt/adww/rhxz/4hxl/0pby", "1,2,2,2,3,3,4,4,4,5,8,8,9,10,12,12,12,12,15,15,16,16,20,24,27,30,32,48" )