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 は許せ笑）。

金貨と銅貨と空箱の「うそつき問題」（Ruby）

rsc.hatenablog.comまたまた rsc さんのブログから問題を拝借して、Ruby で解いてみました。
　

問題

コピペさせてもらいます。

　A～Eの五つの箱があり、これらの箱は、金貨の入った箱、銅貨の入った箱、空箱の3種類の場合がある。
　また、それぞれの箱にはラベルが付いているが、そのラベルの記述の内容は、金貨の入った箱のものは真(真実に一致している)であるが、銅貨の入った箱のものは偽(真実に反している)であり、空箱のものは真の場合も偽の場合もあるという。
　このとき、銅貨の入った箱が二つあるとすると、確実に銅貨の入った箱はどれか。
[ラベル]
A:「Bのラベルの記述の内容は真である。」
B:「Aが空箱ならば、この箱も空箱である。」
C:「この箱は、銅貨の入った箱である。」
D:「AかEの少なくとも一方は、銅貨の入った箱である。」
E:「この箱は、金貨の入った箱である。」

解答例

問題が少し曖昧で、空箱の場合、「真の場合も偽の場合もある」というのは「真でも偽でもどちらでも可」なのか、「真の場合も偽の場合も両方とも満たさないといけない」のかわかりませんが、まあ前者だろうと解釈して解きました。

コード。

N = 5
TBL = [*0...N]

box = Array.new(N)

imp = ->(p, q) {!p || q}

label = Array.new(N)
label[0] = ->{label[1].()}
label[1] = ->{imp.(!box[0], !box[1])}
label[2] = ->{box[2] == :copper}
label[3] = ->{box[0] == :copper || box[4] == :copper}
label[4] = ->{box[4] == :gold}

judgement = ->(i) {
  return true unless box[i]
  f = label[i].()
  (box[i] == :gold) ? f : !f
}

output = ->{
  puts (0...N).map {|i| "#{%W(A B C D E)[i]}=>#{box[i].inspect}"}.join(", ")
}

TBL.combination(2) do |cp2|
  cp2.each {|c| box[c] = :copper}
  (0..3).each do |n|
    (TBL - cp2).combination(n) do |golds|
      golds.each {|g| box[g] = :gold}
      (TBL - cp2 - golds).each {|e| box[e] = nil}
      output.() if (0...N).all? {|i| judgement.(i)}
    end
  end
end

　
結果。

A=>nil, B=>:copper, C=>nil, D=>:copper, E=>nil
A=>nil, B=>:copper, C=>nil, D=>:copper, E=>:gold
A=>nil, B=>:copper, C=>nil, D=>nil, E=>:copper
A=>nil, B=>:copper, C=>nil, D=>:gold, E=>:copper

つまり答えは B ということになります。
　

簡単な解説

箱は A ~ E ということですが、コードでは 0 ~ 4 に置き換えています。

基本的に「総当り法」で、まず「銅」の箱を2つ選び、残りは適当に「金」か「空」を割り当てます。全部「金」になったり、全部「空」になる場合もあります（と解釈して解いたのですが、それも問題では曖昧です）。箱は box[] で、:gold, :copper, nil が入るということです（nil は「空」）。

ラベルの条件は label[] に Proc オブジェクトで記述しています。「p ならば q」という論理包含（IMP）は、「p の否定と q との論理和」と必要十分なので、それを imp という Proc で表現しています。

箱の中身とラベルのマッチングを判断しないといけないので、それは judgement.() で記述しています。すべての箱で judgement.() が真になった場合に、その組み合わせを出力（ output.() ）します。

Proc （ここでは lambda ですが）のクロージャの機能を使いまくっているコードになっています。

Rubyでファイルのツリー構造を出力する

qiita.com
これを見て Ruby でもやってみたくなりました。
　

実行例

<kaki-utils>
  ├<lib>
  │  └<kaki>
  │     ├<utils>
  │     │  ├add_methods.rb
  │     │  ├all.rb
  │     │  ├check_fname_overlapping.rb
  │     │  ├es.rb
  │     │  ├imgsuffix.rb
  │     │  ├nest_loop.rb
  │     │  ├po.rb
  │     │  ├rec_decimal.rb
  │     │  ├retry.rb
  │     │  └safe_mkdir.rb
  │     └utils.rb
  ├README.md
  ├kaki-utils-0.0.1.gem
  ├kaki-utils-0.0.10.gem
  ├kaki-utils-0.0.2.gem
  ├kaki-utils-0.0.3.gem
  ├kaki-utils-0.0.4.gem
  ├kaki-utils-0.0.5.gem
  ├kaki-utils-0.0.6.gem
  ├kaki-utils-0.0.7.gem
  ├kaki-utils-0.0.8.gem
  ├kaki-utils-0.0.9.gem
  ├kaki-utils-0.1.0.gem
  ├kaki-utils-0.1.1.gem
  ├kaki-utils-0.1.10.gem
  ├kaki-utils-0.1.11.gem
  ├kaki-utils-0.1.12.gem
  ├kaki-utils-0.1.13.gem
  ├kaki-utils-0.1.14.gem
  ├kaki-utils-0.1.15.gem
  ├kaki-utils-0.1.2.gem
  ├kaki-utils-0.1.3.gem
  ├kaki-utils-0.1.4.gem
  ├kaki-utils-0.1.5.gem
  ├kaki-utils-0.1.6.gem
  ├kaki-utils-0.1.7.gem
  ├kaki-utils-0.1.8.gem
  ├kaki-utils-0.1.9.gem
  └kaki-utils.gemspec

