Here's a problem that I encountered, and solved to my satisfaction.

There's an escalator taking people into a fiery pit of death. Your task is to save people.

These people are sorted according to race, creed, color, and nation. Each has a different weight. You can check the weight of each individual, and you know ahead of time the total weight of the people on the escalator.

You've got a guy on a tether hanging from your dirigible. You can do two things:
 - Tell him to grab onto the person directly under the dirigible. He'll hang on to them until you tell him to do otherwise.
 - Reel in the person he's hanging on to.

There are a few issues:
 - Your dirigible has a weight limit.
 - Each person has a different weight. There's a maximum weight for a person, but your dirigible isn't guaranteed to be able to hold that much.
 - You're an equal opportunity savior, so you want to take people at roughly even intervals, if possible.
 - People's weights are arranged adversarially.

How do you do it?

Christopher Wright wrote:
> Here's a problem that I encountered, and solved to my satisfaction.
> 
> There's an escalator taking people into a fiery pit of death. Your task is to save people.
> 
> These people are sorted according to race, creed, color, and nation. Each has a different weight. You can check the weight of each individual, and you know ahead of time the total weight of the people on the escalator.
> 
> You've got a guy on a tether hanging from your dirigible. You can do two
> things:
>  - Tell him to grab onto the person directly under the dirigible. He'll
> hang on to them until you tell him to do otherwise.
>  - Reel in the person he's hanging on to.
> 
> There are a few issues:
>  - Your dirigible has a weight limit.
>  - Each person has a different weight. There's a maximum weight for a
> person, but your dirigible isn't guaranteed to be able to hold that much.
>  - You're an equal opportunity savior, so you want to take people at
> roughly even intervals, if possible.
>  - People's weights are arranged adversarially.
> 
> How do you do it?

Break the escalator. ;-)

On Wed, Nov 05, 2008 at 06:57:17PM -0500, Christopher Wright wrote:
> Here's a problem that I encountered, and solved to my satisfaction.
> 
> There's an escalator taking people into a fiery pit of death. Your task is to save people.
[snip]
> How do you do it?

Tell everyone to start running up the escalator to buy time.

Meanwhile, pass down a screwdriver and pair of insulated wire cutters to the guy on the tether and lower him to the ground. Tell him to find the escalator's power cord and snip it.

Everyone can now run to safety.

:P

-- 
Adam D. Ruppe
http://arsdnet.net

Escalators have an emergency stop button at the ends. Press it.

Walter Bright wrote:
> Escalators have an emergency stop button at the ends. Press it.

When I was a child my dad took me to work for one of those "bring your kids to work days."  He worked on Wall Street and commuted through the World Trade Center via the PATH train to get to his office.  So we were heading into work together at the peak of commute time, out of the train and up the massive array of escalators, all packed shoulder to shoulder with businesspeople.  He lost track of me for a moment and seconds later the entire escalator bank shut down.  Shortly thereafter he found me near a hidden emergency stop button, grabbed me, and hurried away. Years later I looked for that button on my way through the WTC and found it key-locked.  I guess once was enough :-)


Sean

This sounds like a job for Dijkstra's algorithm!  The easiest solution would be to simply exclude the individuals who are above tether capacity and run the algorithm on the rest.  However, this doesn't account for groups of low-weight individuals would could all be tethered together. For that, the best I've come up with so far is to do a best-fit sort on the people to determine optimal grouping for tether loads and then iteratively run Dijkstra's algorithm using that information to determine the proper path to take.  But the iterative part is bothering me and I'm sure there's a better solution.

Perhaps use Floyd's algorithm and make edges between group members bidirectional and edges between single person tether loads bidirectional but have edged from single-person loads to group loads unidirectional into the group and unidirectional out of the group?  Then to keep the groups together, every edge out of a group would have to have a relatively high cost in order to prevent the tether from grabbing a single group member and then moving on to someone outside the group, then later returning for another group member.  I hope that makes sense :-p


Sean

Sean Kelly wrote:
> When I was a child my dad took me to work for one of those "bring your kids to work days."  He worked on Wall Street and commuted through the World Trade Center via the PATH train to get to his office.  So we were heading into work together at the peak of commute time, out of the train and up the massive array of escalators, all packed shoulder to shoulder with businesspeople.  He lost track of me for a moment and seconds later the entire escalator bank shut down.  Shortly thereafter he found me near a hidden emergency stop button, grabbed me, and hurried away. Years later I looked for that button on my way through the WTC and found it key-locked.  I guess once was enough :-)

If it needs a key, it's a pretty useless emergency stop button.

There have been cases of people getting clothing caught in the works and getting injured.

I once tried to show how cool I was by bypassing the packed up escalator and running up the empty down escalator. My delusions of coolness were shattered when I tripped half way up.

I think we all have jumped over something in our lives only to trip horribly... sigh and it always such a good idea. I once fell down an escalator and someone stopped it after I got off... people are people...

Sean Kelly Wrote:
> This sounds like a job for Dijkstra's algorithm!  The easiest solution would be to simply exclude the individuals who are above tether capacity and run the algorithm on the rest.  However, this doesn't account for groups of low-weight individuals would could all be tethered together. For that, the best I've come up with so far is to do a best-fit sort on the people to determine optimal grouping for tether loads and then iteratively run Dijkstra's algorithm using that information to determine the proper path to take.  But the iterative part is bothering me and I'm sure there's a better solution.
> 
> Perhaps use Floyd's algorithm and make edges between group members bidirectional and edges between single person tether loads bidirectional but have edged from single-person loads to group loads unidirectional into the group and unidirectional out of the group?  Then to keep the groups together, every edge out of a group would have to have a relatively high cost in order to prevent the tether from grabbing a single group member and then moving on to someone outside the group, then later returning for another group member.  I hope that makes sense :-p

I explicitly don't want to take people who are close together. I want them evenly spaced, so I can get an even coverage of each race, religion, et cetera.

The guy on the tether is just there so you can pass someone and grab them later, but you can only keep track of one.

The original problem relates to a cache-oblivious lookahead array ( http://portal.acm.org/citation.cfm?id=1248393 ). Specifically, the problem is fractional cascading with variable length elements.