Advent of code 2019/22

Ajax Direct

// ==================================================
// > PART 1
// ==================================================
$deck = range(0, 10006);
foreach ($input->lines as $line) {
    match (true) {
        (bool) ((string) $line == "deal into new stack") =>
            $deck = array_reverse($deck),

        (bool) preg_match("/cut (-?[0-9]+)/", (string) $line, $match) =>
            $deck = array_merge(array_slice($deck, (int) $match[1]), array_slice($deck, 0, (int) $match[1])),

        (bool) preg_match("/deal with increment ([0-9]+)/", (string) $line, $match) => $deck = (function ($incr) use ($deck) {
            $other = array_fill(0, count($deck), 0);
            foreach ($deck as $j=>$card) $other[$j * $incr % count($deck)] = $card;
            return $other;
        })((int) $match[1]),
        default => die($line)
    };
}
$solution_1 = array_search(2019, $deck);

// ==================================================
// > PART 2 : Translated from reddit, I have no clue...
// ==================================================

/**
 * Convert rules to linear polynomial
 * (g∘f)(x) = g(f(x))
 */
function parse($l) {
    global $input;
    [$a, $b] = [1, 0];

    foreach ($input->lines->reverse() as $line) {

        if (((string) $line == "deal into new stack")) {
            $a = -$a;
            $b = $l - $b - 1;
            continue;
        }

        if ((bool) preg_match("/cut (-?[0-9]+)/", (string) $line, $match)) {
            $n = (int) $match[1];
            $b = ($b + $n) % $l;
            continue;
        }

        if (preg_match("/deal with increment ([0-9]+)/", (string) $line, $match)) {
            $n = (int) $match[1];
            $z = gmp_invert($n, $l);
            $a = gmp_mod(($a * $z), $l);
            $b = gmp_mod(($b * $z), $l);
            continue;
        }
    }

    return [(int) $a, (int) $b];
}

/**
 * modpow the polynomial: (ax+b)^m % n
 * f(x) = ax+b
 * g(x) = cx+d
 * f^2(x) = a(ax+b)+b = aax + ab+b
 * f(g(x)) = a(cx+d)+b = acx + ad+b
 */
function polypow($a, $b, $m, $n) {
    if ($m == 0) return [1, 0];
    if ($m % 2 == 0) return polypow(gmp_mod(gmp_pow($a, 2), $n), gmp_mod((gmp_mul($a, $b) + $b), $n), floor($m / 2), $n);
    [$c, $d] = polypow($a, $b, $m - 1, $n);
    return [gmp_mod($a * $c, $n), gmp_mod($a * $d + $b, $n)];
}

[$a, $b] = parse(119315717514047);
[$a, $b] = polypow($a, $b, 101741582076661, 119315717514047);
$solution_2 = (int) ((2020 * $a + $b) % 119315717514047);