Найти минимальную возможную разницу между числами с неизвестными цифрами

Ответ 1

Хорошо, у меня есть решение.

Объяснение:

Использует регулярное выражение для захвата двух чисел, затем сравнивает их в парах слева направо, начиная с предположения, что они равны. Это означает, что они оба разрешают одинаковое число, где это возможно, или 0, если они оба ?.

После того, как существует пара чисел, которые не равны, она начинает устанавливать нижние ? на 9, а высшие - от ? до 0, чтобы сделать их как можно ближе.

Вот пример этого в действии.

function minDiff($str) {
    preg_match("/([\d\?]+) ([\d\?]+)/", $str, $matches);

    $first = $matches[1];
    $second = $matches[2];

    $biggest = 0; // -1 = first, 0 = none, 1 = second

    $firstResult = 0;
    $secondResult = 0;

    for ($i = 0; $i < strlen($first); $i++) {
        $powerValue = strlen($first) - $i - 1;
        if ($biggest != 0) { // not equal
            if (!strcmp($first[$i], '?') && !strcmp($second[$i], '?')) {
                if ($biggest > 0) { // second is biggest
                    $firstResult += 9 * pow(10, $powerValue);
                } else { // first is biggest
                    $secondResult += 9 * pow(10, $powerValue);
                }
            } elseif (!strcmp($first[$i], '?')) {
                if ($biggest > 0) { // second is biggest
                    $firstResult += 9 * pow(10, $powerValue);
                }
                $secondResult += $second[$i] * pow(10, $powerValue);
            } elseif (!strcmp($second[$i], '?')) {
                if ($biggest < 0) { // first is biggest
                    $secondResult += 9 * pow(10, $powerValue);
                }
                $firstResult += $first[$i] * pow(10, $powerValue);
            } else {
                $firstResult += $first[$i] * pow(10, $powerValue);
                $secondResult += $second[$i] * pow(10, $powerValue);
            }
        } else { // both equal (so far)
            if (!strcmp($first[$i], '?')) {
                $firstResult += $second[$i] * pow(10, $powerValue);
                $secondResult += $second[$i] * pow(10, $powerValue);
            } elseif (!strcmp($second[$i], '?')) {
                $firstResult += $first[$i] * pow(10, $powerValue);
                $secondResult += $first[$i] * pow(10, $powerValue);
            } else {
                if (intval($first[$i]) > intval($second[$i])) {
                    $biggest = -1;
                } elseif (intval($first[$i]) < intval($second[$i])) {
                    $biggest = 1;
                }
                $firstResult += $first[$i] * pow(10, $powerValue);
                $secondResult += $second[$i] * pow(10, $powerValue);
            }

            // Find if next number will change
            if (($i + 1) < strlen($first) && strcmp($first[$i + 1], '?') && strcmp($second[$i + 1], '?')) {
                $diff = preg_replace('/\?/', '0', substr($first, $i + 1)) - preg_replace('/\?/', '0', substr($second, $i + 1));
                echo "$diff\n";
                // Check to see if you need to add 1 to the value for this loop
                if ($diff > pow(10, $powerValue) / 2) {
                    $secondResult += pow(10, $powerValue);
                    $biggest = 1;
                } elseif ($diff < pow(10, $powerValue) / -2) {
                    $firstResult += pow(10, $powerValue);
                    $biggest = -1;
                }
            }
        }
    }

    echo "first: ".str_pad($firstResult, strlen($first), "0", STR_PAD_LEFT)."\n";
    echo "second: ".str_pad($secondResult, strlen($second), "0", STR_PAD_LEFT)."\n\n";
}