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 😉

G.O.A.L.S.

Global Awareness: As the son of two Pakistani immigrants, the importance of global awareness is not lost on me; every individual draws some sort of identify from their cultural background, and without taking the time to digest the differences between cultures and truly appreciate such distinctions, it is hopeless to claim to be a global citizen. In attempting to become more globally aware and sensitive to other cultures, I plan on sating my hunger for learning about new cultures by studying topics in foreign literature, whether that encompasses the works of those living in other nations, or those living in cultures at home yet unknown. In fact, my progress in increasing my cultural awareness has already begun, as I have recently joined the Ohio State University Kendo Club, of which I have recently been chosen as an officer. Such an activity has brought me closer to a rich art drawing its roots from feudal Japan, and as such, has introduced me to a wide array of individuals and personalities as well. I hope that maybe my newfound hobby will bring me opportunities to visit Japan and perhaps watch individuals compete overseas, as well as discover other aspects of East Asian culture.

Original Inquiry: Perhaps my primary motivation for attending university, were it not for the wealth of information and abundance of possibility, would be the ability to conduct research in fields in which I find the most passion in studying. Much of the past experiences I’ve had in visiting Pakistan have opened my eyes to the sheer deficit of technological and scientific progress, or rather, implementation, in many other areas of the world. As a result, I’ve felt the desire to pursue nuclear energy research in order to help improve the standards of living globally, by helping on the forefront of discovery. In fact, I’m currently in the process of searching for research projects to which I will apply in order to learn more about the research process while contributing to the fields that I enjoy. On the opposite side of the spectrum, I’ve also been performing in the Collegiate Winds, one of OSU’s large wind ensembles; the ability to play expressive music as a part of a larger team brings nothing but serenity and joy to all of us.

Academic Enrichment: In pursuing my honors double major in Mathematics and Physics within the College of Arts and Sciences, I have begun to build a foundation onto which I can carefully build with new knowledge gained from advanced courses in my intended majors. By electing to stress myself a little more during my first year by skipping a few course sequences, I set myself on a path to study graduate level topics in mathematics and physics: two intense and interesting studies that display a kind of symbiosis in how well they play into each other. As a result, by the end of my four years I should have hopefully developed a rigorous foundation unto which I can specialize even further through graduate studies in the years after. My general education classes, then, will serve to broaden my horizons and serve my interests in topics such as literature and foreign cultures.

Leadership Development: Much of my anticipated journey throughout post-secondary education will entail taking new leadership responsibilities upon myself in extracurricular clubs and activities elsewhere. My prior experience as an Eagle Scout should hopefully have prepared me enough to tackle new leadership tasks, such as working with the other Eminence Fellows of my class to develop and coordinate a service project for the Columbus community that shall stand for the duration of our time on campus and beyond. Additionally, my responsibilities in future lab environments and clubs to which I plan on committing more time, such as Kendo, will also require me to go beyond my past requirements in leading others and serving as an example. Regardless, I am no less than excited for the opportunities that await.

Service Engagement: To help other people at all times. As a boy scout, such a phrase was repeated by every individual at our weekly meetings to remind us of our obligation to our community. As such, I intend to pursue service opportunities as part of extracurricular club service events, as well as perhaps my largest anticipated service engagement during my time at the university: the Eminence Fellowship service project. With my 26 fellow classmates, I plan to help develop and execute a service project within the Columbus community meant to do more than simply resemble routine volunteer work. However, the first and most important part still remains for us to tackle developing a feasible yet substantial idea for a project.

About Me

users.each {|user| puts "Welcome, #{user}!"}

My name is Sameed Pervaiz and I have the privilege of studying Physics and Mathematics (with a little bit of Comp Sci) at the Ohio State University as an Eminence Fellow of the Class of 2020! I anticipate utilizing my passion for math, physics, and computers to help the community, be it locally, globally, through volunteer work or through undergraduate research.

I grew up in North Canton, Ohio, where I attended Jackson Local Schools for (nearly) my entire education. I always used to favor math and science in my early schooling, but it wasn’t until high school when I seriously started gravitating towards physics as I took various AP classes at Jackson. Having been introduced to computers by my older siblings as a young child, I also like to tinker with programming and neat software tools — perhaps you’ll see some of my blog posts migrated from teknik to here!

I so wish I could say academics use up all my time, but some of my other hobbies also see their share of its use! For one, music is dear to me — I’ve played trumpet since the fifth grade and have enjoyed playing in my high school marching, concert, and jazz bands; perhaps you’ll see me performing in Weigel Hall during the year in one of the university’s concert bands. I’ve also recently taken up Kendo as a hobby, and practice weekly with others in OSU’s Kendo Club (shameless plug: come try it out on Sundays from 12-3!). If you hear a group of people screaming and the sound of earthquakes inside the North Rec Center or the PAES — yep, that’s us.

That’s all I have for now — hope to see you around campus (or maybe online?), whether it be this year or in the future!