Advent of Functional PHP: Day 6

Day 6's challenge is a little fishy. Given what we've already done so far, it's pretty simple. The only catch is making sure you do it in an efficient way.

Specifically, we're asked to model the growth patterns of fictional lantern fish. In this silly model, we start with a list of fish at various ages. Each fish spawns a new fish every 7 days, and a newborn fish takes an extra 2 days before it starts spawning new fish. Fish also never die. (Someone warn the AI people that we've found the paperclip optimizer.)

Part 1 asks us how many fish there are after 80 days, all around the world, given the start data. Let's find out, but let's do so efficiently.

Getting the input

Getting the input in this case is trivial. It's a single line file of numbers 0-6, comma-delimited. Easy enough:

$fish = pipe($inputFile,
    file_get_contents(...),
    trim(...),
    explode(','),
);

Don't be naive

The naive, brute-force approach here is not going to work, but it's worth examining why. The basic logic goes like this: Every generation, iterate over all the fish and decrement their ages. If a fish rolls over from 0, set its age to 6 and also add a new fish, with a countdown of 8." With a foreach() loop that's easy. A map() operation wouldn't work, however, as map() is always 1:1. We cannot add new values. However, a reduction easily can. That is, the update for a single fish could be done like this:

// Don't do this.
function oneFishEvolver(array $nextgen, int $fish): array
{
    if ($fish === 0) {
        $nextgen[] = 6;
        $nextgen[] = 8;
    } else {
        $nextgen[] = $fish - 1;
    }
    return $nextgen;
};

$nextgen = reduce([], oneFishEvolver(...))($fish);

Where $nextgen starts as an empty array, and we reduce across the list of fish. Then we would do that 80 times to get our list of fish, the size of which is our answer.

That would work, but perhaps you can see two problems with it. One, we're calling a function every generation for every fish. That's n*m times. Given that the number of fish doubles every 6-8 days, n is going to get very big, very fast. That uses a ton of CPU time.

The second problem is that as the number of fish doubles every 6-8 days, meaning the memory needed to track them all also doubles every 6-8 days. With a reasonably modern computer, it could survive 80 generations, perhaps, but it's going to run into scaling problems sooner or later.

We can do better.

I don't want the fish

The insight here is that we don't care about individual fish. All fish of a given age will behave identically. We don't need each fish, we just need a count of the number of fish of a given age. There's only 9 possible ages, so that means we have an array of 9 elements as our only tracking state. So let's write a fishSummarizer() routine that converts our input list of raw fish into a summary of fish ages.

function fishCounter(array $fish): callable
{
    return static fn (int $number): int => pipe($fish,
        afilter(static fn (int $f): bool => $f === $number),
        count(...),
    );
}

function fishSummarizer(array $fish): array
{
    return pipe(range(0, 8),
        amap(fishCounter($fish)),
    );
}

The number of fish of a given age is just the count of fish of that age, so we have a fishCounter() routine that filters the fish list and then counts what's left. We need both the list of fish and the number to get, however, and pipe() only works with single-argument functions. This is another case where partial function application would make everything easier, as we could simply map over fishCounter($fish, ?). PHP doesn't support that, sadly, so we have to do it manually. So fishCounter() take the list of fish and returns a new function, closed over that list, which takes the number to find and returns the count of that number.

We then map a range of 0-8 into that function, and get back a list of the number of fish with that number, in the initial data.

$fishCounter = pipe($inputFile,
    file_get_contents(...),
    trim(...),
    explode(','),
    fishSummarizer(...),
);

Growing the fish

Next, we need a way to evolve one generation of fish to the next, given this summary data structure. The logic for how fish age is nice and simple, so the funciton is as well:

function fishMapper(array $fishCounter): array
{
    return [
        0 => $fishCounter[1],
        1 => $fishCounter[2],
        2 => $fishCounter[3],
        3 => $fishCounter[4],
        4 => $fishCounter[5],
        5 => $fishCounter[6],
        6 => $fishCounter[7] + $fishCounter[0],
        7 => $fishCounter[8],
        8 => $fishCounter[0],
    ];
}

Every next generation of fish, the number of fish of a given age is equal to the fish that were one day higher. (We're not tracking their actual age, remember; just how long until they spawn again.) There's two exceptions to that:

Fish that roll down past 0 bump up to age 6.
When a fish rolls down past 0, a new fish is added at age 8.

All of that is captured in the simple array definition above. So now we have a single operation to map one generation to the next. Huzzah!

How do we apply that repeatedly to simulate multiple generations? The imperative answer would be a for() loop and a counting variable, but we're not being imperative. How do we convert a single map into a loop?

There's a number of ways to do so, depending on the language you're in. In PHP, I believe the easiest is... a reduce(). (It's coming up a lot, isn't it.) The reducing operation takes the previous generation and returns the next generation... but also has that extra new value from the list. We don't actually care about that variable, so we can explicitly drop it:

$fishCounter = pipe($inputFile,
    file_get_contents(...),
    trim(...),
    explode(','),
    fishSummarizer(...),
);

$total = pipe(range(1, 80),
    reduce($fishCounter, static fn (array $counts, int $gen): array => fishMapper($counts)),
    array_sum(...),
);

We reduce the list 1-80, using the fish count from the file as our starting state. The reducing operation just sub-calls to fishMapper(), ignoring the generation number we're on as we don't care. Finally, we sum up all of the counts in the array to get the number of fish.

Moar fish!

Part 2 is where our insight into the performance characteristics pays off. Part 2 only changes one thing: We want 256 generations instead of 80. Had we gone with the brute force method we may have been able to fit 80 generations into memory and a reasonable runtime, but not 256.

However, since we were smart and are just using summaries, literally all we have to do is change the range() call to be 1-256. That's it. The memory usage is identical, and the runtime is O(n) for the number of generations.

Generalize

Just for fun, let's try to abstract out that iteration-via-reduction process. We need to keep the explicit interstitial function to ignore the counter, as PHP user-space functions will happily ignore extra arguments but internal functions will not. (Just to make life difficult.) The rest is pretty straightforward:

function nth(int $count, mixed $init, callable $mapper): mixed
{
    return reduce($init, static fn (mixed $val, int $gen): mixed => $mapper($val))(range(1, $count));
}

We can now rewrite our final call like so:

$total = pipe(
    nth(256, $fishCounter, fishMapper(...)),
    array_sum(...),
);

All we've done her is abstract out the reduce() call, much as map() is just abstracting out a foreach() loop. But we now have, effectively, a version of reduce that doesn't care about the number in the incoming array. (We could also refactor it down to just being a foreach() loop, which is probably faster in practice as the two would be isomorphic. That's left as an exercise for the reader.)

It also suggests a way we could have an infinite series of generations, similar to the iterate operator in Haskell.

function iterate(mixed $init, callable $mapper): iterable
{
    yield $init;
    while (true) {
        yield $init = $mapper($init);
    }
}

That will continually yield the next evolution of a value without any additional effort. Combined with some sort of condition check we can functionally iterate until some point, or pipe it into iterator-based calls (itmap() and itfilter(), not amap() or afilter()) to create complex, reactive-programming-style behaviors out of simple pieces. The generator is slightly slower than the range() approach if we only care about a specific value, but more flexible. Take your pick.

Fin.

Code is, of course, on GitHub.

Want to know more about functional programming and PHP? Read the whole book on the topic: Thinking Functionally in PHP.