隣り合わないのがマナー?(Ruby)
アルゴリズム・パズルです。
電車の中に 6人がけのロングシートが向かい合いになって、計12の席があるとします。
すべて空いている状態からすべてが埋まるまで、両隣が空いている空席があるときはそちらから座るというルールで、全部で何通りの席の埋まり方があるでしょうか?
Ruby で解いてみました。
q68.rb
L = 6 # 両隣が空いている空席を返す def get_scattered(spaces) before = spaces.select {|i| i < L} after = spaces - before result = ([-1] + before + [L]).chunk_while {|i, j| i + 1 == j} .select {|a| a.size >= 3}.flat_map {|a| a[1..-2]} result + ([L - 1] + after + [L * 2]).chunk_while {|i, j| i + 1 == j} .select {|a| a.size >= 3}.flat_map {|a| a[1..-2]} end # 与えられた空席での座り方の総数を返す def sit_down(spaces) return 2 if spaces.size == 2 return @memo[spaces] if @memo.has_key?(spaces) co = 0 scattered = get_scattered(spaces) if scattered.empty? spaces.each {|sit| co += sit_down(spaces - [sit])} else scattered.each {|sit| co += sit_down(spaces - [sit])} end @memo[spaces] = co end @memo = {} puts sit_down([*0...L * 2])
メモ化で高速化を図っています。
結果。
$ time ruby q68.rb 14100480 real 0m0.148s user 0m0.088s sys 0m0.024s
RubyPico で
じつは最初は待ち時間に RubyPico でコーディングしていたのでした。RubyPico でもほぼ同じコードが走りますが、Enumerable#chunk_while
が mruby で実装されていないようなので、自分でこんな風に実装してみました。このあたりがオープンクラスの Ruby (mruby) のおもしろいところですよね。
module Enumerable def chunk_while result, tmp = [], [] f = true a = nil each do |b| if f tmp << b f = false else if yield(a, b) tmp << b else result << tmp tmp = [b] end end a = b end result + (tmp.empty? ? [] : [tmp]) end end
もちろん答えは同じで、時間は自分の iPad mini で 0.396秒ほどになりました。Core i5 の PC と比べて 2.6倍くらい遅い(0.37倍の速さ)という感じでしょうか。まずまずですよね。
追記
メソッド get_scattered
はこういう実装の方が簡潔かな?
def get_scattered(spaces) before = spaces.select {|i| i < L} after = spaces - before result = ([-1] + before + [L]).each_cons(3) .map {|a, b, c| b + c == 2 * a + 3 ? b : nil}.compact result + ([L - 1] + after + [L * 2]).each_cons(3) .map {|a, b, c| b + c == 2 * a + 3 ? b : nil}.compact end
ここでは実行時間はまるで変わりません。L = 10 にして実行してみると、こちらの方が 2割ほど速いようです。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (9件) を見る