import kotlin.math.floor
import kotlin.math.log
import kotlin.math.pow
import kotlin.time.DurationUnit

fun main() {
    fun part1(input: List<String>): Long = Day11Solver(input).solve(25)

    fun part2(input: List<String>): Long = Day11Solver(input).solve(75)

    val testInput = readInput("Day11_test")
    check(part1(testInput) == 55312L)
    //check(part2(testInput) == 0L)  No test output available.

    val input = readInput("Day11")
    part1(input).println()
    part2(input).println()

    timeTrials("Part 1", unit = DurationUnit.MICROSECONDS) { part1(input) }
    timeTrials("Part 2", repetitions = 1000) { part2(input) }
}

class Day11Solver(input: List<String>) {
    private val parsedInput = input[0].split(' ').map { it.toLong() }

    /*
     * i ∈ ℕ₀ ∪ {-1}, φᵢ: ℕ₀ → ℕ shall be the function mapping the amount of stones generated to the amount of steps
     * taken with a stone of starting number i.
     *
     * Furthermore, ѱ: ℕ₀ → ℕ₀ ⨯ (ℕ₀ ∪ {-1}) shall be the function mapping an index to two new indices after a step.
     *
     *         ⎧ (1, -1)       if i = 0
     * ѱ(i) := ⎨ (a, b)        if ⌊lg(i)⌋ + 1 ∈ 2 ℕ    with a := i/(10^((⌊lg(i)⌋ + 1) / 2)), b := i - 10^((⌊lg(i)⌋ + 1) / 2) * a
     *         ⎩ (2024 i, -1)  otherwise
     *
     *          ⎧ 0                      if i = -1
     * φᵢ(n) := ⎨ 1                      if n = 0
     *          ⎩ φₖ(n - 1) + φₗ(n - 1)  otherwise    with (k, l) := ѱ(i)
     *
     * With that φᵢ(n) is a sum with n up to 2ⁿ summands, that are either 0 or 1.
     */
    private val cacheIndices = mutableMapOf<Long, Pair<Long, Long>>()  // Cache the next indices for going from φᵢ(n) to φₖ(n - 1) + φₗ(n - 1).
    private val cacheValues = mutableMapOf<Pair<Long, Int>, Long>()  // Also cache already calculated φᵢ(n)

    fun calculatePsi(i: Long): Pair<Long, Long> = cacheIndices.getOrPut(i) {
        if(i == -1L) throw IllegalArgumentException("Advancement made: How did we get here?")
        else if (i == 0L) 1L to -1L
        else {
            val amountOfDigits = (floor(log(i.toDouble(), 10.0)) + 1)

            if (amountOfDigits.toLong() % 2 == 0L) {
                // Split digits at the midpoint.
                val a = floor(i / 10.0.pow(amountOfDigits / 2))
                val b = i - a * 10.0.pow(amountOfDigits / 2)
                a.toLong() to b.toLong()
            } else {
                2024 * i to -1L
            }
        }
    }

    fun calculatePhi(i: Long, n: Int): Long = cacheValues.getOrPut(i to n) {
        if (i == -1L) 0L
        else if (n == 0) 1L
        else {
            val (k, l) = calculatePsi(i)
            calculatePhi(k, n - 1) + calculatePhi(l, n - 1)
        }
    }

    fun solve(steps: Int): Long = parsedInput.sumOf {
        val debug = calculatePhi(it, steps)
        debug
    }
}

#ingesloten "zee.kop"
#ingesloten "algemeen.kop"

besloten getal
splits(
    zeer groot natuurlijk getal x,
    zeergrootnatuurlijkgetalverwijzing a,
    zeergrootnatuurlijkgetalverwijzing b)
{
	zeer groot natuurlijk getal m;
	getal n, g;

	mits (!x) lever 0;
	voor (n=0, m=1; m<=x;  n++, m*=10) ; mits (n%2) lever 0;
	voor (g=0, m=1; g<n/2; g++, m*=10) ;
	volg a = x/m;
	volg b = x%m; lever 1;
}

#definieer GEHL (1024*1024)
besloten zeer groot natuurlijk getal geh[GEHL][76];

besloten zeer groot natuurlijk getal
afdalen(zeer groot natuurlijk getal w, getal n)
{
	zeer groot natuurlijk getal a,b;

	mits (n<1 ) lever 1;
	mits (w==0) lever afdalen(1, n-1);
	mits (w<10) lever afdalen(w*2024, n-1);
	mits (w<GEHL && geh[w][n])        lever geh[w][n];
	mits (!splits(w, naar a, naar b)) lever afdalen(w*2024, n-1);

	lever w<GEHL ? geh[w][n] =
	    afdalen(a, n-1) + afdalen(b, n-1) :
	    afdalen(a, n-1) + afdalen(b, n-1);
}

getal
aanvang(getal parametersom, vasteletterverwijzingsverwijzing parameters)
{
	zeer groot natuurlijk getal d1=0,d2=0, waarde;

	mits (parametersom > 1)
		VERWERP(heropen(parameters[1], "r", standaardinvoer));

	zolang (invorm(" %llu", &waarde) == 1) {
		d1 += afdalen(waarde, 25);
		d2 += afdalen(waarde, 75);
	}

	uitvorm("11: %llu %llu\n", d1, d2);
	lever 0;
}

#include "common.h"

/* returns 1 and splits x if even-digited, 0 otherwise */
static int
split(uint64_t x, uint64_t *a, uint64_t *b)
{
	uint64_t p;
	int n, i;

	if (!x) return 0;
	for (n=0, p=1; p<=x;  n++, p*=10) ; if (n%2) return 0;
	for (i=0, p=1; i<n/2; i++, p*=10) ;
	*a = x/p;
	*b = x%p; return 1;
}

/*
 * recur() is memoized in mem[]. Testing found the size MEMZ to be optimal:
 * lowering siginificantly reduced hits, but raising tenfold didn't add a
 * single hit.
 */

#define MEMZ (1024*1024)
static uint64_t mem[MEMZ][76];

static uint64_t
recur(uint64_t v, int n)
{
	uint64_t a,b;

	if (n<1 ) return 1;
	if (v==0) return recur(1, n-1);
	if (v<10) return recur(v*2024, n-1);
	if (v<MEMZ && mem[v][n]) return mem[v][n];
	if (!split(v, &a, &b))   return recur(v*2024, n-1);

	return v<MEMZ ? mem[v][n] =
	    recur(a, n-1) + recur(b, n-1) :
	    recur(a, n-1) + recur(b, n-1);
}

int
main(int argc, char **argv)
{
	uint64_t p1=0,p2=0, val;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	while (scanf(" %"SCNu64, &val) == 1) {
		p1 += recur(val, 25);
		p2 += recur(val, 75);
	}

	printf("10: %"PRId64" %"PRId64"\n", p1, p2);
	return 0;
}