アルゴリズム・パズルです。
問題。
1~9 のカードを横一列に適当に並べ替えます。そこからスタートして、左端のカードの数字の枚数だけ、左からカードを取って逆順にし、また置き直します。例えば [4, 5, 6, 7, 8, 9, 1, 2, 3] だったら [7, 6, 5, 4, 8, 9, 1, 2, 3] とします。これを繰り返すと、左端が 1 になったら終了することがわかります。
さて、終了するまでの手順がもっとも長くなる初期配置を与えなさい。
Ruby で解きます。
q40.rb
def try(order, co) 8.times do |i| if order[i + 1] == i + 2 tmp = order[0, i + 2].reverse + order[(i + 2)..-1] try(tmp, co + 1) unless tmp[0] == 1 end end @max, @result = co, order if @max < co end @max = 0 [*2..9].permutation(8) {|ar| try([1] + ar, 0)} p [@max, @result]
終了した配置から逆に求めていきます。
結果。
$ time ruby q40.rb [30, [6, 1, 5, 9, 7, 2, 8, 3, 4]] real 0m0.599s user 0m0.596s sys 0m0.000s
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (8件) を見る