(A case study in bad and good algorithm design.  Hopefully, a bit of fun for anyone in a programming frame of mind, but also serving as a useful reference for the ‘Are There Any Hard Problems?’ post that follows.)

In ‘A Scandal in Bohemia‘ (Arthur Conan Doyle, 1891), Holmes and Watson discuss the difference between seeing and observing:  “You see, but you do not observe [Watson]. The distinction is clear. For example, you have frequently seen the steps which lead up from the hall to this room.”  “Frequently.”  “How often?”  “Well, some hundreds of times.”  “Then how many are there?”  “How many? I don’t know.”  “Quite so! You have not observed. And yet you have seen. That is just my point. Now, I know that there are seventeen steps, because I have both seen and observed.”

Who knows; perhaps, if they hadn’t moved on to discuss more pressing issues (that King of Bohemia has a lot to answer for), Holmes may have set Watson something a little more interesting:  “How many of these steps do you generally take in a single stride, Watson?”  “I suppose one or two, Holmes, it varies; never three. Sometimes I take different combinations of one and two steps as the mood takes me”  “Excellent, Watson; another challenge! So, taking these steps one or two at a time, in any combination you wish, how many different ways are there of climbing the seventeen steps?”  “Well, I’m quite sure I don’t know, Holmes; rather a lot, I would imagine!” Continue reading