PHPで「1時間以内に解けなければプログラマ失格となってしまう5つの問題」の問題4と5を改めて解いてみました - Inside Closure

前回、解いた

ですが、さすがにあんまりな内容だったので問題4と5の答えを改めてそれっぽい感じにつくってみました。

主に次のページを参考にしました。
http://qiita.com/tanakh/items/b4069a6d3485ef4278ce
http://techblog.mindpl.co.jp/2014/09/array_combination/

つまりカンニングしました。

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる(解答例)。

<?php
require_once 'util.php';

function p4(array $xs)
{
    $xs = array_sort($xs, function($a, $b) { return "{$b}{$a}" < "{$a}{$b}"; });
    return implode($xs);
}

echo p4([50, 2, 1, 9]). "\n";

$ php 4.php 
95021

問題5

1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる(解答例)

<?php
require_once 'util.php';

function calc($expr)
{
    $f = function(array $acc, $term) {
        if ($term === '+') {
            $acc['x'] = $acc['f']($acc['x'], $acc['y']);
            list($acc['f'], $acc['y']) = ['add', 0];
        }
        else if ($term === '-') {
            $acc['x'] = $acc['f']($acc['x'], $acc['y']);
            list($acc['f'], $acc['y']) = ['sub', 0];
        }
        else if ($term === '=') {
            $acc['x'] = $acc['f']($acc['x'], $acc['y']);
        }
        else if ($term !== '') {
            $acc['y'] = $acc['y'] * 10 + $term;
        }
        return $acc;
    };

    $expr[] = '=';
    $acc = array_reduce($expr, $f, ['x' => 0, 'f' => 'add', 'y' => 0]);
    return $acc['x'];
}

function is_n($n)
{
    return function($expr) use($n) { return calc($expr) === $n; };
}

function p5()
{
    $nums = array_map('wrap_array', range(1, 9));
    $opes = replicate(8, ['+', '-', '']);
    $exprs = array_filter(direct_product(alternate($nums, $opes)), is_n(100));
    return array_map('implode', $exprs);
}

foreach (p5() as $expr) {
    echo $expr. "\n";
}

$ php 5.php 
1+23-4+56+7+8+9
12+3-4+5+67+8+9
1+2+34-5+67-8+9
1+2+3-4+5+6+78+9
123-4-5-6-7+8-9
123+45-67+8-9
1+23-4+5+6+78-9
12-3-4+5-6+7+89
12+3+4+5-6-7+89
123-45-67+89
123+4-5+67-89

util.phpはこんな感じです。

<?php

function array_sort(array $xs, $isAsc)
{
    usort($xs, function($a, $b) use($isAsc) { return $isAsc($a, $b) ? -1 : 1; });
    return $xs;
}

function alternate(array $xs, array $ys)
{
    return $xs === [] ? $ys : array_merge([$xs[0]], alternate($ys, array_slice($xs, 1)));
}

function div_qr($n, $d)
{
    return [intval($n / $d), $n % $d];
}


function replicate($n, $x)
{
    return array_map(function($n) use($x) { return $x; }, range(0, $n - 1));
}

function add($x, $y)
{
    return $x + $y;
}

function sub($x, $y)
{
    return $x - $y;
}

function count_direct_product(array $xss)
{
    $f = function(array $acc, array $xs) {
        $n = count($xs);
        $acc['direct_product'] *= $n;
        $acc['own']++;
        $acc['each'][] = $n;
        return $acc;
    };
    return array_reduce($xss, $f, ['direct_product' => 1, 'own' => 0, 'each' => []]);
}

function direct_product(array $xss)
{
    $count = count_direct_product($xss);

    $direct_product = [];
    for ($i = 0; $i < $count['direct_product']; $i++) {
        $combination = [];
        for ($q = $i, $j = 0; $j < $count['own']; $j++) {
            list($q, $r) = div_qr($q, $count['each'][$j]);
            $combination[] = $xss[$j][$r];
        }
        $direct_product[] = $combination;
    }
    return $direct_product;
}

function wrap_array($n)
{
    return [$n];
}

プログラマになりたいなぁ。