隣り合わないのがマナー?(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割ほど速いようです。