Singing with Loops

Loops are programming constructs for repeating a set of instructions until a given termination a criterion is met.

Ann cheered at the sight of the brightly lit inn. A sign by the door read, “One night only! The world famous bard Larry de Loop!” After another full day of walking, she felt tired and seemed no closer to finishing her quest. But, at least, she’d found a place to rest. And some cheerful music might help take her mind off her quest.

Ann chose a small table by the stage. After ordering a bowl of Surprise Stew, regrettably the only item on the menu, she settled in for the show.

Though unable to play even a basic tune on his accordion, Larry de Loop was the most enthusiastic bard Ann had seen. He belted out three simple songs, then asked for requests.

“The Ballad of Lady Algorithm,” called Ann, wanting to hear the tale of her favorite adventurer.

Larry looked surprised. “I’m sorry miss. I only sing songs in loop form.”

“Loop form?” Ann asked. “I’ve never heard of that style of music.”

“It’s quite popular in the North. The songs have to use either FOR loops or WHILE loops. Loops are constructs for repeating things until some conditions are met.”

“What?” asked Ann. Naturally she was familiar with the concept of loops. They were a basic building block of algorithms. She used loops in archery (while you have arrows, shoot at the target), cooking (stir for two minutes), counting coins (for each coin, add its value to the total), and even walking (while I’m not there yet, take another step). But she’d never heard of loop-based music.

“I mostly sing in FOR loops,” explained Larry. “A FOR loop iterates over a set number of things. 99 Bottles of Beer on the Wall uses a FOR loop. FOR each number of bottles from 99 down to 1, sing a verse. Or perhaps you’ve heard of old McDonald’s Farm? FOR each animal on the farm, sing about the cute noises it makes. Or—“

“Aren’t those songs all quite repetitive?” Ann interrupted. Of course, repetition was precisely the function of a loop.

Larry smiled broadly. “That’s why I also use a WHILE loop. WHILE loops repeat a set of actions until a condition is met. In my case I always use the same loop: WHILE no one has thrown a tomato at me, keep singing. So once the first tomato is thrown, I know it's time to stop.”

Variables, IF statements, and Magic Boots

A variable represents a location in the computer’s memory where you can store a single piece of data. You can use the variable’s name to look up, set, or modify the value stored in that location.

Ann jolted in surprise as a loud tone cut through the silence. She quickly tapped her boots together, resetting them before they could blare their pre-recorded message. She mumbled a few insults at her footwear. Did they have to alert her after every mile?

Ann realized this was the eighth warning chime today. Had she walked eight miles already? She’d been so lost in her thoughts, that she hadn’t been paying much attention to the journey itself. She was now three days into her quest to save the kingdom and she still had no idea what to do. Why couldn’t the seers have been more specific than, “There is a darkness coming. Princess Ann must travel forth alone to save the kingdom.” Maybe they could have told her what the darkness was or, at least, hinted at which direction to travel. Stupid vague prophecies.

Ann looked down at her boots and debated for the hundredth time whether they were worth the annoyance. The boots had been a birthday gift from Marcus, the royal wizard. They represented his first foray into variable magic—a form of magic that allowed an object to store a single piece of information. In this case, her boots’ variable (helpfully called dist) stored the distance she traveled. After each step, dist increased by the length of the step.

dist = dist + step_length

Initially the boots had provided wonderful entertainment. Ann measured everything. She measured the length and width of her room, the distance to the kitchen, the distance to all ten of the castle’s bathrooms, the circumference of the castle wall, and the diameter of Fido’s turtle pond (the boots were, of course, water proof). She’d even annoyed the castle architect by noting the courtyard was six inches shorter than advertised.

After every trip she’d read the variable’s value from her left heel. Then she’d click the heels together to set the distance back to zero.

IF heels clicked: set dist = 0

If she also used her watch to track the time, she could even compute her speed:

Average speed = dist / time

Variable magic provides such wonderful power.

Unfortunately, Marcus had gone overboard. In addition to the variable itself, he added his own IF-statement based enhancements. After walking a mile the boots would loudly recommend that she take a break:

IF dist > 1 mile: Alert the wearer to take a break

The message, which sounded like the castle herald with hiccups, grated on her nerves. Worse, Marcus hadn’t properly thought through the details of his IF statement. The statement only checked if dist was greater than a mile. So once she’d walked a mile, the boots would “helpfully” alert her to this fact after every single step. Ann quickly learned to reset the distance to zero the moment she heard the chime.

With a sigh, Ann decided to leave on the boots. While they were extremely annoying, at least they tracked useful information. Marcus had once confided that his original design enabled the boots to track their smelliness. She shuddered as she considered what that alert might say.

-------------

There are now three books out in the Computational Fairy Tales universe!  See the books page for more information.

Encodings for Tic-Tac-Toe

Peter hurried back to the Library of Alexandria, the message clutched tightly in his fist. He resisted the urge to study the parchment, reading it again wouldn’t help. The message was obviously some form of code, and he had memorized the whole thing in his first glance. The entire message read “23G.” Although he didn’t know what those few characters meant, Peter was certain they were important.

“You received a message,” he called out the moment he entered the library. Half a dozen startled patrons glared at him from their tables. Flushing with embarrassment at his outburst, Peter quietly strode to the main circulation desk.

“You have a message,” he whispered to the head librarian, holding out the parchment.

The elder librarian took the message and read it carefully. After a moment he nodded a few times, saying only, “Interesting.”

“What is it? It is it important?” Peter asked impatiently.

The librarian looked surprised. “What gave you that impression?”

“It’s a code, isn’t it?” answered Peter. “And it came through the wizard’s telegraph office, which must mean it’s important.”

The librarian chuckled softly before explaining, “It’s a move in a game called Tic-Tac-Toe. I’ve been playing with the librarian from G’Raph. She’s quite skilled at strategy.”

“What?”

“Tic-Tac-Toe. It’s a simple game, but most enjoyable,” started the librarian. “It’s a two player game that is played on a three by three grid, where—”

“I know what Tic-Tac-Toe is,” cut in Peter. “But how does ‘23G’ represent a move in Tic-Tac-Toe?”

“Ah. I see where you’re confused. We had to invent an encoding scheme that allows us to play over pigeon message or magical telegraph. It’s really quite a simple scheme. The first number represents the row, the second number represents the column, and the last letter indicates who made the move. We need that last one so we can play different games against other librarians. I’m currently winning two of my three games.” As he spoke, he pulled a few pieces of parchment from under the desk. On the one labeled G’Raph, he carefully marked an X in the third column of the second row.

