A solver of tatami mat arrangement problem

tatami.rb

#!/usr/bin/env ruby

# tatami.rb : A solver of tatami mat arrangement problem
#   by takehikom

module Tatami
  class Arranger
    def initialize(w = 4, h = 4, opt = {})
      @width = w
      @height = h
      @action = opt[:action] || :print
      @narrowing = opt[:narrowing]
      init_field
    end

    def init_field
      raise "odd area" if @width % 2 == 1 && @height % 2 == 1
      @num_tatami = @width * @height / 2
      @field = Hash.new
      @tatami_a = []
      @num_answer = 0
    end

    def get_field(x, y)
      @field[[x, y].join(":")]
    end

    def set_field(x, y, v)
      @field[[x, y].join(":")] = v
    end

    def place_tatami(x, y, d)
      puts "place_tatami(#{x},#{y},#{d.inspect})" if $DEBUG
      if d == :ud
        set_field(x, y,     :up)
        set_field(x, y + 1, :down)
        @tatami_a << [x, y, d]
      elsif d == :lr
        set_field(x,     y, :left)
        set_field(x + 1, y, :right)
        @tatami_a << [x, y, d]
      else
        raise "wrong value found in place_tatami"
      end

      if @tatami_a.length == @num_tatami && fit?
        @num_answer += 1
        if $DEBUG || @action == :print
          puts "No.#{@num_answer}#{fitness_to_s(:template => ' (_)', :short => true)}"
          puts field_to_s
        end
      elsif $DEBUG
        puts field_to_s
      end

      @tatami_a.last
    end

    def displace_tatami
      raise "displace_tatami failed" if @tatami_a.empty?
      t = @tatami_a.pop
      x, y, d = t
      if d == :ud
        set_field(x, y,     nil)
        set_field(x, y + 1, nil)
      elsif d == :lr
        set_field(x,     y, nil)
        set_field(x + 1, y, nil)
      else
        raise "wrong value found in displace_tatami"
      end
      puts "displace_tatami(#{x},#{y},#{d.inspect})" if $DEBUG
      puts field_to_s if $DEBUG
      t
    end

    def field_to_s(table = 0)
      case table
      when 0
        table = {
          :up => "↑",
          :down => "↓",
          :left => "←",
          :right => "→",
          :other => "・"
        }
      when 1
        table = {
          :up => "!",
          :down => "i",
          :left => "[",
          :right => "]",
          :other => "?"
        }
      end

      s = ""
      @height.times do |y|
        @width.times do |x|
          v = get_field(x, y)
          s += table[v] || table[:other]
        end
        s += "\n"
      end
      s
    end

    def find_pos
      @height.times do |y|
        @width.times do |x|
          v = get_field(x, y)
          return [x, y] if v.nil?
        end
      end
      raise "empty space not found"
    end

    def eval_fitness
      @fitness = Hash.new
      eval_fitness_four_corner
      eval_fitness_section_line
      @fitness
    end

    def eval_fitness_four_corner
      # returns true if there is no common point of four tatami mats
      if @width == 1 || @height == 1
        return @fitness[:four_corner] = true
      end

      fc_h = Hash.new
      (1...@height).to_a.each do |y|
        (1...@width).to_a.each do |x|
          fc_h[[x, y].join(":")] = true
        end
      end
      @tatami_a.each do |t|
        x, y, d = t
        if d == :ud
          [[x, y + 1], [x + 1, y + 1]].each do |xy|
            key = xy.join(":")
            # puts "delete #{key} by <#{x},#{y},#{d.inspect}>"
            fc_h.delete(key) if fc_h.key?(key)
          end
        elsif d == :lr
          [[x + 1, y], [x + 1, y + 1]].each do |xy|
            key = xy.join(":")
            # puts "delete #{key} by <#{x},#{y},#{d.inspect}>"
            fc_h.delete(key) if fc_h.key?(key)
          end
        end
      end
      puts "fc_h: #{fc_h.inspect}" if $DEBUG

      @fitness[:four_corner] = fc_h.empty?
    end

    def eval_fitness_section_line
      # returns true if there is no section line (except for such a
      # line that runs within one unit length from the periphery)
      sl_h = Hash.new
      (2..(@height - 2)).to_a.each do |y|
        sl_h["h#{y}"] = true
      end
      (2..(@width - 2)).to_a.each do |x|
        sl_h["v#{x}"] = true
      end
      if sl_h.empty?
        return @fitness[:section_line] = true
      end

      @tatami_a.each do |t|
        x, y, d = t
        if d == :ud
          key = "h#{y + 1}"
          # puts "delete #{key} by <#{x},#{y},#{d.inspect}>"
          sl_h.delete(key) if sl_h.key?(key)
        elsif d == :lr
          key = "v#{x + 1}"
          # puts "delete #{key} by <#{x},#{y},#{d.inspect}>"
          sl_h.delete(key) if sl_h.key?(key)
        end
      end
      puts "sl_h: #{sl_h.inspect}" if $DEBUG

      @fitness[:section_line] = sl_h.empty?
    end

    def has_four_corner?
      !@fitness[:four_corner]
    end

    def has_section_line?
      !@fitness[:section_line]
    end

    def fit?
      eval_fitness
      return false if /fc/i =~ @narrowing && has_four_corner?
      return false if /sl/i =~ @narrowing && has_section_line?
      true
    end

    def fitness_to_s(opt = {})
      a = []
      a << (opt[:short] ? "FC" : "four corner") if has_four_corner?
      a << (opt[:short] ? "SL" : "section line") if has_section_line?
      s = a.join(opt[:short] ? "," : ", ")
      s = opt[:template].sub(/_/, s) if !s.empty? && opt[:template]
      s
    end

    def start
      x, y = find_pos
      if y < @height - 1 && get_field(x, y + 1).nil?
        place_tatami(x, y, :ud)
        start if @tatami_a.length < @num_tatami
        displace_tatami
      end
      if x < @width - 1 && get_field(x + 1, y).nil?
        place_tatami(x, y, :lr)
        start if @tatami_a.length < @num_tatami
        displace_tatami
      end
    end
  end
end

if __FILE__ == $0
  if /^B/ =~ ARGV.first
    t = Tatami::Arranger.new(3, 4, :narrowing => "fc")
    t.place_tatami(2, 0, :ud)
    t.place_tatami(0, 3, :lr)
    t.start
    exit
  end

  width = (ARGV.shift || 4).to_i
  height = (ARGV.shift || 4).to_i
  cond = ARGV.shift || ""
  Tatami::Arranger.new(width, height, :narrowing => cond).start
end