Calculating when the 1000th XKCD will appear

Like so many geeks I’m a massive XKCD fan. But I’m often troubled by questions like when will the 1000th XKCD appear, or the 1024th or even the 2000th? Even though the first two numbers are getting quite close now, it’s still more fingers and toes than I have so working it out by hand is out. Fortunately we have computers to this kind of heavy lifting for us, and the solution in F# is kinda cute.

We need 3 pieces of information to be able to work out when any given XKCD will appear: an epoch date and number as well as the days that XKCD is published on. I chose todays date, 2nd September 2011 when XKCD 946 was published. I would have been nice to start with issue 1, but in the early days of XKCD it wasn’t published regularly so starting at the beginning would considerable complexity the task, and besides, we already know when numbers in the past were published. XKCD is published on Mondays, Wednesdays and Fridays, so here’s how we encode this information in F#:

open System

let epochNumber = 946
let epochDate = new DateTime(2011, 09, 2)
let xckdDays = Set.ofList [ DayOfWeek.Monday; DayOfWeek.Wednesday; DayOfWeek.Friday]

 

Now we can implement a function calculate the date of any XKCD after the epoch date. The algorithm is simple, we generate an infinite list dates, starting at the epoch date. Then we filter away any dates that don’t occur on XKCD days. The nth element in this list, taking into account the epoch number, will then be the date of the publication of that XKCD:

let getXkcdDate n =
    if n < epochNumber then failwithf "n was %i, it must be greater than the epoch number %i" n epochNumber
    let n = n - epochNumber
    Seq.initInfinite (fun i -> epochDate.AddDays(float i))
    |> Seq.filter (fun date -> date.DayOfWeek |> xckdDays.Contains)
    |> Seq.nth n

Then it’s just mater of calling the function with the value that interests us:

getXkcdDate 1000
//val it : DateTime = 06/01/2012 00:00:00
getXkcdDate 1024
//val it : DateTime = 02/03/2012 00:00:00
getXkcdDate 2000
//val it : DateTime = 28/05/2018 00:00:00

It’s also a nice demonstration of how functional programming allows us to decompose problems into simple steps, first the creation of an infinite list of dates, then filtering this list to find just the dats that XKCD is published, and finally picking the date which interests us. Yes this problem is simple enough we could have attempted to do it in one step, but the solution we have come up with is nice and simple and understandable.

With XKCD cartoons about lisp and python, I wonder if we’ll see one about F# or other ML style languages any time soon?

Edit: Fixed the error message for numbers less than the epoch number, thanks @jbevain!

Update: I suddenly remembered I could make it really easy for you try it in trysharp.org and tryfs.net by using fssnip.net. (Sorry if these updates are spamming your RSS feeds)

Bookmark
dotnetkicks+, digg+, reddit+, del.icio.us+, dzone+, facebook+

Print | posted @ Friday, September 02, 2011 10:12 PM

Comments on this entry:

No comments posted yet.

Your comment:

(Note: all comments are moderated so it may take sometime to appear)

Title:
Name:
Email:
Website:
 
Italic Underline Blockquote Hyperlink
 
 
Please add 6 and 7 and type the answer here: