The Fairy's Sandbox

Sandboxes are isolated computational environments used for testing or security. For example, a testing sandbox may be a clean installation of a particular operating system and configuration, allowing you to control for the testing environment. Using a sandbox allows you to run code in an environment different from your development environment. Further, a sandbox protects the rest of the computer from potentially harmful effects of the program.

Ferr had barely slept all week. She was too excited. She had been waiting for this day for years. Today was the day that Ferr would finally learn to use her magical powers.

As the youngest fairy in a very large family, Ferr had always been jealous of her older siblings as they flew about and cast various spells. She longed for the day when she too could turn unsuspecting travelers' shoe-laces into worms. That was one of the best parts of being a fairy. Of course, like all young fairies, Ferr had never been permitted to venture outside of the safety of the magically protected kingdom. But, she had heard stories, and they sounded wonderfully fun.

Ferr arrived early to her first lesson. The first hour of the lesson was classroom instruction that reminded Ferr of her "History of the Fairy Kingdom" class. It was horribly dull. The instructor lectured in front of the class in a monotone voice about the origins of fairy magic and the importance of safety. Ferr had heard all of this before. She wanted to get onto the actual magic.

After the introductory lecture was done, Ferr's mentor took her to a practice room buried in the back of the school building. The room was nothing like Ferr had expected. It was a large, but simple, concrete room. It was furnished with a simple wooden table, two plain wooden chairs, a bright plastic beach ball, and a small potted flower.

"What is this place?" asked Ferr. She looked around nervously.

"It is a sandbox." responded her instructor as though that fact should be completely obvious.

"A sandbox?" asked Ferr. She had never heard of this before.

"Yes. You didn't think that we would let you try your magic in the middle of the kingdom, did you?"

"No… but… This does not look magical at all."

Ferr's mentor laughed. "Of course it is not. It is an ordinary room. You supply the magic."

"But, it could at least look magical." protested Ferr.

"The room is simple. That is the important part. You'll see."

Ferr was not sure what the last statement meant, but she let the topic go for now. She followed her mentor over to the center of the room and sat in one of the two chairs.

"First," her mentor began. "You are going to change the color of these flowers from blue to red. Do you know how to do that?"

Ferr nodded eagerly. She had seen her siblings practice changing the colors of flowers all the time. She cleared her mind and tried to concentrate. She gave her wand a quick flick at the flowers.

A large splotch of dark red appeared on the opposite wall. Ferr gasped. She had missed the flowers and stained the wall!

"Oh no!" she cried.

Her mentor did not appear upset in the least. "Try again, but keep your wrist tighter." she instructed.

"But… the wall?" asked Ferr. She had stained the wall. Was she going to be kicked out of school for this? Or banned from using magic? A scary parade of horrible scenarios marched through Ferr's mind.

Her instructor glanced back at the stain. With a quick flick of her own wand, the stain disappeared. "That is why we are in a sandbox." she added.

Over the next hour, Ferr saw the wisdom of the sandbox. Her incorrect spells repeatedly stained, scorched, and pummeled the simple room. To an outsider it would probably have looked as though Ferr had a vendetta against the room itself. But, each time, her mentor calmly restored the room to its previous state. And after 4 hours of practice, Ferr had even managed to turn the flowers a slight purplish.

The rest of the month was the same. Simple spells turned out to be surprisingly hard. And, Ferr repeatedly destroyed the room until she mastered them.

One morning a new surprise awaited Ferr. There, on the table, was a small lizard with a terrible temper. It hissed at her and tried to bite her repeatedly.

"I thought bog lizards could not get through the kingdom's magical protections!" yelped Ferr as it lunged for her. The creature's breath left no doubt that this was indeed a bog lizard.

"They cannot." agreed her mentor. "But we can bring them in here. This room is isolated from the rest of the kingdom. So, we can bring in all the dangerous creatures that we would not want to have running around wildly. You do need to practice dealing with unpleasant creatures, you know."

During that day's class, Ferr reached a new level of room destruction. She even managed to shatter the table. But ultimately, she learned to charm the lizard so that it would not hurt her. Still, the creature's horrible breath made her eager to finish up early.

