Hello everybody

I'm a student and having problems with an assignment - I have at the moment no idea how to achieve an appropriate solution.

I'm aware that you shouldn't help me by showing some code. That's okay for me since I want to solve it by myself but I think it would be helpful when I get a small hint how to think about this problem here:

Write a simple program that controls an elevator in an office building. The
office building has 24 floors (0--23) and 3 elevators. The floors are 3m
heigh and the elevators move with 6m/s. Opening and closing the elevator
doors costs 6 seconds each.
Let's assume that all elevators are parked on the ground floor(0) and that
the doors are open. If a passenger wants to get from the ground floor to the
top floor (23), it would take 6sec (closing) plus 23*3/6sec (moving the
elevator) plus 6sec (opening) the door (=23.5sec). Total delivery time
would be 23.5sec.
Assuming that after 10 seconds another passenger requests an elevator on
the 10th floor (also going to the top floor), you have two options, reuse the
first elevator (which currently is on the 8th floor) or send a different one. If
you reuse the first elevator, it would arrive at second 11 on the 10th floor,
open its door take in the passenger (sec~17), close the doors (sec~23),
move to the top floor (sec~29.5), and open the door (sec~35.5). Total
delivery would be 35.5sec+25.5sec.
Had you used another elevator, the total delivery time would have been
23.5sec+29.5sec (close door (sec~16), move to floor 10 (sec~21), open
door (sec~27), close door (sec~33), move to top floor (sec~33.5), open
door (sec~39.5)).
Your program should read the information about passengers from a file passed as command line paramter
(or cin if '-' is passed as filename). The file contains one line per passenger. Each line contains a triple of
time-of-request, floor-of-request, target-floor-of request. For determining the elevator to use for a given
passenger only consider whether the passenger is going up or down and not the target floor. The target
floor is only considered once the passenger got onto the elevator.
For instance in the above case, the file would look as follows:
0,0,23
10,10,23
Your program should output something similar to the following
0: passenger 1 request on floor 0 handled by e1
6: e1 door closed, moving up (p1-23)
10: passenger 2 request on floor 10 handled by e1
11: e1 stopped on floor 10
17: e1 door opened
23: e1 door closed moving up (p1-23, p2-23)
29.5: e1 stopped on floor 23
35.5: e1 door opened (p1-35.5s, p2-25.5s)
Total delivery time is 61s.

Here is my code so far:

main.cpp

#include <iostream>
#include <fstream>
#include "elevator_system.h"


using namespace std;

int main (int argc, char * const argv[]) {
    
	elevator_system supercomputer;
	string input = argv[1];
	
	// reads from commandline
	if (input == "-") {
		
		bool exit;
		
		while(!exit){
			// get the input string
			string input;
			cout << "Triple: ";
			getline(cin, input, '\n');
			
			if (input == "q") {
				exit = true;
				break;
				
			}
			supercomputer.transform_input( input );

		}
		
		//print_array();
		supercomputer.moving_elevators();
	}
	
	// reads from file
	else {
		ifstream in_stream;
		
		in_stream.open( input.c_str() );
		// check if the file is open
		if ( ! in_stream.is_open() )
		{
			cout << "opening file \'" << input << "\' failed." << endl;
		}
		
		string tmp;
		
		// stream reads a word each iteration
		while( in_stream >> tmp )
		{
			supercomputer.transform_input( tmp );
		}
		// close file
		in_stream.close();
	}
	
}

elevator_system.cpp

/*
 *  system.cpp
 *  c++_06_ex2_elevator
 *
 */

#include "elevator_system.h"

building build1("building1", 24, 3);
elevator el1("el1", 6.0, 0);
elevator el2("el2", 6.0, 0);
elevator el3("el3", 6.0, 0);

static double action[50][3];
static int row_counter;
static int timer;

elevator_system::elevator_system() {
//
}

