In a personal project recently, I came to a problem that ended up being solved via number theory. I’m a little rusty, but this isn’t actually the first time I’ve used number theory to solve a coding problem. I thought it ended up interesting, so I decided to write a short post about it.

The issue is that I wanted a way to represent dates as numbers. The typical unix timestamp was quite a bit more specific than I wanted for my purposes, and I wanted to avoid pitfalls associated with DST and timezones, so struct tm was going to be a bit of a pain to manage. I wanted to handle dates. Only this and nothing more.

Furthermore, I didn’t want to handle something like “Number of days since 1900” or something like that, because handling leap years and different lengths of months is a bit of a pain.

So, this is the process that went through my mind.

The most intuitive way to represent a single date as a number is with multiples of 10. For example, April 13, 2017 would be 20170413. All dates for my use case would be after the year 2000, so I could just chop off those first two digits, making it 170413.

But that’s decimal, and computers think in binary, so I shouldn’t bother setting it up like this, exactly. Instead, I should use base 2. Meaning that rather than \(17\times10^{4} + 4\times10^{2} + 13\), I should use \(17\times2^{10} + 4\times2^{5} + 13\), which would give me, in binary, 100010010001101, which can be decomposed to 17, 4, and 13 in binary with simple bit shifting. (Assuming I did everything right there. I’m not double-checking it, but it’s basically the same idea as in decimal, and it should be easy to do with bit shifting.)

But there’s still a lot of wasted space there. You can still have a lot of invalid dates like the 23rd month of the year.

So, I decided to have a simple rollover system. There are, at most, 31 days in a month, so I could just have that the 32nd day means we know we’re on the next month. And we may as well start at zero, so that means that 0 = first day of the first month (Jan 1), 30 = 31st day of the month (Jan 31), and 31 = first day of next month (Feb 1). So, 35 would mean the fourth day of the second month of the year (Feb 4), and 203 would be the July 18th because it’s crossed the 31 marker 6 times and makes it to 17 more days. It’s easy to find a particular day because the whole thing is mod 31. (It’s easy to get lost in the offsets here, though.)

This still has some invalid dates like April 31st, but it’s also over a much smaller codomain than either base ten or base two.

Then we also have twelve months in a year, so we can use the same concept for finding years. Once we cross 12 months (372 days), we’re in the next year.

With this, we can convert a date into an integer with this equation: \(i = d + 31m + 372y\), where \(d\) is the day of the month (0-31), \(m\) is the month (0-11), and \(y\) is the number of years since 2001. The 31 converts the months to days and the 372 converts the years to days (as \(31\times12\)). We have a one-to-one relationship between a date and the integer resulting from this function.

Resulting in a very easy function:

/**
 * Convert a Date object to an integer.
 *
 * Integer is not human-readable as a date, but it orders the same way.
 *
 * @param   dateObj
 */
int toInt(Date dateObj)
{
    return dateObj.day + DAYMOD * dateObj.month
        + (MONTHMOD * DAYMOD) * dateObj.year;
    // Can actually simplify this a little bit.
}

With the Date struct being defined as:

typedef struct date_obj {
    /** @var Number of complete years since the year 2001. */
    int year;

    /** @var Month number, 0 - 11. */
    int month;

    /** @var Day of month, 0 - 30. */
    int day;
} Date;

But the other direction is slightly more complicated, and that’s where the number theory comes in.

Getting the day of the month is easy. \(i \equiv d + 31m + 372y (\text{mod } 31)\), and the second and third terms on the right are zero mod 31, so if we have an integer x we can easily get back the number of days with x % 31.

Getting back the month is a little more difficult. But not that difficult. Initially I tried working with the \(i \equiv d + 31m + 372y (\text{mod } 31)\), but that was dumb, because we’re using the wrong base there. Plus, there is no inverse of 31 modulo 372, so the equation is unsolvable.

It’s a little easier to start with rearranging the equation.

\[
\frac{i – d}{31} = m + 12y
\]

And we know that \(i – d\) is divisible by 31 because of how we defined \(d\). (My professors would absolutely want a better description than that in a proof, but it’s a blog post while I’m sitting in a coffee shop, so this will work for now.)

We can now use basic number theory to find \(m\) the same way that we found \(d\).

\[\frac{i-d}{31} \equiv m + 12y (\text{mod }12)\] \[\frac{i-d}{31} \equiv m (\text{mod }12)\]

Thus, (x - d)/31 % 12 is our number of months.

And finding the number of years once we have the number of days and months is trivial.

With these three parts, we have a function that’s the inverse of toInt from before:

/**
 * Convert an integer back to a Date object.
 *
 * @param   dateInt
 */
Date toDate(int dateInt)
{
    Date dateObj = {};

    dateObj.day = dateInt % DAYMOD;
    dateObj.month = (dateInt - dateObj.day) / DAYMOD % MONTHMOD;
    dateObj.year = (dateInt - dateObj.day - DAYMOD * dateObj.month)
        / (MONTHMOD * DAYMOD);

    return dateObj;
}

And that’s that.

(This is a copy-paste of the README.md from allquestionsinthebible, where the scripts discussed herein can be found.)

