|
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 States24777 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.
|
You can't solve yesterday's with only 1 question, it's mathematically impossible. One binary question only gives you two possible answers, which necessarily means you would get the same answer for at least 2 of the doors being correct, and have no way to choose between them.
|
Now how about a general solution for randomized values of a, b, c, and d? Perhaps to make this even more devilish, how about an unknown number of participants n?
|
On May 06 2009 11:44 Draconizard wrote:
Now how about a general solution for randomized values of a, b, c, and d? Perhaps to make this even more devilish, how about an unknown number of participants n?
Ok, uhh generalized solution?
For any set of values
Arranged them in increasing order from fastest to slowest (assign fastest = a, slowest = d)
If a + c > 2b, then do what LTT said
If a + c < 2b, then do what Micronesia said
|
|
|
|
|
|
EPT
