www.digitalmars.com         C & C++   DMDScript  

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

reply 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
next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Escalators have an emergency stop button at the ends. Press it.
Nov 05 2008
parent reply 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
parent reply 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
parent 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
prev sibling parent reply 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
parent 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