Peter's Address Stamp (or Strings as Arrays of Characters): Part 1 of Peter and the Postal Service

String are sequences of characters. In fact, in many programming languages, strings are implemented as an array of characters. Thus, in many languages you can access each character as you would any value in an array. For example, in C you might write my_string[0] to access the first character and my_string[9] to access the tenth.

Peter's address was composed of exactly three lines and 37 characters:

Peter Fencer

100 Library Way

Alexandria

The first line had exactly 12 characters, the second line had 15 characters, and last line had exactly 10. Peter knew this for a fact, because he had spent the entire morning trying to order an address stamp.

The form was exactly what you would expect a form for an address stamp to look like. It had three different lines for the three different lines of his address. Each line had a neat label, such as "Name" or "City", followed by 15 blank squares. To complete the form, all you needed to do was fill in the squares with the correct letters of your address. It was really quite simple.

But, Peter had now spent three hours staring at the form.

The problem was that the Imperial Stamp and Scale Company charged by the character. Peter wanted to guarantee that he was writing his address in the fewest letters while still maintaining correctness. After the first hour, he had convinced himself that there was no way to safely shorten his name or city. The address was more of a gray zone. He debated shortening the "Way" to a "W", but ultimately decided against it. Avoiding confusion was worth 2 letters.

The other thing that bothered Peter was blank space at the end of the line. Would he be charged for them? The address strings had to allow for spaces as valid characters. For example, the sixth character in the name string was a space that separated his first and last name. He knew how to handle such cases on library forms: depending on the type of form, you either used a special character to terminate the string (a NULL character) or also wrote down the length of the string. It was easy to tell where the string ended. Although Peter logically knew that the company should simply drop the trailing spaces, he was irrationally worried that they would not.

Finally, after spending the morning fretting over the form, Peter mailed it. In 4 to 6 weeks, he would have a brand new return address stamp. He sighed with relief.

He deeply hoped that this stamp would help clear up some of the problems that he was having with his mail. He had recently discovered that his handwriting was so terrible that no one in the post office could read the addresses. His last letter, which was supposed to go to his neighbor, was routed to West Atlantis! Even worse, the same problem applied to the return addresses, which meant that his letters could not even be returned. So, at least this stamp would solve that problem.

What Peter did not realize is that this address stamp was simply the beginning of a long and epic debate over the how strings should be used in delivering the mail.

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

See more of Peter and the Postal Service in Part 2: Incorrectly Delivered Mail and Comparing Strings.

For more more discussion about arrays, see how Zed used arrays in his coffee shop menus.

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.

Arrays, Linked Lists, and Zed's Coffee Shop

Arrays and linked lists are simple data structures that store multiple values in memory. Where these data structures differ is in how they store and allow access to the data. Arrays are like a set of bins with a fixed number of slots. Their structure makes it easy to read from or write to an arbitrary element in the array. In contrast, linked lists are easily extensible chains of data. However, you must scan to the correct location in the chain to read or modify a piece of data in that node.

One year after Zed opened his coffee shop, business was great. Zed had a devoted set of regulars who bought coffee every morning on their way to the castle. They were mostly bureaucrats, specializing in such jobs as counting the kingdom's cattle or copying maps. They loved their coffee.

Then, one day, a competitor opened shop across the street. Zed started losing business to MegaCup’s low prices and flashy signs. Zed knew he had to expand.

Looking over the books, Zed noticed that he sold a lot of coffee in the morning but almost none at night. None of his customers wanted to be jittery as they headed home and went to sleep. Zed needed a new product -- something he could sell at night.

His supplier told him about a new type of coffee coming from the southern region of the kingdom: “Low Jitter Coffee”. Immediately, Zed knew this coffee would solve his evening sales slump. He ordered eight cases.

Zed needed a way to market his new coffee. The sign outside his store read “Coffee” and did not have room for anything else. After a week of intense thought, Zed ordered a new ArrayDesignBoard menu board for outside his shop. The board had four slots where you could slide in menu items to display. He slid in “Coffee” and “Low Jitter Coffee” tags.

The new coffee was a huge success. Zed's business doubled in a week. He added four baristas to the evening shift.

However, Zed’s competition soon caught on. A week later, Zed noticed a new shingle on MegaCup’s sign: “Low Jitter Coffee”. The war was on.

Then his supplier told him about another type of coffee. It was called “Double Bold Coffee”, and it was significantly stronger than the normal brew. A single cup could keep you awake all night. Zed ordered eight cases and a the new menu tag for the ArrayDesignBoard menu.

The coffee was a huge success. His morning crowd loved it. He also started attracting new customers from the castle’s night guards. They needed something strong to keep them awake during their watch.

Alas, it was not long before MegaCup added a new shingle to the end their sign.

The next time his supplier visited, Zed grilled him on the other types of coffee available. After obsessing over the supply lists, Zed decided to try a novel approach. He order one case each of ten different flavors. He put these flavors into a rotation, constantly offering new variety. This approach worked particularly well with Zed’s sign. Every time he switched a flavor, he would remove one tag and slide a new one in. Sometimes he changed the menu a few times in one day, such as replacing “Double Bold” with “Low Jitter” after noon.

MegaCup took a different approach. The manager quickly found that, while adding new shingles to the end of the list was easy, removing them was frustrating. In order to remove a shingle, he had to: unlink it from both the shingles above and below, then reattach the shingle below to the one above. It was a time consuming process. He decided to take advantage of the ability to easily expand offerings. He offered six different coffees on a semi-permanent basis. On rare occasions, he would grudgingly spend fifteen minutes to unlink a shingle on his sign and add a new one.

The two coffee shops operated in that mode for years. Zed’s coffee shop rotated through different options, and MegaCup offered a more constant, but larger, selection.

Both businesses thrived as the market for coffee grew. Eventually, Zed's Coffee House became one of the largest businesses in the kingdom with over a hundred different locations. Zed continued to expand aggressively until the great sugar famine hit. With business dropping due to the lack of sugar, Zed decided to leave the world of coffee and speculate in coconut sales.

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

Interested in learning more about linked lists? See why choose your own adventure stories should never be linked lists. Or, read about Ann's ocean voyage and her insights into linked lists.