void elevator_system::transform_input( string input ) {
	
	int first_coma;
	int comma_counter = 0;
	string str;
	
	// we iterate through the string
	for (int i=0; i < input.length(); i++)
	{
		str = input.at(i);
		
		if (!str.compare(",") && comma_counter < 1 ){
			comma_counter++;
			first_coma = i;
			
			stringstream Stream;
			Stream << input.substr(0, i);
			int first;
			Stream >> first;
			
			action[row_counter][0] = first;
			
			
		} else if (!str.compare(",") && comma_counter == 1) {
			
			stringstream Stream_second;
			Stream_second << input.substr(first_coma + 1, i);
			int second;
			Stream_second >> second;
			
			action[row_counter][1] = second;
			
			stringstream Stream_third;
			Stream_third << input.substr(i+1, input.length() - 1);
			int third;
			Stream_third >> third;
			
			action[row_counter][2] = third;
			
		}
		
	}
	row_counter++;
}	

void elevator_system::moving_elevators() {
	
// no idea how to use the splitted triple to determine which elevator should be used and how to print it correctly
}

elevator.cpp

/*
 *  elevator.cpp
 *  c++_06_ex2_elevator
 */

#include "elevator.h"

elevator::elevator(string el_name, int el_speed, int floor) 
: name( el_name ), speed( el_speed ), floor_right_now( floor )
{
	door_is_open = true;
}

string elevator::get_name() {

	return name;
}

double elevator::get_speed() {
	
	return speed;
}

double elevator::open_door() {

	door_is_open = true;
	return 6.0;
}

double elevator::close_door() {
	
	door_is_open = false;
	return 6.0;
}

// time to move from one floor to another without door opening / closing
double elevator::moving_time( int target_floor ) {

	return ( ( target_floor - current_floor() ) * 3 ) / get_speed();
}

// total time to move from one floor to another including door opening / closing
double elevator::total_time_to_move_to(int target_floor ) {
	
	static double total_time = 0;
	
	if ( door_is_open ) {
		
		total_time = close_door() + moving_time( target_floor ) + open_door();
		
		
	} else {
		
		total_time = open_door() + close_door() + moving_time( target_floor ) + open_door();
	}


	set_current_floor( target_floor );
	
	return total_time;
}

int elevator::current_floor() {

	return floor_right_now;
}

void elevator::set_current_floor( int end_floor ) {
	floor_right_now = end_floor;
}

I've managed to read in a triple and split it correctly into three integers and put them into an array. But I have no idea how to proceed with this input after I read all in from the cin or file... I thought maybe I should decide for every tripple what to do and then put that decision into a queue and print the queue afterwards but that's seems to be a strange way for me.

Edited 5 Years Ago by Airlike: misspelled

Are you having trouble with the logic of the elevator operation or some syntactical thing about how to pass your array?

A small note: bool exit; - you should not use 'exit' as a keyword. It is very likely used in other libraries etc. I know exit() is usually a valid way to terminate a program.

Edited 3 Years Ago by mike_2000_17: Fixed formatting

Hi daviddoria, thanks for helping.

My problem is that I'm not sure how to proceed with the information I have so far. How can I handle every possible case and how can I store each decision, so I can print it afterwards properly?

Like in the given example (in the quote): how can I store the information, that elevator 1 will have two persons?

I think I don't know which tactic here will fit but I think first I need to check somehow all the given triples from the file or cin and then start checking which routine would be the best. But as said, I have no clue how to manage this...

Your idea of a queue is a good one, but make it more general. Make the queue of the form: <time, pointer to event>. 'event' is a struct that can hold the information of all the event types. For the most part 'events' are the physical events that can occur with people riding elevators (or empty elevators moving floor to floor, opening doors etc). Some events will cause other events to occur later in time, so when that happens you add those future events to the queue.
The way the pgm proceeds is to load the initially 'known' events into the queue, set the 'current virtual time' to zero, and then search the queue for the event with its time the least time after (or equal) the current time. Advance virtual time to the time of that event. Process the event, printing out info about it if thats appropriate, then repeat until the queue has nothing left.

Hint: past elements in the queue are no longer needed, so you can re-use their storage space for new events if you want. Simplest is just make the queue space very large and don't bother to re-use it. Same is true of event space.

Break everything down to small events because you want an event to always proceed to conclusion without being interrupted. For example if you send an elevator 5 floors you might have to interrupt it to pick up someone who arrived after the elevator departed - thus making the arrival event that you put in the queue have the incorrect time. So just send it one floor at a time. A good general rule is that if you find yourself modifying events in the queue, you've not structured the program correctly.