It took a full year before a junior fairy was allowed to use magic outside of the sandbox, and now Ferr understood why. Ultimately, Ferr gained mastery of her skills and the destruction stopped. She was allowed to start using the magic spells that she had mastered within the sandbox. However, the original glee was replaced by a wiser feeling of caution.

And, Ferr always made sure to test new ideas in a sandbox. She would hate to accidentally turn the wallpaper in her room into fly paper as her older sister had done.

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

If you are interested in learning more about the importance of testing, check out the story of why it is important to always unit test your magic spells:

http://computationaltales.blogspot.com/2011/05/importance-of-unit-testing-magical.html

Learning IF-ELSE the Hard Way

The IF-ELSE statement is a computational construct that allows the program to branch off and execute one of two different blocks of code. The IF statement starts by evaluating a Boolean clause. If this clause evaluates to true, the block of code conditioned on this IF statement is executed. If an ELSE statement is present, it can provide a block of code to execute in the case where the Boolean clause evaluates to false.

Ann had learned the value of IF-ELSE statements at a very early age. When she was only three years old, she was given VERY strict instructions from the castle's head chef NOT to randomly eat things in the kitchen. Specifically, she was told:

IF the food is on the 'finished' table

You can eat it.

ELSE

Do not eat it.

Of course, as any three year old is bound to do, Ann ignored these instructions. She would sneak into the kitchen and eat pieces of fruit off of the chef's prep table. Each time that the chef caught her, he would give her a lecture about obeying the IF statement. His lectures would last a full ten minutes and include at least one remark about "kids these days". Ann enjoyed listening to him describe the branching logic of the IF statement almost as much as she enjoyed sneaking fruit. In fact, some days she even made sure that she was caught so that she could listen to his rants.

Then one day, the chef was preparing eight-chili soup for dinner. As the name implies, the ingredients involved eight different types of chilies, including the ultra-hot Dragonia chili. Unfortunately for Ann, the Dragonia chili looked remarkably like a strawberry. She snuck two, and popped them in her mouth. The resulting pain was intense. Ann's eyes did not stop watering for three weeks. After that, Ann never disobeyed the chef's IF statement again.

As she grew older and more responsible, the chef added a chained IF statement to allow Ann access to a wider variety of food:

IF the food is on the 'finished' table

You can eat it

ELSE IF the food is on the 'raw ingredient' table AND you ask first AND the chef says "yes"

You can eat it

ELSE

Do not eat it.

Having learned her lesson from the chili pepper incident, Ann dutifully obeyed this new expanded rule. Food that was on the finished table was always okay to eat. Otherwise, if the food was on the 'raw ingredient' table, she knew that she would have to ask the chefs first. The logic was simple and covered the important cases.

Of course, those rules still did not stop Ann from trying to trick her younger brother into eating Dragonia chilies. She even succeeded -- twice.

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

For more IF-ELSE fun, see The Marvelous IF-ELSE Life of the King's Turtle.

New at Computational Fairy Tales

The menu bar at the top now contains a link to the FAQ and a link to a list of all the stories grouped by topic. Find all of you favorite stories about computational complexity with ease!

While Loops and Dizziness

WHILE loops are computational constructs for repeating a set of instructions while some criteria condition is true. During each iteration of the loop, the program: tests whether the condition is true and, if so, executes the block of code within the loop.

When I was a child, we played a great game called 'Spinning around'. This game was loosely based on the computational construct of a WHILE loop. In fact, legend has it that this game was invented by some of the earliest computational thinkers.

The rules for the game were:

WHILE you are not dizzy

{

    Spin around quickly

}

Throw up or fall down (or both)

I always won. Or, maybe I always lost. Can anyone ever really win that game?

Paul the Pessimist and the Log N Realization

Big-O notation is a method of specifying the worst-case asymptotic complexity of an algorithm. An O(Log N) complexity means that the algorithm’s running time increases as the logarithm of the input size.

Paul was pessimistic about everything. He fretted that none of his letters would arrive in time and bemoaned the possibility of rain each day. However, his true obsession was worrying about how long tasks would take him. On the day he was scheduled to interview with the Bureau of Farm Animal Accounting, he left his house three hours early to account for potential delays during his 200 meter walk.

