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.

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.

Checkpointing Checkers

Checkpoints are a technique for improving a program's fault tolerance by preserving the program's state. Checkpoints can be used to recover after a program crashes or used to save the state for later analysis. They are literally dumps from the program that are sufficient to reconstruct the program's current state.

The Powerful Wizard Marcus was traveling to the city of South Atlantis for the annual World Checkers Championships. The competition was legendary, and it attracted all of the best checkers players in the known kingdoms. This year the heavy favorite was Jennifer "King Me" Stratovarious. She had won thirteen of the major competitions in the last six months. Some people said that she was unbeatable. Any match where she played was guaranteed to be exciting. And, Marcus had front row tickets to the finals.

However, Marcus realized that there was a problem as soon as he arrived at the preliminary rounds. The players were playing a frantic pace. They almost looked panicked.

"What is going on?" Marcus asked King Fredrick, who had also journeyed to South Atlantis to watch the world championships.

"They are playing checkers." answered the king.

"I can see that. But, why are they playing so quickly? It almost looks as though they are trying to race through the game."

The king shrugged and returned to watching Jennifer quickly destroy a young novice from South Patagonia. Marcus had never seen a game won in so few moves. Or, for that matter, played so quickly.

Unfortunately, all too soon he understood the reason behind the players' urgency. South Atlantis happened to be the windiest city in the world. Twenty-three minutes into the preliminary round, the entire building started to shake with the force of an industrial paint mixer. Despite the strong walls and shuttered windows, wind swept through the hall. The oil lamps swayed dangerously, people fell down, and the checkers slid off the boards.

After only half a minute, the wind stopped and the contestants began to gather their pieces off the floor. The contestants that had been winning groaned and griped loudly. "This is unfair!"

"Why are they hosting the tournament in such an awful location?" And, in contrast, the contestants who had been on the losing end of the game smiled quietly, for they now had a new chance to win. Only three games had finished before the wind-storm. The winners of those games smiled broadly; they had beaten the disaster.

"Unbelievable," proclaimed King Fredrick. "All those games were lost."

"Bah." declared Marcus. "Inefficient and stupid."

"What can they do? All of those checkerboards crashed to the floor before the games were finished. There was nothing that they could do." Insisted the king.

But, Marcus had stopped listening. Instead, he was wandering down to the nearest competition table.

"Excuse me, there. Why do you make them replay the game?" Marcus asked the judge at that table. "Why not use checkpoints?"

"Checkpoints?" asked King Fredrick, who had followed Marcus down to the floor.

"Yes. Write down the entire state of the board after each move. That way, if the pieces are upset, you can reproduce the entire board from the most recent checkpoint. It would save your games from being lost." explained Marcus.

"HA! Checkpoints?" cried Jennifer "King Me" Stratovarious from behind. "That would be too slow. Have you ever seen how fast I can play checkers?"

Marcus had indeed seen how faster she could play. He had to admit that checkpointing every move could only slow down someone of her caliber. In fact, Marcus was surprised the even a judge could keep up with her.

Marcus grinned widely. "Perhaps I can be of service." he offered. Then, without any more explanation, he picked up the table's timing clock and waved his hands over it. After a moment he set it back down.

King Fredrick looked at the clock. It appeared mostly unchanged, except that it now had two additional buttons "Save" and "Restore".

"May I?" inquired Marcus. Then, without waiting for an answer, he pressed the "save" button. The clock chirped once like a bluejay. Marcus smiled widely at the assembled crowd and, with a quick flick of his hand, knocked the table's board onto the floor. Checkers flew everywhere. The judge and both players scowled at him.

"Now, observe." commanded Marcus with his best wizard's voice. He reached over and pressed the "Restore" button. Magically, all of the pieces flew up off the floor and reassembled themselves on the board. In less than a second, the full state for the board had been restored.

Everyone gasped and burst into applause.

"Woah." King Fredrick said.

Then, Marcus felt a tap on his shoulder. Behind him stood four hundred and ninety-nine other table judges. Each judge held their table's timing clock out toward Marcus and looked at him expectantly. As he took the clock from the nearest judge and started his spell again, Marcus suddenly regretted having felt the need to show off.

Stacks, Queues, Priority Queues, and the Prince's Complaint Line

Stacks and queues are very simple, yet fundamental, data structures in computer science. Simply put: they store data. You put a piece of data in the stack or queue, go about your business and later take that piece of data out. Where they differ is in how they order the data that is extracted. Stacks are last-in, first-out data structures that return the most recent data inserted. Queues are first-in, first-out data structures that return the least recent data inserted. And priority queues return the highest priority data inserted (accord to some priority value). Understanding these ordering effects is the key insight into understanding how these data structures can effectively be used.