“But why three letters? Why not just draw out the whole board and pass that back and forth?”

The librarian smiled. “Our encoding makes for a convenient abstraction. We can send those letters by pigeon message, magical telegraph, or even by magical mirrors without needing to change the encoding. Each of those communication mediums uses its own underlying encoding to transmit letters. Pigeon messages rely on written letters, which are really just lines of ink on parchment. The magical telegraph uses a new form of dots and dashes to encode each letter. I have no idea what encoding the magical mirrors use. I think it has something to do with pastel colors. But it doesn’t matter. Regardless of the underlying encoding used to store and transmit the message, we only need to worry about encoding it as letters.”

“You go through all of that for a game of tic-tac-toe?” asked Peter.

“Tic-Tac-Toe is more than just a game,” said the librarian. “It is the ultimate test of strategy. It is a window into a person’s inner-most thinking.”

Peter stared at him in disbelief.

“Now if you’ll excuse me,” continued the librarian, “I have to plan my next move.”

Three days later Peter stumbled into the library, looking as though he hadn’t slept in about three days. He walked up to the main counter and stood there silently, beaming at the librarian.

“Are you okay?” asked the librarian.

“I did it!” Peter practically shouted with glee.

“Did what?” asked the librarian, now thoroughly worried.

Peter’s smile grew even wider. “I created a new encoding for the library!” He waited for the librarian’s gasp of excitement. When the librarian’s face remained blank, Peter added, “An encoding… like for your game of tic-tac-toe.”

“I see. And what’s it for?” asked the librarian.

“Books and scrolls!” Peter opened his arms expansively to indicate the contents of the library.

The librarian considered this for a moment. Carefully he said, “We have an encoding system for books and scrolls. It’s called letters. You use them to form words and… you know, encode knowledge.”

“No. I don’t mean for the content of the scrolls. I mean for the topics,” Peter explained. “I have developed a new system that gives each subject a unique code of three numbers in the range 0 to 255 that represent the category, subcategory, and specialization. So we can encode the contents of any scroll, book, or loose parchment with a three number code.”

“Consider this scroll,” Peter continued, picking a scroll from the return bin. “The subject code is 192.168.1, which translates to the communication category (192), the networking subcategory (168), and the specialization of pigeon networks (1).

“And, like your Tic-Tac-Toe encoding, the subject encoding can be transmitted easily. We can share the encoding with other libraries and use it to request resources. If I wanted a book on ancient history (category 0), of the kingdom (subcategory 0), and the development of new eating utensils (specialty 10), I could send a pigeon message to a library in G’Raph simply stating ‘Request: 0.0.10. Alexandria.’ You see?”

The librarian thought about the scheme for a minute. “I suppose it could work,” he admitted. “But it’s no where near as exciting as exchanging moves in a game like Tic-Tac-Toe. Leave it to you to make encodings so… practical.”

--------------------------

Thank you to Caroline Meeks for suggesting the topic of encodings.

Interested in lower level codings? Learn about binary with Unhappy Flowers and Binary or Using Binary to Warn of Snow Beasts.

Best Practices of Spell Design

The Best Practices of Spell Design book is available! The second book in the Computational Fairy Tales universe introduces the programing and software engineering best practices.

In all his years as a wizard, Marcus has never seen a spell cause this much damage. When Hannaldous's sloppy attempt at a shield spell accidentally curses the castle, the walls start crumbling at an alarming rate. Now Marcus and his apprentice Shelly must figure out how to repair the damage before the castle turns to dust. Along the way they will encounter gossiping worms, perfectionist bakers, opportunistic rabbits, and copious amounts of mold.

The Best Practices of Spell Design introduces practical aspects of software development that are often learned through painful experience. Through Marcus and Shelly’s quest, the story encourages readers to think about how to write readable, well-tested and maintainable programs. Readers will discover the importance of comments in recipes, the value of testing potions, the dangers of poorly named ingredients, the wonders of code reviews in magic libraries, and the perils of premature optimization.

For more information, including links to online stores, visit the books page. Or

• Buy the print version at Amazon
• Buy the print version at Create Space
• Buy on the Kindle
• Buy the ePub on Lulu

Nook, iBooks, and Google Play coming soon.


FAQs:
Q: Is this a print copy of your blog? Why should I buy the book?
A: Best Practices of Spell Design consists of almost all new content. A few related blog posts have been included (after significant professional editing).

Q: Is the format of Best Practices in Spell Design the same as Computational Fairy Tales?
A:The format is similar, but not identical. Instead of individual stories with introductory technical blurbs, Best Practices of Spell design is written as a novella. Each chapter of the story introduces, explains, or reinforces a concept.

Q: What is the target audience for this book?
A: Best Practices of Spell Design is written for people who are just starting to program or have some programming experience. The book does not teach programming, but rather reinforces important programming best practices that are often learned through (painful) experience.

Also see Who is the Target Audience? for more details on the audience for Computational Fairy Tales stories.

Who is the target audience?

I have seen the questions of "Who is the target audience for these fairy tales?" and "How can they teach computer science?" come up a few times. Most recently, this was asked by an reviewer of the book.

To be honest, these are questions that I asked myself many times when I was starting.

Below I outline some of the thought process behind the stories, the book, and how they can be used.

Computational Fairy Tales is not a textbook:

I contemplated using the stories to frame a full introductory textbook. But there are a lot of good textbooks out there already. Honestly, I have always seen these stories as supplementing a class or standard textbook. The stories are designed to motivate topics, provide context, and (hopefully) generate interest. The best parallel that I can draw is that each story is meant to serve the same role as an illustration in a textbook; it provides a different way of viewing the problem.

Motivating computational thinking:

The goal of Computational Fairy Tales is not to provide comprehensive coverage of each topic, but rather to provide a high level overview of the breadth and excitement of computer science. Ideally the stories inspire that reaction of "That's interesting…" or "I had not thought about it that way…", followed by a desire to learn more. In rare cases, there might even be laughing involved.

Using Computational Fairy Tales in a class:

Last week, I had the pleasure of talking to a group of high school teachers at CS4HS about Computational Fairy Tales and how they could be used in classes. I proposed using the stories as motivation during the discussion of the material:

