元ネタ
「1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に」
最近になってJSでやってる人を見かけたので、だいぶ乗り遅れた感がありますが何となく好きなPHPでやってみます。
問題
問題1
forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。
解答
簡単すぎるけど一応書いておきます…
function array_sum_for(array $list) {
$sum = 0;
for ($i = 0, $max = count($list); $i < $max; ++$i) $sum += $list[$i];
return $sum;
}
function array_sum_while(array $list) {
$sum = 0;
while ($list) $sum += array_shift($list);
return $sum;
}
function array_sum_recursion(array $list) {
return $list ? array_shift($list) + array_sum_recursion($list): 0;
}
PHPで末尾再帰とかやっても意味ないしね…これでいいよね…
問題2
交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。
解答
function array_zip(array ...$args) {
return count($args) > 1 ? array_merge(...array_map(null, ...$args)) : $args;
}
...演算子、イケてるやん？
問題3
最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。
解答
無難に一番有名な動的計画法のやつで。
function fibonacci_list(int $n) {
if ($n < 1) return [];
if ($n < 2) return [0];
$list = [$x = 0, $y = 1];
for ($i = 2; $i < $n; ++$i) {
$list[] = $z = $x + $y;
$x = $y;
$y = $z;
}
return $list;
}
問題4
正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。
解答
function max_number(array $digits) {
$length = max(array_map('strlen', $digits));
$digits = array_map(function ($digit) use ($length) {
return str_pad($digit, $length, 'X');
}, $digits);
rsort($digits, SORT_STRING);
return str_replace('X', '', implode($digits));
}
最初は単純に文字列で逆順ソートしていたのですが、コメント欄で誤りだとの指摘があったので再考しました。一度最大桁に合わせて全て右端をX(どの数字よりもコードポイントが大きい任意の1バイト)で埋めてソートした後にもとに戻すようにしてみました。
問題5
1,2,…,9の数をこの順序で、+ - またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる。
解答
真っ先に思いついたのが3進数解法だったのでこれでやってみる。
function calc_hundreds() {
$list = [];
for ($i = 0; $i < 3 ** 8; ++$i) {
$f = implode(array_zip(range(1, 9), str_replace(
[0, 1, 2],
['+', '-'],
str_split(str_pad(base_convert($i, 10, 3), 8, 0, STR_PAD_LEFT))
)));
if (eval("return $f;") === 100) {
$list[] = implode(' ', preg_split('/([+-])/', $f, -1, PREG_SPLIT_DELIM_CAPTURE))
. ' = 100';
}
}
return $list;
}
問題5の解法まで15分程度でたどり着いたんですが、最初strtrで「何もしない」を空文字列に置換してしまった後にstr_splitしてしまっていて、なかなかこのバグを直せずタイムオーバー。プログラマ失格です。残念。