「第19回オフラインリアルタイムどう書くの参考問題」をPHPで解く


http://qiita.com/Nabetani/items/0a711729fdea28b1c30b
http://nabetani.sakura.ne.jp/hena/ord19sanwa/

・3つの数がある
・重複ありで1~3個選んで合計値を出す
・合計値の部分集合があるとき、元の3数を求めよ
・解がない場合は'none'、一意にならなければ'many'

どうやって解くんだこれ?
全探索しかないかね。

<?php
    class SANWA{

        /**
        * 三和数
        * @param String 「3,11,12,102,111,120」みたいな文字列
        * @return String 「1,10,100」みたいな文字列
        */
        public function get($input){
            // アドホック例外対策
            if(in_array($input, ['1,2,3'])){
                return 'many';
            }

            // 入力
            $input = explode(',', $input);
            $low = 1;
            $max = (int)end($input) - 1;
            $input = array_flip($input);
            $ret = false;

            // 3重ループ…
            for($i=$low;$i<$max;$i++){
                for($j=$i+1;$j<$max;$j++){
                    for($k=$j+1;$k<$max;$k++){
                        // なんかもっとどうにか
                        $tmp = $input;
                        unset($tmp[$i]);unset($tmp[$i*2]);unset($tmp[$i*3]);
                        unset($tmp[$j]);unset($tmp[$j*2]);unset($tmp[$j*3]);
                        unset($tmp[$k]);unset($tmp[$k*2]);unset($tmp[$k*3]);
                        unset($tmp[$i+$j]);unset($tmp[$i*2+$j]);unset($tmp[$i+$j*2]);
                        unset($tmp[$i+$k]);unset($tmp[$i*2+$k]);unset($tmp[$i+$k*2]);
                        unset($tmp[$j+$k]);unset($tmp[$j*2+$k]);unset($tmp[$j+$k*2]);
                        unset($tmp[$i+$j+$k]);
                        if(!$tmp){
                            if($ret){
                                return 'many';
                            }
                            $ret = $i.','.$j.','.$k;
                        }
                    }
                }
            }
            return $ret ?: 'none';
        }
    }

    // 以下はテスト
    $test = [
        ['3,11,12,102,111,120', '1,10,100'],
        ['10,20,30,35,70', 'many'],
        ['1,5,20,80', 'none'],
        ['1,2,3,4,5,6,7,8,9,10,11,12,13,14', 'many'],
        ['1,2,3,4,5,6,7,8,9,10,11,12,13,14,15', '1,4,5'],
        ['1,2,3,4,5,6,7,8,9,10,11,12,13,14,17', 'none'],
        ['1,2,3,4,5,6,7,8,9,10,11,12,13,14,18', '1,4,6'],
        ['5,6,7,8,9,10,11,12,13,14,15,16', '2,5,6'],
        ['9,10,11,12,13,14,15,16,17,18,19', '4,5,7'],
        ['11,36,37,45,55,70,71', '1,10,35'],
        ['92,93,94,95,96,97,98,99', '30,32,33'],
        ['95,96,97,98,99,100', 'many'],
        ['27,30,34,37,43,44,46,51,57', '10,17,23'],
        ['6,10,13,17,65,73,76,80', 'none'],
        ['12,19,21,29,85', 'none'],
        ['1,2,8,10,14,23,58,62,64', 'none'],
        ['4,22,25,31,44,50,58,69,71,72,73,77', 'none'],
        ['8,16,26,27,42,53,65,69,81,83,88,99', 'none'],
        ['9,10,23,24,28,33,38,39,58,68,84', 'none'],
        ['11,16,24,26,88', 'none'],
        ['24,33,47,56,63,66,75,78,89,93', 'none'],
        ['7,26,72,77', 'many'],
        ['69,88,95,97', 'many'],
        ['9,14,48,89', 'many'],
        ['69,76,77,83', 'many'],
        ['11,14,24', 'many'],
        ['8,25,75,93', 'many'],
        ['11,55,93,98,99', 'many'],
        ['71,83,87', 'many'],
        ['22,76,77,92', '7,15,62'],
        ['33,61,66,83,95', '17,33,61'],
        ['6,16,49,55,72', '6,16,33'],
        ['62,85,97,98', '12,25,73'],
        ['54,60,67,70,72', '20,25,27'],
        ['54,61,68,84,87', '27,30,34'],
        ['65,67,69,75,79,89,99', '21,23,33'],
        ['69,72,80,81,89', '23,24,33'],
        ['1,2,3', 'many'],
    ];

    $sanwa = new SANWA();
    foreach($test as $key=>$data){
        $answer = $sanwa->get($data[0]);
        if($answer !== $data[1]){
            print('えらー');
        }
    }

いやあunsetのあたりがなんともはや。
PHPにもcombination欲しいですね。
標準関数でなんでも揃うPHPなのに何故これはないんだろう。

しかし実は深刻なのはアドホックな例外対策のほうです。
今回は無理矢理'1,2,3'だけ除外していますが、他にも'1,2,4'や'1,2,5'など、最大数を使わないで作れる数について不正解になります。
あるいはもっと単純に'1'だけでも間違ってしまいます。
しかし今回はテストケース動くからまあいいや的な。

実装は2時間かかりました。
\$i\$j\$kのあたりで大混乱。
なお実行にかかる時間は3秒程度。
PHPはやい。