プログラミングクイズ（アルゴリズム問題）の解き方

プログラミングクイズ（アルゴリズム問題）とは？

プログラミングクイズ（アルゴリズム問題）とは、プログラミングを使って解くクイズ（問題）です。要するに Nagoya.php での問題を解く時間や、オフラインリアルタイムどう書くのことです。オンラインでもcodeiqやpaiza等で体験できますね。

2月のNagoya.phpで、「どうやって解いたら良いかわからない」という人が意外とたくさんいたので、アルゴリズム問題に慣れている人（Nagoya.phpの常連とか）がどうやって解いているのかを書いてみることにしました。 ※この記事で紹介するのは飽くまで一例ですので、人によっては全然違う考え方もあるかもしれません。

考え方

下の例題を見てください。

例題
カンマ区切りで与えられた数値を全て足して、3桁ずつカンマで区切って返してください。
たとえば、 100,200,300,400,500 が与えられたら、100+200+300+400+500 の結果である 1500 を 1,500 にして返します。

（問題が簡単すぎて、暗算で解けてしまいますが）これをプログラムを使って解いてみましょう。

まず、問題文から、問題の内容を下記の3つのブロックに分けます。

入力値の処理
計算
出力用の整形

入力値の処理 には、与えられた値（例題では、「カンマ区切りで与えられた数値」）を 計算 するのに適した形にして 計算 に渡す機能を持たせます。 計算 には、問題のメイン部分（例題では、「数値を全て足す」）を実行する機能を持たせます。 出力用の整形 には、 計算 の結果を問題で求められている形式（例題では、「3桁ずつカンマで区切る」）に整える機能を持たせます。

どんなに複雑に見える問題でも、アルゴリズム問題は必ずこの3つのブロックに分けることができます。（現実の仕事で書くコードも…？）

基本の解き方

では、3つのブロックごとに実際に例題を解いて行きます。

入力値の処理

与えられた "100,200,300,400,500" という文字列を、「数値を全て足す」を実行する 計算 過程に渡すのに適した形にするには、どうしたら良いでしょうか？

最初に足す対象の数値を分けなければ、何と何を足し算すればいいのかわかりません。よって、カンマで区切られた一つの文字列の状態から、カンマで分けて別々の値にする必要がありそうです。更に、次の 計算 過程で書く計算内容は「すべて足す」なので、文字列ではなく数値になっているともっと嬉しいですね。

そこで、下のサンプルのように、文字列をカンマで分割して数値化する処理を書くことにします。

$input = '100,200,300,400,500';
$numbers = explode(',', $input);
array_walk(&$numbers, function(&$number){ $number = (int)$number; });

大抵のアルゴリズム問題では入力値は文字列で与えられるので、 入力値の処理 では、文字列を一文字ずつ分かれた配列に変換する str_split() や、文字列を区切り文字で分割する explode() をよく使います。

計算

問題のメイン部分です。書くのは 入力値の処理 で数値の配列に変換された後の入力値に対する計算だけなのですが、複雑な問題の場合はここだけで時間の大半を使うことも珍しくありません。

例題の場合、 入力値の処理 で与えられた文字列から変換済の数値の配列を受け取り、「数値を全て足す」処理を書けば良いでしょう。配列の要素を全て足す処理は色々な書き方がありますが、ここでは一番簡単な array_sum() 関数を使うことにします。

$result = array_sum($numbers);

計算部分に関してはこれが正解というものはなく、標準的な書き方も（ほぼ）ありません。開発者個人の個性が出る・出せるところなので、他の人が書いたこの部分のコードを読むと面白いです。

出力用の整形

今度は、 計算 の結果を求められている出力形式に整えることを考えます。

例題の場合、「3桁ずつカンマで区切って返す」なので、PHP 標準の number_format() を使って3桁区切りにしてから出力することにします。

$output = number_format($result);
echo $output;

3つのブロックをつなげて、与えられた入力値（例題では、 "100,200,300,400,500" ）から期待する出力値（例題では、 1,500 ）が得られることを確認したら、答えの完成です！

PHPUnitを使って楽に全ての値セットを試す

大抵のアルゴリズム問題では、入力値と期待する出力値のセットが複数与えられています。 1つのセットだけだと、期待する出力値と実際の出力値が一致したのは偶然かもしれないからです。

本当に問題で求められている処理が正しく書けたかどうか確認するためにも、全部のセットを試したいのですが、「基本の解き方」の答えのコードだけでは、与えられた値セットごとに $input を書き換え、実行して、出力が期待値と一致しているかを目で見て確認する必要があります。それでは面倒なので、 PHPUnit を使って楽に確認しましょう。

PHPUnit は、 PHP のユニットテストのためのツールです。テストを楽に行うために dataProvider という仕組みがあります。（仕事コードでもたくさんの入力値・出力値セットを試したい場面はあるものです） https://phpunit.de/manual/current/ja/writing-tests-for-phpunit.html#writing-tests-for-phpunit.data-providers

dataProviderを使って、全ての入力値・出力値セットについて「基本の解き方」を楽に確認するサンプルは下記のようになります。

<?php

class MyTest extends \PHPUnit_Framework_TestCase
{
    /**
     * @test
     * @dataProvider provideTestData
     * @param string $input
     * @param string $output
     */
    public function test($input, $expectedOutput)
    {
        // 「基本の解き方」の答えここから
        // 入力値の処理
        $numbers = explode(',', $input);
        array_walk(&$numbers, function(&$number){ $number = (int)$number; });

        // 計算
        $result = array_sum($numbers);

        // 出力値の整形
        $output = number_format($result);
        // 「基本の解き方」の答えここまで

        // 期待する出力と実際の出力が一致しているかどうかを確認
        $this->assertEquals($expectedOutput, $output);
    }

    public function provideTestData()
    {
        return [
            ["100,200,300,400,500", "1,500"],
            ["1,2,3,4,5", "15"],
            ["1000,2000,3000,4000,5000", "15,000"],
            // ここにもっと他の入力値・出力値セットを書くことができる
        ];
    }
}

PHPUnit自体のインストールや他の活用法については公式のサイトや書籍を参考にしてください。

まとめ

アルゴリズム問題は、一見複雑怪奇に見えても、細かく分割して一つ一つ解決していけば、解けるものです。（現実世界の諸問題はその限りではありませんが）「基本の解き方」では 入力値の処理 ・ 計算 ・ 出力用の整形 の3つのブロックに分けて考えましたが、より複雑な問題を解く場合は、それぞれのブロックの中で更にいくつかの部品に分ける必要も出てくるでしょう。

関心を分離するってどういうこと？

次のNagoya.phpでは、ただ問題を解いて終わりではなく、答えのコードをお互いに見せ合って、どのように分けられるか、どの分け方がよりわかりやすいか、あるいは、分けた部品の中の計算そのものの違い、などを語り合える場ができれば良いなあ、と思います。

QUARTETCOM TECH BLOG カルテットコミュニケーションズ開発部ブログ