POH5 special

POHでMINAMIちゃんと結婚できて嬉しいと思っていたら、
もう一つスペシャル版があったんですね。
https://paiza.jp/poh/enshura-special

これは・・・難しい。。こっちがメインなんですね。

当然ですが、幅優先探索すると15パズルの場合メモリがエラいことになるので、
「最短の手数でパズルを完成させる必要はなく」という条件が入ってるんだろうと
思うのですが、それはそれで難しい。。

まずは最後まで解ききるプログラムを作ってみよう、ということで
作ってみたんですが、かなりのスパゲッティコードなってしまった。。
https://paiza.jp/poh/enshura-special-ending/22b23878?o=2cf67029

ソースはもうちょっと整理してから載せようと思います。

2015/04/19 21:56追記

整理してもスパゲッティ度はあんまり変わらなかったのでとりあえず今の状態で記録。

基本的な考えは幅優先探索で解けるサイズまで地道に揃えてから、
残りは最適解にして手数を稼ぐという方式にしました。具体的には

1. 1,2段目(1~8)までは最適解を目指さずとにかく揃える
2. 3,4段目は幅優先探索で最適解を計算する

とりあえず揃える

まず使う記号ですが、

• 1~15はそのまま数字で。
• 任意の数字はアルファベット(X,Y・・・)で。
• 空白の場所は*で。
• 特に注目する場所の場合@で。

ということにします。

まず最初の1,2段目の処理ですが、いろいろ方法があると思いますが、
私が行っている処理は下記のようなものです。

2段階ありまして、1段目を例すると、
1,2,3,4に関して、まずこの形を目指します。

 1 2 3 X
 X X X X
 ...

この後、4をここに持ってきます

1 2 3 X
X X X 4
...

このとき

1 2 3 *
X X X 4
...

となっていれば素直に4を上に移動させばおしまいです。
そうではないとき、まず、1,2,3を下記のように移動させます。

2 3 * Y
1 X X 4
...

で、4をあるべき位置に持っていきます。

2 3 Y 4
1 X X X
...

そしたら適当に邪魔なYを下にさげて空いた所に、1,2,3を戻して完成です。

2 3 * 4
1 X Y X
...

1 2 3 4
X X Y X
...

で、これをするにあたって、任意の数字を今ある場所から、本来あるべき位置に持っていく処理が必要です。
例えば、下記のような例で2を本来の場所に持って行く場合

1 Y X X
X X X X
2 X X X
* X X X

Yがある場所に持っていく必要がありますが、このときすでに本来の場所にいる1を
動かしていいとなると、それを元の位置にまた直すのが面倒なので、
今動かそうとしている数字(2)より小さい数字は動かさずに、Yまで行く最短経路を見つけます。
これは普通に幅優先探索で見つければいいですね。上記の例の場合

1 @ X X   or  1 @ X X
@ @ X X       X @ X X
2 X X X       2 @ X X
* X X X       * X X X

のいずれかですね。とりあえず最初に見つかった方でいいので、例えば前者のルートで2を
移動させるにあたり、今2の上にある数字をどかす必要があります。その数字をどかすために、
また別の数字をどかす必要があります。
つまり、今から動かそうとする最初の1手目にある位置から、今の動かそうとする数字(2)より
大きい数字だけを使って、現在の空白の位置までの最短距離を求めればいいですね。
これも幅優先探索で行けます。

1 X X X
Y X X X
2 X X X
* X X X

つまり上記のYから1,2を動かさずに最短で*に行ける経路、下記の経路,A->B->Cを見つけます。

1 X X X
Y A X X
2 B X X
* C X X

それが見つかったら、下記のように移動して、2を上に移動させます

1 X X X
2 Y X X
* A X X
C B X X

こんな感じに1,2,3を移動させていって、最初に書いた1段目でいう4の処理を施すと

1 2 3 4
5 6 7 8
X X X X
X X X X

という形まではもっていけます。
ここまで持ってきたら、下2段は単純な8パズルと同じ形ですので、
普通に幅優先探索で処理出来るサイズになります。
ただ、ちょっとでも時間を稼ぐために、単純に下段を揃えながら最終状態になる探索だけではなく、
最終状態からも同時に幅優先探索を行って(双方向探索)ちょっとでもメモリと速度を稼ぐようにしてみました。

とまぁ、こんな手段なので無駄に処理が長いのですが、上位の方とくらべて、
完成までのstepが約倍程度(40step程度に対して80step)になってしまっています。

#coding: Windows-31J

class NextPositionGenerator
  DIR = [[-1, 0], [1, 0], [0, 1], [0, -1]]

  def initialize(row, col)
    @row_size = row
    @col_size = col
  end

  def next_pos(row, col)
    DIR.each do |delta_row, delta_col|
      #p [:a, row, col, delta_row, delta_col]
      next_row = row + delta_row
      next_col = col + delta_col
      if next_row >= 0 && next_col >= 0 && next_row < @row_size && next_col < @col_size
        yield next_row, next_col
      end
    end
  end