Three months into his new job, Paul found himself overwhelmed by the thought of his daily workload. His job as a file clerk consisted of retrieving files for other members of the bureau. Each morning he received a long list of files that he needed to retrieve. Even though he always finished early, his first though each morning was: "There is no way I can finish this."

Luckily for Paul, the Bureau of Farm Animal Accounting: Large Mammal Division was home to some of the kingdom's finest computational theorists. Over her ten years in the bureau, Clare O'Connell had assembled a collection of some of the greatest minds. Thus, it was during a serendipitous lunch conversation that Paul finally came to the Log N realization that would forever change his life.

"There is no way I can finish finding all of these papers," Paul complained for the fifteenth day in a row.

Sid groaned. He was tired of hearing the same pessimistic complaint every day.

"Sure you can," Sid assured Paul. "You do it every day."

"But, today's list looks bigger," responded Paul.

"How much bigger?" asked Sid. He was determined to end Paul's complaining today.

"I don't know. Maybe two more files." answered Paul.

"And how long does it take you to find a file?" inquired Sid.

"Well, usually not that long. But it COULD take a long time! Imagine if I cannot find the correct location. I could spend hours on a single file!" Paul started to panic.

"No, you couldn't." Sid laughed. "The files are all sorted. Right?"

"Yes." answered Paul. He was unsure why it mattered.

"And you use a binary search to find the files, right?" prompted Sid.

"Yes," answered Paul.

"Then you are all set. Binary search is an O(log N) algorithm." explained Sid. The matter thus resolved, Sid went back to eating his pie. It was key-lime pie today, which was Sid's third favorite flavor.

"I am not sure what that means," admitted Paul. "Couldn't it still take hours? What if they add another filing cabinet? I heard a rumor that they might merge in the files from the Small Mammal Division. They have over twice as many files as we do. Do you know how many chipmunks there are in the kingdom?"

"You are looking at it wrong," answered Sid. "Big-O notation gives the WORST case solution."

"But Log N can still be big, right?" asked Paul.

"Sure. In theory log N can grow large. But it takes an absurdly large value of N." answered Sid. "In binary search, each step chops the problem in half. If you have 1,000 files: after the first step you have limited it to 500 files, then after the second step you have 250, then after the third step 125, and so on. That means if you double the number of files to search through, you are only adding one more step. Log N algorithms are wonderful! You would be fine if they merged in the small animal division, the insect division, the fish division, AND the bird division. You still would only add a few more steps to your search."

Paul gasped at the thought of so many files. As the panic started to build inside him, he focused on what Sid had just said. As long as he continued to use a Log N algorithm, they could double the number of files several times over, and he could still get his work done on time. With that thought, life did not seem so scary anymore. He wanted to stand on the table and sing for joy.

"Wow. You are right." Paul said. "It is not that bad. Do you have any other advice?"

"Yeah. Don't let them double the size of the list." offered Sid. "Even though it is O(Log N) to find each file, you still have to search for each one. If you have M files on your list, finding them all is O(M * Log N) time."

With that one statement, the pit of dread returned to Paul's stomach.

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

If you are interested in learning more about Big-O Notation, check out the story of how Clare used the computational complexity to shift the balance of power in the wizard's war.

Minimax Search and the Oracle of Old Toronto

Minimax search is an algorithm for determining which action to take in a multi-player game. The algorithm literally searches through all different sequences of moves, looking for a series of moves that will maximize its performance. At each point in the search, the algorithm considers the current game state (e.g., chess board configuration) and all possible moves from that state. In order to determine which move the current player would (or should) make, the search recursively branches off and tries ALL possible moves. The algorithm continues to search further and further into the future, until it reaches a state indicating the end of the game and determines who would win from that sequence of moves. The algorithm can then pass the outcome back to the previous state and use it to determine what move the player would make at that state. Specifically, if the current state represents the opponent's move: the algorithm assumes the opponent will choose whatever move is in their best interest. And, if the current state represents your move: the algorithm chooses the move that is best for you. By using the computed outcomes of each move (assuming the opponent will play as well as possible), the algorithm can choose the move that is best.