1. Introduce the concept.
2. Use the story to motivate it or put a new spin on it.
3. Go into more details, possibly involving real code or formal proofs.
4. Assign copious amounts of homework on the topic.

A few of the teachers suggested swapping 1 and 2, assigning the stories to be read the night before as homework. I have seen some of the stories used this way in courses already.

Suggestions? Comments?

I am very interested in learning more about how people use these stories or would like to use them. Please feel free to contact me with questions, suggestions, requests, or comments.

Book (and FAQs)

The Computational Fairy Tales book is available (in print and on the Kindle). More details can be found at the book page, including links to the various stores.

The Computational Fairy Tales book includes ~30 rewritten or revised stories from the online collection and 15 all new chapters. Each story serves to illustrate a computational concept, supplementing official instruction or motivating computer science concepts. The stories have also be set up to provide a natural progression both within the computer science concepts and within the fairy tale quest.

Go to the book page.

A few FAQs:

Q: Is this a print copy of your blog? Why should I buy the book?

A: There are a few significant changes. First, there are fifteen new chapters. Second, the book covers the full tale of Ann's quest to save the kingdom from the darkness. The stories are set up to provide a natural progression both within the computer science concepts and within the fairy tale quest. Third, the stories have been rewritten and edited by a professional editor.

Q: What is the target audience for this book?

A: It is primarily written for junior high to high school students who are interested in computer science (and their teachers). However earlier versions were read and enjoyed by younger readers. It can also be amusing for people who know about computer science, but want to read about it in a different light.

Q: My favorite story is not there! What's the deal?

A: Not all stories fit into the book. In fact, less than half the online stories were used. Some were redundant and some just didn't fit.

Q: Does this mean that the online collection is going away?

A: No. I want these stories to continue to be useful. I plan to leave the current collection of stories online. However, I do not plan on updating them all (I have updated a few). So think of the online versions as very rough first drafts of the final stories.

The Importance of Design in Five Course Meals

For any moderately complex program or algorithm, it often helps to design the solution before work begins. Good design practices can save a significant amount of time, help avoid wasting effort, and prevent mistakes.

"I can fix this," Chef Pepperton said to himself as he rummaged through a box of fresh vegetables.  "I just need some radishes."

Behind him, the kitchen was in chaos.  The other cooks dashed about, trying to prepare the remainder of a five course meal.  The soup had just been carried out, and the other four courses were far from ready.  In fact, they were not exactly decided yet.

"Radishes?!?" screamed Chef Pepperton.  "Do we have any radishes?"

One of the other chefs paused for a moment in thought.  "No," he said.

Pepperton turned back to the box.  "I can fix this," he mumbled. "Carrots.  I can do it with carrots."

Then he loudly announced, "We are changing the menu to carrot ravioli.  CARROT RAVIOLI."

In the back corner of the kitchen the dessert chef groaned.  Since Chef Pepperton had now claimed the carrots, the dessert chef scratched his plans for carrot cake and started working on a chocolate pudding.  He hated when Pepperton changed his mind halfway through a meal.

"How is the appetizer coming?" Pepperton asked.

"A little burnt, but we can peel off the worst bits," answered his assistant.

Pepperton looked at the stove top.  Three pots and two pans occupied the stove's five burners.  Delicious aromas crept from two of the pots and a beautiful sauce simmered in one of the pans.  In the other pan, the cooked tomatoes for the appetizer sent up curly wisps of black smoke.  The final pot contained boiling water, but Pepperton could no longer remember what he had meant to boil.

Pepperton cursed under his breadth.  He thought for a moment, surveying the countertop for inspiration.  Then he replied, "Add some lime juice and call it something festive."

An hour ago he had felt a lot better about this meal -- confident even.  "I can whip up a five course meal for his majesty," he had boasted.  "I'm sure we have everything we need in the kitchen."

"If we do ravioli, we need another burner," noted his assistant. "Something else will have to come off."

Pepperton looked at the stove.  He counted the burners to confirm the problem.  Even if they took off the now charring tomatoes, they were one burner short.  He racked his brain and scanned the kitchen.  He again saw the mysterious pot of boiling water.

"Forget the mashed potatoes," he said, his memory kicking in. "Throw the potatoes in the fire for two minutes and call them charred potatoes.  Say they go with the tomatoes.  We'll use the boiling water for the ravioli."

"I need the fire for the salad," protested the assistant.

"Make it a cold salad," ordered Pepperton.  "And where is the salt?"

"Over here," called the dessert chef.

Pepperton dashed over to retrieve the salt.  "Curse the king's surprise visit," he thought.  Then he quickly amended his internal commentary to include a statement on how nice it was that the king had chosen this dining establishment. You could never be too careful.

"And the radishes?" asked Pepperton.

"You switched to carrots," reminded the assistant.

"Hold on a second," said Pepperton. "I think I might need to write this down."

An unnatural hush fell through the kitchen. It was worse than if someone had screamed it out loud.  Pepperton knew what everyone was thinking.  He could hear his own boastful words echo through his head, "We don't need any planning. We've done this a hundred times. We'll just put something together."  He shook his head to clear away the doubts and tried to concentrate on saving the meal.

He was halfway through finally writing down a menu when his assistant interrupted him. "Chef, your carrots are burning."

Pepperton groaned and crossed "Carrot Ravioli" off his menu.

--------------------------

Want to read more about programming and kitchens?  See Variable Initialization in Busy Kitchens or Computer Memory and Making Dinner.

Book update: The second draft of the book is complete.  It includes 30 revised stories and 15 new stories.  Story list coming soon.

Enums and Hair Colors

Enums, or enumerated types, are data types that can take on a fixed set of values. The elements in the enumerated set are named, allowing programmers to reference specific elements in an understandable form. These data types allow stricter checking (elements must be one of a limited set) and improved code readability (actual names are used).

"It is blue!" wailed a lady three chairs over.

Angela snuck a glance. Sure enough, the woman's hair was a vibrant, electric blue. Angela turned her attention back to the head in front of her.

"I… I…" stammered Derek. He stood behind the blue-haired woman. His face registered a mixture of shock and fear.

"It is supposed to be blond," screamed the lady. "But it is blue!"

"I know," said Derek. "It is just that… I thought… Umm... let me go check something."

Angela heard Derek rush toward the supply room. Knowing the seriousness of the problem, Angela paused, excused herself, and followed Derek. It was only Derek's first week; he could probably use some help.

