## digitalmars.D - [OT] Quiz of the Day [2008-11-04]

• 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?
Nov 05 2008
"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. ;-)
Nov 05 2008
"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
Nov 05 2008
Walter Bright <newshound1 digitalmars.com> writes:
Escalators have an emergency stop button at the ends. Press it.
Nov 05 2008
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
Nov 05 2008
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.
Nov 05 2008
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...
Nov 06 2008
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
Nov 05 2008
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.
Nov 06 2008