1時間以内に解けなければプログラマ失格?
blog.kazuhooku.comここで次のような問題を見つけました。
1,2,…,9の数をこの順序で、”+”、”-“、またはなにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる。
1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に | ソフトアンテナブログ
で、自力で解けばよいのですが、ついそこでの Cコードを読んでしまいました。これがとてもきれいなコードだったので、Ruby に移植してみました。自力ではたぶんこんなにうまく解けなかったと思います。まず結果から。
$ time ruby solve.rb 1+2+3-4+5+6+78+9 = 100 1+2+34-5+67-8+9 = 100 1+23-4+5+6+78-9 = 100 1+23-4+56+7+8+9 = 100 12+3+4+5-6-7+89 = 100 12+3-4+5+67+8+9 = 100 12-3-4+5-6+7+89 = 100 123+4-5+67-89 = 100 123+45-67+8-9 = 100 123-4-5-6-7+8-9 = 100 123-45-67+89 = 100 real 0m0.107s user 0m0.064s sys 0m0.008s
全部で 11とおりあるのですね。Ruby でも一瞬で解いています。
MAX_POS = 9 EXPECTED = 100 def doit(pos, sum, st, sign) st += (sign == 1) ? "+" : "-" n = 0 pos.upto(MAX_POS) do |i| st += i.to_s n += i s = sum + sign * n n *= 10 if i == MAX_POS puts st[1..-1] + " = 100" if s == EXPECTED else doit(i + 1, s, st, 1) doit(i + 1, s, st, -1) end end end doit(1, 0, "", 1)
ほぼ Cコードと同じです。総当りなのだけれど、非常にきれいに再帰で書かれていますね。すばらしい。
なお、関数 doit() の呼び出しは 6561回で、なるほどこの程度なら一瞬の筈ですね。
問題4 もやってみた
大本の記事の問題4 もむずかしいというので、やってみました。
正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。
1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に | ソフトアンテナブログ
これは以下でいいのかな。これだとRuby の恩恵で、全然むずかしくない。
def solve(given) max = 0 given.permutation do |ar| n = ar.join.to_i max = n if n > max end max end p solve([50, 2, 1, 9]) #=>95012
ここで Go言語でもやってみました。
ついでに全部やってみた
問題1。
forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。
def sum1(given) result = 0 for i in given result += i end result end def sum2(given) result = 0 while (n = given.first) result += n given = given.drop(1) end result end def sum3(given, sum = 0) return sum if given.empty? sum3(given.drop(1), sum + given.first) end a = [4, 10, -9, 25, 1] p sum1(a) p sum2(a) p sum3(a)
問題2。
交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。
def zip(a, b) a.zip(b).flatten end p zip([:a, :b, :c], [1, 2, 3]) #あるいは def zip(a, b) result = [] a.each_index do |i| result << a[i] result << b[i] end result end #あるいは def zip(a, b) a.flat_map.with_index {|x, i| [x, b[i]]} end
問題3。
最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。
def fib Enumerator.new do |y| a, b = 0, 1 loop do y << a a, b = b, a + b end end end p fib.take(100)