The war with West London was not going well. The armies of Old Toronto were stretched too thin, and the supply lines we cut off. If something did not change soon, the province of East Shore would be lost.

General Grimm was sitting in his command tent studying maps when the oracle arrived. Despite having heard the tales since he was a child, General Grimm was still shocked when he saw her. She was at least ninety years old and dressed like a punk rocker. She wore ripped jeans and a Bronze Maiden '32 teeshirt. Her snow white hair was in a perfect mohawk.

"Madam Oracle." he started.

"Hi" she replied while looking around the tent. She noted that there was nothing of value to take.

"Our forces are in trouble. We are stretched too thin, and our supply lines have been cut off. We need your guidance." the general pleaded. He had heard stories about the tribute demanded by the oracle. During the battle of South Atlantic she had demanded that the commander organize a three-stage, two-day concert. But, General Grimm did not have the time or men to organize a massive party for her. He was desperate.

"Okay." answered the oracle.

"Well... then..." stammered the general. That was too easy.

"You are waiting for my demands. Aren't you?" The oracle asked. She had seen this before, and frankly she was tired of the reputation she had earned during her party days. Now she just wanted to get this over with, go home, and take a nap. "I don't do that anymore." she clarified. "Show me the maps."

The general pointed to the maps on the table. They showed his army stationed a few miles from the Farnough Castle. The castle was the largest West London stronghold in the region. He had been planning on trying to take the castle the next day.

"That will not work." replied the oracle simply.

"Why not? We can take the castle! They do not have provisions to withstand a long siege." argued the general.

"True. But, if you do that then they will march their reserves south and attack Hampton. You will be forced to divert your forces to protect the city. And, they will move in their northern armies to take Old Toronto. You will lose in 26 days."

"How do you know this? Have you seen a vision?"

"No. I do not see visions. I am not the Oracle of Delphi with her magic, her prophecies, and her irrational love of marching bands. I actually work for a living." This was obviously a sore point for the oracle.

"Then, how do you know?" pressed the general.

"It is simple. Look at the possibilities at each step. Once you attack the castle the forces of West London only have three options. First, they could send troops to free the castle. Second, they could attack Hampton. And third, they could do nothing. Doing nothing would obviously mean they lose, so we can discard that possibility. Sending troops to free the castle would work, but would deplete both your armies. It would only stall any real progress. Finally, there is attacking Hampton. If West London attacks Hampton: you then have three options. You could defend Hampton, attack one of their cities, or do nothing. Doing nothing means you lose Hampton. Attacking one of their cities would require a two week march, and during that time Hampton would fall anyway. So, you would have to defend Hampton. And once you send your troops to defend Hampton, the capital of Old Toronto is unprotected and West London will obviously conquer it. The end."

As the oracle spoke, she drew out a branching diagram on a piece of paper. At each branch point she put a little note, such as "Your armies outside castle, their reserves attacking Hampton." Each branch represented a decision that either he or the West London commander could make at that point in the battle.

"But... If I attack one of their cities maybe they would pull their troops back from Hampton" the general reasoned.

"No. Because, once you send your troops they could just take Old Toronto and win. Why would they miss an opportunity to do that?" As the oracle answered, she added the new branch to the diagram. At the end of the branch she drew a little diagram of Old Toronto on fire. She liked illustrating things.

The general was at a loss. The logic was sound, but depressing.

"So what do I do?" he asked.

"Obviously, you do not attack Farnough Castle." the oracle resisted adding a "you idiot" at the end. During her years of service, she had found that generals did not like being called idiots. In fact, she avoided calling anyone above the rank of second lieutenant an idiot. It was safer that way, and that still left more than enough people for her to call idiots.

"Instead, you attack the village of Antoch." the oracle declared.

"Why? That is a small cattle village. There is no strategic value there. Even the cattle are rather sickly looking."

"True. But West London will still need to rush to defend it. Otherwise, they will not be in place to stop you from taking Antoch." explained the oracle.

"So, we will win at Antoch?" asked the general.