I’ve long been a proponent (admittedly, not a particularly vocal one) that everyone should learn to code at least a little. I don’t mean in the sense of the “You lost your job, so learn to code” buffoonery, just because coding professionally isn’t for everyone. That said, even if you have zero intention of using code professionally, it can be very handy to learn, say, a little bit of Python to get a job done.

What I have to present to you today is an example of how code can be a useful tool in your belt. This is just one of many instances of my using Python to demonstrate achieving a goal that would be difficult to do manually, whether you’re a professional developer or not. (And I don’t actually write Python professionally– My professional work is PHP, which is very different.)

There’s a background to this that’s relevant here. One of my Sunday School teachers made a passing comment at the Christmas party that he’d like to see a list of every question asked in the Bible. I thought to myself, “That should be easy, since every question ends with a question mark”, and I said I could probably do that with a Python script. He said he’d pay me if I did it, and I said it wasn’t necessary since it would be only about five lines of Python.

Well, it turned out not to be five lines of Python, but it was a pretty fun project in any case.

More importantly, though, it’s a great example of something that I could do because I knew how to write code, and why I think it would be beneficial for anybody to learn to code.

Essentially, code does nothing more than automate a monotonous task. So, something like finding every question in the Bible could be done by taking out a Bible and a sheet of paper, and painstakingly finding every single question, as a months-long task that in ages past would be performed by monks with nothing better to do (or by Strong, whoever that is). Or you could write a Python script that does all of it for you in seconds.

So, I took on the task during the week between Christmas and New Years, and this is how I did it. (I didn’t spend the whole week doing it, ftr.)

First off, I needed to use the World English Bible translation (WEB). The reason for this is that it is a modern language translation that is public domain. I could hypothetically do some webscraping and get the entirety of the ESV, but that would be legally sketchy at best.

I was disappointed to find that the current organization of the WEB in html is not terribly programmer-friendly. It’s far from horrendous, but I was expecting each verse to be in its own span or div, with an appropriate class name. Instead, the chapter and verse numbers themselves are in these divs/spans, and interspersed throughout the text. It makes perfect sense if you’re reading it in a browser, but makes things slightly difficult from a programmatic perspective. So, the first thing I did was reorganize everything– All of the WEB (just the Protestant canon) as an XML file. This is the first script, reorganizeasxml.py, and was the bulk of the work done.

To do this, I used the archive of the html version of the WEB. To run the first script to generate the XML, unzip the contents of that archive into a folder, drop reorganizeasxml.py into the directory, and run it. It will create complete.xml— One giant XML file containing the entire WEB translation, in a programmer-friendly XML format.

It’s about five MB in size, so I do not recommend trying to open it in Notepad or any other text editor that’s not designed for large files (I used less to view the contents).

I could have made this easier, theoretically, by using the plaintext version, which seems to have one verse per line. I decided against that, though, because I’m not 100% sure that it’s always the case that it’s one verse per line– It never explicitly says so– and since the file names seem to indicate to me that these files exist for the purpose of reading out loud, so I expect they’re not necessarily going to be particularly careful about line breaks. I think, then, that it would be better to put in the extra effort in the clearer source material. (And, honestly, a big part of my motivation here is that doing it the hard way is a lot more fun.)

reorganizeasxml.py loops through every file, uses BeautifulSoup to identify where every verse begins and ends, and dumps every verse into the output file, in (Protestant) canonical order. This is mostly pretty easy– The only thing that was mildly difficult is getting the end of the final verse, because the text content of each chapter is not organized into one big div, so I had to find where the site navigation began instead. Apart from that, it’s pretty straightforward.

After running reorganizeasxml.py, we have complete.xml. We can now run findallquestions.py, which is significantly simpler overall, and doesn’t even define any functions. It doesn’t need to because of how reorganizeasxml.py built the xml structure.

It starts out by finding every vs element that contains a question mark. Then it creates a csv file, creates a header line, and then dumps all of the information into that csv file, one line at a time. Bam. Done.

What this script does not do is identify the one asking or the one being asked. I think I’d have to use some AI/ML for that, and I’ve never done anything with that. For that reason, those columns are blank, to be filled in manually. (I don’t actually expect that that would ever be 100% completed.)

Well, there you go. There’s a case study in a one-off use of Python code to accomplish a task that would be a pain to do manually. It’s just one example of how coding can be useful in day-to-day things, whether you’re a developer or not.

Another example is something that I made using matplotlib when the Covid panic started. The only historical data Oklahoma gave us at the time was the the cumulative case count, but I had a friend that wanted a graph of the daily case count. Converting the raw data from cumulative to daily was easy, so I made a graph in matplotlib, then made a script to scrape the website and update the chart on Github. I then made a cron job on my laptop to update it daily. It was a fun project, but only lasted about a week before the Oklahoma health dept changed the format of the website so it stopped working. At that point, they started giving us the chart exactly as we wanted it anyway, so there wasn’t much point in fixing it.

The Bible questions scripts probably seem overwhelming to someone new to coding, but I can assure you that, given time, writing code becomes as natural as breathing. What’s hard today is easy tomorrow (which I keep telling myself while learning C++). I’ve learned that lesson repeatedly a million times.