松江Ruby会議08のプログラミングコンテスト参加記

松江Ruby会議08のプログラミングコンテスト に参加してました。最終的な順位は再度集計が行われるので確定ではありませんが、締め切り時点では3位でした。

問題

公式ページより引用

「S」「G」「#」で構成される迷路が与えられます。
「S」「G」間をなるべく最短かつ早くクリアできるプログラムを作成してください。
「S」から「G」までは解答例のように「:」で経路を表示させて下さい

NxN で構成される以下のようなテストケースが与えられます。
10≦N≦100となる迷路を生成します。

入力として迷路が与えられるので、ゴールまでの経路を追加したフィールドを出力する問題でした。

戦略

迷路の探索法には色々あり 迷路で眺める探索アルゴリズム に様々な手法が紹介されています。今回のコンテストで自分は「幅優先探索」と「深さ優先探索」の2つの手法の実装を行いました。

幅優先探索 (Breadth First Search)

幅優先探索は探索を開始した地点からの距離が近い場所を1つずつ調べていく手法です。この手法では最初に見つけた経路が 必ず最短 になるので、今回の問題の制約的にはこの手法が想定解だと思われます。（下のgifは幅優先探索の様子です）

ただ、この手法では現在の探索状況や探索済みのマス情報などの様々な状態を保持する必要があり、その処理部分がボトルネックとなって実行時間を最短にすることが出来ませんでした。（270msec程）

Node = Struct.new(:ypos, :xpos, :route)
DY = [-1, 0, 1, 0]
DX = [0, 1, 0, -1]

field = $<.map(&:chomp)

height = field.size
width = field[0].size

height.times do |y|
  width.times do |x|
    if field[y][x] == 'S'
      que = []
      que.push(Node.new(y, x, []))
      check_list = Array.new(height) { Array.new(width, false) }

      while que.any?
        node = que.shift

        4.times do |i|
          ny = node.ypos + DY[i]
          nx = node.xpos + DX[i]

          next if check_list[ny][nx]
          check_list[ny][nx] = true

          if field[ny][nx] == 'G'
            node.route.each do |y, x|
              field[y][x] = ':'
            end
            puts field
            exit(0)
          end

          if field[ny][nx] == ' '
            que.push(Node.new(ny, nx, node.route + [[ny, nx]]))
          end
        end
      end
    end
  end
end

深さ優先探索 (Depth First Search)

今回最終的に一番高速になった手法です。この手法ではひたすら迷路の行き止まりにぶつかるまで経路を伸ばし、行き止まりになったら、その手前の分岐の別の方向にまた探索を行っていきます。この手法の場合、最初に見つけたゴールまでの経路が最短とは限らないのですが、今回の問題のテストケースにおいて分岐が存在したときの探索する方向の順番を一定の順番に固定することで全てのケースで最適解が出るようになっていました。（恐らくですがケース5以外はゴールまでの経路が1つしか無く、ケース5も2本ぐらいしか存在していないのかなと思います）

GC.disable;$f=$<.map &:chomp
def d(y,x)
$f[y][x]!=' '&&return
$f[y][x+1]==?G&&($f[y][x]=?:;puts$f;exit)
$f[y][x]=?:
d(y+1,x)
d(y,x-1)
d(y-1,x)
d(y,x+1)
$f[y][x]=' '
end
$..times{|y|x=0;$f[y].chars{|c|c==?S&&d(y,x+1);x+=1}}

高速化

今回のコンテストではテストケースが5つ用意されており、正解数が同一の場合は実行時間が短い順にランキングがつけられていました。ここでは自分が処理速度をなるべく速くするために行ったことを紹介します。

GC.disable

プログラムの実行中にGCが走らないよう、まず最初に GC.disable を実行しました。

変数展開

ループが存在している場合に、その処理内容をループを使用せず書くことで少し高速化されます。

テストケースに特化

今回のテストケースでは全てスタート地点が左端、ゴールが右端に存在していたので、探索開始地点の決め打ちや、ゴール地点の判定式をそれにあわせて記述しました。

テストケースの生成とベンチマーク

サンプルコードではテストケースが1つだけ与えられていたのですが、高速化をするにあたって1つのテストケースではコードの評価が難しかったので、いくつか迷路を生成してテストケースを増やしました。迷路の生成については クラスタリングによる迷路作成アルゴリズム を参考にしました。

最初は100ケースぐらい作ってから、必要になったら1000ケースぐらいに増やそうかなと思ったのですが、途中から本番のテストケースに合わせた最適化を行っていたのであまり有効活用出来ませんでした。

require 'pp'

