AOJ 0192 Multistory Parking Lot (Ruby)

僕は競技プログラミングは大したことがないけれど、印象に残っている解答を載せてみようと思います。

これは Aizu Online Judge (AOJ)の問題。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0192&lang=ja
 
コード。

class Car
  num = 1
  
  define_method(:initialize) do |wait_time|
    @num = num
    num += 1
    @time = wait_time
  end
  attr_reader   :num
  attr_accessor :time
  
  define_singleton_method(:clear) {num = 1}
end

class ParkingLot
  Space = Struct.new(:upper, :lower)
  
  def initialize(num)
    @spaces = num.times.map {|i| Space.new}
  end
  
  def add_car(wait_time)
    idx = @spaces.index {|sp| sp.lower.nil?}
    if idx
      @spaces[idx].lower = Car.new(wait_time)   #下のスペースが空いている
    else
      return false if @spaces.all?(&:upper)     #満車
      
      #下は空いていないが満車でない場合
      idxs = @spaces.map.with_index {|sp, i| sp.upper ? nil : i}.compact
      idx = idxs.map {|i|
        diff = @spaces[i].lower.time - wait_time
        diff >= 0 ? [diff, i] : nil
      }.compact.sort.first&.last
      unless idx
        idx = idxs.map {|i| [wait_time - @spaces[i].lower.time, i]}
                  .sort.first.last
      end
      
      @spaces[idx].upper = @spaces[idx].lower
      @spaces[idx].lower = Car.new(wait_time)
    end
    true
  end
  
  def next
    @spaces.each do |sp|
      if sp.lower
        sp.lower.time -= 1
        sp.upper.time -= 1 if sp.upper
      end
    end
    
    out = []
    2.times do
      @spaces.each do |sp|
        if sp.lower && sp.lower.time <= 0
          out << sp.lower.num
          sp.lower = sp.upper
          sp.upper = nil
        end
      end
    end
    
    out
  end
  
  #車庫が空か
  def empty?
    @spaces.all? {|sp| sp.lower.nil?}
  end
end


until (given = gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  parking_time = n.times.map {gets.to_i}
  
  pl = ParkingLot.new(m)
  result = []
  entrance = []
  Car.clear
  t = 0
  
  loop do
    result += pl.next
    
    entrance << parking_time.shift if (t % 10).zero?
    
    while (wait_time = entrance.shift)
      unless pl.add_car(wait_time)
        entrance.unshift(wait_time)    #満車の場合
        break
      end
    end
    
    break if pl.empty?
    t += 1
  end
  
  puts result.join(" ")
end

別に速くも短くもない解答だけれど、なかなか複雑な問題で、コードを自分なりに読みやすく書けたのが印象に残っています。0.05秒。
 

解説

問題が複雑なので、どう解説したものかな。
まず、車を表すCarクラスと、駐車場を表すParkingLotクラスを作りました。

Car クラス。

  • car = Car.new(wait_time)で、駐車時間 wait_time の車を作る。car.timeで残りの駐車時間にアクセスできる。car.numで車の整理番号がわかる。
  • Car.clearで、車の整理番号を最初に戻す。

 
ParkingLot クラス。

  • 内部に駐車スペースを表すParkingLot::Spaceクラスがあって、(sp = Space.new として) sp.uppersp.lowerで、駐車スペースのそれぞれ上段、下段に入っている車を意味する。nil なら空いている。
  • pl = ParkingLot.new(m)で、m台の駐車スペースをもった駐車場を作る。
  • すべての駐車スペースは@spaces[]
  • pl.add_car(wait_time)で、駐車時間 wait_time の車を(満車でなければ)1台入庫させる。返り値が true のときは駐車できた、false のときは満車だったことを意味する。
    • 順番に、下段が空いていれば下段に入庫させる。
    • 下段が空いていなければ、下段の車を上段に上げて、空いた下段に入庫させる。このときのルールは面倒だが(上段の車が出やすいようにしている)、頑張って処理する。
  • pl.nextですべての車の残り時間を1分減らし、出庫できる車は出庫させる。返り値は配列で、出庫するすべての車の整理番号が入っている。
    • まず下段の出庫可能な車をすべて出し、出したもので上段に車があれば下段に下ろし、また下段の出庫可能な車をすべて出す。
  • pl.empty?で、駐車スペースがすべて空になったか判定する。

 
最初は時刻t= 0。車の整理番号を初期化する(Car.clear)。
メインループ。

  • 出庫できる車は出庫させる(pl.next)。
  • 10分ごとに1台、車がやってくる。入り口で待たせる(その車の駐車時間をentrance[]に push する)。
  • 満車になるまで、待っているすべての車を入庫させる(while ループ)。満車になったら入り口で待たせておく。
  • 駐車スペースがすべて空になっていたら break で終了。
  • 時間を1分進める。で、繰り返し。

終わったら結果result[]を出力。


いやあ、面倒ですねえ。
 

あとから気づいた問題点

  1. メインループでは車を wait_time で表しているが、これはじつは残りの駐車時間なので、Car クラスのインスタンスで表した方がよい。
  2. それぞれの車の残りの駐車時間を減らすのをすべて ParkingLot クラスで処理しているけれど、Car クラスのメソッドにした方がよかった。
  3. 時間管理はそれぞれの車の残りの駐車時間@timeと、全体の時刻tの二つあるけれど、両者に関連がないので、統一した方がよかったか。しかしこれは、統一するのはちょっと面倒そう。TimeManage クラスとか作るとよいかも知れない。まあ、統一はいたずらに複雑になって、ここではオーバースペックな気もする。実際の駐車場管理プログラムを書くのなら、絶対に統一しないといけないだろうな。

以上を考慮に入れて、リファクタリングしました。
AOJ 0192: Multistory Parking Lot · GitHub