Finding factor combinations ... tangent to a mensa puzzle

benchmark.php

<?php

require_once 'FactorFinder.php';
require_once 'findFactorCombinations.php';

$lowNumber = (array_key_exists(1, $argv)) ? $argv[1] : 72;
$highNumber = (array_key_exists(2, $argv)) ? $argv[2] : 999;
$factorCount = (array_key_exists(3, $argv)) ? $argv[3] : 10;

$metric = 0; // positive means class wins; negative means function wins
for ($i = $lowNumber; $i <= $highNumber; $i++) {
    $start = microtime(true);
    findFactorCombinations($i, $factorCount);
    $functionTime = microtime(true) - $start;

    $start = microtime(true);
    $factorFinder = new FactorFinder();
    $factorFinder->findFactorCombinations($i, $factorCount);
    $classTime = microtime(true) - $start;

    if ($functionTime > $classTime) {
        echo sprintf("Class beat function by %s seconds\n", $functionTime - $classTime);
        $metric++;
    } elseif ($functionTime < $classTime) {
        echo sprintf("Function beat class by %s seconds\n", $classTime - $functionTime);
        $metric--;
    }
}

echo "metric is {$metric}\n";
if ($metric > 0) {
    echo "Class is faster than function\n";
} elseif ($metric < 0) {
    echo "Function is faster than class\n";
} else {
    echo "Class and function same speed\n";
}

demo.php

<?php

require_once 'FactorFinder.php';

$number = (array_key_exists(1, $argv)) ? $argv[1] : 72;
$factorCount = (array_key_exists(2, $argv)) ? $argv[2] : 3;

$factorFinder = new FactorFinder();
$combos = $factorFinder->findFactorCombinations($number, $factorCount);

foreach ($combos as $combo) {
    $product = array_product($combo);
    echo sprintf("%s = %s\n", implode(' * ', $combo), $product);
    if ($number != $product) {
        echo sprintf("That's not %s!\n", $number);
    }
}

echo sprintf("%s combinations found\n", count($combos));

FactorFinder.php

<?php

class FactorFinder
{
    protected $pairSets = array();

    public function findFactorCombinations($number, $factorCount)
    {
        if ($factorCount < 2) {
            return false;
        }

        $pairs = $this->findPairs($number);

        if ($factorCount == 2) {
            return $pairs;
        }

        $combos = array();
        foreach ($pairs as $pair) {
            $lastFactorCombos = $this->findFactorCombinations($pair[1], $factorCount - 1);
            if ($lastFactorCombos === false) {
                break;
            }
            foreach ($lastFactorCombos as $combo) {
                $combo[] = $pair[0];
                sort($combo);
                $product = array_product($combo);
                if (!in_array($combo, $combos)) {
                    $combos[] = $combo;
                }
            }
        }
        return $combos;
    }

    protected function findPairs($number)
    {
        if (array_key_exists($number, $this->pairSets)) {
            return $this->pairSets[$number];
        }

        $pairs = array();
        for ($factor1 = 1; $factor1 <= $number; $factor1++) {
            if ($number % $factor1 != 0) {
                continue;
            }
            $pair = array($factor1, $number / $factor1);
            sort($pair);
            if (in_array($pair, $pairs)) {
                break;
            }
            $pairs[] = $pair;
        }

        $this->pairSets[$number] = $pairs;
        return $pairs;
    }
}

findFactorCombinations.php

<?php

function findFactorCombinations($number, $factorCount)
{
    if ($factorCount < 2) {
        return false;
    }

    $pairs = array();
    for ($factor1 = 1; $factor1 <= $number; $factor1++) {
        if ($number % $factor1 != 0) {
            continue;
        }
        $pair = array($factor1, $number / $factor1);
        sort($pair);
        if (in_array($pair, $pairs)) {
            break;
        }
        $pairs[] = $pair;
    }

    if ($factorCount == 2) {
        return $pairs;
    }

    $combos = array();
    foreach ($pairs as $pair) {
        $lastFactorCombos = findFactorCombinations($pair[1], $factorCount - 1);
        if ($lastFactorCombos === false) {
            break;
        }
        foreach ($lastFactorCombos as $combo) {
            $combo[] = $pair[0];
            sort($combo);
            $product = array_product($combo);
            if (!in_array($combo, $combos)) {
                $combos[] = $combo;
            }
        }
    }
    return $combos;
}