class MazeGenerator
  MIN_N = 5
  MAX_N = 50

  DY = [0, 1, 0, -1]
  DX = [1, 0, -1, 0]

  def self.generate(seed = 0)
    new.run(seed)
  end

  def run(seed)
    init(seed)
    generate_wall(seed)

    until complete?
      break_wall
      update_field
    end

    STDERR.puts "N = #{@n}"

    show_field
  end

  def init(seed)
    rnd = Random.new(seed)
    @n = 2*(rnd.rand(MAX_N - MIN_N) + MIN_N) + 1
    @field = Array.new(@n){ Array.new(@n) }

    @startY = 2*rnd.rand(@n/2) + 1
    @startX = 0
    @goalY = 2*rnd.rand(@n/2) + 1
    @goalX = @n-1

    id = 0

    @n.times do |y|
      @n.times do |x|
        if y == 0 || y == @n-1 || x == 0 || x == @n-1 || (y.even? || x.even?)
          @field[y][x] = '#'
        else
          @field[y][x] = id
          id += 1
        end
      end
    end

    @field[@startY][@startX] = 'S'
    @field[@goalY][@goalX] = 'G'
  end

  def generate_wall(seed)
    rnd = Random.new(seed)
    @wall = Array.new(@n){ Array.new(@n){ Array.new(4, false) }}
    @remain_walls = []

    @n.times do |y|
      @n.times do |x|
        next if y == 0 || y == @n-1 || x == 0 || x == @n-1 || @field[y][x] == '#'

        2.times do |i|
          ny = y + 2*DY[i]
          nx = x + 2*DX[i]
          next if ny <= 0 || ny >= @n-1 || nx <= 0 || nx >= @n-1

          @remain_walls << [y, x, i]
        end
      end
    end

    @remain_walls.shuffle!(random: rnd)

    STDERR.puts "wall count = #{@remain_walls.size}"
  end

  def break_wall
    while @remain_walls.any?
      wall = @remain_walls.pop
      y, x, i = wall
      ny = y + 2*DY[i]
      nx = x + 2*DX[i]

      next if @field[y][x] == @field[ny][nx]
      @field[y+DY[i]][x+DX[i]] = ' '
      break
    end
  end

  def update_field
    @check_list = Array.new(@n){ Array.new(@n, false)}

    1.step(@n-1, 2) do |y|
      1.step(@n-1, 2) do |x|
        unless @check_list[y][x]
          dfs(y, x, @field[y][x])
        end
      end
    end
  end

  def dfs(y, x, id)
    @check_list[y][x] = true

    4.times do |i|
      ny = y + DY[i]
      nx = x + DX[i]

      next if ['S','G','#'].include?(@field[ny][nx]) || @check_list[ny][nx]
      @field[ny][nx] = id
      dfs(ny, nx, id)
    end
  end

  def complete?
    1.step(@n-1, 2) do |y|
      1.step(@n-1, 2) do |x|
        return false if @field[y][x] != 0
      end
    end

    true
  end

  def show_field
    @n.times do |y|
      @n.times do |x|
        if @field[y][x] == 0
          print ' '
        else
          print @field[y][x]
        end
      end

      puts
    end
  end
end

MazeGenerator.generate(10)

こんな感じで迷路が生成されます

#############################
#       #   # #       #     #
### ### # # # # ##### # #####
# # #     # # #   #   #     #
# # # ##### # # # ### # ### #
#   #   #   # # # # #   # # #
# ####### ### ### # ### # ###
# #     #         #       # #
# # # ### ### # ######### # #
# # #   # #   #   # #   # # G
# ##### # ##### # # # ### # #
#     #       # # #   # #   #
# ### ### ##### ##### # # # #
#   # #   #   # #       # # #
### ### # # ### # ##### #####
# # # # #   #     # #   #   #
# ### # ### ##### # ##### ###
#   #   #   # #       # # # #
# ### ####### # # # # # # # #
#   # #   # # # # # # #     #
# # # # ### # ### ####### ###
# #   # # #               # #
# # ### # ### ##### ### # # #
# # # # # #     #   #   #   #
# # # # # # ##### ##### # # #
# #       # # # #   #   # # #
# ### # ##### # # ##### ### #
S   # #     #       #   #   #
#############################

ベンチマーク

最初に10個だけテストケースを作ってベンチマーク用のコードを書きました。（以降テストケースが増えることはありませんでした）

require 'benchmark'

Benchmark.bm do |x|
  x.report do
    (1..10).each do |seed|
      system("ruby solve.rb < test_case/seed#{seed}.txt")
    end
  end
end

おまけ

最終的に実行時間で並んでしまったのでコードの短さで争うことになったのですが、途中から実行時間がどうしても250msecより長くなってしまったので本番では断念してしまいました。（最終日付近は採点サーバ自体の速度もちょっと遅くなっていた気がします）

しかし、せっかくですのでどこまで短くできるかチャレンジしてみました。

d=->y,x{f=F[y];?G==f[x]?(puts F;exit):f[x]>?!||(f[x]=?:;d[y+1,x];d[y,x-1];d[y-1,x];d[y,x+1];f[x]=?\s)};d[(F=*$<).index{|s|s>?R},1]