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 でも一瞬で解いています。

Ruby コード。でもあまり 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)