"No." replied the oracle. "But, that battle is not important relative to the war. Once West London has moved their reserves troops to Antoch your can move your reserves to West Antoch. From there they will split the garrison at Farnough Castle. You can withdraw and march on East London. They will combine the divisions at Antoch and West Antoch and follow your reserves to East London. You can then take your main army and conquer West London. It will take 91 days and a few battles. But you will win." She continued to draw out the various battle states and branches as she spoke. Occasionally, she would add another branch with an obviously bad ending to illustrate why the general would want to make a particular move.

The general was stunned. This plan was so far in the future and required so many of the "correct" enemy responses.

"What if they do not follow the plan?" he asked. "What if they do not defend West Antoch."

The oracle thought for a second. "Then you win in 67 days. You will march from West Antoch to East London to West London. It is better for you."

"But, what if they do something else?" he asked.

"Then you win quicker. Defending West Antoch is the best that they can do. Any other move will play out worse for them and better for you."

The general looked confused. "And, you have not seen this in a vision?" he confirmed.

"No. I am just playing out all possible scenarios."

"All scenarios?"

"Yes. Every single one. I take EVERY possible move that you could make and determine which is best based on ALL the possible sequences of moves that follow. I do the same for West London assuming that they will make the best moves they can." explained the oracle. "I keep going back and forth, testing each move and response until someone has won."

"But what if they do not make the best moves?" The general looked worried. He did not like the idea that his success depended on him facing a skilled opponent. Despite the fact West London was winning, General Grimm still regarded them as dullards.

"Then by definition it is worse for them and better for you. I have determined how good each of their moves is by the best move you could make in response. And, I determine your best move by assuming that they will make the best move in response. If they do not make the best move in response, then they have to have made a worse choice. As long as you keep making the best moves, they cannot cause you to lose by fighting poorly."

The general still looked unconvinced.

"Consider Tic-Tac-Toe." continued the oracle. "What do you do if it is your turn and your opponent has two boxes in a row?"

"Block them?" the general answered hesitantly.

"Yes. Because you assume that if you don't, they will take the best move for them and win. So, can they throw you off by playing poorly? What if they don't block you when you have two in a row?" pressed the oracle.

"Umm… I win." answered the general.

"Exactly!" Excitement burned in the oracle's eyes as she spoke. She did love her work. "All that you need to do is play out all possible sequences of moves. Always assume the opponent will try to do their best and do the best move in response."

"And this is your skill?" the general asked. He realized he was probably being insulting. But this sounded more like logical reasoning than being an oracle.

"Yes." sighed the oracle. "My power is the ability to very quickly play out all of the scenarios in my head." She paused. "When I was younger I played up the magical aspect of my skill on purpose. It got me invited to the best parties."

"Oh." The general looked down uncomfortably at his shoes. He was acutely aware of the fact that the oracle's skill was that she was much better at his job than he was.

"So... Antoch?" confirmed the general.

"Yes." confirmed the oracle.

"Um... well then... thanks. I can take it from here." The general felt the need to reassert his authority. After all, he was the general. As the oracle turned to leave he quickly added "You know, next time it would just be less awkward for you to act all magical and have outrageous demands."

"Next time I will go back to that." she agreed. The oracle smiled as she left. Next time she was going to demand her own castle.

The Importance of Unit Testing Magical Spells

Unit tests are small tests designed to exercise specific components of a program, such as individual functions. The goal is to test components in isolation, allowing for: more targeted and thorough testing, quicker detection of errors, and finer grained debugging. Further, ensuring the correctness of the low level building blocks helps to better ensure the correctness of the overall program. Unit tests can also easily detect low level errors that might be masked by other logic in the program.

Marcus did not become a master wizard by being lazy. Unfortunately, it seemed as though the apprentices these days did not appreciate the value of hard work. His newest apprentice, Shelly, was obsessed with moving onto complex spells.

"You have to master the fundamentals first." Marcus insisted.

"But, I already know the fundamentals." Shelly responded petulantly.

Marcus sighed. Kids these days were so difficult. In his day, an apprentice did not argue with his or her master. You listened and were respectful. Why was everyone suddenly so impatient? Marcus blamed the latest pop culture fad: marching bands. Sadly, there was only one way to reinforce the value of correct building blocks.

