Self Puzzleation

[SamBones]

Do you have any programming puzzles that you "assign" yourself?

I have a couple puzzles that I have given myself over the years. I thought I'd share them and hopefully see what others may have done as self assigned programming exercises.

One I've used for a very long time, and have done in at least four or five different languages, is an elevator simulator. It has multiple parts; elevator, the building that they're in, people that need to go places, and others things depending on how complicated you want to make it.

The elevator must be able to go from and to a specific number of floors. It might not start at the ground floor. It might not go to the top floor. It can only hold so many people. It takes time to go from floor to floor.

The building can have more than one elevator. It must have more than one floor (else the elevator to nowhere).

The people have to first enter the building. They have to choose a destination floor. They have to fit on the elevator. They have to get on and off.

One thing also needed is a controller/simulator to create the building, and then start feeding people to it. Each person in the building needs to be tracked and controlled and randomly be given places to go.

That's the "hard" stuff. The fun stuff, for me anyway, is trying to optimize the logic that the elevators use to move people the most efficiently. I always assume a single controller controlling all elevators, so they always know what the others are doing and what's needed.

Two of my breakthroughs that gave the highest building throughput, were giving elevators a staging floor to go to when there was no work, and allowing multiple floor button pushes to let the elevator know how many people want a specific floor.

The staging floor is best with a larger building with more elevators. If there's nobody needing a ride, and each elevator goes to a different floor spread evenly among the floors to wait, then there is always a fairly close elevator when someone needs a ride. They get picked up quickly.

The multiple pushes is basically just a count of how many people on the elevator need a certain floor. That is, if there are 10 people needing the 20th floor, and one person needing the 15th floor, you get better overall throughput by passing the 15th floor on the way up to let the 10 people off, then going back down to let the one person off. Yeah, not very fair to that person, but that gets a larger number of people to their destination quicker. The problem with this in real life is that once people learn the logic being used, there's nothing to stop that one person from pushing their button 100 times to get preferential treatment.

There are variations I've added, for things like express elevators and elevators getting stuck.

I first played with this puzzle in BASIC. A few other scripting and interpreted languages were tried. The C version ended up being pretty cool. Java was by far the easiest to write and became the most fun to play with.

So, what kind of programming exercises to you give yourself? Or do you?

 

[SamBones]

Just as an example of sub-games and findings with the elevators, I once tried to optimize emptying a very full building. With an example of 15 floors above ground level, and three elevators, it unloaded the building faster with one elevator only serving the top 4 floors, another elevator serving the middle 5 floors, and the last elevator serving the bottom 6 floors.

If each elevator just stopped at the first floor it came to, the building emptied out from bottom up and took a very long time. If each elevator went to the highest floor with a request, the elevators would fill up and have to keep passing floors, so it emptied the building from the top down, and took a very long time.

I found by splitting the workload and biasing it by the distance it had to travel, it seemed to get an optimal speed for clearing the building.

 

[Mike Lewis]

An interesting exercise, Sam. Could I add a few more factors (just to complicate the issue / make it more challenging):

1. Do people use the elevators in a steady flow? Or in some other predictable way? Or completely at random? For example, if this is an office building, it's likely that demand will be heaviest at the start and end of the working day, and around lunchtime. But if it's, say, a public library, the traffic might be more spread out. The simulation would need to take this into account.

2. How easy is it for people to avoid using the elevator? If I just wanted to travel one floor, and if the waiting time was likely to be more than, say, 30 seconds, I might opt to use the stairs instead. But not if the stairs were at the far end of the corridor, or if the staircase was dirty or otherwise unattractive. (This is actually a significant point. Many buildings seem to be designed with the idea that everyone will always use the elevator all the time, and the only reason to provide a staircase is in the event of an emergency or a power cut. The architects don't consider that using stairs could, even in a limited number of cases, reduce the load on the elevators and therefore save time for everyone.)

3. What are the aims of the building's operators? Clearly, moving people between floors quickly will be one of them. But is saving energy also an aim? If so, that might be an argument against your idea of sending the elevator to a staging floor when not otherwise in use. (Or would it? Maybe doing that would result in an overall saving of energy?)

So, lots of fun waiting to be had in designing a simulation.

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[SamBones]

Hey Mike,

Awesome! This is why I shared this. Not everyone thinks the way I do.

1) I've always written it so I can define the workload before starting (i.e. 1000 people entering the building). Early iterations it was just one huge queue. Later it was spread out and more random. The "empty the building" test was starting with the floors loaded, and then everyone decides to leave at once (lunch or end of day). The nice thing about building a simulator like this is that once you have the basic pieces built, you can play with things like this.

2) Well, I've never given them a chance to use another means. That may be my next addition. I'll have to think it through.

3) My goal has always been to optimize people throughput. I had never considered optimizing power consumption. That's brilliant and will require some thought on my part.

Currently my elevators don't travel at a constant speed. I can change the actual numbers, but they can take like 3 seconds to get to the next floor (had to accelerate from a standstill), 1 second per floor while moving, and 3 seconds to cover the last floor (due to deceleration). So to go from the 10th to the 5th floor, with these numbers, it would take a total of 9 seconds (3+1+1+1+3).

 

[Mike Lewis]

Sam,

I just got round to thinking a bit more about this.

I hadn't thought about the fact that the speed wouldn't be constant - that the elevator would need to accelerate and decelerate. But that should be easy to build in.

Interesting that you have already experimented with various languages. It seems obvious that it should be object-oriented. I guess the building and the elevators would both be objects. The building would have an elevator collection. The elevator's properties would include capacity, acceleration, deceleration, maybe minimum dwell time, and maybe the time it takes to load or unload as a function of the number of people. Methods might include stopping and starting. And I guess it would need to respond to events, such as the call button being pushed.

It all sounds fascinating. I just wish I had the time to play with it myself, but as always real work gets in the way.

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[SamBones]

Hi Mike,

Yeah, that's why I've played with this for so long. You can go crazy with the details. One of the reasons I came up with elevators to model is because my entire career I've ridden elevators just about every work day. A lot of times you don't know anyone else, so after the initial "Good Morning"s, you've got some time to let your mind wander. I always pull this mental toy out and observe things going on. If I think of something cool, I'll add it to the simulation later.

Another detail I've learned from observation is that sometimes elevators move at different speeds. Not intentionally, they're just different for whatever mechanical reasons. I worked in downtown LA for a while and you could always find at least one elevator in a bank that moved quicker or slower from floor to floor. I always wondered if it would be better to wait for "the fast one" instead of taking the first one that came (we're talking extremely minor differences).

You are absolutely right that object oriented languages are easier to model this. It almost becomes trivial in Java, just time consuming for the detail you want to add. My first big successful implementation was in C. That's only because that's the tool I was using at the time and C++ wasn't around yet. Yeah, I'm an old grey-hair.

Sam