いきなりですが問題です．
正整数nを入力にとり，"a"と"b"の文字で構成される長さnの文字列で，かつその中には，同一の部分文字列が3回連続して出現しないものを生成しなさい．
以下では，文字列であることが明確なときは引用符を書きません．たとえばn＝14として，aabaabbaabbaabという文字列を生成したとき，aa / baab / baab / baabと分けてみると，baabが3回連続して出現するので，条件を満たさないと言えます．
さっそくですが解答となるコードです．Gistにて公開しました．
このRubyスクリプト，repeat3.rbは，コマンドライン引数により挙動が変わります．引数なしの場合は，ランダムにaとbを生成して文字列を1文字ずつ長くし，条件を満たさなくなるまで続けます．
ruby repeat3.rb g1を実行すると，乱数の種を10000から10999に1ずつ増やしていき，それぞれでaとbをランダムに生成してn≦100の文字列を生成し，1文字ごとに条件判定を行います．手元の実行環境ではいずれも途中で失敗しており，最大長はn＝28のaababaabbababbaabaabbabbaabbです．
ruby repeat3.rb g2を実行すると，n＝2000で，条件を満たす文字列を生成します．乱数を使用していないため，常に同じ文字列です．考え方としては，インスタンス変数@aと@bの初期値をそれぞれ"a"，"b"とし，@a + @b + @a + @bという文字列を作り，長さがnに満たないときは，以下の式により，変数@aと@bの更新を同時に行います．
- @a = @a + @a + @b + @a + @a + @b + @b + @a + @b
- @b = @a + @a + @b + @b + @a + @b + @b + @a + @b
そして生成したい文字列の後ろに@a + @b + @a + @bを追加し，長さがnに到達するまで繰り返します．
ruby repeat3.rb g3を実行すると，n＝2000で，条件を満たす文字列を生成します．乱数を使用していないため，常に同じ文字列です．これについては，wikipedia:千日手にある「同一局面に戻る手順AとBがあるとき、A-B-BA-BAAB-BAABABBA-... と、それまでの手順を逆にしてつなげることで、同一手順3回を回避しながら同一局面を繰り返すことができる。」にもとづいて，コーディングを行いました．
引数g2もしくはg3の後ろに，数値を書くと，nの値となります．あるLinux環境で，ruby repeat3.rb g2 50000をやってみたところ，980秒かかりました．n≧3で，2つの生成法の出力が異なります．n＝100のとき，それぞれが生成する文字列は以下のとおりです．
- 「ruby repeat3.rb g2 100」：ababaabaabbabaabbabbabaabaabbabaabbabbabaabaabbabaabaabbabaabbabbabaabaabbabaabaabbabaabbabbabaabbab
- 「ruby repeat3.rb g3 100」：abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabba
プログラム内で定義した，条件チェックのためのクラス（Repeat3::Inspector）のほか，正規表現および後方参照を用いた/(.+)\1\1/でも，同一の部分文字列が3回連続して出現しないことを確認しました．
（最終更新：2018-01-09 早朝．「同じ長さの部分文字列」を「同一の部分文字列」に修正しました）