Angela found Derek in the supply room staring at a shelf full of dye bottles. The salon's owner Karen stood next to him gesturing angrily.

"I picked the wrong bottle," moaned Derek. "I thought blond was bottle #14, but it was #15. Oh no! What am I going to do?"

"It is not his fault," interjected Angela. After a brief pause she added, "Well, technically it IS his fault. But this system makes it easy to make mistakes."

Karen spun toward Angela, anger in her eyes. "Not this again! I have used this system for ten years. Everyone who works here learns it."

Feeling protective of Derek, Angela pressed on. "It is a bad system. You have 20 different hair dyes in numbered bottles. In order to find the correct dye, you need to either remember or look up the correct 'magic number' for that color. It is too easy to make a mistake."

Karen waved dismissively. "What would you suggest?" she asked. "We already implemented a bunch of your ideas, and they always seem to add overhead. Just last month, we started unit testing the hair dryers. What now?"

Angela noticed the Karen had omitted the fact that the ideas also prevented errors. She decided not to press the point.

"Enums," answered Angela.

"Enums?" asked Derek.

Karen squinted in confusion as if wracking her brain.

"An enumerated type is basically a set of NAMED elements. You refer to an element in the set using its name, instead of some magic number. For example, in this case we could create an enumerated type for hair dyes. It would contain items like BLOND, DIRTY_BLOND, PLATINUM_BLOND, SUNSET_RED, and so forth. Then, to find the correct color, you give the name of the type."

"We tried that," said Karen. "Remember, the stock person could never remember how to spell 'blond'. The bottles were labeled 'blund' or 'bloond'. That is why we started using numbers."

"Enums give the best of both worlds," Angela assured her. "Like the numeric options, you have a limited set of options. And, like the free text labels, you have descriptive names. No more spelling errors. No more memorizing magic numbers."

Karen was silent for a moment. "What will it cost me?" she asked.

From outside they heard a loud, tearful scream. "Blue!!!"

Angela shrugged. "I guess that it will take longer to write the color code on the form, since the name will be longer than a number."

"BLUE!!!" came another scream.

"I think it might be worth it though," Angela added.

-------------------------------

Thank you to David Karl for recommending the topic of enumerated types!

Want to learn more about practical programming tips? Read about the importance of: variable initialization, unit testing, source control, comments, or data validation.

Classes, Inheritance, and the Three Little Pigs

In object oriented programing, inheritance refers to the ability to create derived classes (or subclasses) of a class. These derived classes can reuse attributes or code defined in the original (or base) class. The subclasses can inherit the attributes and methods from their base class. In addition, these new classes can also contain code that is specific to the new class itself.

Once upon a time, three little pigs decided to leave home and venture out into the world. They traveled together for a few days until they came upon a charming village nestled within a large forest. Immediately taken with the beauty of the village, the pigs decided to settle there.

Each pig found an open plot of land and began setting up his new home. The first order of business was to build a house. The pigs, knowledgable in both architecture and object oriented programming, each created houses based on the common House class. The House class specified the basic attributes, such as NumberOfWindows, and functionality, such as HeatHouse, that people had come to expect in a house. However, each pig chose a unique subclass to suit his own needs.

The youngest pig decided create a house from the StrawHouse subclass. Many people have argued that this was done out of laziness, as the Build operation for StrawHouse houses requires little work. However, the truth is that the pig had always marveled at the concept of thatched roofs, and the possibility of creating an entire thatched house was exciting.

The middle pig decided to create a house from the WoodHouse subclass. Again the reason went beyond the cost of the Build operation. The second pig preferred the rustic look of wooden houses. Moreover, wooden houses had a nice HangPictureWithNail function that appealed to the pig.

The oldest pig was obsessed with safety. He built his house from the SecureBrickHouse subclass, paying a large upfront cost. He slept better at night knowing that his house provided unique functionality of LatchDeadbolt.

Then, one night, a big bad wolf wandered into the village. He spotted the first pig's house and hungrily eyed its inhabitant. He walked up to the straw house's door and pounded. Of course, knocking on the door was a function that could be applied to any house subclass.

"Little pig, let me in. Or I will huff and puff and blow your house in." threatened the wolf.

"Not by the hair on my chinny chin chin." responded the pig. Despite his bold words, he was worried. He knew that his house had a very poor response to WithstandWind. He very much doubted that his house could handle the breadth of a asthmatic turtle, let alone the wolf.

Fortunately for the pig, the wolf was unaware that houses in the StrawHouse class lacked a LockDoor function. That oversight gave the pig some time. As he heard the wolf begin to huff, the little pig made a small opening in the back of the house and ran for it.

The wolf was in the middle of his first puff when he saw the pig running. He grinned wickedly and gave chase.

The little pig reached his brother's wooden house mere seconds before the wolf. He slammed the door behind him and flipped the lock. His brother looked up from a newspaper.

"Wolf… huff… puff…" was all the first pig could get out between his own heavy breadths. It had been a long run uphill.

Outside the wolf surveyed the house. The construction of this house was more solid, but he was confident that he could still blow it down. And now there were two tasty pigs inside.

"Little pigs, let me in. Or I will huff and puff and blow your house in." threatened the wolf.

"Not by the hair on our chinny chin chins." responded both pigs in unison. Then they looked at each other and darted toward the back of the house. They knew that the house did not stand a chance.

The wolf, seeing the pigs darting out of the house, again gave chase. This time the two little pigs headed to the house of their older brother. It was a long run, but they knew his SecureBrickHouse could withstand a lot of huffing and puffing.

They made it to their brother's house before the wolf. Their brother was in his yard, digging a deep moat. Although he knew that a moat was unnecessary in this neighborhood, it would help him sleep better at night.

"Brother… wolf… huffing…" the two new arrivals panted.

The brother looked up and saw the approaching wolf. The three little pigs dashed into the house, threw the deadbolt, and closed the windows.

"I told you that the cost of the SecureBrickHouse would pay off," started the oldest pig in a lecturing tone. In his view, nobody ever paid enough attention to safety.

"Sure," responded the middle pig. "It is great for cases like this. But your house has a terrible implementation of RetainHeat. Do you remember how cold you were last winter? You had to borrow two quilts."

"And the way sound echoes in here is annoying," added the youngest pig. "Have you ever considered putting up some drywall?"

