Google Developer Day 2011 Tokyo / DevQuiz: Sliding puzzles

solve.rb

# this script requires ruby 1.9.2
# usage: ruby solve_with_desc.rb [filename]
# or     ruby solve_with_desc.rb < filename (via STDIN)

require 'pp'

class Array
  def hdup
    self.inject([]){|r,i| r << i.dup }
  end
end

module Puzzle
  def self.parse(input=ARGF.read)
    Parser.new(input).parse
  end

  class ProblemList
    include Enumerable

    attr_reader :solves

    def initialize(ary,l,r,u,d)
      @problems = ary
      @solves = nil

      @l_limit = l
      @r_limit = r
      @u_limit = u
      @d_limit = d

      @l = \
      @r = \
      @u = \
      @d = 0
    end

    def [](i)
      @problems[i]
    end

    def each(&block)
      @problems.each &block
    end

    def solve_all
      @problems.each {|problem| puts problem.solve }
    end

    def limit(of=nil)
      if of
        raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(of.to_sym)
        eval "@#{of}_limit"
      else
        Hash[[:l,:r,:u,:d].map{|t| [t, limit(t)] }]
      end
    end

    def used(type=nil)
      if type
        raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(type.to_sym)
        eval "@#{type}"
      else
        Hash[[:l,:r,:u,:d].map{|t| [t, used(t)] }]
      end
    end

    def remain(of=nil)
      if of
        raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(of.to_sym)
        limit(of) - used(of)
      else
        Hash[[:l,:r,:u,:d].map{|t| [t, remain(t)] }]
      end
    end

    def use(type)
      case type
      when Hash
        type.each do |k,v|
          eval "@#{k} += #{v}"
        end
      else
        raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(type.to_sym)
        eval "@#{type} += 1"
      end
      self
    end
  end

  class Problem
    attr_reader :board, :commits, :latest, :no, :empty

    def initialize(board, i=0)
      @board = board
      @latest = board.hdup
      @first = to_s
      @commits = []
      @empty = nil
      @no = i
      #@dic = {}
    end

    def latest
      @latest
    end

    def used
      @commits.inject({l:0,r:0,u:0,d:0}) do |r,i|
        r[i]+=1;r
      end
    end

    def use(type)
      raise ArgumentError, "only lrud" unless [:l,:r,:u,:d].include?(type.to_sym)

      detect_empty unless @empty

      case type.to_sym
      when :l
        return false if @empty[1] == 0
        if @latest[@empty[0]][@empty[1]-1] == :"="
          return false
        else
          @latest[@empty[0]][@empty[1]-1], @latest[@empty[0]][@empty[1]] = @latest[@empty[0]][@empty[1]], @latest[@empty[0]][@empty[1]-1]
          @empty[1] -= 1
        end
      when :r
        return false if @empty[1] == (@latest[@empty[0]].size-1)
        if @latest[@empty[0]][@empty[1]+1] == :"="
          return false
        else
          @latest[@empty[0]][@empty[1]+1], @latest[@empty[0]][@empty[1]] = @latest[@empty[0]][@empty[1]], @latest[@empty[0]][@empty[1]+1]
          @empty[1] += 1
        end
      when :u
        return false if @empty[0] == 0
        if @latest[@empty[0]-1][@empty[1]] == :"="
          return false
        else
          @latest[@empty[0]-1][@empty[1]], @latest[@empty[0]][@empty[1]] = @latest[@empty[0]][@empty[1]], @latest[@empty[0]-1][@empty[1]]
          @empty[0] -= 1
        end
      when :d
        return false if @empty[0] == (@latest.size-1)
        if @latest[@empty[0]+1][@empty[1]] == :"="
          return false
        else
          @latest[@empty[0]+1][@empty[1]], @latest[@empty[0]][@empty[1]] = @latest[@empty[0]][@empty[1]], @latest[@empty[0]+1][@empty[1]]
          @empty[0] += 1
        end
      end

      @commits << type.to_sym

      true
    end

    def detect_empty
      @empty = board.each_with_index.inject([]) do |r,(l,i)|
        r[1] ? r : [i,l.index(nil)]
      end
    end


    def goal?
      if @latest[-1][-1].nil?
        m = self.to_s
        a = m.gsub(/[=0]/,"")
        b = a.chars.sort.join

        a == b# && m[-1] == "0" #&& (m.gsub(/\d/,"!") == n.gsub(/\d/,"!"))
      end
    end

    def to_s
      @latest.map do |l|
        l.map{|x| x.nil? ? :"0" : x }.join
      end.join
    end

    def undo(n=1)
      n.times do
        @commits.pop
      end
      self
    end

    def complete
      @commits.join.upcase
    end

    def solve
      reset
      queue = [[@board.hdup, @commits.dup, detect_empty]]
      types = [:l,:r,:u,:d]
      hash = {}

      i = 0
      while (a=queue.shift)
        if i != a[1].join.size
          puts a[1].join
          i = a[1].join.size
        end
        types.each do |t|
          set *a
          next if reverse?(t)
          next unless use(t)
          return complete if goal?

          unless hash.has_key?(@latest)
            hash[@latest] = true
            q = [@latest.hdup, @commits.dup, @empty.dup]
            queue << q
          end
          #@commits.pop #undo
        end
      end
    end

    def set(b,c,s)
      @latest = b.hdup
      @commits = c.dup
      @empty = (s.nil? ? nil : s.dup)
    end

    def reset
      @commits = []
      @empty = nil
    end

    class CannotMove < Exception; end
    class LimitReached < Exception; end
    class Goal < Exception; end

    def reverse?(t)
      hash = {
        l: :r,
        r: :l,
        u: :d,
        d: :u
      }
      hash[@commits[-1]] == t
    end
  end

  class Parser
    attr_reader :input, :list

    def initialize(input)
      @input = input
      @list = nil
    end

    def parse
      lines = input.split(/\r?\n/)
      l,r,u,d = lines.shift.split(/ /).map(&:to_i)
      problem_count = lines.shift.to_i
      problems = []
      while (problem = parse_problem(lines.shift, problems.size))
        problems << problem
      end
      raise "problem_count != problems.size" unless problems.size == problem_count

      problems.sort_by{|problem| problem.board.size * problem.board[0].size }
      @list = ProblemList.new(problems,l,r,u,d)
    end

    private

    def parse_problem(line, i)
      if line
        w,h,b = line.split(/,/)

        b = b.chars.to_a
        w,h = w.to_i, h.to_i

        ls = []
        h.times do |i|
          l = []
          w.times do |j|
            chr =  b.shift.to_sym
            if chr == :"0"
              l << nil
            else
              l << chr
            end
          end
          ls << l
        end
        raise "b is not empty" unless b.empty?
        Problem.new ls, i
      else
        nil
      end
    end
  end
end

#pp Puzzle.parse
Puzzle.parse(ARGF.read).solve_all