|
Last day's puzzle was first solved by Malongo, good job! I wonder what quality do I lack in such a way that I can describe what kind of solution it is but I cannot find it, hopefully I learned something. Again awesome job Malongooo~
+ Show Spoiler [solution] +
See Malongo's solution. I did not solve this puzzle, but his solution is correct by testing and inspection.
Today's puzzle is:
You have a dark tunnel, and 4 people has to cross the tunnel. These 4 people, a, b, c, d, takes different amounts of time to cross the tunnel.
a takes 1 min
b takes 2 min
c takes 5 min
d takes 10 min
There's only 1 flash light, and to cross the tunnel, you must keep the flashlight close by. Only 2 persons can go at a time, and the faster person has to slow down for the slower person. For instance, if a and d go together with the flash_light, it will take 10 minutes.
Your Job:
Devise an algorithm such that it takes the shortest amount of time for all 4 persons to cross the tunnel, how long does it take?
Extra info:
Again, put answers in spoilers, and please show HOW you arrive at the solution, not just the solution if possible so others can learn some problem solving techniques.
GL HF!
|
United States24799 Posts
+ Show Spoiler +Obvious choice:
idea = fastest guy keeps returning with flashlight
a and d go together (10)
a comes back (1)
a and c go together (5)
a comes back (1)
a and b go together (2)
total = 10 + 1 + 5 + 1 + 2 = 19 minutes
I'm guessing there's a quicker way but that's a good start :p
|
+ Show Spoiler +Same thing micro said, I can't think of a way it could possibly be done faster.
|
+ Show Spoiler +You want to eliminate the most amount of minutes. You do that by crossing 10 and 5 at the same time. The rest is just setup.
a + b => 2 minutes
a back => 1 minute
c + d => 10 minutes
b back => 2 minutes
a + b => 2 minutes
17 Minutes.
|
+ Show Spoiler +0
a and b go togeter +2
a comes back +1
a and c go together +5
a comes back +1
a and d go together +10
= 19 minutes
edit: thats brilliant LTT
|
LTT has the correct answer. I remember this puzzle being posted on TL before multiple times in other threads.
|
alright, next puzzle... 
|
+ Show Spoiler +a takes 1 min
b takes 2 min
c takes 5 min
d takes 10 min
a/b= 2 min
a comes back -> 1 min
c/d -> 10 min
b comes back -> 2 min
a/b = 2 min
Definitely a common problem, LTT got it right.
|
|
|
+ Show Spoiler +
ok we obviously need to run the 10&5 together to save as much time as possible, and 10/5 must only run once.. therefore we need to run the quick ones around them, to minimize downtime in between and allow going back and forth
1&2 forward = 2 //quick ones first
1 back = 3
5&10 forward = 13 //necessary
2 back = 15
1&2 forward = 17 //quick ones last
|
On May 05 2009 10:49 Lemonwalrus wrote:
/me bows before LTT
I hate TL in how everyone is smarter than me... But I love it so much more...
|
Sanya12364 Posts
+ Show Spoiler +
17 minutes
1) 2 across and 1 back means that to get all 4 across, the shortest is 3 pairs across and 2 singles back.
2) 10 and 5 should be brought across together since 5 is much larger than both 2 and 1. It's possible to cross back and forth with 1 & 2 twice over in the same time it takes for the 5.
3) Trips across to the other side have to either 1 & 2 or 10 & 5 in order to segregate 1 & 2 and 5 & 10.
4) 5 & 10 has to be the middle trip across. Otherwise, a single trip back with 5 or 10 would have to happen. Therefore, the first and third trips across have to be 1 & 2.
5) Since 1 & 2 cross over twice, both have to cross back once during the two single trips back.
6) The trips back can be in any order. Making the trip with 1 first or 2 first does not matter.
Trips across takes 2 + 10 + 2
Trips back takes 1 + 2.
Total is 17 minutes.
|
Usually it's phrased as a boat and a river. Way to change it up with a flashlight in a tunnel.
|
+ Show Spoiler +Tell the people to man up and go through the tunnel without a flashlight, how hard can it be...... send them one after another with fastest first so it takes the slowest guy 10 minutes ot get through
Total Time: 10 minutes + a few seconds for the others to go in first
|
yeah last day my solution was ugly in someway. I arrived at it after several minutes of trying with logic combinations with the doors. With a lot of failed math (trying a and b or a or c in the doors) I realized that 2 direct questions about the doors (whatever the combination between them) left me with the 2 lights still unknown as "variables". I decided then trying some weird questions involving directly the lights in the clock (would you turn white if theres a car). Then I realized that whenever the answer is no the lights where the same and from there it was almost all try and error.
|
I just saw yesterday's, and I'm wondering why the problem allows two questions. That makes it trivial!
|
I am too lazy to solve this one ^^
|
+ Show Spoiler + A+B go together (2 mins) then A comes back(+1min). C+D go together ( +10 mins) then B comes back (+2min). Then A+B go together (+2 min)
So it's : 2+1+10+2+2=17 mins yay.
|
On May 05 2009 13:42 BottleAbuser wrote:
I just saw yesterday's, and I'm wondering why the problem allows two questions. That makes it trivial!
how
|
On May 05 2009 16:16 evanthebouncy! wrote:Show nested quote +On May 05 2009 13:42 BottleAbuser wrote:
I just saw yesterday's, and I'm wondering why the problem allows two questions. That makes it trivial! how
Wow you can solve it with only one question? i dont think thats posible. Again anything is posible.
|
|
|
|
|
|
EPT