"Okay." Marcus responded. "Today we will do the spell of Transmogrified Mold, which transforms ordinary house mold into a candy. It is a complex spell that requires six potions and three hours. Are you able to handle that?"

"Yes!" agreed Shelly readily. She was visibly bouncing with excitement.

Marcus smiled as he handed her the directions. "Here you go then. There should be plenty of mold in the kitchen. I believe a certain apprentice has not cleaned there in weeks."

Ignoring the comment, Shelly ran off to the kitchen to begin the spell.

The key to the spell of Transmogrified Mold was correctly making each of the six potions. If any one of the potions is off by even a little, the product is a complete failure. Granted, the result will still look, taste, and smell like chocolate. However, it will cause three hours of intense nausea and powerful hiccups. Together, those turn out to be a most unpleasant combination.

While Shelly buzzed around the kitchen working, Marcus decided to take a nap. No need to remind Shelly to test each potion individually. By this point in her training, the value of testing should be ingrained. Of course, young apprentices always complained that testing their potions slowed them down too much. But, there was really only one way to learn the value of unit testing potions.

Three hours later, Marcus was woken by the sound of loud vomiting. "I believe she is done." he mumbled to himself as he made his way down to the kitchen.

There he found Shelly, with her head in a bucket.

"How did it go?" he asked.

"I don't know what went wrong." moaned Shelly between hiccups.

"Well, let me just see." offered Marcus. He wandered over to the counter and started testing the individual potions.

The first three were correct.

"Ah. Too much vinegar in the fourth potion. Common mistake. My guess is that you did not notice, because there is too much salt in the last potion. Yep. There it is. All very common."

"But, they all looked correct." Shelly protested between powerful hiccups. "And the end result seemed to work out."

"You will be fine in another two hours and fifty three minutes. Until then, I would recommend keeping a bucket close." Marcus advised.

He paused at the door on his way out. He did not look back as he spoke. "And in the future, I would encourage you to thoroughly test each individual component of a spell. You need to make sure the fundamentals are correct before building off of them. Otherwise, you can find unpleasant surprises."

The Valley of NAND and NOR: Part 3 of Ann's encounter with the Booleans

NAND and NOR are Boolean logic operations. They are negations of AND and OR respectively. NAND (Not AND) evaluates to true if and only if at least one of the inputs is false. NOR (Not OR) evaluates to true if and only if both inputs are false.

After leaving the wizard's resort and completing her trek through the Lagrange mountains, Ann came to the Valley of NAND and NOR. She had heard rumors that it was a most disagreeable place, filled with negative people. The valley itself certainly seemed to uphold this reputation. It could only generously be described as a desert oasis. A more accurate description would be two small villages on either side of a large muddy puddle.

Ann considered passing by the villages without stopping. Her experience at the wizard's resort had left her feeling bitter. But, her horse needed water and Ann herself was tired. She decided to try the village of NAND first.

"Hi." Ann began cheerfully as she walked up to the counter at the village's only inn. "I would like a room for the night and some dinner, please." Ann smiled broadly, hoping to set a cheerful tone.

"No." responded the inn keeper. "One or the other." She pointed behind her to a sign on the wall that read: 'NAND INN - Providing a room, or dinner, or neither.'

"But, that does not make any sense." objected Ann.

The inn keeper shrugged. "That is how we do things in NAND. If you do not like it, you can always try NOR. They are really nice over there." She laughed as she spoke.

"So, I can NOT have a dinner AND a room?" Ann confirmed.

"No!" The inn keeper was most rude.

Frustrated, Ann left the inn and started her journey to NOR on the other side of the mud puddle. She had heard that the villagers in this valley were descendants of the Booleans, but she had hoped that they did not adhere quite as strictly to the Boolean's beliefs. If anything though, the people of NAND seemed worse!

It took an hour before Ann arrive at NOR's inn.

"I would like a room for the night and some dinner, please." Ann asked the inn keeper. This time Ann was too tired to pretend to be overly cheerful.

"No." he responded. Without any additional explanation, he pointed to a sign on the wall that read: NOR INN - Providing no rooms or food.

"Wait." Ann objected. "You are telling me that this inn does NOT provide rooms OR dinner? What sort of an inn is that? What do you provide?"

