September 13, 2011

Google Developer Day 2011:DevQuiz解答晒し大会(7)

スライドパズル

結果はというと……364/5000。いまひとつうまくいかなかった感じ。

  • 基本は幅優先探索
  • 評価値の小さいものを優先的に探索
  • ある程度展開した時点で評価値の小さい64組以外をカット(3*3を除く)
  • 評価値 = (パネルのマンハッタン距離の和)+(異なるパネル数)

A*探索も実装してはみたが投入まではいかなかった。

コードはrubyで実装。Pentium4 2.4GHz、メモリ4GBのマシンで実行した。マス数9～16の状態で一通りまわして300問、マス数18～25は1000問くらいの時点で打ち切って64問という具合。効率を一切考えずに書いたんで課題は多いかな。

プログラムは3つに分割した。

1. solver/mod_bfsearch.rb


load 'solver/util.rb'

class Solver

  include SolverUtil

  attr :board
  attr :width
  attr :height
  attr :result

  def initialize(b,w,h)
    @board=b
    @width=w
    @height=h
    r="123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[0..b.length-2] + '0'
    (0..b.length-1).each { |pos|
      r[pos]='=' if b[pos]=='='
    }
    @result=r
  end

  def solve(start=@board,close=[])
    queue=[]
    board=start
    init_score = major(@board)
    move = ''
    until (board == @result || move ==  nil)
      available(board,@width,@height).split('').delete_if { |c|
        after = move(c,board,@width,@height)
        close.include? after
      }.map { |c|
        after = move(c,board,@width,@height)
        score = major(after)
        queue.push [move+c, after, score] if (init_score > score || @width*@height < 10)
        close.push after
      }
      if (queue.length > 512)
        queue.sort! { |a, b| a[2] <=> b[2] }
        if (@width*@height > 10)
          new_queue = queue[0..63]
          queue = new_queue
          # init_score = (init_score * 9) / 10
          init_score = queue[63][2]
        end
      end
      (move, board, s) = queue.shift
    end
    move
  end

  def major(board)
    dist=0
    (0..board.length-1).each { |n|
      if (board[n] != '=')
        m = @result.index(board[n])
        dist += dist(m,n,@width)
      end
    }
    dist + diffs(board)
  end

  def dist(m,n,w)
    d = abs(m-n)/w
    if (m > n)
      m -= d*w
    else
      n -= d*w
    end
    d+abs(m-n)
  end

  def abs(x)
    x = -x if x < 0 
    x
  end

  def diffs(board)
    d = 0
    (0..board.length-1).each { |n| 
      d += 1 if board[n] != @result[n] && board[n] != '0'
    }
    d
  end
end

2. solver/util.rb


module SolverUtil

  def available(board,width,height)
    result=''
    pos = board.index('0')
    result += 'L' if (pos%width != 0 && board[pos-1] != '=')
    result += 'R' if (pos%width != width-1 && board[pos+1] != '=')
    result += 'U' if (pos/width != 0 && board[pos-width] != '=')
    result += 'D' if (pos/width != height-1 && board[pos+width] != '=')
    result
  end

  def move(c,board,width,height)
    case c
    when 'L'
      result=left(board,width,height)
    when 'R'
      result=right(board,width,height)
    when 'U'
      result=up(board,width,height)
    when 'D'
      result=down(board,width,height)
    end
    result
  end

  def left(board,width,height)
    result=board.dup
    pos=board.index('0')
    if (pos%width != 0 && board[pos-1] != '=')
      result[pos]=result[pos-1]
      result[pos-1]='0'
    end
    result
  end

  def right(board,width,height)
    result = board.dup
    pos = board.index('0')
    if (pos%width != width-1 && board[pos+1] != '=')
      result[pos]=result[pos+1]
      result[pos+1]='0'
    end
    result
  end

  def up(board,width,height)
    result = board.dup
    pos = board.index('0')
    if (pos/width != 0 && board[pos-width] != '=')
      result[pos]=result[pos-width]
      result[pos-width]='0'
    end
    result
  end

  def down(board,width,height)
    result = board.dup
    pos = board.index('0')
    if (pos/width != height-1 && board[pos+width] != '=')
      result[pos]=result[pos+width]
      result[pos+width]='0'
    end
    result
  end

end

3. main.rb


load 'solver/mod_bfsearch.rb'

def consume_count(s,c)
  r=0
  s.split('').each { |c1|
    r += 1 if c1 == c
  }
  r
end

result_file = ARGV[0]
min_size = ARGV[1].to_i
max_size = ARGV[2].to_i

result = open(result_file,"wb")

open("problems.txt", "r") do |f|
  move_limits = f.gets.split(' ').map{ |n| n.to_i }
  num_problems = f.gets.to_i
  num = 0
  solved = 0
  while (f.gets)
    w,h,b=$_.chomp.split(',')
    w = w.to_i
    h = h.to_i
    STDERR.puts "#{num+1} #{solved} #{b} #{w} #{h} #{move_limits}"
    if (w.to_i * h.to_i > max_size || w.to_i * h.to_i < min_size)
      result.puts ''
    else
      board=Solver.new(b,w.to_i,h.to_i)
      s=''
      begin
        s = board.solve
        if (s != nil)
          move_consume = ['L','R','U','D'].map { |c| consume_count(s,c) }
          (0..3).each { |n|
            move_limits[n] -= move_consume[n]
          }
          STDERR.puts "#{s} #{move_consume}"
          result.puts s
          solved += 1
        else
          result.puts ''
        end
      rescue SystemStackError
        result.puts ''
      end 
    end
    num += 1
  end
end