Algorithmic Diversions

The Nature of Things / Martin Gardner from Wagner Brenner on Vimeo.

Almost 15 years ago I ran into a copy of Martin Gardner's "The Night Is Large" at a small used book store, in Oregon. This was a pivotal book for me. Both as an introduction to the complete Gardner, and personally as a life saver. I was going through a difficult period in my life, and in dire need of what has been called "consolation of philosophy." The book put me on a path to untangling dozens of previously intractable knots in my mind, for which I shall remain eternally indebted to the author.

So with tremendous sadness I mourn the loss of this great mind, this great teacher, the scrivener, the skeptic, the philosopher, the fringe watcher, the magician, the pied puzzler, the mathematician(*), and an all too brief personal acquaintance. Its been a month, since his passing into the night, on May 22, 2010. Born in 1914, that put him at almost 96 years of age (see mainstream media obituary announcements in London Times, NY Times, and Boing Boing). While mouring his death, this is also a time to celebrate his fruitful life. Just a few more individuals as tirelessley enriching to all as he was, and our world would blossom into a cognizant, sane, intellectually competent place it ought to be.

PS: I'd be interested in hearing from any Martin Gardner fans in Northern Virginia. I'd like to organize a rememberance gathering here.

(*) I despise the prefix 'amateur' that is often associated with him in this regard, and refuse to use it. The amount of work he did puts more PhD weilding, junk paper publishing, unteaching teachers, the so called 'professionals,' to shame than I care to name.

Its been a while since I have had any time to post anything on this blog. Not that I have time right now. It seems I am a constant rat-race marathon runner, and any kind of leisure, even of the educational variety, is unaffordable luxury. What that means is that this post isn't going to be as detailed as I would have liked it to be (which is probably how most of the future posts here will have to look like if I am going to be able to keep this blog alive at all).

So, here goes ...

A few weeks ago I ran into the puzzle below posted on the web somewhere. I don't remember the original link, but it turned out to be an applicant screening puzzle originating from the search engine company Nextag.

Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:

static long shuffles(int nCards,int iCut);

Please send the results of shuffles(1002, 101) along with your program ...

This is a perfect example of the kind of puzzles that fall into the category of Algoritmic Diversions. The sort of problems that are hard to solve by hand or analytically, and algorithmic solutions to which are difficult enough to make naive implementations inadmissible. For the best examples of such puzzles (which this is certainly one of), there are short and elegant solutions that trigger the "AHA!" response in people who have interest in such matters.

It seems the puzzle has been up for a while, and there are dozens of solutions posted all over the place. It had me going for a couple of days, at the end of which I came up with my own solution. I don't know if this is the best solution, it certainly seems more terse than some of the ones I have seen floating around. My spoiler is posted here (zip form, password is "crafty1255"), but I recommend that readers resist the temptation to look before coming up with their own solutions. I promise it will be a lot of fun. I'd love to see other solutions (not necessarily in Java), and will post the best and/or most interesting ones here. So get out your compilers, get set, ready, go ...

Finally, someone responded to my call. Jesper Gerved from Denmark has put up a bunch of Mike Mudge's articles from PCW on his site:

http://gerved.dk/nc/nc1983.pdf
http://gerved.dk/nc/nc1984.pdf
http://gerved.dk/nc/nc1985.pdf
http://gerved.dk/nc/nc1986.pdf
http://gerved.dk/nc/nc1987.pdf
http://gerved.dk/nc/nc1988.pdf
http://gerved.dk/nc/nc1989.pdf
http://gerved.dk/nc/nc1990.pdf
http://gerved.dk/nc/nc1991.pdf

Thanks Jesper!

Those who grew up in the 80s reading the British computer magazine Personal Computer World might recall a certain regular column titled Numbers Count, by Mike Mudge. It was my favorite part of the magazine, a very accessible Computational Number Theory puzzles column, the place where I first learned about integer partitions, perfect numbers, Smarandache functions and a host of other perplexing and entertaing notions from the Queen of mathematics. I have extremely fond memories of it. His articles created a permanent place in my heart for the theory of numbers, and 20 years later I am finding a nostalgic yearning for those sort of things.

Sadly my PCW collection is gathering mildew in an inaccessible basement a couple of oceans away, and libraries in USA do not carry the magazine. In fact I am yet to run into an American who knows what I am talking about. Information on Mike Mudge, what became of him, whether he is still alive or not, and whether he wrote anything else besides those columns, is difficult to come by. There are about half a dozen references to an article or two that he wrote besides the Numbers Count column, but that's about it.

I am really interested in seeing a separately bound collection of his Numbers Count columns, along the lines of Martin Gardner's compendiums of his Scientific American columns. If he is still alive, I would love to do an interview or exchange emails and letters. Failing all that I would like to see the columns scanned and collected on the internet, together with a biography and bibliography site. I am sure there are other fans out there who would be interested in this project.

So, if anyone has any information about Mike Mudge, his whereabouts, his contact info., his biography and bibliography, anything at all, please contact me. I am also interested in obtaining old copies of Personal Computer World (from before they went "modern,") either full volumes, or just the Numbers Count columns.