Before he became king, Prince Fredrick had a tradition of hearing his future subjects' complaints every Tuesday in the great room. At 10 am the doors would open, and his loyal subjects would fill the room to raise their complaints. On days that he was feeling particularly generous, Prince Fredrick would even task his steward with addressing some of the complaints. However, on most days Fredrick felt that he had done his part by just listening and he would promptly forget everything that was said.

By 6 am every Tuesday a great crowd formed outside the doors to the Hall of Complaints. In fact, farmers with particularly pressing concerns camped out for days or weeks hoping to be near the front of the crowd and thus be selected to discuss their complaint. The fact that their complaint would likely be ignored did not dampen their resolve. They needed to be heard.

Fredrick never gave much thought to what happened before the doors opened. After all, he was the prince. Why should he care about what happened outside of his room?

Then, Rok the Dragon arrived. In early June the dragon started burning crop fields and eating the livestock -- typical dragon activities. However, Fredrick continued to use his system, selecting the subjects from the front of the room.

In late July, Fredrick finally selected a farmer who was there to talk about the dragon. "What is your complaint?" asked Fredrick.

"A dragon ate my farm." the farmer replied.

"A dragon?" Fredrick screamed. "We must act now before it destroys a second farm!"

Silence followed Prince Fredrick's proclamation.

"What is it?"

Fredrick

asked, but nobody responded. Fredrick singled out another farmer and directed the question at him.

"It is just... Well... The dragon has destroyed over twenty farms since it arrived here in June. My farm was actually destroyed six weeks ago."

"Then why am I only hearing about it now?" screamed the prince.

"Noble sir, I have been lining up for six weeks to discuss the dragon. It is only today that you gave me an audience." answered the second farmer.

"How many others are here to talk about the dragon?" inquired the prince. Half the people in the room raised their hands. The prince screamed at everyone in general. Eventually he calmed down enough to send his best knights to run the dragon out of town.

"This will never happen again." the prince vowed. "From hence forth there will be a SYSTEM. Each person will write down their complaint and put it on top of a complaint stack. Each Tuesday from 10 am to 11 am I will take the top complaints off the stack and read them. This way I will always hear the most recent complaints."

Everyone in the room looked at each other. They gave a half-hearted cheer. "Yay."

For the next few months life returned to normal and the Royal Complaint Stack worked about as well as the unorganized mob of people in the complaint room. Then Rok returned. On Wednesday he ate one farm and took a week-long nap.

On the following Tuesday the prince read through the first ten complaints on the stack. All ten were about the refereeing at last Sunday's sporting event. The blue team had lost and its fans were unhappy. The prince had an easy solution and told the steward to bet against the blue team next week. Feeling like he had fulfilled his duty to the people, the prince decided to quit early and play some golf.

The prince found Rok sleeping on the golf course. The prince screamed when he saw the dragon. "What is it doing here? Why was I not told?" He threw his golf clubs at his caddy in frustration and stormed back to the castle.

He was still fuming when he got back to the castle. "I should have been told. Why did no one complain?"

"Your honor" started the steward very carefully. Fredrick picked up on his tone immediately.

"Where is the complaint stack?" he demanded. The steward brought in the stack of complaint papers. The prince started to leaf through them. The top eight were something about food poisoning from today's special at some local restaurant. Under those were more complaints about refereeing. Then he found it. Complaint number thirty one on the stack was about the dragon.

"Curses!" he yelled at the stack of papers.

"No more complaining about minor things when there are important problems!" the prince declared.

The steward sighed. "Sir, how will we tell? The people want to be able to complain about what is bothering them."

"Then there shall be a NEW SYSTEM." Everyone groaned quietly.

The prince retired to his study and began working on the new system. It had to let people voice their frustrations. It had to allow the prince to find the most important issues. More importantly, it could not take too much of his time; he really hated dealing with complaints. He spent three weeks in isolation working on his system.

The following Monday, he addressed his subjects. "I have devised a new system: a priority queue. Each of you shall write your complaints on a piece of paper. Every Monday night, the steward shall read each complaint and assign a priority from 0 to 10. We shall then deal with the highest priority complaints first." The prince paused and waited for the applause. A few subjects clapped lack-lusterly. The steward audibly groaned at his new task. He knew quite well that everyone was going to complain to him about the assigned priorities.

And so the kingdom adopted a priority based complaint system. Over time, the subjects embraced this system. The prince went on to become king and guide his kingdom through a period of unprecedented happiness and quick responses to dragons. Everyone in the kingdom was happy... except of course the steward.

Hunting Dragons with Binary Search

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.

