Sunday, November 20, 2011

Coming Soon (or Maybe Later)

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

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

What to expect from the collection:
  • A few new stories - Covering some earlier concepts and filling in the gaps.
  • More details of Ann's quest.
  • A reasonable ordering (both by concept and plot)
  • Extensive editing - At least 10% fewer gramatical errors!
I am planning on continuing adding new stories here, but with a slightly lower frequency than before. I am also cleaning up and even rewriting stories as I go. Admittedly, a lot of the stories are still in very rough form and could use a round or two of reworking.

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

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

Thursday, November 10, 2011

Names for Ingredients (and Variables)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The clerk did not respond.

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

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

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

"But it is shorter." tried the clerk.

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

"You have?" asked the clerk.

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

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

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

The clerk hesitated.

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

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


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

Wednesday, November 2, 2011

Recursion, Overhead, and Computational Graffiti

Recursion can allow a complex algorithm to be specified in a short, simple, and often beautiful form. A function calls itself on a subset of the data, using the results from those subproblems to form the final solution. However, Recursion can also add computational overhead due to the new recursive function calls.

On her way to the library of Alexandria, Ann could see the signs of chaos engulfing the kingdom. The traditionally smooth operation of the kingdom's services inefficiently squeaked along under the burden of additional complexities. Overhead the pigeons of the kingdom's vast carrier network flew about aimlessly. The postal carriers had given up sorting the mail before embarking on their delivery routes. Instead, they stood in front of each mailbox and flipped through their full bag to find that house's letters. Everything was a mess.

Ann first noticed the computational graffiti in the outskirts of Alexandria. Initially, it looked harmless -- the rebellious proclamations of teenagers: "DFS Rulez" or "Dynamic Programming FTW". The signs soon became more troubling: "Say 'No' to Big-O" and "BRUTE FORCE ALGORITHMS FOREVER". At first, Ann thought these signs were jokes. Who would argue against an efficient algorithm? The absurdity made them almost unbelievable.

Then Ann saw a message that stopped her cold:
int RecursiveAdd(int n, int m) {
if (m == 0) return n; // base case
return RecursiveAdd(n, m-1) + 1;

The recursive algorithm for adding two numbers covered the entire North wall outside a Florist's shop. While technically valid, the sheer inefficiency of the of the approach shocked Ann. Why take a simple mathematical operation, m + n, and embed it within a chain of m function calls? The overhead was staggering. The graffiti clearly pointed to the complete collapse of computational thinking.

Tearing herself away from the disturbing image, she broke out in a full run. There was no time to lose.