Outside the wolf reissued his threat. He received no answer. The occupants of the house were too busy arguing the relative merits of the different types of houses.

"At least we can all now agree that building a House was a better idea than building a ApartmentBuilding, right?" offered the oldest pig with a quick glance toward the middle brother. "I could never deal with tenants complaints all day. We got the base class correct."

The other brothers nodded in agreement.

Outside they could hear the faint sounds of rushing wind and a hyperventilating wolf.

"Could we create a new SecureWoodHouse?" asked the middle brother. He liked the warm feeling of wood paneling.

The other two pigs paused in deep thought. "Would we derive it from the WoodHouse?" asked the oldest brother.

"Of course," responded the middle brother, "But we could change the implementation of some of the key functions to make it more suitable to this kind of attack. Maybe add some support beams along the walls. And a LatchDeadbolt function, of course."

"Interesting…" said the oldest brother as he thought over the proposal. "What other functions are you thinking about? How about ShutterWindows?"

Outside the wolf had huffed and puffed until he had passed out.

--------------

Interested in learning more about object oriented programming? Read about it Marcus's visit to a cheese factory (Objects, Classes, and Inheritance).

Interested in computational takes on other classic fairy tales? Read Binary Searching for Cinderella or Goldilocks and the Boolean Bears.

On a random note, this is the 75th actual story on Computational Fairy Tales. Have a favorite story or found one that works? Have a request? Let me know at computationaltales@gmail.com. For updates follow @CompFairyTales on twitter.

Using Binary to Warn of Snow Beasts

Binary is a number system where each digit can only take one of two values: zero or one. Binary is used within computers, because it allows the computer to encode information in a series of switches that are either on (1) or off (0). Each digit of binary represents a power of two. The first (right-most) digit represents the 1's place, the second digit represents the 2's place, the third represents the 4's place, and so forth. For example, the binary number 10110 = 1*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 0*2^0 = 22 in decimal.

The outpost of Iceton stood on the northern edge of the kingdom. It was little more than a scrawny barracks surrounded by a short fence and miles of tundra. Snow fell during most of the year, except in the winter months when it was too cold for snow. Few soldiers were stationed there by choice.

Despite the outpost's persistent recruiting problems, it was absolutely vital to the safety of the kingdom. North of Iceton roamed dangerous snow beasts. The beasts resembled elephant-sized polar bears with sharp antlers. They had nasty tempers and a particular fondness for attacking the kingdom's outposts. Iceton watched for these incoming threats and warned the cities to the south.

Since few pigeon messengers could survive Iceton's wintery conditions, giant fires signaled any impending danger. A fire atop one of Iceton's large signal towers indicated an incoming snow beast. The lack of a fire indicated the comparative safety of frostbite, hypothermia, and tundra goblins. Iceton's neighbor to the south, Garroow, watched for signals of trouble from Iceton and relayed the warning further south.

One day, a Garroow guard noticed a troubling sight: two fires burning on the Iceton signal tower. Being that Garrow's entire platoon was new to the outpost, no one knew what two fires meant. After much discussion, Garroow's commander dispatched a rider to investigate. The unlucky soldier, Mavis Yates, arrived at Iceton a few hours later.

"What news do you bring us from Garroow?" asked Iceton's commander with a note of worry.

"I came to investigate the fires," answered Mavis. "What do they mean?"

Commander Dorn looked confused. "They mean the same thing they always have -- snow beasts are heading toward Garroow."

"Why are there two of them?" asked Mavis.

"There are two snow beasts," answered the commander as though the answer was obvious; which, in retrospect, it was.

Moreover, this confirmation was certainly not worth a two hour trek through the tundra. Mavis, desperately wishing to avoid any future journeys to Iceton, decided to clarify. "And three fires would mean three snow beasts?"

"Well…" stalled the commander, "Three or more. We only have space for three signal fires. If you see three fires, you will have to come investigation. There could be five snow beasts heading in your direction."

Mavis had no intention of repeating this journey. Especially not if there were three or more snow beasts heading toward her.

"Oh, no." Mavis protested. "There has to be a better way."

Commander Dorn shook his head. "I assure you that this is how we have communicated for the last ten years. It is quite effective. We only see packs of more than two snow beasts a few times a year."

Mavis shivered involuntarily. "We can do better with three fires. Why not use binary?"

"Binary?" asked the commander.

"Binary," confirmed Mavis. "Each signal fire can indicate a power of two."

"Power of two?

"From East to West they will represent powers of 0, 1, and 2. That is 2^0=1, then 2^1=2, and then 2^2=4. We can encode a lot more information that way."

"That will only tell you that there are 1, 2, or 4 snow beasts coming. How does that help?" protested the commander.

"You add the digits that have fires," explained Mavis. "Let's say the first and last fires are lit. That means there are 1 + 4 = 5 snow beasts."

Mavis walked to the wall, grabbed her hunting knife, and began to carve the following code into the wall:

NO-FIRE, NO-FIRE, NO-FIRE = 0 snow beasts

NO-FIRE, NO-FIRE, FIRE = 1 snow beasts

NO-FIRE, FIRE, NO-FIRE = 2 snow beasts

NO-FIRE, FIRE, FIRE = 3 snow beasts

FIRE, NO-FIRE, NO-FIRE = 4 snow beasts

FIRE, NO-FIRE, FIRE = 5 snow beasts

FIRE, FIRE, NO-FIRE = 6 snow beasts

FIRE, FIRE, FIRE = 7 snow beasts

She stepped back and examined her work.

"Binary," she stated.

The commander stared at the code. "I think it will work," he remarked finally.

"What happens if there are eight snow beasts?" asked one of the commander's aids. "Should someone from Garroow come and investigate?"

"I do not think it is worth worrying about that," the commander answered without looking away from the wall. Mavis smiled. She had found a way to avoid future treks altogether.

"After six, it does not matter much," continued the commander. "When there are that many, they skip Iceton and head straight for Garroow. It is not worth their trouble here. And all that Garroow can do is warn the other cities and flee south."

Mavis's smile vanished. "Wait… what?" she asked.

"Oh… right… you are from Garroow." responded the commander. "Umm.. Good luck with that."

------------

To learn more about binary, also read Unhappy Magic Flowers and Binary. Or read about Ann's visit to Garroow in The Important of Variable Names.

The Ant and the Grasshopper: A Fable of Algorithms

An algorithm is a set of specific steps or instructions for solving a problem.

