アルゴリズム・パズルです。
問題:
1 ~ 7 の数字を並べてあみだくじを作ることを考えます。引く横線の数を 10本とするとき、下に得られる数字の並びは何とおりになるでしょうか。ただし、下に得られる数字の並びが 10本より少ない横線のあみだくじで既に得られる場合、それは除くことにします。
Ruby で解いてみました。
q57.rb
require 'set' N = 7 List = "1234567" def exchange(i, ls, num) ls[i], ls[i + 1] = ls[i + 1], ls[i] if num == 10 @result << ls else @store << ls (N - 1).times do |j| next if i == j exchange(j, ls.dup, num + 1) end end end @store = Set[List] @result = Set.new (N - 1).times {|i| exchange(i, List.dup, 1)} puts (@result - @store).size #=>573
答えはいちおう 573通りと求められたのですが、時間が約 16秒もかかってしまいました。exchange() の呼び出しは 14648436回もあります。力任せのやり方で、これではダメですね。
模範解答の一。
v, h = 7, 10 total = 0 [*0..v - 1].permutation do |final| cnt = 0 v.times do |i| cnt += final.take_while {|j| j != i}.count {|k| k > i} end total += 1 if cnt == h end puts total
超シンプルなコードなのだが、これで 0.1秒。さらに高速なアルゴリズムも紹介されている…。すごいな。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (9件) を見る