The morning's news was nothing short of dismal. King Fredrick had only been awake for twenty minutes when he decided that today was going to be awful. It had started manageably enough, with his head butler informing him that his favorite crown was still being polished and was not available. However, that news was quickly followed by his chief knight, Sir Braver, informing King Fredrick that a dragon was now terrorizing his kingdom.

"Tell me what happened," commanded the king in a weary tone. He hated dragons.

"There is a dragon," declared Sir Braver.

"You have already told me that part. Now tell me what has happened. Has anyone seen this dragon? Has it attacked anyone?" prompted the king.

“Yes, sir. We have received six confirmed sightings. Farmer McDonald has lost his prize cow."

"The one that won last year’s competition?" inquired the king. If he recalled correctly, it was a sizable cow and would be a perfect target for the dragon.

"Yes, sir," answered the knight.

The king sighed. The story sounded like a textbook dragon attack. Soon the dragon would eat half the cows in the kingdom. "Well, you had better take the dragon hunter and get rid of the dragon."

"But sir, no one knows where the dragon is. How shall we hunt it?" asked the knight.

"Really?" the king asked, surprised that his head knight did not know how to hunt a dragon.

Sir Braver remained silent.

"Find the last farm that it attacked,” said the king. "Dragons take long naps after each meal, so you have time to catch it there.”

"But sir, how will we know where that is?" asked the knight.

"Have you studied dragon attacks at all?" the king asked. "There is an order to these attacks. Dragons are smart. They eat the biggest cow in the area, then the second biggest, then the third, and so forth. They keep eating smaller and smaller cows, until the only remaining cows are too small to be worth the bother. Then the dragon goes on to the next kingdom."

"But sir…" started the knight.

"Use the rankings from last year's cow competition!" cried the king, losing his patience. "They have a sorted list of the largest cows!"

"Ah. Of course, sir. We shall work down the list until we find the dragon!" confirmed the knight.

The king nodded, relieved that the knight was finally thinking on his own. Sir Braver and the dragon hunter would visit the each of the farms on the list, in order, and find the dragon. Even as he tried to comfort himself with this thought, warning bells went off in the king's head.

"Not down the list," the king admonished. "Do you know anything about searching?"

The knight looked confused. He had been certain that he was on the correct track. "But sir, I don't understand" he said.

"How long does it take you to travel between farms?" asked the king.

"A few hours, sir."

"How many farms are on the list?"

"Maybe a hundred."

"That means that it could take you hundreds of hours. By that time, the dragon will have eaten more cows. It might even be gone by then."

"But, sir…"

"Use binary search," commanded the king.

"Binary search, sir?" asked Sir Braver, regretting having fallen asleep in his 'Algorithms for Knights' class.

"Start in the middle of the list and check whether the cow is still there. If it is still there: rip the list in half, throw away the bottom half, and repeat the process on the top half of the list. If the cow is gone: rip the list in half, throw away the top half, and repeat the process on the bottom half of the list. Each time you visit a farm, rip the list in half and concentrate your search on only one of the two halves."

"But sir, that sounds complex," protested Sir Braver.

“It is not," argued the king. "It is simple. If the cow in the middle of the list is still at the farm, then so are all the cows below it on the list. That is how dragons eat. It is not going to eat a smaller cow first. That would be absurd.

“On the other hand, if the cow is missing, then so are all the cows above it on the list. Dragons do not skip around lists randomly. There is an order to these things."

“What if the dragon moves while we are searching?” asked the knight.

Finally, a reasonable question. “Your search effectively tracks two bounds: the smallest cow that you know has been eaten and the largest cow that you know has not been eaten. If you get to a point where those bounds are next to each other on the list, and you do not see a dragon, then proceed to the largest uneaten cow and wait there.”

"But sir, how is that any faster than just scanning down the list?" asked the knight.

The king sighed, again. His confidence in the knight’s ability to handle this task was eroding rapidly. "If the dragon has attacked 45 farms, how long will it take you to scan those farms? 90 hours? But in the case of binary search: after the first farm you will have ruled out 50 farms on the list -- one way or another. After the second farm, you will have ruled out another 25. Each time, you are cutting the problem in half. In fact, you can find the dragon after checking only 7 farms."

The knight nodded, yet looked unconvinced. "But sir, are you sure?"

The king screamed. "Of course I am sure! I am the king! And, further, every idiot knows that binary search is a logarithmic time algorithm while scanning down a list is a linear time algorithm. NOW GO AND GET THAT DRAGON!"

For the first time in his long career as a knight, Sir Braver ran away. He told himself that he was running in order to carry out the king's orders as quickly as possible. But in truth, the king looked really mad.

As he watched his top knight clank noisily down the hall, the king decided that it was indeed time to go back to bed.

For more on binary search also see Binary Searching for Cinderella.