Wednesday, June 29, 2011
Variable Initialization in Busy Kitchens
Sunday, June 26, 2011
Pixels, Peacocks, and the Governor's Turtle Fountain
Pixels are tiny, individual blocks of color that are used in computer displays. A common computer display may include many millions of individual pixels. By setting each pixel's color, the display can represent many different images. The number of pixels determines a screen's resolution, which in turn determines how complex a picture that screen can display. The key to many computer graphics algorithms is automatically determining how to set the color of each of the individual pixels.
Brian was the resident peacock at the governor's palace. For the past three years, he had been a main attraction there. His beautiful features were a sight to behold. Moreover, they were magical. Brian could change the color of each of his twenty tail feathers however he wanted. Some days, he would choose a single color for all of them to represent his mood. Other days, he would vary them to create complex patterns.
Thus, Brian was understandably jealous when a master wizard gave the governor a magical turtle fountain as a gift.
The fountain itself was not all that exciting, and the seven turtles that lived in it were certainly not magical. However, the bottom of the fountain was lined with over a million magic tiles that could change colors just like Brian's feathers. They were arranged in 1024 by 1024 square in the center of the fountain. At the Governor's command, they would change colors to form different murals.
One day Brian decided to confront the fountain. He walked up, squawked loudly, and changed his features into a beautiful rainbow of twenty different colors.
The fountain, having no real concept of the competition, gurgled happily. It instantly changed its tiles to be a picture of a peacock with rainbow tail feathers. The picture looked surprisingly like Brian.
Brian squawked angrily at the fountain's insult. His tail feathers shimmered in an oscillating wave of red and black. He called those his angry feathers. If he changed the colors fast enough, such as multiple times per second, it looked as though the colors were actually moving across his tail.
The fountain mimicked this motion. Unlike Brian, it could flip colors at an amazing 60 changes per second, providing the appearance of smooth motion. Deciding to take advantage of its ability to change colors vertically too, the fountain animated its picture of the peacock jumping up and down. It almost looked as though the angry peacock in the fountain was dancing.
Brian was furious. Unable to take the taunting, he wandered off to go chase visitors around the yard. At least the fountain could not do that.
Unaware that a competition had taken place or that it had won handily, the fountain continued to gurgle merrily.
Wednesday, June 22, 2011
Swapping Array Values and the Swimmy Friends Pet Store
Swapping two values in an array is a basic operations that helps illustrate how arrays store data. Each entry in an array can be viewed as an individual variable -- it stores one piece of information. Thus, in order to swap the values contained two different entries, additional (temporary) storage must be used. Specifically: 1) The data from one array entry is written to the temporary storage, 2) the data from the other array entry is written into the memory location of the first entry, and 3) the data from temporary storage is written into second array entry. For example to swap array entries at indices i and j in C, we might write:
int temp_variable = my_array[i];
my_array[i] = my_array[j];
my_array[j] = temp_variable;
Casey's first day at the Swimmy Friends Pet Store had not gone smoothly. Within fifteen minutes, he had accidentally allowed all thirty turtles to escape. He then spent the next eight hours trying to round them up. Although the turtles were slow, they scattered in different directions and hid under store shelves. No matter how nicely he asked, the turtles refused to come when he called them.
Casey sincerely hoped that his second day would go better.
"Hey, Casey. I have a job for you." called the manager as Casey entered the store.
"Sure!" responded Casey eagerly. He wanted to prove that he was a good employee.
"We are starting a promotion on tiger barbs this week." the manager explained. "I want to put them in the big tank at the front of the wall. Can you swap them with the neon tetras?"
Casey looked at the fish section. The entire back wall of the store was lined with large, brightly lit fish tanks. At the front was the tank currently occupied by the neon tetras. Five tanks over, two dozen tiger barbs swam lazily around a small rock. Both tanks looked quite heavy.
"You want me to move the tanks?" asked Casey. Casey's mind froze as he pictured himself dropping a full 50 gallon fish tank.
"Of course not!" the manager answered. "The tanks are full of water. Just swap the fish. The temperature and PH are already identical."
Casey nodded. He walked over to the tiger barb tank and began trying to scoop up barbs in the net. The manager watched from the side.
"What are you doing?" the manager asked.
"Moving the tiger barbs over." responded Casey without looking up. The tiger barbs were fast, and Casey was not particularly coordinated. He thrashed about with his little green net, hoping that he could at least catch one by luck.
"You do know that tiger barbs and tetras cannot go in the same tank, right?"
"Uh huh." responded Casey, still lost in concentration.
"So, what are you going to do with the tiger barb that you are having trouble catching?" prompted the manager.
"I am going to put it… oh." Casey suddenly realized his mistake. There was no way he could transfer the tiger barbs over without first moving the tetras. And there was no way to transfer the tetras over without first moving the tiger barbs. The whole swap was deadlocked.
The manager watched for a minute as Casey grappled with the problem, waiting for him to see the solution. After all, it was not a hard problem. Finally, the manager realized that Casey was not going to figure it out.
"Just use that empty tank as a temporary storage." The manager prompted. "First, put the tetras in that empty tank. Then move the tiger barbs to the old tetra tank. Then move the tetras to the old tiger barb tank."
Step 1:
Step 2:
Step 3:
"But… that means three sets of moving things. I know that I can do it in two." responded Casey. He was determined to prove that he was a good employee.
The manager sighed. "No. You cannot. You need to use temporary storage. Otherwise, you will end up putting tiger barbs in the tetra tank and causing problems."
Casey wanted to argue, but he could not think of a better solution. "Okay," he finally agreed.
The manager looked at Casey doubtfully. While he was semi-confident that Casey could handle the fish swap, he worried about Casey doing something stupid later.
"Come find me when you are done." the manager instructed. "And, stay away from the turtle tank." he added for good measure.
Sunday, June 19, 2011
The Incident at the North Gate (or Why = Is Not ==)
In many modern programming languages the expression "a = b" is used to assign the value b to the variable a. In contrast, the expression "a == b" tests for equality and returns true if and only if the values of a and b are the same. Unfortunately, in some languages, such as C and C++, this syntax can lead to difficult to detect errors because the = operator returns the value being assigned. For example, "if (a = b)" will compile without problems and trigger if and only if b's value is equal to true.
King Fredrick loved to tell the tale of the "incident at the northern gate". He was a firm believer in the importance of clear, correct documentation. And, the occurrences of that day provided a perfect case study.
The incident had occurred during the last period of war and unrest. King Fredrick's father held the throne and was working hard to guide the kingdom toward peace and prosperity. As part of this effort, he personally oversaw the creation of new rules for the castle guards.
The new rules read:
"Check the entrant's ID and examine their entrance ID class.
IF (ID class == 0): they are a member of the royal family, so let them pass,
ELSE IF (ID class == 2): they are a member of the carpenters' guild, so let them pass;
ELSE IF (ID class == 3): they are a member of the plumbers' guild, so let them pass;"
and so forth. Unfortunately, even a king makes syntax mistakes occasionally. The erroneous line read:
"ELSE IF (ID class = 72): they are a mime, so stop them"
The king had used an assignment statement instead of an equality test.
It took three days for someone to reach this test in the series of IF-ELSE statements. On that day a young hedgehog walker (ID class 185) arrived at the north gate with the King's prize hedgehog. He presented his ID to the guard. The guard consulted his manual and paused in confusion.
"What is wrong?" asked the boy.
"Well. The manual says here that I am to change your ID class to 72 and prevent you from entering." The guard responded. As he spoke he reached into his booth and pulled out a permanent marker. He crossed out the ID class of 185 and wrote 72 in its place.
"But, I am supposed to go inside." argued the boy. "I have the king's hedgehog."
"I am sorry lad. No mimes allowed in here!" responded the guard.
The boy looked confused. "Mime?"
"Yes. It says ID class 72. That means you are a mime!" answered the guard.
"But, you just wrote that. It was ID class 185. I am a certified hedgehog walker. And, I am working on my parrot walking license too. I provide a valuable public service."
"The manual told me to reclassify you as a mime, so that is what I did. And, we do not allow mimes here!" responded the guard formally.
"But…" started the boy.
"Be gone!" shouted the guard.
The boy quickly retreated and circled around to the south gate. Unfortunately, his ID now clearly indicated that he was a mime. He was not allowed to enter. Discouraged, the boy went home, bringing the king's hedgehog with him.
The incident went unnoticed for almost a day, until the king sent a search party to find his hedgehog. Fifty knights arrived at the boy's home, scaring both the boy and the hedgehog out of their wits. It took three hours for the boy to pull himself together enough to explain what had happened. And, it took another five hours to calm down the hedgehog.
The king was furious when he found out. He marched down to the north gate and grilled the guard on why he had changed the boy's ID. The guard pointed to the instruction and explained himself. But when the king saw that this was his own mistake, his mood only worsened. The king launched into a six hour rant and then immediately insisted on three sweeping changes:
1) All IF statements would put the constant value before the variable (e.g., 0 == Class ID), so that no assignments could happen by mistake;
2) Every new set of rules had to be checked by at least one other person for correctness (although this was a great practice in its own right, the king also wanted someone else to blame if there was a mistake).
3) All new rules would be unit-tested by a group of Shakespearean actors.
Despite the seeming overhead of these new regulations, the castle was launched into an unexpected period without any mistakes. Even the castle stables, which had 100 page rulebooks, went a full week without any mistakes.
Feeling satisfied with his contribution for the day, the king decided to get a pet parrot. He had heard good things about parrots recently.
-------------------------
Related stories: Also see the story of how King Fredrick rewrote the instruction castle instruction manuals to use the Switch/Case format in Switch/Case and the Palace Guards. Or read more about the IF-ELSE statement in Learning IF-ELSE the Hard Way.
Thursday, June 16, 2011
Unhappy Magic Flowers and Binary
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 deliveryman paused outside of Marcus's house. He stood transfixed, staring at the flowers. After two minutes, Marcus finally went outside to see what the problem was.
"Your flowers have changed since yesterday." observed the deliveryman. "I am sure that the one on the right was red yesterday. Today it is blue."
"No. Those are the same flowers." responded Marcus. "Some of them are just sulking today. Stupid flowers."
"Sulking? Do flowers sulk?" the delivery man asked.
"These flowers do. They are, of course, magic. If there is not enough rain, they sulk. It is quite aggravating really. It is not as though they are not getting water. I water them every day. Yet, they still insist on sulking when there is no rain. It appears that the water I give them is not good enough for them."
"Huh?" The deliveryman looked most confused. He looked back and forth between Marcus and the flowers.
"They sulk by changing to blue. Roses are supposed to be red. That is why so many poems start out that way. But, they insist on telling me how long it has been since it rained." Marcus gestured angrily at the roses as he spoke.
"They talk to you?" The deliveryman took a step back away from Marcus. He looked as though he was ready to run.
"Of course not. They simply change color." Marcus sighed.
"And, that tells you how long it has been without rain?"
"Well…" started Marcus. "They used to all change color together after three days without rain. A sort of mass protest. But, then they started to organize. They want to let me know exactly how unhappy they are. So, now they count the days."
"But… only two are blue. It has not rained all week." observed the deliveryman.
"Nine days to be exact." corrected Marcus after looking at the flowers. "They use binary."
"Huh?"
"Binary. Red flowers are zero and blue flowers are one." Marcus added.
The deliveryman did not look as though he was following. But, at least he did not look like he was about to run away anymore.
"Binary?" prompted Marcus. "Each flower represents a different digit, and thus a different power of two. The rightmost flower means one (2^0), the one next to it means two (2^1), the one next to that means four (2^2), and so forth. Add up the numbers represented by the blue flowers and you get the total number of days. Right now only first (2^0 = 1) and fourth (2^3 = 8) flowers are blue, so it has been 2^0 + 2^3 = 1 + 8 = 9 days."
The deliveryman looked. Sure enough, the five flowers across Marcus's porch were: Red Blue Red Red Blue (or 01001).
"Why do they use binary?" asked the deliveryman.
"They tried to spell out the numbers on their petals and they got too confused. So they had to settle for each flower being either all red or all blue. It turns out that flowers are not that smart. Binary is a simple enough system for them. If they were smart enough for anything else, do you think they would be complaining to me about the rain? There is nothing I can do!" Marcus shouted the last part directly at the flowers.
"But, how do they work together?" The more absurd the story got, the more interested the deliveryman became. He took a step forward towards the flowers.
"It is really quite simple for them to count in binary. When it rains, they are all happy and turn red. It is like reseting the counter to 00000. I like those days a lot." started Marcus.
"Then, each morning all of the flowers wake up and decide what color they are going to be for the whole day. If it has not rained, they increase the count.
After 1 day they are: Red Red Red Red Blue (00001 = 1)
After 2 days they are: Red Red Red Blue Red (00010 = 2)
After 3 days they are: Red Red Red Blue Blue (00011 = 2 + 1 = 3)
After 4 days they are: Red Red Blue Red Red (00100 = 4)
After 5 days they are: Red Red Blue Red Blue (00101 = 4 + 1 = 5)
And so on.
"You see, each flower looks to its right in order to decide what to do. If its right-hand neighbor changes from blue to red (1 to 0), then the flower flips its own color. I like to think of it as passing along the unhappiness. Basically, if its neighbor is changing from blue to red then the sullenness is rolling over to the current flower. If it is red, then it becomes blue. And if it is blue, it becomes red and passes the sullenness further down the line. This keeps happening until one of the flowers does not change from blue to red."
The deliveryman thought about it. "What if a flower changes from red to blue (0 to 1)?"
"Its neighbor does nothing. Didn't I just say that?" Marcus was impatient. He felt like he was talking to one of his apprentices. "Think about it the way you would counting with numbers 0-9. When you hit 9, you roll the first digit back to 0 and increment the next digit to 1. That next digit stays where it is until its right-hand neighbor switches from 9 to 0 again. You don't count 10, 11, 12, 23. Do you? NO! You wait until the digit to your right rolls over. Only here there are exactly two options 0 and 1, so things roll over more frequently."
"What about the right-most flower?" asked the deliveryman. "How does it know what to do?"
"Ah. THAT ONE IS THE INSTIGATOR! I am sure that he is the one that started it. Every morning there is no rain, he flips. He is the one that starts the process off. Red to blue to red to blue to..."
"And that system always works?" interrupted the deliveryman.
Marcus tore his attention away from the right-most flower. He suddenly wondered how the discussion had gone from a rant about magic flowers to counting in binary. Did the deliveryman not have any other deliveries? For that matter, where was the delivery for Marcus?
"Yes. They already counted out nine days, haven't they?" answered Marcus flippantly.
Then, seeing the look of interest on the deliveryman's face, Marcus returned to his teaching tone. "Imagine that these three flowers were blue." explained Marcus as he pointed to the first three flowers. "That would be 1 + 2 + 4 = 7 days without rain. The next day the first flower (1) switches to red, so the second flower (2) switches to red, so the third flower (4) switches to red, so the fourth flower (8) switches to blue. Then they would show 8 days without rain. The count effectively gets pushed down into the fourth flower."
The deliveryman looked impressed. Marcus could not understand why. The flowers were really very annoying.
"So tomorrow they will be: Red Blue Red Blue Red (01010)?" asked the deliveryman.
"Probably. But, I really hope that it just rains." responded Marcus with a sigh.
Monday, June 13, 2011
Bog Dragons Do Not Support Multithreading
Multithreading is a technique in modern computer architectures to process multiple sets of instructions on a single CPU core. Different sets of instructions run in different threads, and the operating system switches between these threads. Unlike multi-core or multi-processer systems, multithreaded systems are not actually running these sets of instructions in parallel (at the exact same time). Instead, a single CPU core is rapidly switching between the threads to allow each to make progress.
The ability to multithread instructions allows modern computers to effectively do work "in the background". For example, the spell check operation in a word processor might run in a separate thread, allowing the user to continue to work as the full document is being spell checked. In the absence of multithreading, computationally expensive operations can cause the entire computer to "freeze" as the CPU is stuck on one task.
Ferr dove low as another bog lizard snapped at her from a nearby tree branch. She hated traveling through the bog. It was filled with nasty creatures, and it always smelled like… a bog. At least there was only a few miles left to go. She would be home in time for dinner. For a brief moment, Ferr let her mind drift and wondered what dinner would be.
Then, Ferr heard a loud screech. The sound sent a chill through her. It was a bog dragon, and it sounded hungry.
Bog dragons are particularly vicious creatures, especially with respect to fairies. In fact, fairies seemed to be either their sworn enemies or their favorite snacks. Nobody was really sure which it was. Regardless of the dragon's motivation, Ferr knew that she was in grave danger. She took off flying as fast as she could.
Ferr dodged trees as she flew through the swamp. Unfortunately, bog dragons are much smaller than regular dragons, being about the size of a house cat, and thus are able to maneuver quickly in the dense swamp. Ferr knew that she had little chance of winning this race. The bog dragon was both fast and familiar with the swamp. It was only a matter of time before it caught up to her.
Her mind raced, trying to find anything that would save her. She mentally ran through the list of all of her spells. Nothing seemed promising. She cursed herself for having not perfected any defense spells against a bog dragon. Bog dragon sightings were rare enough that she had never made it a priority. Now, that seemed like a mistake.
She could hear the bog dragon breathing behind her.
Distracted by the sound and her own thoughts, Ferr clipped a tree. Her left wing missed a beat, and she was thrown off balance. She spun through the air, trying to regain control. But, it was no use. She had been flying too fast. She barreled into the soft mud with a loud squish, sliding fifteen feet. She was coated from head to toe in brown bog mud.
Above her, the bog dragon circled eagerly.
As she scolded herself for not paying more attention, a memory popped into her head. Bog dragons were not multithreaded. They could not multitask. They could only ever do one thing at a time! No matter what it was, that one thing would occupy their full attention. Right now, the dragon was doing one thing: hunting her. But, if she could distract it with some other task, it would not be able to context switch. She could escape.
Ferr ran through the list of spells again in her mind. Finally, she hit upon the perfect solution: the spell of Mental Flash Cards.
Ferr had used this spell on herself to prepare for her finals last year. When cast, it ran through five minutes of simple math flashcards in the back of the target's mind. Ferr would use this to practice math while flying to school. Since the math was simple, she could balance the two tasks. She would quickly solve each flash card and then concentrate on flying: one card, one beat of her wings, one card, one beat of her wings, and so forth. As long as she switched between the tasks, she could do both safely. But, the bog dragon could not.
Hoping that she was remembering this characteristic of the bog dragon correctly, Ferr cast the spell. If she was mistaken, and the bog dragon could multitask, then giving it math flash cards would probably just anger it. It would be like having someone rudely scream "WHAT IS 1 + 3?" in your ear every few minutes. Nobody enjoyed that.
Three seconds later, the bog dragon flew directly into a tree. It fell to the ground with a squishy thud.
The spell had worked. The bog dragon was fully occupied with the flash cards. It was unable to switch between the flash cards and flying.
Ferr did not waste any time. She was up and flying immediately. The five minutes would give her enough time to escape.
Ferr looked back once. The bog dragon was lying on the ground looking miserable. Ferr could not feel too bad. After all, she would have been the dragon's lunch. And even though the dragon had lost its lunch, at least it would learn some simple math in exchange.
Friday, June 10, 2011
Switch/Case and the Palace Guards
Switch/Case is a computational construct in many modern programming languages that allows the program to choose one of multiple execution options. The option is chosen by "switching" on the value of an input parameter.
King Fredrick loved performing surprise inspections of the palace guards. Naturally, he felt that these inspections kept everyone prepared. But, more importantly, he found that wandering the grounds for an inspection was the best way to keep the castle steward from finding him. If Fredrick stayed in the throne room, the steward would constantly bring problems to his attention. Sometimes, the king just needed some quiet.
"You there. Guard." called the king.
The guard groaned quietly. Unlike the king, the guards were not fond of surprise inspections.
"Yes, sir!" the guard responded in his best military voice.
"Tell me, are you always at this gate?" inquired the king.
"Yes, sir!" The guard could sense that it was going to be a long day.
"Wonderful. Wonderful. I have some questions about security. If someone comes down the path, how do you know whether to let them in?"
The guard reached into his little guard booth and pulled out a thirty page instruction manual. He quickly opened to the first page, hoping that the king did not see the coffee rings on the cover. It was considered disrespectful to use the official castle manuals as coasters. But, truthfully, that was often their most useful function.
The guard started to read from the manual in a loud military voice:
"Check the entrant's ID and examine their entrance ID class.
IF the person is a member of the royal family (ID class 0): let them pass,
ELSE IF the person is a merchant of a registered guild (ID class 2, 3, or 6): let them pass,
ELSE IF the person is from an opposing army (IF class 107): stop them,
ELSE IF the person is a registered juggler (IF class 71): let them pass,
ELSE IF the person is a registered mime (IF class 72): stop them,
ELSE..."
"Enough!" interrupted the king. The manual was in the familiar IF-ELSE series of conditions of which the past king, Fredrick's father, had been so fond. Why any king would prefer that style was beyond Fredrick. Fredrick was certain that he had updated all the manuals by now.
"It looks as though we need to update your manual." the king stated.
The guard was confused. He also looked scared. "But Sir, I have not made any mistakes. No intruders have been let in and no VIPs made to wait. I have not done anything wrong!"
The king gave the guard a reassuring smile. It did nothing to assure the guard. "No. That is not it. The manual uses a complex format that is simply harder to understand. We switched everything else to switch/case a few years ago. For a long list of conditions like that, it can be cleaner."
"Switch/case?" asked the guard. He did not remember that from his training.
"Yes." the king looked around for a prop to illustrate. Finding none, he started gesturing with his hands.
"Here is how that would work in switch/case." the king began.
"Check the entrant's ID and find the first matching case.
Case Royal Family: let in and done,
Case Enemy: Keep out and done,
Case Merchant of a registered guild: let in and done
And so forth!"
"You just go down the list and find a match. It is the same logic as the long list of nested IF-ELSE conditions. It is just easier to read... Sometimes." finished the king. He loved explaining computational constructs and was debating launching into a description of unrolling loops, when he realized that he could be boring the guard. He had a habit of boring people sometimes. Then again, the guard was nodding intently as the king spoke. Maybe the guard would want to hear about unrolling loops.
"Oh..." responded the guard, clearly thinking this over. "Why do you keep saying 'and done' after each command?"
"Well technically, the way it works is that you go to the first case that matches and keep reading instructions down until you hit a break. That way you can use complex blocks of commands for multiple cases without repeating them. When I say done, I just mean break out of the switch statement."
"Oh... But what if the appropriate condition is not there?" asked the guard.
"You can always have a default case to cover everything else. For you, I would make that 'Keep the person out and call for clarification.'"
The guarded nodded. "Yes. That would seem like a good default. I would hate to have to make a judgement call on my own. But, it seems that you are not actually changing any of the procedures?"
"That is correct." answered the king. "Switch/case can be thought of as a sort of shorthand for a long series of if statements. We will simply clean up the manual… and maybe put something in there about marching bands. Yes. We should certainly have a case about marching bands."
The king trailed off and stared out at the castle wall. Although he could not explain it, he knew that marching bands, mimes, and clowns all needed their own cases. Something about each of them made him profoundly uneasy.
"Well, I shall return to the castle and set to work on a new manual right away." proclaimed king Fredrick. He was excited by the opportunity to update more castle documentation. Given the recent peace in the kingdom, he had not had much real work to do for a while.
This was the best news of the guard's day: an early ending to the surprise inspection.
------------------------
For more information on IF-ELSE statements, see Learning IF-ELSE the Hard Way.
Or for more adventures of King Fredrick, see Hunting Dragons with Binary Search or Stacks, Queues, Priority Queues and the Prince's Complaint Line.