Ruby2D で穴掘り迷路

見てのとおり、穴掘り迷路です。Gem 'ruby2d' を使いました。Ruby2D についてはこちら。

コード。
dig_maze.rb

require "ruby2d"

L = 20    #迷路の大きさ
W = L * 2 + 3

Block_w = 10
set width: W * Block_w, height: W * Block_w, fps_cap: 10

blocks = W.times.map {|y|
  W.times.map {|x|
    Square.new x: x * Block_w, y: y * Block_w,
               size: Block_w, color: "green"
  }
}

field = Array.new(W) {Array.new(W, 1)}
field[0] = field[-1] = Array.new(W, -1)
(1..W - 2).each {|y| field[y][0] = field[y][-1] = -1}

field.define_singleton_method(:show) do
  each_index do |y|
    self[y].each_index do |x|
      self[y][x].zero? ? blocks[y][x].remove : blocks[y][x].add
    end
  end
end

start = [2, 2]
stack = [start]
show_stack = [start]

dig = ->(now) {
  movable = []
  [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
    x = now[0] + dx * 2
    y = now[1] + dy * 2
    movable << [x, y] if field[y][x] == 1
  end
  if movable.empty?
    return if stack.empty?
    jump = stack.delete_at(rand(stack.size))
    dig.(jump)
  else
    nxt = movable.sample
    show_stack << [(now[0] + nxt[0]) / 2, (now[1] + nxt[1]) / 2]
    show_stack << nxt
    stack << nxt
  end
}


update do
  now = show_stack.shift
  next unless now
  field[now[1]][now[0]] = 0
  field.show
  dig.(now) if show_stack.empty?
end

show

Gem 'Ruby 2D' で遊ぶ（2）

過去記事のプログラムを少し改変したものです。
　
コード。
ruby2d_sample2a.rb

require 'ruby2d'
require 'matrix'
include Math

Width = 500
C = 15    #円の数
R = 20    #円の半径

L = 70    #三角形の外接円の半径

set width: Width, height: Width

circles = C.times.map {
  Circle.new x: rand(R..Width - R), y: rand(R..Width - R),
     radius: R, color: Color.new([rand, rand, rand, 0.8]), z: 0
}
cvs = circles.map {[rand(-3.0..3.0), rand(-3.0..3.0)]}    #円の移動ベクトル
circles_move = circles.zip(cvs)


rot = ->(θ) {
   θ1 = θ / 180.0 * PI
   Matrix[[cos(θ1), sin(θ1)], [-sin(θ1), cos(θ1)]]
}

points = ->(θ) {
  o = Vector[Width / 2.0, Width / 2.0]
  v0 = Vector[0, -L]
  p1 = o + rot.(θ +   0) * v0
  p2 = o + rot.(θ + 120) * v0
  p3 = o + rot.(θ + 240) * v0
  [p1, p2, p3]
}

triangle = Triangle.new z: 10, opacity: 0.8

triangle.define_singleton_method(:rotate) do |θ|
  p1, p2, p3 = points.(θ)
  self.x1 = p1[0]
  self.y1 = p1[1]
  self.x2 = p2[0]
  self.y2 = p2[1]
  self.x3 = p3[0]
  self.y3 = p3[1]
end

triangle_color = [rand, rand, rand]
triangle_color_step =
   (Vector[rand(-1.0..1.0), rand(-1.0..1.0), rand(-1.0..1.0)]
     .normalize / 100).to_a

triangle_color.define_singleton_method(:update) do
  triangle.color = self + [0.8]
  replace(zip(triangle_color_step).map {|a, b| a + b})
  triangle_color.each_index do |i|
    if triangle_color[i] < 0 || triangle_color[i] > 1
      triangle_color_step[i] = -triangle_color_step[i]
    end
  end
end


θ = 0

update do
  #円の移動
  circles_move.each do |c, vec|
    c.x += vec[0]
    c.y += vec[1]
    c.x = Width + R if c.x < -R
    c.y = Width + R if c.y < -R
    c.x = -R if c.x > Width + R 
    c.y = -R if c.y > Width + R 
  end
  
  #三角形の回転
  triangle.rotate(θ)
  triangle_color.update if (θ % 3).zero?
  θ = (θ + 1) % 360
end

show

inject が Enumerator を返さない（Ruby）

例えば true/false の配列をビット列に変換したいとして、こうしたかった。

cond = [true, false, false, true, false, true]

cond.inject(0).with_index {|(acc, c), i| c ? acc | 1 << i : acc}
#=>TypeError (0 is not a symbol nor a string)

injectはブロックを取らない場合、Enumerator を返さないのですね。

仕方がないのでenum_forを使う。

cond.enum_for(:inject, 0).with_index {|(acc, c), i| c ? acc | 1 << i : acc}
#=>0b101001

これでinjectも Enumerator を返します。

しかし、enum_forってどうなっているのだろうね。どうも、ブロックを取るメソッドはすべて使えるらしい。変な例。

class String
  def upcase🍓
    yield(upcase)
  end
end

enum = "aaa".enum_for(:upcase🍓)
enum.map {|e| e + "0"}    #=>["AAA0"]

謎である。

Ruby で同値（必要十分）関係

Ruby で「p と q が同値」あるいは「必要十分」、つまり
　
の関係を表すにはどうしたらよいでしょうか。

これはp == qのことでも、p.equal?(q) のことでもありません。ではなくて、

p が T ならば q も T、p が F ならば q も F

ということです。T とか F は何だということになりますが、Ruby のtruefalseはちょっと曖昧で、Ruby の if ではnilとfalseが「偽」と判定されますね。この「偽」になるオブジェクトを F、それ以外のオブジェクトを T とする、という意味です。真偽表だと

p	q	p⇔q
T	T	T
T	F	F
F	T	F
F	F	T

となります。

じつは同値 EQ は、排他的論理和 XOR の否定です。なので簡単そうですが、じつは Ruby には XOR を表す演算子がありません。
ここにあるように、Ruby で XOR を表すには、!!p ^ !!qあるいは!p ^ !qとすればよいようです。なので同値を判定するメソッドは

def eq(p, q)
  !(!p ^ !q)
end

とすればよいことになります。

AOJ 0141 Spiral Pattern （Ruby）

問題。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0141&lang=ja

「ぐるぐる模様」を出力します。簡単そうでかなりむずかしかったので、印象に残っています。

6番目の「ぐるぐる模様」

######
#    #
# ## #
# #  #
# #  #
# ####

　
コード。

result = []

gets.to_i.times do
  n = gets.to_i
  
  field = Array.new(n) {" " * n}
  x, y = 0, n - 1
  
  go = ->(dx, dy, l) {
    l.times do
      field[y][x] = "#"
      x += dx
      y += dy
    end
  }
  square = ->(l) {
    if l != 1
      go.(0, -1, l - 1)
      go.(1,  0, l - 1)
      go.(0,  1, l - 1)
      if l != 3
        go.(-1, 0, l - 3)
        if l != 4
          if l > 4
            go.(0, -1, 2)
            square.(l - 4)
          end
          return
        end
      end
    end
    field[y][x] = "#"
  }
  
  square.(n)
  result << field.map {|l| l + "\n"}.join
end
puts result.join("\n")

解説

• まず、キャンバスfield[][]の左下に、開始位置 (x, y) をセットします。
• go.(dx, dy, l) は、(dx, dy) 方向に l ステップだけ描画して、(x, y) を進めます。
  • まず (x, y) に # を置いてから、ステップを進めるという順です。
• square.(l)は l 番目の「ぐるぐる模様」のいちばん外側一周を描き、(x, y) を進めます。
  • l > 4 の場合は、外周一周を描いたら、2ステップ上に進んで、square.(l - 4) を再帰的に呼びます。
  • l <= 4 の場合はややこしくて、場合分けがたくさんあります。

square.(l)は、冗長でも case ~ when 式で書けばもっとすっきりしましたね。
こんな感じか。

  square = ->(l) {
    case l
    when 1
      field[y][x] = "#"
    when 2
      go.(0, -1, 1)
      go.(1,  0, 1)
      field[y][x] = "#"
    when 3
      go.(0, -1, 2)
      go.(1,  0, 2)
      go.(0,  1, 2)
      field[y][x] = "#"
    when 4
      go.(0, -1, 3)
      go.(1,  0, 3)
      go.(0,  1, 3)
      go.(-1, 0, 2)
    else
      go.(0, -1, l - 1)
      go.(1,  0, l - 1)
      go.(0,  1, l - 1)
      go.(-1, 0, l - 3)
      go.(0, -1, 2)
      square.(l - 4)
    end
  }

これだと平凡ですね。

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.upper、sp.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

AtCoder ABC128C （関数型Ruby?）

https://atcoder.jp/contests/abc128/tasks/abc128_c

きれいに Ruby らしく解けたので、メモ。

n, m = gets.split.map(&:to_i)
cond = m.times.map {
  k, *ss = gets.split.map(&:to_i)
  ss.inject(0) {|acc, s| acc | 1 << (s - 1)}
}.zip(gets.split.map(&:to_i))

puts (2 ** n).times.count {|switches|
  cond.all? {|c, p| (switches & c).to_s(2).count("1") % 2 == p}
}

11ms。関数型 Ruby？（笑）

• cond[i]は、i + 1 番目の電球の条件[c, p]で、cはkビット目がスイッチkの状態（1ならばon）という条件を表す。電球の個数はm。
• acc |= 1 << s は、acc のsビット目（最初が0ビット目）を立てる。
• cond.all? {|c, p| (switches & c).to_s(2).count("1") % 2 == p} は、スイッチの状態がswitchesのとき、すべての電球が on ならば true になる。
• switchesはスイッチの状態で、kビット目がスイッチkの on/off を表す。スイッチはn個あるので、総当りの状態数は 2^n 個ある。nが最大でも10なので、2^10 = 1024。これだけの回数をcount で回して true の個数を数える。

for, times, each, uptoなどのループをまったく使わず、map, inject, zip, all? などで頑張っております（times.map は許せ笑）。