これ、やってみた。

- 1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に
http://www.softantenna.com/wp/software/5-programming-problems/
(元記事: Five programming problems every Software Engineer should be able to solve in less than 1 hour)

問題1、問題2、問題3は簡単すぎなので飛ばして問題4と問題5に挑戦。

問題4:

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

最初は単純に数値を文字列として降順にソートするだけと思ってシンプルなワンライナーを書いてみた。

perl -le 'print join "", reverse sort @ARGV' 50 2 1 9

しかし、"10 1 15" が "15101" となってしまう。正しくは "15110" なのに。"10" と "1" の場合、つまり桁が異なるときの比較が問題。そこで、"10" と "1" の比較は先頭の数字を末尾にくっつけた "10111111..." と "11111111..." で比較することにした。直してみたのがこれ。

perl -le '
print join "", reverse sort {
my $t=substr($a, 0, 1);
$t != substr($b, 0, 1) ?
  ($a cmp $b) :
  ($a.($t x length($b)) cmp $b.($t x length($a)))
} @ARGV' 50 5 55 1 10 11 9

正解をみてみたらもっとシンプルで、"10" と "1" の比較はを "101" ("10"+"1") と "110" ("1"+"10") の比較で解決してた。なるほどなあ。合理的でエレガントだ。

問題5:

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

こちらは総当たりしただけ。
"123456789" の各数字の間に入るのは、"+" か "-" か "" (なにもなし) の3種類。
なので3の8乗 (6561) 個のパターンがあるだけ。
再帰とかじゃなく、単に0から6560までの6561個の数を3進数に変換する処理で実装。

perl -le '
for (0..3**8) {
  my $s = 1;
  my $n = $_;
  for (2..9) {
    $s .= ("+", "-", "")[$n % 3].$_;
    $n /= 3;
  }
  print $s if eval($s) == 100;
}'

ワンライナー：

perl -le 'for(0..3**8){$s=1;$n=$_;for(2..9){$s.=("+","-","")[$n%3].$_;$n/=3}print $s if eval($s)==100}'

というか、問題4と問題5は問題1,2,3の結果を踏まえてプログラムを書くのが正しい流れだったのかも。