On Bicycles, and.... what else is there?

The prisoner's dilemma is a description of a problem where you have two suspects are captured, accused of committing a crime, and are isolated in separate cells. If either admits to the crime while the other does not, the prisoner admitting to the crime is set free, the other given the most severe punishment (10 years in prison). If they both confess, they are given a light, 2 year sentence. If neither confess, they are held in prison for one year, but eventually freed for lack of evidence. So if you're one of the prisoners, what do you do? If they could collaborate, then the best approach would be for neither to confess. They'd esch serve a year in prison, which isn't great, but overall they'd serve only two years. That's much better than the alternates. But they're isolated, so they can't collaborate. For each prisoner, what the other prisoner does is beyond their control. If the other prisoner confesses, then he is better off confessing as ...

On only page 18 of Flanagan and Matsumoto's excellent "The Ruby Programming Language" a relatively complex example is presented: a Sudoku puzzle solver. I've had a decades-long interest in maze solvers, and this tied in nicely with that. I resolved to give the code a close look when I'd finished the book. And surprising myself, I soon did. I read it cover-to-cover, frequently even re-reading sections I'd already covered when a lack of mastery of specific material became evident later. The language is a nice alternative to Perl, which had been my scripting language of choice since 1998. Ruby has a lot of cool characteristics, even if it sometimes falls weakness to Perl's desire to appease too much diversity in coding styles. I personally think being able to do things effectively two different ways is inferior to being able to do things as effectively only one, as the latter makes multi-author code easier to follow and coherently maintain. But as usu...

As I was flying back home from Newark Airport yesterday I was bored.... the movies were of no interest, I'd forgotten to bring a book, and the battery on my ThinkPad T60 lasts only 25 minutes. Not even enough to get past the Wikipedia page on Henri Desgrange, which was cached there, let alone amuse myself by working on my code for 4-dimensional mazes, which I'd planned to do. Okay -- backup. I pulled out my HTC smart phone. At least I could review the photos I'd taken of my cousin's wedding. Sorry -- battery dead. So I was stuck reading the copy of Technology Review in my backpack. Nothing wrong with Technology Review, it's an excellent magazine. But it's nice to get away from thinking about technology too often. I think this is one reason engineers are so attracted to cycling. Bikes are so amazingly elegant in their simplicity. Technology's review theme was the top 10 emerging technologies of the year. There among those listed was solid sta...

Back to the boat puzzle... I freely admit this is perhaps among the most boring topics ever posted to a blog in this history of the Intenet. But I feel the irrational need to put some sort of closure on this. I proposed that all solutions to the arbitrary boat puzzle could be reduced to the simple example of Mac-Nadia-Flannel. It was first proposed to me that if there is at least one member not a part of a maximal independent set incompatible with no more than two members of the maximal independent set, the problem can always be solved. This is true: just leave everyone else on the boat and solve the simple Mac-Nadia-Flannel-cans problem with the one remaining seat. But there's a more general approach, in which each elemnt of the "Mac-Nadia-Flannel-cans" puzzle is represented by a group rather than an individual. First, identify which animals which are going to go across on the first trip (the rest are a maximal independent set). Then bring the rest across. T...

Previously I described the boat puzzle and how it's provided some mental exercise for my train commutes. The traditional example is the Mac-Flannel-Nadia case: The solution, as I described, is to identify a maximum independent set, in this case Mac and Nadia. Then you need a number of seats on the boats sufficient to transport the rest, in this case Flannel. So: 1. Flannel taken from shore A to shore B. 2. return with empty boat. Next step doesn't matter, as Mac and Nadia are identical in this problem. I'll pick Mac: 3. Mac taken from shore A to shore B. Now Mac and Flannel are together. I need to return with Flannel on the boat, as I cannot leave the two, or Mac will turd. 4. Flannel taken from shore B to shore A (leave Mac on B). But then.... 5. Take Nadia from A to B (leave Flannel alone). Nadia is now with Mac, and they lick each others faces, so that's fine. 6. Return with empty boat. 7. Bring Flannel from A to B. When I add in the can...

I'll now continue my discussion of the boat puzzle in which the goal is to get cats across a river in a boat, where there are fewer seats on the boat than cats, and certain cats must not be left with each other unsupervised. For the first trip across the goal is simple: to leave no two incompatible cats back on the first short. For example, consider the following problem, with cats Mac, Nadia, and Flannel, where I spiced it up slightly with the requirement to also transport a supply of cat food cans: I want to find a group which has no mutual connections to leave back on the shore. Ideally, my boat should require no more seats than the number of cats + objects to be transported in that first trip. Thus I want this group without mutual connections to be as large as possible. The largest group without connections is called the maximal independent set . Here is the maximal independent set for the graph shown above: The only element not in the maximal independent set is...

Another puzzle... actually I spent quite a few train commutes thinking about this one. There's a classic puzzle where a farmer needs to get a fox, a sheep, and a cabbage across a river on a boat. I don't have much experience with transporting fox or sheep, and cabbage aren't very exciting, so I'll recast the problem in terms of cats. Consider I want to transport three cats across a river on a boat. I can watch over the cats while they're on the boat, but when they're on one shore or the other, they need to get along. The names of the three cats are Mac, Flannel, and Nadia. If I can watch them they're fine, but if Nadia is left unsupervised with Flannel, Flannel will harrass Nadia. who needs her rest. And if Flannel is left unsupervised with Mac, Mac will turd, so we need to be careful not to let that happen. On the other hand, if Mac and Nada are left with each other, they'll just lick each others faces, so that's fine. The challenge is...

Previously I described a puzzle of prisoners and hats. Each of 100 prisoners had a 50-50 chance to pick his number from his 50 picks from hats. For any prisoner to survive (puzzles tend to be violent; it's true), every one of the 100 prisoners needed to succeed with his 50-50 chance. Simple probability says the chance of the prisoners surviving is essentially zero: you can't flip a fair coin 100 times and get heads every time. The key, it turns out, is to use a rigged coin.... Go to that link now if you don't want to see a really big hint. Move below the cute kitten photos to proceed... Okay, enough of that. Here's that big hint. For simplicity, I'll assume 8 (not 100) prisoners and 4 (not 50) hats. I show two sequences: one which wins, the other which loses. The winning sequence: 4, 6, 3, 0, 2, 1, 5, 7 The losing sequence: 4, 2, 3, 0, 1, 6, 5, 7 These sequences are permutations: various orderings of the same elements. The key insig...

"I have a puzzle for you" my fellow passenger asked.... I was riding on the last northbound Caltrain baby bullet train out of Mountain View at 6:38 pm, the one I've been taking pretty much every day since starting my new job last October. If I leave any later, I start paying the price of riding trains which make more stops, get me home even later. This is the latest train I can take and have time to eat dinner, relax a bit, and get a solid night's sleep before catching the 6:11 am southbound the next morning. Long days, sure, but I'm having fun. "A jailer has too many prisoners in his prison and needs to get rid of 100. So he gathers 100 prisoners in a room. In an adjacent room he puts 100 hats, each hat containing one of the names of the prisoners, in random order. One by one, prisoners are brought into the room with the hats where they can pick from up to 50 hats (half) to find their name. If they find their name in those 50 picks, they leave thro...