• Christopher Wright (20/20) Nov 05 2008 Here's a problem that I encountered, and solved to my satisfaction.
• Chris R. Miller (2/27) Nov 05 2008 Break the escalator. ;-)
• Adam D. Ruppe (11/16) Nov 05 2008 Tell everyone to start running up the escalator to buy time.
• Walter Bright (1/1) Nov 05 2008 Escalators have an emergency stop button at the ends. Press it.
• Sean Kelly (12/13) Nov 05 2008 When I was a child my dad took me to work for one of those "bring your
• Walter Bright (7/17) Nov 05 2008 If it needs a key, it's a pretty useless emergency stop button.
• mgen (1/1) Nov 06 2008 I think we all have jumped over something in our lives only to trip horr...
• Sean Kelly (18/18) Nov 05 2008 This sounds like a job for Dijkstra's algorithm! The easiest solution
• Chris Wright (4/22) Nov 06 2008 I explicitly don't want to take people who are close together. I want th...

Christopher Wright <dhasenan gmail.com> writes:

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?

"Chris R. Miller" <lordsauronthegreat gmail.com> writes:

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. ;-)

"Adam D. Ruppe" <destructionator gmail.com> writes:

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

Walter Bright <newshound1 digitalmars.com> writes:

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

Sean Kelly <sean invisibleduck.org> writes:

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

Walter Bright <newshound1 digitalmars.com> writes:

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.

mgen <bmeck stedwards.edu> writes:

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 <sean invisibleduck.org> writes:

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

Chris Wright <dhasenan gmail.com> writes:

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.