The inn keeper shrugged. "If you don't like it, you can always try the village of NAND."

Ann stormed out with responding, and left town. NAND and NOR were just as negative as everyone had warned. As she looked back at the two villages disappearing into the distance, she hoped that the next place she went would not be filled with Booleans.

The Gates of XOR: Part 2 of Ann's encounter with the Booleans

XOR is a binary operation that evaluates to true if exactly one of its inputs is true. Formally, A XOR B = (A AND NOT B) OR (NOT A AND B). XOR is used as an operation in a variety of computer programming languages as well as low-level machine operations.

As she left the town of Bool, Ann realized that she would have to face the gates of Xor. The gates of Xor stood in front of a small pass through the Lagrange mountains. While it was possible to simply walk around the Lagrange mountains, it would add another 500 miles to Ann's journey. The mountain pass was the obvious choice, but the gates were known to be highly dangerous. Either you were allowed to pass through the gates, or you were dropped into a pit of spikes. As with everything in the town of Bool, there were only two completely opposite outcomes.

The gates of Xor were a classic example of the complete adherence to binary logic that the Booleans had long embraced. Boolean wizards had built the gates such that they would only allow the people whom they judged worthy to pass. Specifically, the gates were rumored to evaluate two characteristics: Intelligence and strength. Both characteristics were evaluated in a completely binary way; you were either weak or strong. However, no one understood how the gates actually used these criteria to judge the travelers. The wizards that had built the gates had never explained their reasoning, and they had disappeared shortly after construction was completed.

Ann walked up to the gates and tentatively placed her hand on the evaluation panel. She was nervous. She understood the danger all too well. But, her quest came first; and she needed to take this short cut.

With a loud click the gates unlocked and opened. Breathing a sigh of relief, Ann walked through and into the mountain pass.

Ann had walked about a mile when she came upon a completely unexpected sight. There, nestled in the mountains, was a lavish resort filled with wizards. Wizards lounged by the pools, played beach volleyball, and were generally having a good time. Ann stood in shock, until an old wizard approached her and introduced himself.

"What is this place?" asked Ann.

"A wizard's resort." answered the wizard.

"But, it is completely hidden." stated Ann. "I have never heard of this place."

"Of course not." laughed the wizard. "We built the gates of Xor to ensure that. No-one that passes through the gates is a threat to us."

"Excuse me?" asked Ann, offended by the wizard's statement.

The wizard smiled broadly. "I mean no offense. It is just a matter of binary logic. We constructed the gate using two attributes, strength and intelligence, and an xor function. A person can only pass through if they have exactly one of the attributes. Basically, they need to be (strong AND NOT intelligent) OR (NOT strong AND intelligent). That is how we created the gate."

"But how does that protect you?" asked Ann.

"Let's look at the 4 cases:

1) If you are smart and strong: then you are a real threat. So, we do not let you pass.

2) If you are strong and dumb: then you only think you pose a threat. We can use your overconfidence to cast a spell of confusion. So, you are really no threat; and we let you pass.

3) If you are weak and smart: then you pose no threat, because you are smart enough to know that you cannot win in a fight with us. So, we let you pass.

4) If you are weak and dumb: then you will probably go tell your big friends where to find us. So, we do not let you pass.

It is all very simple."

"But that means…" started Ann.

"That you are either weak or dumb." finished the wizard. "Either way, you are not a threat to us. Now, off you go." As he finished, the wizard started to push Ann down the path out of the village.

"But… but…" objected Ann. She was definitely offended now. But, given the fact that a frail-looking wizard in his late eighties was pushing her down the road with seemingly super-human strength, she was smart enough to know that she would not win this fight.

"Off you go," repeated the wizard.

Suddenly, a thought came to Ann. "You could help me in my quest." she suggested.

"We don't do that." answered the wizard. "That is why we built a secret resort in the middle of the mountains, so that we do not have to help with quests... or perform at birthday parties. Now go on."

As Ann walked away from the wizard's resort, she wondered whether the short cut through the Lagrange mountains was worth the insults.

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

Read Part 3 of Ann's encounter with the Booleans in The Valley of NAND and NOR!