Equation resolver for https://youtu.be/Mogkxm9600o

equation-resolver.md

Example usage

php equation-resolver.php

Output:

(1 / 7 + 7) * (7 + 7) = 100
((1 / 7) + 7) * (7 + 7) = 100
(7 + 1 / 7) * (7 + 7) = 100
(7 + (1 / 7)) * (7 + 7) = 100
(7 + 7) * (1 / 7 + 7) = 100
(7 + 7) * ((1 / 7) + 7) = 100
(7 + 7) * (7 + 1 / 7) = 100
(7 + 7) * (7 + (1 / 7)) = 100

Performed 57600 test calculations, found 8 equations.

Parameters

• Use another target value: php equation-resolver.php 99
• Find equations for 5, 3 and 2 that result in 25: php equation-resolver.php 5 3 2 25

equation-resolver.php

<?php
declare(strict_types = 1);

$target = 100;
$numbers = [7,7,7,7,1];

$arguments = $_SERVER['argv'] ?? [];
array_shift($arguments);
if (count($arguments) > 0) {
    $target = (int)array_pop($arguments);
}
if (count($arguments) > 0) {
    $numbers = array_map('intval', $arguments);
}

(new EquationResolver($target, $numbers))->perform();

class EquationResolver {
    private const DIGIT = 'd';

    private array $valueGroups;
    private array $operationGroups;
    private int $maxDigits;

    public function __construct(
        private int $targetValue,
        array $values,
        array $operations = ['+', '-', '*', '/'],
    ) {
        $this->maxDigits = count($values);
        $valueGroups = [];
        foreach ($values as $value) {
            $valueGroups = $this->addCombinations($valueGroups, $value);
        }
        $this->valueGroups = $this->arrayUunique(
            $valueGroups,
            fn (array $a, array $b): int => strcmp(implode('', $a), implode('', $b))
        );

        $this->operationGroups = $this->combineOperations($operations, [[]], $this->maxDigits - 1);
    }

    private function combineOperations(array $operations, array $existingGroups, int $iterations): array
    {
        if ($iterations <= 0) {
            return $existingGroups;
        }

        $groups = [];
        foreach ($operations as $op) {
            foreach ($existingGroups as $id => $group) {
                $groups[] = [...$group, $op];
            }
        }

        return $this->combineOperations($operations, $groups, $iterations - 1);
    }

    private function arrayUunique(array $array, callable $comparator): array {
        $uniqueArray = [];
        do {
            $element = array_shift($array);
            $uniqueArray[] = $element;

            $array = array_udiff(
                $array,
                [$element],
                $comparator
            );
        } while (count($array) > 0);

        return $uniqueArray;
    }

    private function addCombinations(array $existingCombinations, int $number): array
    {
        if (count($existingCombinations) === 0) {
            return [
                [$number]
            ];
        }
        $combinations = [];
        foreach ($existingCombinations as $combination) {
            for ($i = 0; $i < count($combination) + 1; ++$i) {
                $combinations[] = [
                    ...array_slice($combination, 0, $i),
                    $number,
                    ...array_slice($combination, $i)
                ];
            }
        }

        return $combinations;
    }

    private function canonicalizeExpression(string $expression): string
    {
        return str_replace('(' . self::DIGIT . ')', self::DIGIT, $expression);
    }

    private function countNumberPlaceholders(string ...$expressions): int
    {
        return array_sum(
            array_map(
                fn (string $expression): int => strlen(preg_replace('/[^a-z]/', '', $expression)),
                $expressions
            )
        );
    }

    private function combineExpressions(array $expressionsA, array $expressionsB): array
    {
        $expressions = [];

        foreach ($expressionsB as $eb) {
            $expressions[] = $eb;
        }
        foreach ($expressionsA as $ea) {
            $expressions[] = $ea;

            foreach ($expressionsB as $eb) {
                if ($this->countNumberPlaceholders($ea, $eb) > $this->maxDigits) {
                    continue;
                }

                $expressions[] = sprintf('%s _ %s', $ea, $eb);
                $expressions[] = sprintf('%s _ %s', $eb, $ea);

                $expressions[] = sprintf('(%s) _ %s', $ea, $eb);
                $expressions[] = sprintf('(%s) _ %s', $eb, $ea);

                $expressions[] = sprintf('%s _ (%s)', $ea, $eb);
                $expressions[] = sprintf('%s _ (%s)', $eb, $ea);

                $expressions[] = sprintf('(%s) _ (%s)', $ea, $eb);
                $expressions[] = sprintf('(%s) _ (%s)', $eb, $ea);
            }
        }

        return array_unique(
            array_map(
                fn (string $value) => $this->canonicalizeExpression($value),
                $expressions
            )
        );
    }

    public function perform(): void
    {
        $expressions = [self::DIGIT];
        for ($i = 0; $i < $this->maxDigits - 1; ++$i) {
            $expressions = $this->combineExpressions($expressions, $expressions);
        }
        $patterns = array_filter(
            $expressions,
            fn (string $expr): bool => $this->countNumberPlaceholders($expr) === $this->maxDigits
        );

        $iterations = 0;
        $found = 0;
        $patternValues = [];
        foreach ($this->valueGroups as $values) {
            foreach ($values as $i => $value) {
                $patternValues[$i * 2] = $value;
            }
            foreach ($this->operationGroups as $operationGroup) {
                foreach ($operationGroup as $j => $op) {
                    $patternValues[$j * 2 + 1] = $op;
                }
                ksort($patternValues, SORT_NUMERIC);

                foreach ($patterns as $pattern) {
                    ++$iterations;

                    $formatString = str_replace(['_', self::DIGIT], ['%s', '%d'], $pattern);
                    $calculation = vsprintf($formatString, $patternValues);

                    try {
                        $result = eval('return ' . $calculation . ';');
                        if ($result == $this->targetValue) {
                            printf("%s = %s\n", $calculation, $result);
                            ++$found;
                        }
                    } catch (\DivisionByZeroError $e) {
                        // ignore
                    }
                }
            }
        }

        printf("\nPerformed %d test calculations, found %s equations.\n", $iterations, $found);
    }
}