問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。
例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる

#!/usr/bin/env ruby
def max_combination(ar)
  ar.sort { |x, y| "#{y}#{x}" <=> "#{x}#{y}" }
end

ar = [50, 2, 1, 9]
max_combination(ar).join
# => "95021"

一瞬戸惑ったけど、配列の要素を文字列比較すればok。

問題5

1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となる
あらゆる組合せを出力するプログラムを記述せよ。
例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる

#!/usr/bin/env ruby
def detect_total(ar_size, total)
  ope = ['+', '-', '']
  comb = (1...ar_size).inject([]) do |res, i|
    res << [i].product(ope).map(&:join)
  end
  first = comb[0]
  other = comb[1..-1]
  first.product(*other)
    .map { |elm| "#{elm.join}#{ar_size}" }
    .select { |formula| eval(formula) == total }
end

pp detect_total(9, 100)
["1+2+3-4+5+6+78+9",
 "1+2+34-5+67-8+9",
 "1+23-4+5+6+78-9",
 "1+23-4+56+7+8+9",
 "12+3+4+5-6-7+89",
 "12+3-4+5+67+8+9",
 "12-3-4+5-6+7+89",
 "123+4-5+67-89",
 "123+45-67+8-9",
 "123-4-5-6-7+8-9",
 "123-45-67+89"]

しばらく考えても妙案が浮かばず。
総当たりでやってみました。
まずは、1〜8までの数値それぞれに演算子を付けた配列を用意（comb）。

=> [["1+", "1-", "1"], ["2+", "2-", "2"], ["3+", "3-", "3"], ["4+", "4-", "4"], ["5+", "5-", "5"], ["6+", "6-", "6"], ["7+", "7-", "7"], ["8+", "8-", "8"]]

あとは、これの総当たりを作成してevalで評価。
一見よろしくないですが、product って便利だなと再認識。

以下余談。20150618追記

コメントもらってたので回答してみます。

id:yohshiy

問4 は文字列にした先頭文字で比較した方がちょこっとだけ処理が速いかも。(y.to_s[0] <=> x.to_s[0])

これはまずいですよ。 ar = [50, 5, 1, 9] ならOKですが ar = [5, 50, 1, 9] だとNGです。

id:takun71

問5で最初の1がマイナスの場合は考えなくていいのかな？

おお、なるほど。と一瞬思いましたが
問題素直に読むとその考慮はいらなさそうです。

原文もbetweenなのでやっぱりいらなさそうです。

Write a program that outputs all possibilities to put + or - or nothing 
between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. 
For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

でも、これで終わってしまうのもあれなので、ちょっと考えてみました。
-1始まりというのは結局「2..9 までで101」となるケースを考えれば良いので簡単そうです。
手元で2始まりに変更して動かしてみると1パターンしかありません（え？ホント？）。
　
ついでに両方対応させると、こんな感じになりました。

def detect_total(ar_size, total)
  ope = ['+', '-', '']
  comb = (0...ar_size).inject([]) do |res, i|
    res << ((i == 0) ? ["", "-", ""] : [i].product(ope).map(&:join))
  end
  first = comb[0]
  other = comb[1..-1]
  first.product(*other)
    .map { |elm| "#{elm.join}#{ar_size}" }
    .select { |formula| eval(formula) == total }
    .uniq
end

pp detect_total(9, 100)
["1+2+3-4+5+6+78+9",
 "1+2+34-5+67-8+9",
 "1+23-4+5+6+78-9",
 "1+23-4+56+7+8+9",
 "12+3+4+5-6-7+89",
 "12+3-4+5+67+8+9",
 "12-3-4+5-6+7+89",
 "123+4-5+67-89",
 "123+45-67+8-9",
 "123-4-5-6-7+8-9",
 "123-45-67+89",
 "-1+2-3+4+5+6+78+9"]

0始まりで考えれば簡単やー、と発想を変えてみたのですが
0始まりの数値は8進数として扱われてしまうので、一旦空白として扱っています。

もう一個追加。uniqはuglyなので、こっちの方がもいいかも。

def detect_total(ar_size, total)
  ope = ['+', '-', '']
  comb = (1...ar_size).inject([]) do |res, i|
    res << [i].product(ope).map(&:join)
  end
  first = comb[1]
  other = comb[2..-1]
  ['', '-'].product(first.product(*other))
    .map { |elm| "#{elm.join}#{ar_size}" }
    .select { |formula| eval(formula) == total }
end

rochefort's blog

Re: 1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に

問題4

問題5

以下余談。20150618追記

id:yohshiy

id:takun71