One summer day a grasshopper came upon an ant who was collecting grain. The grasshopper watched as the ant struggled to remove a kernel from a fallen stalk. After a few minutes, the grasshopper spoke.

"Little ant, what are you doing?" the grasshopper asked.

"Collecting food for the winter," responded the ant in a weary voice. He was exhausted from a day of hard labor.

"But it is the middle of the summer," said the grasshopper. "Winter is not for months, and the food is plentiful. Why do you spend your day like this?"

The ant paused for a moment while he thought. "It is the algorithm that we use," he finally replied.

"Algorithm?" asked the grasshopper.

"A set of steps or instructions for accomplishing a task," explained the ant. "Like when a carpenter builds a chair, he uses an algorithm that includes measuring, cutting, smoothing, and hammering."

"What task does your algorithm solve?" asked the grasshopper. "Does it solve the problem of having too much time during the summer?" He chuckled out loud at his own joke.

"It accomplishes the task of keeping the colony healthy all year round. Everyday we have a set of tasks that we perform. During the summer we spend the mornings collecting food, the afternoons digging tunnels, and the nights sleeping. It might not sound like much, but it ensures that we have food during the cold of the winter."

"That sounds like a simple algorithm," remarked the grasshopper.

"Algorithms can be simple or complex," explained the ant. "They can even include steps that require other algorithms to solve. For example, when I collect food, I use a special food collection algorithm. It has five steps: 1) walk to the field, 2) search for a wheat stalk with grain on it, 3) remove a kernel of grain from the stalk, 4) carry the grain back to the ant hill, and 5) place the grain in the storage tunnel. I follow those exact steps to collect a giant pile of grain."

"That sounds boring," said grasshopper. "I do not use algorithms. I just do whatever I want, whenever I want. Complete freedom. In fact, I think I am going to climb to the top of the wheat stalk and sing for a while. I bet your algorithm does not let you do that."

The ant shrugged in response. He had his algorithm, and thus his next steps. It had worked for his colony for hundreds of years. While the grasshopper jumped away singing, the ant returned to his task.

Epiloge:

Six months later, a harsh winter engulfed the land. The grasshopper scavenged the, now bare, wheat field for food. There was not a single kernel to be found.

At the same time, the ant was safe and warm in his colony's tunnels. He was hard at work following his winter day algorithm, which consisted of: digging tunnels, eating, and relaxing. He greatly preferred the winter algorithm to the summer one. As he worked on extended the eastern food tunnel, he paused and thought back to the grasshopper. He wondered if the grasshopper was still spending his days singing in the wheat fields or whether he had learned the value of a good algorithm.

--------------------

To learn more about the computational ingenuity of ants read: The Tortoise, the Hare, and 50000 Ants.

Or see the full list of stories here.

The Tortoise, the Hare, and 50000 Ants

A parallel algorithm breaks a large piece of work into smaller units and solves those units at the same time. The algorithm does this by distributing the work over multiple CPUs or cores within a CPU.

"I want a rematch," screamed the hare.

"Not today," answered the turtle, "I am still tired from our race. It would not be fair."

"But… I should have won," argued the hare. "I want a rematch."

"I will race you," said a tiny voice. The hare looked around, but could not find the speaker.

"Down here," added the voice. The hare looked down and found an ant staring back at him.

"You?" the hare asked suspiciously. "You are just an ant."

"Yes," answered the ant. "I am an ant, and I would like to race you. If the turtle can win, I believe that I can too."

The hare scoffed.

"Okay," replied the hare. "I will race you. Let's make it 5,000 meters. Can you even walk that far?"

The ant thought for a moment. "That is a long way for someone as small as me. I am not sure that my legs could make it. Perhaps I could split the work with my family members. We could each race part of the way."

"Of course," replied the hare, "I am not afraid of a thousand ants."

The turtle looked at the hare in surprise. Surely, the hare had learned the price of arrogance already.

"But 5,000 meters will still take us a very long time," continued the ant. "We will be running for days. The crowd will want to see everyone finish. Perhaps my family could each run their leg of the race at the same time."

"Yes," answered the hare. "That way I will not have to wait for days to see the look on your faces when you lose."

The turtle's jaw dropped. "Really?" he asked.

The hare did not respond. He busied himself with a short warm-up jog.

Meanwhile, the ant scurried off to fetch his family. A total of 50,000 ants agreed to each run a 10 centimeter leg of the race. They lined up carefully at the start.

The turtle shuffled down the track 10 centimeters and drew a finish line with a stick. "The race is over when the hare finishes one lap and crosses the original finish line OR the last of the ants crosses this finish line. Either way a total of 5,000 meters will be run."

The turtle looked at the hare and waited for this to sink in. The hare continued stretching his legs -- there would be no rests during this race.

"On your mark," announced the turtle.

"Get set."

The hare and 50,000 ants tensed.

"Go."

The hare speed away from the line, kicking little tufts of dirt behind him as he ran. In contrast, the 50,000 ants poked along. Each pebble was a formidable obstacle, and their finish line loomed in the distance. The slowest ant, Geoffrey, lagged nearly an inch behind the leader.

Still, the ants were finished in under a minute.

As the hare rounded the final bend, he could barely hear the chorus of ant cheers. The spectators were gathered around the ant's finish line. It looked as though the race was already done.

Then, the hare realized what had happened.

--------

For other familiar tales, see Binary Searching for Cinderella or Goldilocks and the Boolean Bears.

Or see a full list of stories here.

Goldilocks and the Two Boolean Bears

Boolean logic is based on two values: TRUE and FALSE. Boolean values are used within programs to perform logic such as: determining if an IF statement executes or controlling when a loop terminates.

Once upon a time, a girl named Goldilocks came across a small cottage. She had been wandering around the woods all day and was eager to rest. She furtively peeped into the windows and listened at the door. There was no sign of life. Convinced that the cottage was empty, Goldilocks climbed in through an open window.

The smell of fresh porridge wafted through house. Goldilocks followed her nose as if in a trance. Presently, she came to the kitchen and saw two large bowls of porridge sitting on a low wooden table.

"Nobody will mind if I have just a little," thought Goldilocks. Her stomach grumbled in agreement. The smell of freshly ground cinnamon pushed away the last of her doubts.

Goldilocks skipped over to the table and tried the first bowl of porridge. It was ice cold. "This porridge is completely cold," she thought to herself. "It is not hot at all."