コード

元の Python コードはまったく見ていません。簡単な再帰で実装しています。
print_dir_tree.rb

class Dir
  def self.print_tree(top_dir = Dir.pwd)
    unless File.directory?(top_dir)
      raise %("#{top_dir}") + " is not directory."
    end
    puts "<#{File.basename(top_dir)}>"
    
    walk_dir = ->(dir, pre) {
      Dir.chdir(dir) rescue return
      d_f = Dir.glob("*").sort
      dirs = d_f.select {|df| File.directory?(df)}
      files = d_f - dirs
      end_num = d_f.size
      line_num = 1
      
      dirs.each do |d|
        s0 = (line_num == end_num) ? "└" : "├"
        line_num += 1
        puts pre + s0 + "<#{d}>"
        s1 = pre + ((s0 == "└") ? "   " : "│  ")
        walk_dir.(d, s1)
      end
      
      files.each do |f|
        s = (line_num == end_num) ? "└" : "├"
        line_num += 1
        puts pre + s + f
      end
      
      Dir.chdir("..")
    }
    walk_dir.(top_dir, "  ")
  end
end


if __FILE__ == $0
  Dir.print_tree("./kaki-utils/")
end

Julia でじゃんけんゲームを書いてみる

いつものじゃんけんゲームを Julia のお勉強として書いてみました。Julia のバージョンは 1.0.4 です。
janken.jl

using Printf

mutable struct Person
    name::String
    wincount::Int
    hand::Int
end

function judge(player1::Person, player2::Person)
    show_hand(player::Person) = ["グー", "チョキ", "パー"][player.hand]
    
    @printf("%s　対　%s で　", show_hand(player1), show_hand(player2))
    
    winner = player1
    if player1.hand == player2.hand
        println("引き分けです。")
        return
    elseif (3 + player1.hand - player2.hand) % 3 == 1
        winner = player2
    end
    println("$(winner.name)の勝ちです。")
    
    winner.wincount += 1
end

function game(player1::Person, player2::Person, i::Int)
    println("*** $(i)回戦 ***")
    
    n = ""
    while true
        n = Base.prompt("$(player2.name)の手を入力して下さい（1:グー, 2:チョキ, 3:パー）")
        if n == "1" || n == "2" || n == "3" ; break end
    end
    player2.hand = parse(Int, n)
    
    player1.hand = rand(1:3)
    
    judge(player1, player2)
end

function winner(player1::Person, player2::Person)
    p1 = player1.wincount
    p2 = player2.wincount
    
    print("\n*** 最終結果 ***\n$(p1) 対 $(p2) で　")
    
    final_winner = player1
    if p1 == p2
        println("引き分けです。")
        return
    elseif p1 < p2
        final_winner = player2
    end
    
    println("$(final_winner.name)の勝ちです。")
end

function main()
    pc = Person("Computer", 0, 0)
    
    name = Base.prompt("あなたの名前を入力して下さい")
    if name == "" ; name = "名無し" end
    player = Person(name, 0, 0)
    
    print("$(pc.name)　対　$(player.name)　：じゃんけん開始\n\n")
    
    for i in 1:5 game(pc, player, i) end
    
    winner(pc, player)
end


main()

Julia はオブジェクト指向言語ではないですね。コードの見た目はすっきりした感じです。

Go言語版はこちらです。リンク先に他の言語での実装もまとめてあります。
Go言語でじゃんけんゲーム - Camera Obscura

Julia で 8 queens 問題

obelisk.hatenablog.com
ここで Go と Ruby でやっていることを、Julia でやってみました。

結果はこんな感じ。

$ time julia eight_queens.jl
--------------
n = 1
@.......
....@...
.......@
.....@..
..@.....
......@.
.@......
...@....
--------------
n = 2
@.......
.....@..
.......@
..@.....
......@.
...@....
.@......
....@...
--------------

....

--------------
n = 92
.......@
...@....
@.......
..@.....
.....@..
.@......
......@.
....@...

real	0m0.367s
user	0m0.474s
sys	0m0.211s

　
コード。
eight_queens.jl

N = 8
count = 0

function get_space(field, n)
    result = fill(true, N)
    for i in 1:n
        queen = field[i]
        result[queen] = false
        dst = n - i + 1
        if queen - dst >= 1 ; result[queen - dst] = false end
        if queen + dst <= N ; result[queen + dst] = false end
    end
    result
end

function solve(field, n)
    if n == N
        global count += 1
        println("--------------")
        println("n = $count")
        for queen in field
            println(repeat(".", queen - 1) * "@" * repeat(".", N - queen))
        end
    else
        tmp = get_space(field, n)
        for i in 1:N
            if tmp[i]
                field[n + 1] = i
                solve(field, n + 1)
            end
        end
    end
end

solve(repeat([0], N), 0)

配列のインデックスが 1 から始まるのには戸惑いました。あと、Ruby の each_with_index に相当する文法がないのかな？ それ以外はかなり書きやすいですね。型の記述はしませんでした。このあたり、柔軟である。
　
N = 13 にしてかつ最終的な解の個数だけ出力するようにしてみると、

$ time julia eight_queens.jl
73712

real	0m12.339s
user	0m12.401s
sys	0m0.276s

という感じ。