28
35

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

1時間以内に解けなければプログラマ失格となってしまう5つの問題をPHPで解く

Last updated at Posted at 2015-09-08

元ネタ

「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となる。

解答

無難に一番有名な動的計画法のやつで。

$nに100を渡して実行
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してしまっていて、なかなかこのバグを直せずタイムオーバー。プログラマ失格です。残念。

28
35
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
28
35

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?