Zebra Puzzle – Design of Computer Programs


Oh, hey. We’re back. Welcome. Excuse me a sec. I was just sketching out a business plan on the back of this napkin. So I have an idea, then question mark, then profit. But you know, this just doesn’t work so well. These napkins are so porous the markers don’t work on them. I think I’m going to throw away this cliche and move to a different cliche: the back of the envelope. Much easier to write on the back of the envelope, and it’s a really valuable skill. It’s a valuable skill in real life to be able to do quick and dirty calculations, and it’s especially useful for computer programmers. It allows computer programmers to have the important virtue of being lazy. You don’t normally think of lazy as being a virtue, but it is. It allows us to say we’re going to come up with the simplest design we can, validate on the back of an envelope that that design is efficient enough for what we’re trying to do, and then we can stop. We don’t have to try to make it more complex. This whole class is about managing complexity, and one of the most important ways to manage complexity is to leave it out completely, just go for the simple solution. If we can do that, then we’re well on our way to better designs. In this class we’ll learn how to do that, we’ll learn how to do the calculations of when you’re efficient enough, we’ll learn when to stop, and we’ll learn how to make programs more efficient. I’m going to start with a well-known puzzle called the Zebra Puzzle. Here’s a description of it. We’re going to try to address this puzzle, see if we can come up with a program to solve it, and explore the methodology for how we come up with that solution and the process of deciding what’s a good enough solution and whether a brute force solution will work. You can read the description of the puzzle here. Now let’s start to analyze it. We’ll begin with an inventory of the concepts in the puzzle just to make sure that we understand what’s going on. The first concept is houses. We’re told there’s 5 of them. And then there’s properties of the inhabitants of these houses and of the houses themselves. So there’s nationality, colors of the houses, the pets that they own, the drinks that they drink, and the smokes that they smoke. And then in addition to properties, there’s a notion of assignment of properties to houses. And you can think of that either way. You can think of it as assigning house number 2 the color red or think of it as assigning red to house number 2. Then there’s a notion of locations, the locations 1 through 5 that mention the idea of the first house and the middle house and of the next to relation and of the immediately to the right relation. And I think that covers most of what was in the specification. Let’s go back to it and see if it works. So I’m seeing lots of concepts that we’ve already covered: 5 houses, Englishman, red house, Spaniard, dog. There’s a few words that we haven’t covered, things like lives in and owns the. We covered them in a generic sense of saying it’s an assignment of Englishman to a house and assignment of the dog to a house, but the question is, do we need to separate out the different types of assignment? So the question is, are we missing this idea of a property name with a description attached? So for example, the property name would be nationality and the description is lived in. Do we need to name them like that, or do we just need the notion of a property group to say that there are these properties of Englishman, Spaniard, Norwegian, Japanese, and Ukranian, and the 5 of them go together but we don’t need the name for them, or can we ignore this notion of grouping altogether? This is somewhat subjective–what’s a good design choice?– but tell me which of these 3 do you think are plausible or reasonable design choices and check all that apply.


2 Responses

Leave a Reply