Sharpen your Coding Skills - Elevator Puzzle
Written by Joe Celko   
Article Index
Sharpen your Coding Skills - Elevator Puzzle
Answer

Introducing Melvin and Bugsy, characters who figure in a series of challlenges from Joe Celko. Sharpen your coding skills with puzzles that will both amuse and torment you.

Joe Celko is best known as the database expert who writes  books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code. Put on your thinking cap as we assist Melvin Frammis and the rest of the programming staff at International Storm Door and Software write beautiful code in whatever programming  language they have.

 waitingelevator

The Elevator Problem

“Bugsy, what are you doing?”

asked Melvin Frammis as he came to the lobby of the company office. Bugsy Cottman is a junior programmer at International Storm Door & Software, where they both work., Bugsy often makes up for his lack of skill with blind enthusiasm and today he was disassembling the control panel of one of the elevators.

“I am going to automate the elevators, and speed up travail time. It can save us millions in lost employee time!” replied Bugsy.

“Was there a problem?”

“Of course!”, said a mildly vexed Bugsy.“Did you notice that when you want to go up, the elevator is going down, and vice verse?”

Melvin shook his head. The odds of getting an elevator going in one particular direction depends on the floor and its not 50-50 as you might think.

Imagine a two story building; the lobby elevator is going up 100% of time and the top floor elevator is going down 100% of the time.

“I got a speech gizmo and a badge scanner so that when someone steps into the car, we can read their floor from the badge and tell them to get on or off at a floor until they get to where they want to be.” said Bugsy.

“That is not much of an improvement over a button and the built in scale to count the number of people we have now” Said Melvin, looking for the stairwell door.

 “But I am writing a program that will optimize overall travel time by telling people to get on and off the car, even if they are not at their destination floor. Here is the spec:

  1. The building has (n) floors numbered from one to (n)

  2. The car holds (p) passengers.

  3. Exactly (p) passengers want to get to each floor.

  4. The passengers start off randomly distributed over the floors and there are (p) of them on each floor.

  5. The goal is to minimize the total distance the car travels measured in floors.

 “This is a sorting problem with some weird restrictions” said Melvin. “I might get to a floor, get out and then get back on when the car comes to me again. I am not sure if people will like that.”

 “Hey, I want to save elevator time, not worry about those silly-ass 'people skills' my stupid boss says I don't have!”

“Bugsy, when you put out the fire, come on up and I will write a short program you. You are not old enough to recognize it, but this is what is known as a bi-directional one-tape sort. We will just use one dimensional arrays, say, ten floors and five passengers per floor and in the car. ”

Bugsy said, “What is a tape drive? And what fire?” as he looked up and saw the answer to his second question in the form of smoke coming from the wall of the elevator.

There is nothing more dangerous than a programmer with a screwdriver,

 

karpindicator

 

When you are ready turn the page to read the answer.