She tried the next bowl of porridge.

"Argh!" she screamed. The molten porridge seared the inside of her mouth. She spit the porridge across the room, eager to distance herself from the fiery pain. She then dove for the bowl of cold porridge, filled her mouth with the icy sludge, and waited for the pain to subside.

"Who makes porridge that hot?" she moaned to no one in particular.

Traumatized, she looked for someplace to rest. In the living room, she found a single small chair.

"Only one chair?" Goldilocks wondered aloud. Then, noticing the well worn patch of carpet adjacent to the chair, she concluded: "I guess one person sits and the other does not sit. That seems awkward."

Goldilocks climbed into the chair, which promptly collapsed onto the floor. After quick examination of the wreckage, Goldilocks mumbled to herself in confusion "Who makes a chair out of balsa wood? No wonder the other person did not sit down. You would have to be tiny for that chair to support you."

Continuing her search for a place to rest, Goldilocks ventured upstairs. The large bedroom held two beds. The first bed looked incredibly soft. Cotton balls filled the four foot thick mattress. In stark contrast, the second bed consisted of a flat plank of iron supported by four cinder blocks.

"What is going on?" asked Goldilocks. "One bed is clearly comfortable. The other is not. Who makes a bed out of an iron plank?"

Golidlocks debated crawling into comfortable bed when the truth dawned on her. Everything in this house was Boolean. The porridge was hot or NOT hot. One person sat in a chair and the other did NOT sit. One bed was comfortable and the other was NOT comfortable. Whoever lived in this house did not believe in a middle ground. That did not bode well for visitors.

Goldilocks dove out an open window. She sprinted down the path and away from the house before the owners returned. She had no interest in learning whether they were welcoming or not.

---------------------

For more about Boolean logic, see Ann's visit to the city of Bool.

For another take on familiar tale, see Binary Searching for Cinderella.

Binary Searching for Cinderella

Binary search is an algorithm for efficiently finding a target value within a sorted list. The algorithm maintains a shrinking search window. It narrows down that window by repeatedly ruling out half of the remaining search space. At each step, the algorithm checks the middle item in the current window and compares it with the target value. If the value in the middle is less than the target, you can rule out the lower half of the window. If the value is greater than the target, you can rule out the upper half. This process repeats until the target item is found or the window shrinks to a single (non-matching) item.

Alfred Charming could not understand his cousin, Prince Charming. For the last sixteen hours, the prince had babbled continuously about his magical, life-changing night at the ball. The prince had met the girl of his dreams, and she was perfect. Yet, the night had ended with that very same girl running from the party and diving into an oversized pumpkin on wheels. Alfred was certain that was a bad sign. It ranked somewhere between a fake headache and an actual slap to the face. Despite this setback, his cousin was still obsessed with finding this mystery girl. The prince desperately clung to her glass slipper, determined that it would lead him back to her.

Of course, Alfred could excuse his cousin's romantic notions. He had witnessed first-hand the disaster of last month's ball. He had been there to comfort the prince through the tears that had followed. His cousin was under tremendous pressure to marry, but finding his princess had been far from smooth. For now, at least, the prince could bask in the delusional glow of a magical night of dancing and small talk with a mysterious party goer.

However, Alfred could NOT excuse his cousin's flawed strategies for finding the woman of his dreams.

"I shall go forth to every house and find the owner of the slipper," proclaimed Prince Charming.

"Are you crazy?" objected Alfred. "That would take weeks. And you have to help them try on a slipper made of glass. Think of the germs. It is a health nightmare."

"I must find my true love," protested the prince.

"Fine," said Alfred. "I am still not sure why, but let's say that you do need to find this girl. You don't have to go to every house."

"I must be thorough," said the prince.

"You can still be thorough using a good algorithm," argued Alfred. "Trade data for time."

"Data? Time?" asked the prince.

Alfred thought for a moment. "Ye Old Foot Shoppe has a list of everyone in the kingdom's shoe size. Have them compute the size of the glass slipper, and you can look for a match on their list. They keep sizes with two decimal points of precision, so there will only be a few matches at most. I bet the slipper is around a size 5.75. And, if you do happen to find a few matches, you can go try them all."

The prince did not look convinced. "Spend the day searching for numbers in a list? How is that romantic? It sounds like hours of dreadful effort."

"The store's list is already sorted," explained Alfred. "You can use binary search to find a match. It is better than days of trying to fit the same glass slipper on different feet."

"Binary search?" The prince's education had not required an algorithms class.

"The search algorithm," said Alfred.

The prince continued to stare blankly back at Alfred.

"You can do it using your fingers," explained Alfred. "Use two fingers to track where in the list the slipper's owner could be. One finger indicates the start of the range, and one finger indicates the end of the range. Let's keep it simple and call them the 'start' and 'end' fingers respectively. If you do the search correctly, the matching shoe size is always somewhere between (or possibly under) your fingers."

"Initially, the entire list is under consideration," continued Alfred. "So start with your 'start' finger at the beginning of the list, and your 'end' finger at the end."

"Then I use my fingers to scan through the whole list?" interrupted the prince. "What do I do? Move one finger up then the other down? Sounds dreadful. I might get a paper cut!"

"No," answered Alfred. "Then you do binary search. First, you look at the list entry halfway between your fingers. Call that the 'middle' entry, because it will be in the middle. Second, you can compare the middle value to the one from the shoe. And third, you move one of your fingers depending on the value of the middle entry.

"There are only three cases to consider:

1) If the glass slipper is smaller than the middle value, you only have to work on the 'smaller' half of the list. Move the 'end' finger to where the middle value is, because all of the entries after the middle are too large to match. The matching size will still be between your two fingers.

2) If the glass slipper is larger than the middle value, you only have to work on the 'larger' half of the list. Move the 'start' finger to where the middle value is, because all of the entries before the middle are too small to match. Again, the matching size will still be between your two fingers.

3) If the middle value matches the slipper's size, you are done. You found a match. Yay."

"Your method only eliminates half the list," objected the prince.

"You repeat the process on the remaining half of the list," sighed Alfred. "Pick the entry halfway between your two fingers and call that the new 'middle'. Compare the middle value to the shoe size and use the same logic to eliminate half the list. After each step, you cut the size of the list in half, and still guarantee that the target value is between your fingers."

"When do I stop?" asked the prince. "When do I find my princess?"

