Code Golf: Enterprise Edition

Note: This article was written around September 2016, but I didn’t end up publishing it until this summer 🙂

Around July 2016 I was intrigued by a certain code golf problem that my online friend winny introduced to me. The problem involved testing the primality of the indices of a given array in a computer program and traversing the array in various ways, depending on the test outcome. The final goal was to either escape the array and report the number of steps required to break free, or fail with an error that meant escape could not possibly be achieved.

Logically speaking, the premise of the problem is rather simple; we can formulate it as so:

Imagine you have a function is_escapable() that takes two arguments: a zero-indexed array and a starting index. If you’re on a prime index n, you’re going to move back array[n] indices, and if you’re on a non-prime (note: not equivalent to composite) index n, you’re going to move to the index array[n]. From here you keep repeating until you either make it out of the jail (access an invalid index) or realize that escape is impossible.

So one of the two big questions is how you determine if it’s impossible to escape. It turns out to have a beautiful answer — if we fix our array (i.e. make it constant) we realize that our next location is a function of only our current index — our current state.
So if you revisit an index before you make an escape, you realize that it’s impossible to escape at all, because you’re going to keep looping indefinitely. Another way to visualize this is to imagine each index jump as a new recursive function call of is_escapable() using the same array but a new index. If you see the same function call as your starting call, you know the call stack will just keep enlarging.

The next big question is how to write a primality test in a terse way. This is significant because the entire premise about code golf is solving fun little problems in the least amount of bytes of source code as possible. As a result, people have made entire programming languages with built-in features designed to solve certain common tasks in terse ways (just as iterative constructs in general-purpose languages do for us).

Regardless of language, however, we still need to find some mathematical theorem or formula that lets us check primality in a simple way. Note that this does not require us to have an arbitrarily fast solution, so exponential (or even factorial!) time algorithms are okay to use. A common solution that almost everyone uses for this is Wilson’s theorem, a theorem stated in 1770 by mathematician John Wilson but proved by Lagrange in 1771 (funny how naming theorems works). The theorem states that

A natural number n > 1 is prime iff (n-1)! == -1 (mod n)

Upon the discussion of computational complexity and code-golfiness, I decided it would be a fun (and silly) exercise to embody everything wrong about code golf while also ignoring the true goal of code golf. I wanted to write insanely bloated and slow code to demonstrate exactly what *not* to do, but I only focused on one part of the problem at hand: the primality test.

Specifically, I wanted to write a slow implementation of the gamma function, which for positive integers is conveniently equivalent to (n-1)!, the expression we would want to calculate for Wilson’s Theorem. However, to calculate the gamma function, we were going to have to calculate partial products for Euler’s infinite product definition of the gamma function until successive terms were sufficiently close to each other. So our gamma function looks like this:

#include <cmath>
#include <limits>

long double apprx_gamma(long double t) {
    long double last_gamma {0.0};
    long double current_gamma {1.0/t};
    for (long double n {1.0}; std::abs(current_gamma - last_gamma) > 10 * LDBL_MIN; n += 1.0) {
        last_gamma = current_gamma;
        current_gamma *= std::pow(1 + 1/n, t) / (1 + t/n);
    return current_gamma;

(Note that our method does not actually satisfy the definition of convergence for infinite products)

This solution pretty much grinds to a halt before you can even calculate 15!, so it’s probably not production-ready yet 😉

Leave a Reply

Your email address will not be published. Required fields are marked *