end

State = Struct.new(:key, :r, :c, :dir, :prev) do
  class << self
    def board_to_key(board)
      board.map{|e| e.join}.join
    end

    def key_to_board(key)
      #p [:key, key, key.chars.each_slice(4).to_a]
      key.chars.each_slice(COL_SIZE).to_a
    end

    def state_to_array(s)
      if s.prev
        if s.dir == :forward
          state_to_array(s.prev) + [s]
        else
          [s] + state_to_array(s.prev)
        end
      else
        [s]
      end
    end
  end
end

class Solver
  attr_reader :row_size, :col_size
  def initialize(row, col)
    @row_size = row
    @col_size = col
  end

  def solve
    board = load_board
    sub_solver = BruteForceSolver.new(self)
    sub_solver.solve(board)
    brute_moves = sub_solver.moves
    unless brute_moves.empty?
      puts brute_moves.map{|e|
        e.to_i(16).to_s
      }.join("\n")
    end
    puts solve_shortest_path(board).join("\n")
  end

  def find_pos(board, num)
    @row_size.times do |row|
      @col_size.times do |col|
        return row, col if board[row][col] == num
      end
    end
  end

  def find_space_pos(board)
    find_pos(board, "0")
  end

  def dump_board(board)
    board.map{|row|
      row.map{|e|
        num =
        case e
        when "0"
          "*"
        else
          e.to_i(16).to_s
        end
        "%02s" % [num]
      }.join(" ")
    }.join("\n")
  end


  private
  def solve_shortest_path(board)
    search(board)
  end

  def load_board
    readlines.map {|line|
      line.chomp.split(/ /).map{|e|
        case e
        when "*"
          "0"
        else
          e.to_i.to_s(16)
        end
      }
    }
  end

  def list_answer(s1, s2)
    if s1.dir == :forward
      fs, bs = s1, s2
    else
      fs, bs = s2, s1
    end
    (State.state_to_array(fs) + State.state_to_array(bs)).each_cons(2).map do |e1, e2|
      (State.key_to_board(e1.key)[e2.r][e2.c]).to_i(16)
    end
    #puts State.state_to_array(fs).join("\n")
    #puts State.state_to_array(bs).join("\n")
  end

  #初期状態と終了状態から双方向に幅優先探索
  def search(board)
    b = board.drop(2).to_a
    r, c = find_space_pos(b)
    queue = []
    history = {}

    init_key = State.board_to_key(b)
    init_state = State.new(init_key, r, c, :forward, nil)
    queue << init_state
    history[init_key] = init_state

    goal_key = "9abcdef0"
    goal_state = State.new(goal_key, (@row_size - 2) - 1, @col_size - 1, :backward, nil)
    queue << goal_state
    history[goal_key] = goal_state

    pos_gen = NextPositionGenerator.new(@row_size - 2, @col_size)

    while not queue.empty?
      s = queue.shift
      pos_gen.next_pos(s.r, s.c) do |nr, nc|
        board = State.key_to_board(s.key)
        #p [:board, board]
        num = board[nr][nc]
        board[nr][nc] = "0"
        board[s.r][s.c] = num
        new_key = State.board_to_key(board)
        h = history[new_key]
        if h
          if h.dir != s.dir
            #p :found

            return list_answer(h, s)
          end
        else
          new_state = State.new(new_key, nr, nc, s.dir, s)
          history[new_key] = new_state
          queue << new_state
        end
      end
    end
    false
  end

  class BruteForceSolver
    REGULAR_POS = {
      "1" => [0, 0],
      "2" => [0, 1],
      "3" => [0, 2],
      "4" => [0, 3],
      "5" => [1, 0],
      "6" => [1, 1],
      "7" => [1, 2],
      "8" => [1, 3]
    }

    attr_reader :moves
    def initialize(parent)
      @parent = parent
      @moves = []
    end

    def distance_to_regular_pos(r, c, rr, rc)
      [rr - r, rc - c]
    end

    def brute_solve(board, a, b, c, d)

      #p :initial
      #puts @parent.dump_board(board)

      #最初の3つ(1, 2, 3)は愚直に動かす
      [a, b, c].each do |num|
        r_delta, c_delta = distance_to_regular_pos(*@parent.find_pos(board, num), *REGULAR_POS[num])
        #p [:delta, r_delta, c_delta]
        if [r_delta, c_delta] != [0, 0]
          move(board, num, r_delta, c_delta)
        end
      end

      #この時点でで4が正しい場所にあれば終わり
      if @parent.find_pos(board, d) == REGULAR_POS[d]
        return @moves
      end

      #4はまず[1, 3]に持ってくる
      # 1 2 3 X
      # X X X 4
      prev_pos = [REGULAR_POS[d][0] + 1, REGULAR_POS[d][1]]
      #p [:prev_pos, prev_pos]
      if @parent.find_pos(board, d) != prev_pos
        r4_delta, c4_delta = distance_to_regular_pos(*@parent.find_pos(board, d), *prev_pos)
        move(board, d, r4_delta, c4_delta)
      end

      #4の場所が空いてたらそのまま動かす
      if board[REGULAR_POS[d][0]][REGULAR_POS[d][1]] == "0"
        move(board, d, -1, 0)
      else
        #空いてなければ、1,2,3を一旦どけて、
        # 1 2 3 X -> 2 3 X *
        # X X X 4    1 X X 4
        move(board, a, 1, 0)
        move(board, b, 0, -1)
        move(board, c, 0, -1)

        #4をいれて
        # 2 3 X 4
        # 1 X X *

        move(board, board[REGULAR_POS[d][0]][REGULAR_POS[d][1]], 0, -1)
        move(board, d, -1, 0)

        #1,2,3を元に戻す
        # 1 2 3 4
        # X X X X
        left_of_d = [REGULAR_POS[d][0], REGULAR_POS[d][1] - 1]
        move(board, board[left_of_d[0]][left_of_d[1]], 1, 0)
        move(board, c, 0, 1)
        move(board, b, 0, 1)
        move(board, a, -1, 0)
      end
      @moves
    end

    def solve(board)
      #4x4サイズを幅優先で解くのは辛いので、1,2段目だけ頑張って揃える(残りの2x4は最適解にする)
      brute_solve(board, '1', '2', '3', '4')
      brute_solve(board, '5', '6', '7', '8')
    end

    def calc_path_helper(f, t)
      if (f < t)
        (f + 1).upto(t)
      else
        (f - 1).downto(t)
      end
    end

    def calc_path(board, from_r, from_c, to_r, to_c)
      path_history = find_path_to_num(board, board[to_r][to_c], from_r, from_c, from_r, from_c)
      path = []
      while path_history
        path << [path_history.r, path_history.c]
        path_history = path_history.prev
      end
      path.reverse.drop(1)
    end

    BruteState = Struct.new(:r, :c, :prev)
    def find_path_to_num(board, num, r, c, next_r, next_c)
      #p [:find_path_to_space, r, c, next_r, next_c]
      history = {}
      queue = []

      history[[next_r, next_c]] = true
      queue << BruteState.new(next_r, next_c, nil)
      pos_gen = ::NextPositionGenerator.new(@parent.row_size, @parent.col_size)
      while not queue.empty?
        #p [:queue, queue.map{|e| [e.r, e.c]}]
        s = queue.shift
        pos_gen.next_pos(s.r, s.c) do |nr, nc|
          #p [:hoge, nr, nc, r, c, board[nr][nc], board[r][c], history, [nr, nc], board[nr][nc] > board[r][c], history[[nr, nc]]]
          if board[nr][nc] == num
            return BruteState.new(nr, nc, s)
          elsif [nr, nc] != [r, c] && board[nr][nc] > board[r][c] 
            unless history[[nr, nc]]
              history[[nr, nc]] == true
              queue << BruteState.new(nr, nc, s)
            end
          end
        end
      end
    end


    def move_tile_out_of_the_way(board, s)
      if s.prev
        @moves << board[s.prev.r][s.prev.c]
        board[s.prev.r][s.prev.c], board[s.r][s.c] = board[s.r][s.c], board[s.prev.r][s.prev.c]
        move_tile_out_of_the_way(board, s.prev)
      end
    end

    def move_num(board, num, r, c, path)
      current_r, current_c = r, c
      path.each do |next_r, next_c|
        #p [:move_num, num, next_r, next_c]
        unless board[next_r][next_c] == "0"

          #p :before
          #puts @parent.dump_board(board)
          s = find_path_to_num(board, "0", current_r, current_c, next_r, next_c)
          move_tile_out_of_the_way(board, s)
          #p :after
          #puts @parent.dump_board(board)
        end

        @moves << num
        board[next_r][next_c], board[current_r][current_c] = board[current_r][current_c], board[next_r][next_c]
        #puts :result
        #puts @parent.dump_board(board)
        current_r, current_c = next_r, next_c
      end

    end

    def move(board, num, r_delta, c_delta)
      r, c = @parent.find_pos(board, num)

      path = calc_path(board, r, c, r + r_delta, c + c_delta)
      #p [:path, num, path]
      move_num(board, num, r, c, path)
    end
  end

end

ROW_SIZE = 4
COL_SIZE = 4
Solver.new(ROW_SIZE, COL_SIZE).solve

上記のコードの結果は
https://paiza.jp/poh/enshura-special-ending/cd0ee374?o=6c545ecd
です。

2015/04/20 20:25
なんか今日から上位30位まで表示させるようになったんですね。
記念！