"You stop when you find a match," answered Alfred. "Unless, of course, there is no match. If you reach a point where there is nothing left to search, then the list does not contain a match."

"How will I know that there is nothing left to search?" asked the prince.

"There is nothing left to search when there are no new values between your fingers. This can happen if both fingers point to the same place or if they are right next to each other. As I like to say: 'If your fingers touch, you are out of luck'."

"That does not rhyme. It would sound better if it rhymed," observed the prince. "More importantly, what if my princess's name gets skipped? Your algorithm involves big jumps early on. I am not sure that I could survive losing her."

"It won't skip her," answered Alfred. "At each step we guarantee that if there is a match, it is between your fingers. However, it is true that binary search will only give you ONE match and it might not be the first one. If you want all the matches, which you do, you will need to check the list entries near the match. Scan outward from the match."

The prince nodded solemnly. "I am sure that there will only be one match. My princess is perfectly unique."

Alfred stifled back a thousand comments and smiled politely.

After a moment, the prince continued. "While your idea has merit, I believe that I shall stick to my original plan. I shall go forth to every house and test the slipper."

"Why?" asked Alfred. "What if someone is not home? What if your mystery girl is locked in a basement by evil family members? What if someone breaks the slipper? That plan has so many problems."

The prince smiled. "I want the people to know that I am searching for my true love. If I use your binary search, I miss the excitement of the search. Binary search is not romantic."

Alfred sighed. He did not have an argument to counter that.

-------------------------

For more about binary search, see Hunting Dragons with Binary Search.

Also see my recent note on why updates will be less frequent for a while.

Coming Soon (or Maybe Later)

If you follow this blog, you might have noticed that the frequency of new stories has dropped off significantly in the past few weeks. Do not worry. I am not out of ideas.

I have been working on assembling an initial collection of stories for publication For the most part, I have been spending time editing and reworking previous stories. I have also been working on filling in some gaps.

What to expect from the collection:

• A few new stories - Covering some earlier concepts and filling in the gaps.
• More details of Ann's quest.
• A reasonable ordering (both by concept and plot)
• Extensive editing - At least 10% fewer gramatical errors!

I am planning on continuing adding new stories here, but with a slightly lower frequency than before. I am also cleaning up and even rewriting stories as I go. Admittedly, a lot of the stories are still in very rough form and could use a round or two of reworking.

In the mean time, feel free to check out the current set of stories (around 70): By Topic or By Level.

Or to learn more about this blog, its goals, etc. at the FAQ.

Names for Ingredients (and Variables)

The use of clear variable names can help make code more readable and reduce the likelihood of mistakes.

"Excuse me. I am looking for powdered rose petals." said Marcus.

"On the shelf behind you." replied the young clerk without looking up. He continued to sit behind the counter, copying text onto a sheet of parchment.

Marcus glanced behind himself to confirm that he had already checked those shelves. Marcus turned back to the clerk.

"I did not see it there." responded Marcus. "In fact, I did not see any ingredients that I recognize. Everything seems to be encoded."

"Shorted," responded the clerk without additional explanation. Before Marcus could ask for clarification, the clerk hopped off his stool and walked around the counter. He proceeded up to the nearest shelf, selected a small bottle, and returned to the counter. He placed the bottle on the counter.

"That will be three copper pieces." said the clerk.

Marcus studied the bottle. It was labeled with large letters: "RP3p". He picked up the bottle and turned it over in his hands, searching for any other markings. There were none.

"Are you sure this is powdered rose petals?" Marcus asked.

The clerk nodded. "Yes. This one clearly states 'RP3p', which means 'Rose Petals Powdered'."

"I see. You abbreviated it. RP for Rose petals and p for powdered. But why the 3?" asked Marcus.

"There is more than one ingredient that can be abbreviated as RP. RP1 is 'Raspberry Puree', RP2 is 'Red Pollen', RP3 is 'Rose Petals', and so forth." answered the clerk.

"That is terribly confusing." exclaimed Marcus. "I have never heard of such a strange system."

A troubled look crossed the clerk's face. "It is my own scheme. It is more efficient." he explained.

"More efficient? You have to figure out awkward abbreviations in order to understand anything." objected Marcus. "It is a wonder that anyone can find what they need."

"But the abbreviations all make sense." responded the clerk. "They are all quite simple actually. How else would you abbreviate 'Rose Petals'?"

"I would not!" answered Marcus. "I would label each ingredient clearly with its proper name."

"But that is so inefficient." complained the young clerk. "Everyday, I have to copy hundreds of potions to sell to patrons. I have to do that all by hand. Do you know how much faster it is to copy potions with this new system? I save hours."

"My word!" exclaimed Marcus. "You sell potions that use this idiotic encoding? Are you serious?"

The clerk did not respond.

"Do you know how dangerous that is? What if one of your customers confuses rose petals and rabbit pellets? It could be a disaster!" argued Marcus.

"But it is more efficient." protested the clerk.

"For you… and at the moment." countered Marcus. "But it makes the potion recipes harder to understand. Worse, it makes it easier to make a mistake."

"But it is shorter." tried the clerk.

Marcus shook his head sadly. "I know it seems faster and more efficient now, but there is a high price for using such shortcuts. It is much better to use clear names. Trust me. I have confused ingredients before; it never ends well."

"You have?" asked the clerk.

"Yes. I once copied down a recipe with 'S' for Salt. Unfortunately, three weeks later, I mistakenly read it as Sulfur. S for sulfur seems quite reasonable. Needless to say, the bread tasted terrible. It was completely inedible."

The clerk did not seem to have an argument for that. "I guess that I could change them back." he said.

"Yes. You should." encouraged Marcus. "Now. Are you absolutely sure that this is the ingredient that I need?"

The clerk hesitated.

"I see." said Marcus. "I will be back some other time then."

And with that Marcus left the store. He turned down a side street and started for the "Potion Ingredients and More" shop on the other side of town. It was a long walk and the prices were higher, but he needed to be absolutely certain that he had the correct ingredients. The last time he had incorrectly mixed up a batch of magic soap, he had ended up smelling like a skunk for a week. There were some things on which he refused to take any chances.

---------------------

Also see Ann's experience with names in The Importance of (Variable) Names.

Or read more practical advice by Marcus in: The Importance of Unit Testing Magic Spells; Data Validation, Marcus, and the Minstrel of Cheese, or Version Control in Magic Spell Development.