This general approach is used for a large fraction of simulations in the time domain. When the problems get complex one needs a more sophisticated organization of the queue so you don't waste lots of time searching it. Event and queue space have to be recycled, etc.

Comments
Great reply!

Hi errntknght

many thanks for your help - finally I have a plan in my mind's eye. Also the general rule about modifying events in the queue is really helpful!

I'll try to use this idea in my program and will show my progress here again.

Hello

I finally found some time to deal with this problem here again. I still think the way which errntknght described in his post seems to be a good one.

But I have some (trivial) problems.

How can I create a queue of the form: <time, pointer to event>?

I think I will create the struct "event" somehow like that:

struct event {  
    int   start_floor;
    int   target_floor;
    double arrival_time;
  }

This is just a "prototyp", I will find out the necessary information I need for the struct by trial-and-error as soon as I figured out how to create the queue.

@errntknght, it seems you understood the problem quite well, because all problems which may appear you have already mentioned in your post. You explained a certain problem as well: For example if you send an elevator 5 floors you might have to interrupt it to pick up someone who arrived after the elevator departed - thus making the arrival event that you put in the queue have the incorrect time.

I am now confronted with this problem but don't understand your suggestion here. Can you please explain that again? Assumed there is a passenger at floor 0 and he requests at time 0 an elevator to bring him to floor 23, I have to insert the request-event "passenger 1 requested elevator at time 0" at the time 0 and the future-event "leaves the elevator after xy seconds on floor 23" into the queue at the time xy. But when some seconds later another request occurs and the same elevator will handle this request, the future-event for the first passenger ("leave the elevator after xy seconds on floor 23") isn't correct anymore, as you already explained it. But I don't get it how to handle this situation :(

thanks so far for everything!

Edited 5 Years Ago by Airlike: n/a

A queue can take a variety of forms, the simplest would be an array large enough to hold all the <time, event_pointer> structs you'll need for the whole problem. Create a collection of functions that perform the operations on the queue so you can change the details of queue handling without disturbing the rest of the program - the concept behind object oriented. addQelement() and findnextQelement() may be all you need.

The problem of elevator flights being interrupted by new arrivals on passed floors is dealt with by breaking flights down to one floor at a time - instead of making a flight from 0 to 25, make it a flight from 0 to 1 with a final target of 25. When the elevator gets to floor 1, if someone is waiting to go up, load that party then whether someone is loaded or not, create a flight from 1 to 2, destination 25. Yes it creates 25 flights instead of 1, but the problem of loading and unloading at a variety of floors is dealt with easily. The key to writing robust simulators is to break complex 'events' down to the simplest form - many simple 'events'. You've got it sufficiently simplified when every event runs to conclusion without alteration or interruption. Don't worry much about having lots of events - thats what computers are good at dealing with.

It may have occured to you that the destination floor is not really part of the event going from 0 to 1, or 1 to 2. Thats a sign that it should be isolated from the events. In this case you create an object/struct for each of the elevators and the elevator struct holds the information of its current destination (and probably other information as well) The events reference the elevator in question.

Thinking about real elevator systems they have switches at each floor that signal passengers waiting to go up and to go down. Make a struct per floor that hold that information and when there is an arrival event at a floor, that floors struct is examined for the existence of passengers awaiting. The system has to maintain an awareness of all waiting passengers so that elevators may be dispatched to where needed. Now you see the need to know which waiting passengers are on the path of some operating elevator so don't require a dispatch of an idle elevator(or a change of destination of an operating elevator) to pick them up. Notice the benefit of isolating the destination to the elevator struct - you don't have to change any in-progress events when the destination changes. Naturally one has to follow rules in changing the destination - for example the path to the new destination must pass the floor of the old destination.

You want to isolate the dispatch operation to a function for similar reasons of isolating the queue operations - its much easier to change if the code is not distributed throughout the program. In simulating a real elevator you'd probably experiment with various dispatch algorithms because that can have a significant impact on the elevator system efficiency. Even the positioning of idle elevators can be important in determining response time.

This article has been dead for over six months. Start a new discussion instead.