Regularly Divisible
Update: read the comments at Hacker News to see some succinct approaches to this, as discussed by gjm11, qntm and patio11. Thanks to Robin for providing this demonstration that can find a regex for testing divisibility of any number, in any base (he also made the code available, nice).
Earlier this year, at the advice (once more) of Chad Fowler, I took to the idea of practicing programming every day. Perhaps this appealed to me because it echoed the rituals of my better musician friends, and allowed me to draw parallels between programming and my fading dream of becoming a famous rockstar.
Possibly because of my failed interview at Google (hey, I wouldn't have hired the back-then me either, so no hard feelings!), I was also interested in job-interview styled problems [1]. Not FizzBuzz though, more like the computer science 'riddles' found on this page [2].
At the time I was teaching Computing Theory [3], 80% of which was formal languages: regular expressions, context free and context sensitive grammars, Turing machines and other automata, and their locations in the Chomsky Hierarchy. So, this problem appealed to me:
Construct a finite state machine (or equivalently, write a regular expression) which accepts all strings over the alphabet {0,1} which are divisible by 3 when interpreted in binary.
It is pretty interesting that languages can be defined to communicate patterns in binary sequences that are divisible by 3. Let's solve it in more detail than necessary :)...
