Sunday, January 29, 2012

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.

Tuesday, January 24, 2012

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.

Thursday, January 19, 2012

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.