Problem 191 (written in Ruby) (途中経過?)

ProjectEuler

注: 未完です



status = ""
$count = 0
$reject_pat1 = /AAA\z/

$reject_pat2 = /L.*L/
def a_day(current_status, day, max)

  #print "Day=#{day} STATUS=#{current_status}"
  if $reject_pat2 =~ current_status || $reject_pat1 =~ current_status then

    #puts "NO MORE MONEY!"

    return

  else

    #puts ""

  end
  if max != day-1 then

    a_day(current_status + "A", day+1, max)

    a_day(current_status + "L", day+1, max)

    a_day(current_status + "O", day+1, max)

  else

    puts "OK: #{current_status}(#{current_status.length}chars)"

    $count += 1

  end

end
a_day(status, 1, 30)

Problem:
http://odz.sakura.ne.jp/projecteuler/index.php?Problem%20191

枝狩りをするようにはしたものの, メソッド呼び出しのコストが高くついているのか一時間ほど放置しても答えはでない...
これも計算爆発系ですね、組み合わせについて考えてもうちょっと最適化できる部分がないか考えます。

追記:
a. 全てのパターン
b. AAAを含む全てのパターン
c. Lを二個含む全てのパターン
であるので
答えは a - b - c + (bとcの和集合)ということになると思います。
おそらくbとcの和集合をどうとくか?が問題な気がする。

追記2:
正規表現ではなく, 連続するAの数や, パターン中のLの数を整数として引き回すようにしたところ報奨金がもらえる出席パターン数100万までの探索で16秒から9秒程度まで高速化できました。