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.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.