Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

元ネタ

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした