@@benstevens44 They are in the woods, there are plenty of dead branches all over the place. I don't think it would be possible to make a second torch... /jk Also, is it the full moon? If so, it would be bright enough to see. But I guess not, since the puzzle specifies they need the torch.
This video took 13:45 to watch, and therefore it can be argued that it took 13:45 to confirm that the 19-minute solution to problem 1 was “optimal”-all before any of the people started crossing the bridge. So overall, that solution took 13:45+19:00 = 32:45 to complete. If they had instead just immediately sent any two people across the bridge, and then always sent back the fastest person from the far side, the WORST finishing time they could have had is 26 minutes! Often, the fastest overall solution is to just do it, rather than sitting around planning what you’re gonna do.
well considering theyre all engineers and also not taking time to explain the problem to themselves and probably wouldnt start creating complicated systems of equations to solve it, i think theyll probably do a bit better than that
I think you're missing the funniest detail. They somehow know their individual crossing times. As in, they went ahead and timed it, wasting an additional amount of time equal to the sum of their crossing times. PS: Yeah I know they could be estimates, but that only introduces more errors and uncertainty into the solution.
A group of engineers would take much longer arguing the details. Just nominate the fastest person as torch bearer, and get started while the others argue. Once your down to 3 engineers they may come to a consensus, but by then the solution is trivial.
Point is, the job this question is used for is not the kind of job where you'd ever have to do something without optimization planning. When trillions of dollars are on the line, it's best to plan it out in detail.
The FASTEST way is not always the FUNNEST way! 😇😇 I wonder how many days/years it took the mathematicians to design a proof for this problem, and I assume many gave up after some time with no useful result.
I’m surprised you keep comparing (2A+B+C+D) to (A+3B+D) to determine which four-person strategy is best. Why not simplify that calculation, by subtracting (A+B+D) from each side? This leaves you with simply determining whether A+C is more or less than 2B to determine the better strategy…
The eventual goal is not to determine which method is the right method, the goal is to determine the number of minutes. Finding the right method is only a step towards that answer. Doing extra math steps subtracting numbers you're just going to have to add back in is self-defeating. There's a limited amount of screen space and script time, and since the numeric result of each of the longer equations is needed for the concrete example, repeatedly removing and re-adding (A+B+D) (to get the numeric result) a bunch of times adds visual noise and time that is unnecessary.
That’s a good way of determining the inequality, but these two expressions determine the solution to the problem in minutes. Subtracting A, B, and D would be meaningless.
@@jetx_47But as we saw with puzzle 3, knowing the amount of minutes for the optimal strategy is irrelevant because you stop employing the method once the two slowest have crossed the bridge. Thus, simply comparing A+C with 2B to determine the optimal strategy is perfectly reasonable.
Fun bit of logic. I was looking at it that when you have a pair crossing, you get a 'savings' when you group a pair to cross based on the faster of the two. Like when 8 and 12 minute people cross together, you've 'saved' the 8 minute trip because the 12 minute one was inevitable and you now don't have to make a trip of 8 minutes. But you have to compare this 'savings' with the 'penalty' of not having the fastest person returning. Like sending a 2 minute person back versus a 1 minute person. So you have to weigh the 'savings' of pairing up two really slow people, with the 'penalty' of not having the fastest person for the return trip. You worked it out mathematically, but I was looking at it from an optimization philosophy.
@@justinwhite2725 You ARE saving the 8 minutes, replacing it with the second-fastest time - say 2 minutes. But you're also replacing the fastest crossing - say 1 minute - with that same 2 minutes. In this case 8 is replaced by 2, and 1 by 2 - obviously better. And there really is no trace left of an 8-minute crossing - change it to 7 or 9 and there's no difference, as they're slowing their pace all the same.
@@justinwhite2725 I pointed that out, there is a 'penalty' having a slower person doing the return. So you 'save' 8 minutes, but 'lose' a minute because you have a 2min person returning instead of the 1 minute. Depending on all the different times, you can have a 'net savings', but not always.
As a retired senior software engineer (who worked at Google) I despise these types of interview questions. Unless, and only if, the interviewer is evaluating the ability of the interviewee to methodically explore the problem and identify potential non-obvious factors that could affect the algorithm. Not that they can find the optimal algorithm. If the interviewer is merely expecting the interviewee to find the optimal solution in a high stress, short duration, interview then they are really only looking for someone who has already prepared for that specific question. Which is an awful reason to hire the person.
The general case would be a good coding exercise to practice recursion. The program's input would be a list of crossing times (1 per person), and would print the optimal crossing strategy.
They need to be careful to return to one side, once they finished reinforcing and setting up the lights. Otherwise the time will be undefined, since nobody needs to walk on it. And that will cause a government audit of why the bridge was fixed when it was not needed.
To solve the first part of puzzle 3, and any case where n>4, it's actually compare 2A+C+D vs A+2B+D since that's as far as you get before you're back to a new reduced group on the left side, and you could cancel off A+D out of both, to just compare A+C Vs 2B. This makes it MUCH easier to figure out the optimal strategy at each stage. To demonstrate that that's correct, the trip's that are different between the two strategies are AC go across and A comes back, Vs B comes back (after CD cross) and AB go across again. Everything else is the same.
The two are the only ones possible, which are worked out from a set of 4 people. Any higher group of people, you simplify the problem by picking the 2-fasts 2-slows, solving it with the 4-people strategies. Repeat this step; itwill reduce the group two by two.
It wouldn't be difficult to mathematically show that any other strategy is just a worse version of those strategies. When the torch is on the other side, there's never any reason to not send the fastest person on the other side back to the start (that should be quite obvious). When the fastest and 2nd fastest person are both at the start, there's also never any advantage to not sending them together (if you sent the 2nd fastest person with anyone other than the fastest person, then the 2nd fastest person will just have to travel back with the torch, so it's just worse than sending the fastest person, and if you ever sent the fastest person without the 2nd fastest person then again, you're just going to send them back with the torch, and eventually you'll send them with the 2nd fastest person and the order you do it in won't change anything, and there can only ever be upsides to doing it earlier because that means the fastest people can bring the torch back from the other side). From there the only actual choice is whether or not it's more advantageous to send 2 slow people together to reduce the number of "slow trips" and send the 2nd fastest person back so that they can team up with the fastest person again, or if it's better to have the fastest person to team up with each person individually.
@asdfqwerty14587 That all sounds valid, but some of your arguments, while intuitive, aren't really formal proofs. And even your write-up contains a lot more arguments than the video, so I think it's fair to say that the video glosses over the vast majority of the difficulty in proving a general optimal solution.
I wasn’t convinced, so I did some brute-forcing up to n=10. Got some deeper insights into the problem, and found that indeed nothing beats the strategy described in the video.
To make things clearer for the general case solution, I think the best way to present the "fastest person returns" strategy, is to start with the fastest person crossing with the slowest then returning, then crossing with the second lowest, then returning and finally crossing with the second fastest. This way in both the "fastest person returns" and the "group two slowest" strategies the last step is the crossing of the two fastest together. When optimizing a solution for a larger group, this final and common step can be skipped which explains why the comparison remains fair. With the example of puzzle 3 the complete crossing of 4 people (1,4,9,12) last 27 minutes with the "fastest person returns" strategy and cost 23 minutes when applied to a group of 6 people while the complete crossing of 4 people (1,4,9,12) last 25 minutes with the "group two slowest" strategy and cost 21 when applied to a group of 6 people.
Presumably need to read the paper, but why is it clear that solving the 4 case and recursing is the optimal solution for n? It's not totally obvious that for certain speeds and n people, there could be another way, e.g. for n=10 and the numbers are sending the 5th and 9th together at some point is better.
@volodyanarchist If 1st or 2nd person is on the other side, you won't need 5th to return back. If 1st and 2nd are both on this side, let them go to the other side first, or let 1st and 9th go together. No matter which situation, let 5th and 9th go together just makes no sense.
@@DoongXiouHua Yes, but recall the 5th and 9th together was a totally arbitrary example. However, your general argument does suggest some constraints to a best solution. I think my problem started with the fact that there are two different solutions to n=4 depending on the actual numbers. I think I would have (wrongly) decided the fastest back was obviously always the best way. And since there are two solutions with different properties, I thought it might be the case that for higher n there will be another very different solution
@ I mean, it should be easy to prove that nth person always cross the bridge with (n-1)th person or 1st person. If we have (s,n-1) and (t,n) crossing the bridge, where s
On the general case, while I agree with your conclusions, Presh, I find your explanation inadequate. I agree that the best option will always be to either send the two fastest across (with one of them returning with the torch, then the two slowest (with the remaining fast guy returning the torch), OR to have the fastest guy shuttle people across. But you seem to assumed _without actually proving_ that the only options are to either group the two slowest people or to have *both* of them shuttled across individually by the fastest guy. Why couldn't the solution be to have the fastest guy take the slowest guy across, then try the group-slowest with the second-slowest and third-slowest? Or even shuttle across the second-slowest guy and try the group-slowest with the slowest and third-slowest? And once you consider those options, the whole solution falls apart, because you no longer have two strategies that both result in the exact same situation for the next step. Which means you can't just apply the fastest strategy in each step; you now have to be prepared to back-track and consider multiple branching paths in your decision tree.
After some thinking, playing around with the puzzle in Python, and trying to understand the linked math paper, I think I've figured out the proof which is missing from the video: Consider the problem where we have 5+ people. Assume that, at some point in the optimal solution, we have a step where we shuttle over a single person (either the slowest or second-slowest), then a step where use group-slowest. Let A < B < C < D < E be the travel times for the two fastest and three slowest people, as of before the step where a single person gets shuttled. First consider the case where the slowest person, i.e. E, is the one that gets shuttled. Thus the next steps of our optimal solution are: - A & E cross in E time - A returns in A time - A & B cross in B time - A returns in A time - C & D cross in D time - B returns in B time Total time is thus 2A + 2B + D + E. Next consider the case where the second-slowest person, i.e. D, is the one that gets shuttled. Thus the next steps of our optimal solution are: - A & D cross in D time - A returns in A time - A & B cross in B time - A returns in A time - C & E cross in E time - B returns in B time Total time is thus also 2A + 2B + D + E. However, consider this alternative sequence of moves: - A & B cross in B time - A returns in A time - D & E cross in E time - B returns in B time - A & C cross in C time - A returns in A time Total time is thus 2A + 2B + C + E. Given we know C < D, this is a better time, and it has the same result: C, D, and E all on the other side, A & B back where they started. Thus our original solution was not optimal. Contradiction. Thus, the optimal solution can never have a case where a single-person-shuttle precedes a group-slowest step. Thus it is, in fact, sufficient to just consider the two strategies listed in the video. Indeed, you can make the algorithm more efficient: all uses of the group-slowest strategy will come before all uses of the send-fastest strategy, so you can use binary search to find the transition point.
@macdjord no need for binary search. Group transfer of the slowest only benefits when the faster in the group is slower than the second fastest of all crossing and returning So after each crossing, compare the sum of the second slowest on the starting side and the fastest among all with twice the second fastest of all. If 2B= A+candidate, and you do fastest shuttle from then on.
@@aaronbredon2948 Yes, but using binary search, you don't have to do that check for every pair of candidates. You do the search to find the changeover point, and _everybody_ slower than that can be sent over in pairs, and everybody faster gets walked over individually.
Worst mandatory work bonding trip ever. Or … The one minute person grabs the torch, runs across, sets the bridge on fire, goes back Monday and puts in for the promotion for the empty spots that just opened 🤷♂️
LOL! The person who runs across and sets the bridge on fire is the one person who _doesn't_ return Monday... how can he get back when the bridge is gone?! The rest of the group will be happy that they got rid of the jerk of the group, though. 😅
Don't leave anyone who has a disability, but if they're just a very slow walker just ignore them. I keep being sent on team building exercises and all they're doing is giving me more opportunities to ignore people who are holding us back without a good reason
For computer scientists, this problem can also be solved using Dijkstra's algorithm on a suitable undirected, weighted graph. ^^ The vertices of the graph are given by the positions. If there are N people in the group, there are 2^(N+1) vertices of the graph, since each person is on either the left or right side and the torch is on either the left or right side; this gives two possibilities for the position of each person plus the torch. Example vertices are 1L 4L 5R 8R TL and 1R 4L 5R 8L TR for Puzzle 1 (where N = 4 and the T stands for the torch). The edges are given by the moves that can be made, and are weighted by the number of minutes the move takes. For example, there is an edge from 1L 4L 5L 8R TL to 1L 4R 5R 8R TR of weight 5, which corresponds to People 4 and 5 crossing the bridge together while 1 stays on the left and 8 stays on the right (remember that they have to take the torch with them). We also have moves where only one person crosses the bridge, so we have, for example, an edge from 1L 4L 5R 8R TL to 1L 4R 5R 8R TR of weight 4. [It's worth remarking that this graph is bipartite because every move must pass the torch from one side to the other.] The problem is then to find a path from the vertex with everyone on the left to the vertex with everyone on the right with the least possible distance (i.e., sum of the weights), and Dijkstra's algorithm will do it all. @carykh has a nice video where he solves a similar problem by finding a path in a graph: th-cam.com/video/y_ii8QT7zsk/w-d-xo.html For the bridge & torch puzzles in this video, I ran the algorithm in Python and got the same answers as stated by the video (19 min, 15 min, 40 min).
Intuitive explanation: If you send A back both times, the forward crossings depend on B, C, and D's speed. But you can remove C's speed from the process by having them cross with D! As that makes A unavailable to go back, B does so, and is then slower than A on the last crossing. So C's time is replaced by B's, and A is replaced by B for one of the trips back. Is this time save better than the loss, i.e. is C-B > B-A?
@wisteria3032 Yeah, it's unintuitive written down like that. The way I actually see it is if the fastest times are 1-2-5 it's clear the 2 is super-competitive, whereas for 1-4-5 the 4 is not up to the task. I don't even go through the substractions.
Excellent - but if like me you didn't spot the solution, don't feel too bad about it because the problem was the subject of a university research paper and the authors probably worked on it for several months. So there's no shame in the fact that you, like me, didn't work it out in 5 minutes.
What type of torch though? If it's a burning torch then yep. But if it's the type of torch that the Americans would call a flashlight then not so easy!
If 2(B) > (A+C), then the fastest person returns strategy is optimal and If 2(B) < (A+C), then two slowest group strategy is optimal In, four person case
I remember a flash game based about this. There's a family want to cross a log bridge. A skinny guy, chubby kid, big dad, tripping mom, and grandpa with stick. If you fail to cross, the torch will puffed making them fall and drown.
I might be wrong but I think the trick in determining whether to use "fastest returns" or "group 2 slowest" is: if second slowest person takes longer than two fastest combined, use "group 2 slowest".
Back then, there was this flash game that is focused on this torch bridge puzzle (and the other was plant/herbivore/carnivore river-crossing). The premise is basically the same, but the torch has "fuel", so it will run out if you don't get the optimal solution. My baby ass thought "oh, obviously let the fastest person do the work", so I did that, but the torch would always die out at the center of the bridge and the people fell down. One time, I come across the solution to that game, and when they didn't do the "fast person work" (but group the slowest) path, I was absolutely mind blown. Like no way. How can you go fast if you don't let the fastest person work it out? Thank you for allowing me to relieve the rage and malding of that time.
I got puzzle 1 right using what I called fastest torchbearer. I said 17 for puzzle 2 as I didn't spot the other method. I got puzzle 3 right after seeing the explanation of how to do it.
@prash, Thanks for solving this fantastic puzzle. I think this is Glorified arithmetic mean problem, if b is More than arithmetic mean of A and C, Fastest person return will be optimal solution, and Vice versa. if it is exactly Mean both fastest person return and Group two slowest will have same output.
To compare fastest person return and group slowest you can basically eliminate A+B+D as they appear in both. So you just have to see whether 2B is greater than A+C or not. If it is fastest person returns is better, otherwise it’s group slowest
I ignored all strategy’s and solved it before the video I remembered solving a riddle like this, After seeing your strategy’s I was like “no way you can do this in 27minutes” and then skipped to the end of video to see “oh hey I was right”
General strategy: Fastest two cross. Then while there are still people on the starting side: Fastest returns If second slowest plus fastest is greater than 2x second fastest, have 2 slowest cross over and second fastest come back, then two fastest cross. Else, fastest crosses over with next fastest. No recursion, no branching. Just a simple loop. This is simply based on the fact that if you send 2 slower people across, you save the time of the faster of the slow pair plus 1 crossing of the fastest, but have to have the second fastest cross twice instead.
If the combined times of the fastest and third fastest people is less than double that of the second fastest person's time, then the "fastest person returns" strategy is better. If it's more than double, then the "group two slowest'" strategy is better. If it's exactly double (3 minutes in this case), then the two strategies would be equally fast. This is almost never addressed, and this video is the first time I've ever seen someone addressing it.
You can just generate a discriminant for n = 4: (2A + B + C + D) - (A + 3B + D) = A - 2B + C If A - 2B + C > 0, Group 2 Slowest is quicker. If A - 2B + C < 0, Fastest Returns is quicker.
You can optimize even further by having the returning person stop once the torch illuminates the end of bridge. This drops time off at both ends. I'm not sure if this would change order as the difference is not measurable.
Another way to look at A+C vs 2B is whether the 2nd fastest person is closer in speed to the fastest or the 2nd slowest. Also, on the recursion, once you decide 'fastest person returns' is best, it's not possible for the other strategy to become the best after that.
An observation on the choice of strategy: If the 2nd slowest is more than twice as slow as the 2nd fastest, use group the two slowest strategy Else use fastest person returns strategy. Not 100% sure but feels right.
What about solving for the puzzle where if a person crosses over N times they get fatigued and either they can't cross again, or their time increases by a multiplier?
The variant of the puzzle in which the source of light is a flashlight, is IMHO the better one. Using a torch, some might try to argue that those engineers would be able to fashion some kind of a 2nd torch, making the back-and-forth trip unnecessary. 🙂
I think "fastest person returns" isn't a good name for that strategy because any optimal strategy can always send the fastest person back across the bridge. Notice this is true for "group two slowest", where the people who return are always the fastest ones on that side. The only difference is which pairs we send across in the first place. The first strategy always sends the two fastest across, while the other one sends the two fastest, then the two slowest, then the last remaining pair. So better names might be "always fastest" and "fastest then slowest"
The problem does not give enough information to solve. I am thinking of a bridge like in Indiana Jones. 1. How wide is the bridge 2. Does it have handrails even primitive ones. 3. Why does the person with the torch need to cross all the way with the torch. Unless the bridge is just planks with no protection, what kind of bridge is that? So you cut the time of the slower person in half and then cut the return time in half to figure out your total new time. As well as the difference in time and distance you would travel as 1 minute vs the time the next person would travel. 4. You have more than likely taken more physics than I have, but if the bridge can only support 2 people wouldn't that be for a specific point and would be different if the weights were at both ends vs in the middle. They would also be moving so you would need some calculus to figure out the change in weight locations as the people walk.
congratulation you decided that instead of solving a logic/arithmetic problem you would rather ignore it because the framing makes you want to do basically anything else you could frame the problem in pure abstract mathematics... but then it becomes an absolute pain to explain and understand... or you could do it the way its always done and people happily suspend their disbelief to engage with the stated problem thats like being asked to solve the travelling salesman problem and just saying "send out more people" ... thats not solving the stated problem - thats ignoring it to solve for something else entirely
If the difference in time between the 2 fastest is greater than the difference in time between the 2nd fastest and the 3rd fastest, then the 'fastest returns' method is the quickest and if it is the other way round, then the 'group 2 slowest' is quickest. If the difference in time between them is the same then either method is optimal. I think that works as a rule of thumb and would save time working each out if it is correct.
You need to change the question from “engineers” to “logicians” As an engineer I would have said “we’re going to waste more time finding the optimal solution and executing it, than if we just go with Sending the fastest guy back”
He even reference that video at 5:22. But it's exactly like it because here he shows subcases in which Ted-Ed (two-slowest together) solution doesn't work.
Counterpoint: the question as stated is poorly worded and thus allows for a null result. As presented, it states that _only_ two people can cross at a time. This can be interpreted to mean people must _always_ cross in groups of two, which means that, in order to bring the torch back, the two people who cross have to cross back. Thus, you never leave anybody on the other side, and the group never manages to move all people across the bridge. In order to exclude this possibility, you need to phrase the problem such that "a _maximum of two_ can cross the bridge at any time."
I was just going to have the fastest walk each one across. Never thought of sending the 2 fastest twice just to get the slowest to cancel out the 2nd slowest.
In the final puzzle, that method is only 42 minutes anyway, so given how it's only two minutes slower, but takes like half a second to come up with compared to calculating the best way, I'm just gonna say I prefer your method 😂
If they are all lost, and therefore arrive at the bridge for the first time (never have seen or crossed the bridge before), how will they know their crossing times? They may know who is slower or faster (relatively to each other), but they will not know that quantitatively. And choosing the optimal solution requires knowing the actual crossing times, not simply the relative ranking.
The bridge problem has assumptions in it. Like, how long is the bridge? Is it over a canyon or water? Tie a rope to the end of the torch and pull it back over to the other side quicker than A. Assumptions matter
Number 8 carries the torch and sets out with 5. 5 finishes and the torch still on the bridge and lets 2 go next. With 1 minute to spare, 8 and 1 finish with the torch together for 8 minutes total. I made my own question so I had an answer that would work and make me feel better about myself..yay DEI!
I'll call the fastest person A, and the slowest person D. The first thing I'd do is send A and D across, with A carrying the torch. That gets D out of the way (D only needs to cross once.) Since the torch has to keep going back, A will be carrying it the entire time, so that it takes only 1 minute to bring the torch back to B and C. A takes C across next, leaving B behind; now with C and D safely across, A finally comes back to get B a minute later. So my total time would be 8+1+5+1+4, totaling 19 minutes (I just started watching the video, so as of this writing, I don't even know if this is right, but if it's not then it should be close enough to optimal.
One person above posted a fast way to compare: if A+C is less than 2B, then you send A+C over then A back, then A+D and send A back. If A+C is greater than 2B, then send over A+B, send A back, send over C+D, and send B back. Once A&B are back on the original side, recompute with a new pair of C+D.
If you always send the fastest person back, their speed advantage will apply more, but that one time they cross with the second-slowest might waste that. You can instead "hide" the second-slowest behind the slowest, but then you have to send the second-fastest back an extra time. So it all depends on how worse you make things by relying on the second-fastest.
The fastest one runs ahead with the torch, stranding the second fastest on the bridge. Then he uses the torch to burn the bridge down. The second fastest burns and the third and fourth fastest succumb to the elements. The fastest then gets a pay bump to stay at the company because he is the only one left who is familiar with the codebase.
thank you! I thought it was a bit like the crossing river puzzle (preventing the lion attacking the goat or the goat eating the vegetable), but it turned out also resembling the taking the 21 flags puzzle! would like to know how to solve those corssing river puzzles, apart for brute force trial and error!
okay now step away from the illustration the video used, because thats arbitrary and imagine that there are no siderails and sometimes a board is missing or has a hole in it... there also is no moonlight present would you like me to add more arbitrary justifications for the premise, or can you suspend your disbelief now?
This remembers me of the puzzle that you must cross a river with a boat and one cop, one criminal, an adult and a child, something like that. The child cannot operata the boat and the criminal cannot be alone with someone else than the cop.
I'm going with 42 minutes based on the thumbnail. (1+4) cross the bridge, then 1 comes back with the torch. (1+5) (1+8) (1+9) (1+12) So it's 4+5+8+9+12 then all the return trips with the torch is another 4. However that's too obvious so I'm guessing there's more to it than what is described there!
They're engineers, they should know that if only 2 people can cross without the bridge breaking than it isn't very safe even for two people to cross. the fastest person should go back to the camp and get flashlights so they can cross one at a time, as a slight time save is not worth risking your life for.
Clever! I've only ever come across this puzzle in cases where 'two slowest' strategy wins over 'fastest person returns', but I never stopped feeling in the back of my mind that this couldn't possibly always be the case. Which now makes me wonder - do we know for sure that the only two possible strategies for obtaining the shortest crossing time are 'fastest person returns' and 'two slowest', or is there a third possible strategy for optimal crossing time lurking out there somewhere? (Cue Twilight Zone music!) I'm guessing there isn't, and Gunther Rote addressed that in his paper.
11:02 “3. Use procedure just before 2 fastest cross.” But, in the entire video, for the “fastest person returns”, you were doing +(A,B), -(A), +(A,C), -(A), +(A,D). So the last two people are A and D, i.e. the fastest and the slowest. Were we supposed to use the ordering +(A,D), -(A), +(A,C), -(A)? That would leave A and B, i.e. the two fastest, on the left for the next subproblem.
I don't think it was ever said it was obvious. Presh just presents a simplified but incomplete explanation, and probably skips certain technical details and considerations that are addressed in the actual math paper. Moreover, the algorithm of the optimal solution for N people, as presented in the video, _will_ pair "mid-people", namely in cases where the crossing time of the fastest of the two mid-people is greater than (2B - A) (where A and B are the crossing times of respectively the fastest person and the second-fastest person of the whole group).
If I was going by the thumbnail (stating "only 2 can cross at a time" and "only torch") then I'd say that after the first two had crossed, the torch would be unavailable for the other four as a single person returning contradicts the "only 2" rule.
About 5 minutes. The fastest guy just carries the others over one at a time with the torch. There's no evidence that carrying anyone would slow him down so that would be the fastest way. It would take 9 minutes for the group of six.
Group 2 should be called sandwiched-the-2-slowest-with-the-2-fastest (indexed by ST2SWT2F). The 1st mentioned is start-with-2-fastest-end-with-fastest-and-slowest (indexed by SW2FEWFAS).
why can't we send it is like the bridge is old and narrow so it can at max hold the weight of 2 persons and we have only 1 torch so a single person can return with the torch
Actually, the puzzle only states the the bridge must be crossed, not that the people have to reach the other side. Therefore, you could just have each group walk across and back, and still fulfill the literal interpretation of the wording.
For the second puzzle, I would send 8 across with the torch by himself. Then send 5, then 2, then, 1. That way the bridge is lit, never has more than two people on it, and it only takes 8 minutes. If engineering is about bending rules and outside the box thinking, then this is fine. If the asker is a stickler for rules, they will need to have more information. Like how far is the span of light from the torch. If the torch lights up 90% of the bridge, it's fine. And do the people at the ends of the bridge need any light? The assumption is no. Whatever, though. Right?
Why would you think the bridge is lit if there's a person at one end of it with a torch? If that's the case, the torch condition provides no obstacle. It's always either going to be at one end or the other or on the bridge. The real world explanation for this is that some of the planks on the bridge are missing and you need light to see where to step safely.
For n = 5, I don't understand why A and B have to return to allowed C to cross the bridge. If only A retuns, C can cross with him, B has not crossed the bridge again. According to me, A and B have to come back only if n is even.
I think the answer is the sum of their times plus the time of the fastest times n-2 where n is how ever many of them there are. (t1+t2+t3...+tn)+t1(n-2) Or t1(n-1)+t2+t3...+tn
This was more of a strategy or algorithm than an actual proof. It wasn't shown that there did not exist some other more optimal configuration for larger values of n
Twelve minutes. First trip: One-Minute Guy carries Eight-Minute Guy across (one minute elapsed) Second trip: One-Minute Guy returns with the torch (two minutes elapsed) Third trip: Four-Minute Guy and Five-Minute Guy cross with the torch while One-Minute Guy rests (seven minutes elapsed) Fourth trip: Four-Minute Guy returns with the torch (eleven minutes elapsed) Fifth trip: One-Minute Guy carries Four-Minute Guy across (twelve minutes elapsed) And if you're wondering why One-Minute Guy didn't just do all of it, this scenario requires him to transport two people. Let him recover in between literally carrying the team. If he didn't, he'd have to carry three people with less time to catch his breath.
I have two problems with your solution: I’m pretty sure that it will take more than 1 minute for the One-Minute Guy (or 1MG) to cross the bridge carrying someone. It’s fair to assume that it will take closer to 4.5 minutes, which makes the omtimal solution 18.5 minutes long : 1MG carries 8MG (4.5), 1MG comes back (5.5), 4MG and 5MG cross the bridge (10.5), 4MG comes back (14.5), 1MG and 4MG cross the bridge (18.5) And if we consider that it indeed takes the same time for 1MG to carry people, why can’t 4MG carry 5MG when they go together and make the actual fastest solution be 11 minutes?
The answer to question in the thumbnail photo of this video is 12. Since two people constitute a GROUP as long as they are interacting and sharing a common goal, “4” & “1” cross three times thus 6 people have crossed the bridge. The fastest group time is 12 minutes.
With 1, 4, 5, 8 the answer should be 19 With 1, 4, 5, 8, 9, 12, it should be 41 And with 1, 2, 5, 8 should be 17, though there must be some trickery with the fastest 2 being so much faster (there was). Results got by making the 1 minute person be in all groups, to take the return trips. But I haven't checked with paper.
Wait. If they know they need to cross the bridge, they aren't really "lost" are they? Also, that bridge has obvious ropes that could be used to cross the bridge without a torch. Third, leave 8 min beyond. Jenkins does not contribute around the office anyway.
What I love about logic puzzles is that the circumstances the characters are in are always illogical
Right? You have four to six engineers trying to cross a bridge and not one of them can figure out how to make a second torch?
😂
@@benstevens44 They are in the woods, there are plenty of dead branches all over the place. I don't think it would be possible to make a second torch... /jk
Also, is it the full moon? If so, it would be bright enough to see. But I guess not, since the puzzle specifies they need the torch.
@@benstevens44 They could have fixed the bridge!
😂
This video took 13:45 to watch, and therefore it can be argued that it took 13:45 to confirm that the 19-minute solution to problem 1 was “optimal”-all before any of the people started crossing the bridge. So overall, that solution took 13:45+19:00 = 32:45 to complete.
If they had instead just immediately sent any two people across the bridge, and then always sent back the fastest person from the far side, the WORST finishing time they could have had is 26 minutes!
Often, the fastest overall solution is to just do it, rather than sitting around planning what you’re gonna do.
well considering theyre all engineers and also not taking time to explain the problem to themselves and probably wouldnt start creating complicated systems of equations to solve it, i think theyll probably do a bit better than that
I think you're missing the funniest detail. They somehow know their individual crossing times. As in, they went ahead and timed it, wasting an additional amount of time equal to the sum of their crossing times.
PS: Yeah I know they could be estimates, but that only introduces more errors and uncertainty into the solution.
A group of engineers would take much longer arguing the details. Just nominate the fastest person as torch bearer, and get started while the others argue. Once your down to 3 engineers they may come to a consensus, but by then the solution is trivial.
Point is, the job this question is used for is not the kind of job where you'd ever have to do something without optimization planning. When trillions of dollars are on the line, it's best to plan it out in detail.
The FASTEST way is not always the FUNNEST way! 😇😇
I wonder how many days/years it took the mathematicians to design a proof for this problem, and I assume many gave up after some time with no useful result.
I’m surprised you keep comparing (2A+B+C+D) to (A+3B+D) to determine which four-person strategy is best. Why not simplify that calculation, by subtracting (A+B+D) from each side? This leaves you with simply determining whether A+C is more or less than 2B to determine the better strategy…
Or, to make it more visual: Is the average time of A and C higher or lower than B?
The eventual goal is not to determine which method is the right method, the goal is to determine the number of minutes. Finding the right method is only a step towards that answer. Doing extra math steps subtracting numbers you're just going to have to add back in is self-defeating.
There's a limited amount of screen space and script time, and since the numeric result of each of the longer equations is needed for the concrete example, repeatedly removing and re-adding (A+B+D) (to get the numeric result) a bunch of times adds visual noise and time that is unnecessary.
That’s a good way of determining the inequality, but these two expressions determine the solution to the problem in minutes. Subtracting A, B, and D would be meaningless.
@@jetx_47But as we saw with puzzle 3, knowing the amount of minutes for the optimal strategy is irrelevant because you stop employing the method once the two slowest have crossed the bridge. Thus, simply comparing A+C with 2B to determine the optimal strategy is perfectly reasonable.
Exactly my thought, just compare A+C to 2B. It will tell you the fastest approach, all that is left is to calculate it.
Fun bit of logic. I was looking at it that when you have a pair crossing, you get a 'savings' when you group a pair to cross based on the faster of the two. Like when 8 and 12 minute people cross together, you've 'saved' the 8 minute trip because the 12 minute one was inevitable and you now don't have to make a trip of 8 minutes.
But you have to compare this 'savings' with the 'penalty' of not having the fastest person returning. Like sending a 2 minute person back versus a 1 minute person. So you have to weigh the 'savings' of pairing up two really slow people, with the 'penalty' of not having the fastest person for the return trip.
You worked it out mathematically, but I was looking at it from an optimization philosophy.
Yeah, that's the intuitive way to see it.
Yeah that's how I thought about it looking at the thumbnail. I'm glad he covered the general case.
You don't save the 8 minutes though because they have to return with the torch and have to cross again later.
@@justinwhite2725 You ARE saving the 8 minutes, replacing it with the second-fastest time - say 2 minutes. But you're also replacing the fastest crossing - say 1 minute - with that same 2 minutes.
In this case 8 is replaced by 2, and 1 by 2 - obviously better. And there really is no trace left of an 8-minute crossing - change it to 7 or 9 and there's no difference, as they're slowing their pace all the same.
@@justinwhite2725 I pointed that out, there is a 'penalty' having a slower person doing the return. So you 'save' 8 minutes, but 'lose' a minute because you have a 2min person returning instead of the 1 minute. Depending on all the different times, you can have a 'net savings', but not always.
As a retired senior software engineer (who worked at Google) I despise these types of interview questions. Unless, and only if, the interviewer is evaluating the ability of the interviewee to methodically explore the problem and identify potential non-obvious factors that could affect the algorithm. Not that they can find the optimal algorithm. If the interviewer is merely expecting the interviewee to find the optimal solution in a high stress, short duration, interview then they are really only looking for someone who has already prepared for that specific question. Which is an awful reason to hire the person.
The general case would be a good coding exercise to practice recursion. The program's input would be a list of crossing times (1 per person), and would print the optimal crossing strategy.
They're engineers. They would reinforce the bridge, then all walk across together.
They need to be careful to return to one side, once they finished reinforcing and setting up the lights. Otherwise the time will be undefined, since nobody needs to walk on it. And that will cause a government audit of why the bridge was fixed when it was not needed.
they are electrical engineers...
Who is that slowest engeneer that takes 12 minutes to cross the bridge for which his colleague take just 1 minute.
@@HareshVP Must be Skipper or Kowalski from Madagascar.
@@HareshVP There is always one
To solve the first part of puzzle 3, and any case where n>4, it's actually compare 2A+C+D vs A+2B+D since that's as far as you get before you're back to a new reduced group on the left side, and you could cancel off A+D out of both, to just compare A+C Vs 2B. This makes it MUCH easier to figure out the optimal strategy at each stage.
To demonstrate that that's correct, the trip's that are different between the two strategies are AC go across and A comes back, Vs B comes back (after CD cross) and AB go across again. Everything else is the same.
It's not obvious that the two strategies you consider are the only ones possible, or that the optimal solution will be composed of only those two.
The two are the only ones possible, which are worked out from a set of 4 people. Any higher group of people, you simplify the problem by picking the 2-fasts 2-slows, solving it with the 4-people strategies. Repeat this step; itwill reduce the group two by two.
It wouldn't be difficult to mathematically show that any other strategy is just a worse version of those strategies. When the torch is on the other side, there's never any reason to not send the fastest person on the other side back to the start (that should be quite obvious). When the fastest and 2nd fastest person are both at the start, there's also never any advantage to not sending them together (if you sent the 2nd fastest person with anyone other than the fastest person, then the 2nd fastest person will just have to travel back with the torch, so it's just worse than sending the fastest person, and if you ever sent the fastest person without the 2nd fastest person then again, you're just going to send them back with the torch, and eventually you'll send them with the 2nd fastest person and the order you do it in won't change anything, and there can only ever be upsides to doing it earlier because that means the fastest people can bring the torch back from the other side).
From there the only actual choice is whether or not it's more advantageous to send 2 slow people together to reduce the number of "slow trips" and send the 2nd fastest person back so that they can team up with the fastest person again, or if it's better to have the fastest person to team up with each person individually.
@asdfqwerty14587 That all sounds valid, but some of your arguments, while intuitive, aren't really formal proofs. And even your write-up contains a lot more arguments than the video, so I think it's fair to say that the video glosses over the vast majority of the difficulty in proving a general optimal solution.
I wasn’t convinced, so I did some brute-forcing up to n=10. Got some deeper insights into the problem, and found that indeed nothing beats the strategy described in the video.
dude cited a mathematical proof and you still missed it I guess
To make things clearer for the general case solution, I think the best way to present the "fastest person returns" strategy, is to start with the fastest person crossing with the slowest then returning, then crossing with the second lowest, then returning and finally crossing with the second fastest. This way in both the "fastest person returns" and the "group two slowest" strategies the last step is the crossing of the two fastest together. When optimizing a solution for a larger group, this final and common step can be skipped which explains why the comparison remains fair. With the example of puzzle 3 the complete crossing of 4 people (1,4,9,12) last 27 minutes with the "fastest person returns" strategy and cost 23 minutes when applied to a group of 6 people while the complete crossing of 4 people (1,4,9,12) last 25 minutes with the "group two slowest" strategy and cost 21 when applied to a group of 6 people.
Presumably need to read the paper, but why is it clear that solving the 4 case and recursing is the optimal solution for n? It's not totally obvious that for certain speeds and n people, there could be another way, e.g. for n=10 and the numbers are sending the 5th and 9th together at some point is better.
Sending 5th with 9th together spent the same time as sending 8th with 9th together, why choose the former one?
@@DoongXiouHuaBut maybe in the following iteration you want to have that fifth person on the other side, so that they can return back the torch.
@volodyanarchist If 1st or 2nd person is on the other side, you won't need 5th to return back. If 1st and 2nd are both on this side, let them go to the other side first, or let 1st and 9th go together.
No matter which situation, let 5th and 9th go together just makes no sense.
@@DoongXiouHua Yes, but recall the 5th and 9th together was a totally arbitrary example. However, your general argument does suggest some constraints to a best solution. I think my problem started with the fact that there are two different solutions to n=4 depending on the actual numbers. I think I would have (wrongly) decided the fastest back was obviously always the best way. And since there are two solutions with different properties, I thought it might be the case that for higher n there will be another very different solution
@ I mean, it should be easy to prove that nth person always cross the bridge with (n-1)th person or 1st person.
If we have (s,n-1) and (t,n) crossing the bridge, where s
On the general case, while I agree with your conclusions, Presh, I find your explanation inadequate. I agree that the best option will always be to either send the two fastest across (with one of them returning with the torch, then the two slowest (with the remaining fast guy returning the torch), OR to have the fastest guy shuttle people across. But you seem to assumed _without actually proving_ that the only options are to either group the two slowest people or to have *both* of them shuttled across individually by the fastest guy. Why couldn't the solution be to have the fastest guy take the slowest guy across, then try the group-slowest with the second-slowest and third-slowest? Or even shuttle across the second-slowest guy and try the group-slowest with the slowest and third-slowest?
And once you consider those options, the whole solution falls apart, because you no longer have two strategies that both result in the exact same situation for the next step. Which means you can't just apply the fastest strategy in each step; you now have to be prepared to back-track and consider multiple branching paths in your decision tree.
After some thinking, playing around with the puzzle in Python, and trying to understand the linked math paper, I think I've figured out the proof which is missing from the video:
Consider the problem where we have 5+ people. Assume that, at some point in the optimal solution, we have a step where we shuttle over a single person (either the slowest or second-slowest), then a step where use group-slowest.
Let A < B < C < D < E be the travel times for the two fastest and three slowest people, as of before the step where a single person gets shuttled.
First consider the case where the slowest person, i.e. E, is the one that gets shuttled. Thus the next steps of our optimal solution are:
- A & E cross in E time
- A returns in A time
- A & B cross in B time
- A returns in A time
- C & D cross in D time
- B returns in B time
Total time is thus 2A + 2B + D + E.
Next consider the case where the second-slowest person, i.e. D, is the one that gets shuttled. Thus the next steps of our optimal solution are:
- A & D cross in D time
- A returns in A time
- A & B cross in B time
- A returns in A time
- C & E cross in E time
- B returns in B time
Total time is thus also 2A + 2B + D + E.
However, consider this alternative sequence of moves:
- A & B cross in B time
- A returns in A time
- D & E cross in E time
- B returns in B time
- A & C cross in C time
- A returns in A time
Total time is thus 2A + 2B + C + E.
Given we know C < D, this is a better time, and it has the same result: C, D, and E all on the other side, A & B back where they started. Thus our original solution was not optimal. Contradiction.
Thus, the optimal solution can never have a case where a single-person-shuttle precedes a group-slowest step. Thus it is, in fact, sufficient to just consider the two strategies listed in the video. Indeed, you can make the algorithm more efficient: all uses of the group-slowest strategy will come before all uses of the send-fastest strategy, so you can use binary search to find the transition point.
@macdjord no need for binary search. Group transfer of the slowest only benefits when the faster in the group is slower than the second fastest of all crossing and returning
So after each crossing, compare the sum of the second slowest on the starting side and the fastest among all with twice the second fastest of all.
If 2B= A+candidate, and you do fastest shuttle from then on.
@@aaronbredon2948 Yes, but using binary search, you don't have to do that check for every pair of candidates. You do the search to find the changeover point, and _everybody_ slower than that can be sent over in pairs, and everybody faster gets walked over individually.
The explanation in the video is inadequate (it’s not a proof), but the solution is correct
Worst mandatory work bonding trip ever. Or …
The one minute person grabs the torch, runs across, sets the bridge on fire, goes back Monday and puts in for the promotion for the empty spots that just opened 🤷♂️
LOL! The person who runs across and sets the bridge on fire is the one person who _doesn't_ return Monday... how can he get back when the bridge is gone?!
The rest of the group will be happy that they got rid of the jerk of the group, though. 😅
Ooh, I saw this bridge riddle in the news in August. Solution is to leave somebody in the woods! Knew I could solve this puzzle!
Don't leave anyone who has a disability, but if they're just a very slow walker just ignore them. I keep being sent on team building exercises and all they're doing is giving me more opportunities to ignore people who are holding us back without a good reason
For computer scientists, this problem can also be solved using Dijkstra's algorithm on a suitable undirected, weighted graph. ^^
The vertices of the graph are given by the positions. If there are N people in the group, there are 2^(N+1) vertices of the graph, since each person is on either the left or right side and the torch is on either the left or right side; this gives two possibilities for the position of each person plus the torch. Example vertices are 1L 4L 5R 8R TL and 1R 4L 5R 8L TR for Puzzle 1 (where N = 4 and the T stands for the torch).
The edges are given by the moves that can be made, and are weighted by the number of minutes the move takes. For example, there is an edge from 1L 4L 5L 8R TL to 1L 4R 5R 8R TR of weight 5, which corresponds to People 4 and 5 crossing the bridge together while 1 stays on the left and 8 stays on the right (remember that they have to take the torch with them). We also have moves where only one person crosses the bridge, so we have, for example, an edge from 1L 4L 5R 8R TL to 1L 4R 5R 8R TR of weight 4. [It's worth remarking that this graph is bipartite because every move must pass the torch from one side to the other.] The problem is then to find a path from the vertex with everyone on the left to the vertex with everyone on the right with the least possible distance (i.e., sum of the weights), and Dijkstra's algorithm will do it all.
@carykh has a nice video where he solves a similar problem by finding a path in a graph: th-cam.com/video/y_ii8QT7zsk/w-d-xo.html For the bridge & torch puzzles in this video, I ran the algorithm in Python and got the same answers as stated by the video (19 min, 15 min, 40 min).
Intuitive explanation:
If you send A back both times, the forward crossings depend on B, C, and D's speed.
But you can remove C's speed from the process by having them cross with D! As that makes A unavailable to go back, B does so, and is then slower than A on the last crossing.
So C's time is replaced by B's, and A is replaced by B for one of the trips back. Is this time save better than the loss, i.e. is C-B > B-A?
interesting ❤
I phrased it with is 2B grater or lower than A+C?
it took me a bit to understand the subtractions you made. really interesting.
@wisteria3032 Yeah, it's unintuitive written down like that. The way I actually see it is if the fastest times are 1-2-5 it's clear the 2 is super-competitive, whereas for 1-4-5 the 4 is not up to the task. I don't even go through the substractions.
Excellent - but if like me you didn't spot the solution, don't feel too bad about it because the problem was the subject of a university research paper and the authors probably worked on it for several months. So there's no shame in the fact that you, like me, didn't work it out in 5 minutes.
They are engineers, and are in woods. They can just make a few more torches!
and THIS is the optimum logical solution ! thank you
Unfortunately for them, they are software engineers, they can only relit that one torch they own
At best they could draw some torches.
Maybe they are british and we just assumed their torch was a fire stick.
What type of torch though?
If it's a burning torch then yep. But if it's the type of torch that the Americans would call a flashlight then not so easy!
If 2(B) > (A+C), then the fastest person returns strategy is optimal and
If 2(B) < (A+C), then two slowest group strategy is optimal
In, four person case
I remember a flash game based about this. There's a family want to cross a log bridge. A skinny guy, chubby kid, big dad, tripping mom, and grandpa with stick. If you fail to cross, the torch will puffed making them fall and drown.
Puzzle 3 made the whole thing worthwhile, with that extra trick!
I might be wrong but I think the trick in determining whether to use "fastest returns" or "group 2 slowest" is: if second slowest person takes longer than two fastest combined, use "group 2 slowest".
On the 2nd puzzle it doesn't matter who from the 1 & 2 groups goes back, because at some point that person will have to comeback
Back then, there was this flash game that is focused on this torch bridge puzzle (and the other was plant/herbivore/carnivore river-crossing). The premise is basically the same, but the torch has "fuel", so it will run out if you don't get the optimal solution.
My baby ass thought "oh, obviously let the fastest person do the work", so I did that, but the torch would always die out at the center of the bridge and the people fell down. One time, I come across the solution to that game, and when they didn't do the "fast person work" (but group the slowest) path, I was absolutely mind blown. Like no way. How can you go fast if you don't let the fastest person work it out?
Thank you for allowing me to relieve the rage and malding of that time.
I got puzzle 1 right using what I called fastest torchbearer. I said 17 for puzzle 2 as I didn't spot the other method. I got puzzle 3 right after seeing the explanation of how to do it.
you have the best channel to delay my studying
@prash, Thanks for solving this fantastic puzzle.
I think this is Glorified arithmetic mean problem, if b is More than arithmetic mean of A and C, Fastest person return will be optimal solution, and Vice versa. if it is exactly Mean both fastest person return and Group two slowest will have same output.
To compare fastest person return and group slowest you can basically eliminate A+B+D as they appear in both. So you just have to see whether 2B is greater than A+C or not. If it is fastest person returns is better, otherwise it’s group slowest
I ignored all strategy’s and solved it before the video I remembered solving a riddle like this,
After seeing your strategy’s I was like “no way you can do this in 27minutes” and then skipped to the end of video to see “oh hey I was right”
If one of the engineers is Montgomery Scott, not only would it be done in half the time, but he'd also just use the transporters.
Onto a ship traveling at warp speed no less.
General strategy:
Fastest two cross.
Then while there are still people on the starting side:
Fastest returns
If second slowest plus fastest is greater than 2x second fastest, have 2 slowest cross over and second fastest come back, then two fastest cross.
Else, fastest crosses over with next fastest.
No recursion, no branching. Just a simple loop.
This is simply based on the fact that if you send 2 slower people across, you save the time of the faster of the slow pair plus 1 crossing of the fastest, but have to have the second fastest cross twice instead.
nice! especially useful in programming, since recursions tend to be pretty costly in computation compared to loops =)
If the combined times of the fastest and third fastest people is less than double that of the second fastest person's time, then the "fastest person returns" strategy is better. If it's more than double, then the "group two slowest'" strategy is better. If it's exactly double (3 minutes in this case), then the two strategies would be equally fast. This is almost never addressed, and this video is the first time I've ever seen someone addressing it.
You can just generate a discriminant for n = 4:
(2A + B + C + D) - (A + 3B + D) = A - 2B + C
If A - 2B + C > 0, Group 2 Slowest is quicker.
If A - 2B + C < 0, Fastest Returns is quicker.
You can optimize even further by having the returning person stop once the torch illuminates the end of bridge. This drops time off at both ends. I'm not sure if this would change order as the difference is not measurable.
Why, when demonstrating the n=5 case, did you send A and B back together? Just send A back, then A and C cross.
Before watching solutions, here are my guesses:
---------
puzzle 1: 19 minutes (4/1 - 1- 5/8 - 4 - 1/4)
Puzzle 2: 15 minutes (1/2 - 1 - 8/5 - 2 - 1/2)
Puzzle 3: 40 minutes (1/4 - 1 - 9/12 - 4 - 8/1 - 1 - 5/1 - 1 - 4/1)
Another way to look at A+C vs 2B is whether the 2nd fastest person is closer in speed to the fastest or the 2nd slowest.
Also, on the recursion, once you decide 'fastest person returns' is best, it's not possible for the other strategy to become the best after that.
An observation on the choice of strategy:
If the 2nd slowest is more than twice as slow as the 2nd fastest, use group the two slowest strategy
Else use fastest person returns strategy.
Not 100% sure but feels right.
What about solving for the puzzle where if a person crosses over N times they get fatigued and either they can't cross again, or their time increases by a multiplier?
In other terms 2B-A is the added cost of sending C+D together. If the cost is greater than sending C with A that solution will perform worse.
Is the time it takes to determine the best strategy included in the total time to cross the bridge?
The variant of the puzzle in which the source of light is a flashlight, is IMHO the better one. Using a torch, some might try to argue that those engineers would be able to fashion some kind of a 2nd torch, making the back-and-forth trip unnecessary. 🙂
It's so anachronistic, too. Just say only one of their cell phones has battery remaining.
If the puzzle was set in British English though then it makes sense as we say torch as Americans say flashlight.
I think "fastest person returns" isn't a good name for that strategy because any optimal strategy can always send the fastest person back across the bridge. Notice this is true for "group two slowest", where the people who return are always the fastest ones on that side. The only difference is which pairs we send across in the first place. The first strategy always sends the two fastest across, while the other one sends the two fastest, then the two slowest, then the last remaining pair. So better names might be "always fastest" and "fastest then slowest"
The problem does not give enough information to solve.
I am thinking of a bridge like in Indiana Jones.
1. How wide is the bridge
2. Does it have handrails even primitive ones.
3. Why does the person with the torch need to cross all the way with the torch. Unless the bridge is just planks with no protection, what kind of bridge is that? So you cut the time of the slower person in half and then cut the return time in half to figure out your total new time. As well as the difference in time and distance you would travel as 1 minute vs the time the next person would travel.
4. You have more than likely taken more physics than I have, but if the bridge can only support 2 people wouldn't that be for a specific point and would be different if the weights were at both ends vs in the middle. They would also be moving so you would need some calculus to figure out the change in weight locations as the people walk.
congratulation you decided that instead of solving a logic/arithmetic problem you would rather ignore it because the framing makes you want to do basically anything else
you could frame the problem in pure abstract mathematics... but then it becomes an absolute pain to explain and understand... or you could do it the way its always done and people happily suspend their disbelief to engage with the stated problem
thats like being asked to solve the travelling salesman problem and just saying "send out more people" ... thats not solving the stated problem - thats ignoring it to solve for something else entirely
If the difference in time between the 2 fastest is greater than the difference in time between the 2nd fastest and the 3rd fastest, then the 'fastest returns' method is the quickest and if it is the other way round, then the 'group 2 slowest' is quickest. If the difference in time between them is the same then either method is optimal. I think that works as a rule of thumb and would save time working each out if it is correct.
You need to change the question from “engineers” to “logicians”
As an engineer I would have said “we’re going to waste more time finding the optimal solution and executing it, than if we just go with Sending the fastest guy back”
It’s the zombie bridge puzzle from Ted-Ed!
Yeah bro!
He even reference that video at 5:22. But it's exactly like it because here he shows subcases in which Ted-Ed (two-slowest together) solution doesn't work.
Counterpoint: the question as stated is poorly worded and thus allows for a null result. As presented, it states that _only_ two people can cross at a time. This can be interpreted to mean people must _always_ cross in groups of two, which means that, in order to bring the torch back, the two people who cross have to cross back. Thus, you never leave anybody on the other side, and the group never manages to move all people across the bridge.
In order to exclude this possibility, you need to phrase the problem such that "a _maximum of two_ can cross the bridge at any time."
I was just going to have the fastest walk each one across. Never thought of sending the 2 fastest twice just to get the slowest to cancel out the 2nd slowest.
In the final puzzle, that method is only 42 minutes anyway, so given how it's only two minutes slower, but takes like half a second to come up with compared to calculating the best way, I'm just gonna say I prefer your method 😂
If they are all lost, and therefore arrive at the bridge for the first time (never have seen or crossed the bridge before), how will they know their crossing times? They may know who is slower or faster (relatively to each other), but they will not know that quantitatively. And choosing the optimal solution requires knowing the actual crossing times, not simply the relative ranking.
The bridge problem has assumptions in it. Like, how long is the bridge? Is it over a canyon or water? Tie a rope to the end of the torch and pull it back over to the other side quicker than A. Assumptions matter
Steps 2 and 4 could be swapped with no difference in the overall time - therefore there are two equally optimum strategies
I loved this one, great
Number 8 carries the torch and sets out with 5. 5 finishes and the torch still on the bridge and lets 2 go next. With 1 minute to spare, 8 and 1 finish with the torch together for 8 minutes total.
I made my own question so I had an answer that would work and make me feel better about myself..yay DEI!
I'll call the fastest person A, and the slowest person D. The first thing I'd do is send A and D across, with A carrying the torch. That gets D out of the way (D only needs to cross once.) Since the torch has to keep going back, A will be carrying it the entire time, so that it takes only 1 minute to bring the torch back to B and C. A takes C across next, leaving B behind; now with C and D safely across, A finally comes back to get B a minute later. So my total time would be 8+1+5+1+4, totaling 19 minutes (I just started watching the video, so as of this writing, I don't even know if this is right, but if it's not then it should be close enough to optimal.
One person above posted a fast way to compare: if A+C is less than 2B, then you send A+C over then A back, then A+D and send A back. If A+C is greater than 2B, then send over A+B, send A back, send over C+D, and send B back. Once A&B are back on the original side, recompute with a new pair of C+D.
If you always send the fastest person back, their speed advantage will apply more, but that one time they cross with the second-slowest might waste that.
You can instead "hide" the second-slowest behind the slowest, but then you have to send the second-fastest back an extra time.
So it all depends on how worse you make things by relying on the second-fastest.
The answer is simple. You pop up a window that says, "Windows has detected you have left the room, Press Any Key To Continue".
The fastest one runs ahead with the torch, stranding the second fastest on the bridge. Then he uses the torch to burn the bridge down. The second fastest burns and the third and fourth fastest succumb to the elements. The fastest then gets a pay bump to stay at the company because he is the only one left who is familiar with the codebase.
Got given this with 1, 2, 9 and 10 a few years ago. Took me a few attempts to get the fastest time.
thank you! I thought it was a bit like the crossing river puzzle (preventing the lion attacking the goat or the goat eating the vegetable), but it turned out also resembling the taking the 21 flags puzzle!
would like to know how to solve those corssing river puzzles, apart for brute force trial and error!
Dude, it has never been so dark that I could not cross that bridge without the torch.
okay now step away from the illustration the video used, because thats arbitrary and imagine that there are no siderails and sometimes a board is missing or has a hole in it... there also is no moonlight present
would you like me to add more arbitrary justifications for the premise, or can you suspend your disbelief now?
Assuming only two actually means two at the most, the fastest nerd makes each trip so 4 +5+ 8 +2 return trip 19 minutes
This remembers me of the puzzle that you must cross a river with a boat and one cop, one criminal, an adult and a child, something like that. The child cannot operata the boat and the criminal cannot be alone with someone else than the cop.
It would be quicker to compare B to (A+C)/2. If B(A+C)/2 do "fastest person returns". If B=(A+C)/2 then it doesn't matter, the results are the same.
If they just got on with it, it would be faster than analyzing it to death. 😂
I'm going with 42 minutes based on the thumbnail.
(1+4) cross the bridge, then 1 comes back with the torch. (1+5) (1+8) (1+9) (1+12)
So it's 4+5+8+9+12 then all the return trips with the torch is another 4.
However that's too obvious so I'm guessing there's more to it than what is described there!
They're engineers, they should know that if only 2 people can cross without the bridge breaking than it isn't very safe even for two people to cross. the fastest person should go back to the camp and get flashlights so they can cross one at a time, as a slight time save is not worth risking your life for.
What a nice puzzle ! Thank you for ypur research !
Clever! I've only ever come across this puzzle in cases where 'two slowest' strategy wins over 'fastest person returns', but I never stopped feeling in the back of my mind that this couldn't possibly always be the case. Which now makes me wonder - do we know for sure that the only two possible strategies for obtaining the shortest crossing time are 'fastest person returns' and 'two slowest', or is there a third possible strategy for optimal crossing time lurking out there somewhere? (Cue Twilight Zone music!) I'm guessing there isn't, and Gunther Rote addressed that in his paper.
How does the torch get back to the original side if only 2 can cross at a time?
11:02 “3. Use procedure just before 2 fastest cross.” But, in the entire video, for the “fastest person returns”, you were doing +(A,B), -(A), +(A,C), -(A), +(A,D). So the last two people are A and D, i.e. the fastest and the slowest. Were we supposed to use the ordering +(A,D), -(A), +(A,C), -(A)? That would leave A and B, i.e. the two fastest, on the left for the next subproblem.
Why is it obvious that there might not be some cases where pairing some mid people is optimal?
I don't think it was ever said it was obvious. Presh just presents a simplified but incomplete explanation, and probably skips certain technical details and considerations that are addressed in the actual math paper.
Moreover, the algorithm of the optimal solution for N people, as presented in the video, _will_ pair "mid-people", namely in cases where the crossing time of the fastest of the two mid-people is greater than (2B - A) (where A and B are the crossing times of respectively the fastest person and the second-fastest person of the whole group).
If I was going by the thumbnail (stating "only 2 can cross at a time" and "only torch") then I'd say that after the first two had crossed, the torch would be unavailable for the other four as a single person returning contradicts the "only 2" rule.
I think that’s just the semantics of “only 2” vs “2 have to” as you can safely interpret it to mean up to 2 or restricted to 2 can cross
@@johnthompson5741 Nope, "only" means "exclusively", and so does "2 have to". "A maximum of 2" or "1 or 2 may" means what is meant.
About 5 minutes. The fastest guy just carries the others over one at a time with the torch. There's no evidence that carrying anyone would slow him down so that would be the fastest way. It would take 9 minutes for the group of six.
Very clever - nice!
Group 2 should be called sandwiched-the-2-slowest-with-the-2-fastest (indexed by ST2SWT2F). The 1st mentioned is start-with-2-fastest-end-with-fastest-and-slowest (indexed by SW2FEWFAS).
This smells like a situation where dynamic programming would help.
The problem is impossible: only two people can traverse the bridge at a time, so you can't send only one back
I understood it as max 2 people.
why can't we send it is like the bridge is old and narrow so it can at max hold the weight of 2 persons
and we have only 1 torch
so a single person can return with the torch
The joke
⤴🗣⤵
Actually, the puzzle only states the the bridge must be crossed, not that the people have to reach the other side.
Therefore, you could just have each group walk across and back, and still fulfill the literal interpretation of the wording.
For the second puzzle, I would send 8 across with the torch by himself. Then send 5, then 2, then, 1. That way the bridge is lit, never has more than two people on it, and it only takes 8 minutes.
If engineering is about bending rules and outside the box thinking, then this is fine. If the asker is a stickler for rules, they will need to have more information. Like how far is the span of light from the torch. If the torch lights up 90% of the bridge, it's fine. And do the people at the ends of the bridge need any light? The assumption is no. Whatever, though. Right?
Why would you think the bridge is lit if there's a person at one end of it with a torch? If that's the case, the torch condition provides no obstacle. It's always either going to be at one end or the other or on the bridge. The real world explanation for this is that some of the planks on the bridge are missing and you need light to see where to step safely.
For n = 5, I don't understand why A and B have to return to allowed C to cross the bridge. If only A retuns, C can cross with him, B has not crossed the bridge again. According to me, A and B have to come back only if n is even.
1 minute guy must be so bored once he's walking with 8 minute guy
Back when tech companies still used IQ tests to attract talent.
A good demonstration that greedy algorithm might not always yield optimal results
So A+C >/< 2B is the check for which method to use. If A+C = 2B, both methods are the same.
I think the answer is the sum of their times plus the time of the fastest times n-2 where n is how ever many of them there are.
(t1+t2+t3...+tn)+t1(n-2)
Or
t1(n-1)+t2+t3...+tn
This was more of a strategy or algorithm than an actual proof. It wasn't shown that there did not exist some other more optimal configuration for larger values of n
The torch had an update which ended in a BSOD by the time everyone crossed the bridge.
Made a C++ prog that solves these, results confirmed!
More interview riddles please! I don't really care for the "impossible" 6-year old hw problems :(
Twelve minutes.
First trip: One-Minute Guy carries Eight-Minute Guy across (one minute elapsed)
Second trip: One-Minute Guy returns with the torch (two minutes elapsed)
Third trip: Four-Minute Guy and Five-Minute Guy cross with the torch while One-Minute Guy rests (seven minutes elapsed)
Fourth trip: Four-Minute Guy returns with the torch (eleven minutes elapsed)
Fifth trip: One-Minute Guy carries Four-Minute Guy across (twelve minutes elapsed)
And if you're wondering why One-Minute Guy didn't just do all of it, this scenario requires him to transport two people. Let him recover in between literally carrying the team. If he didn't, he'd have to carry three people with less time to catch his breath.
I have two problems with your solution:
I’m pretty sure that it will take more than 1 minute for the One-Minute Guy (or 1MG) to cross the bridge carrying someone. It’s fair to assume that it will take closer to 4.5 minutes, which makes the omtimal solution 18.5 minutes long : 1MG carries 8MG (4.5), 1MG comes back (5.5), 4MG and 5MG cross the bridge (10.5), 4MG comes back (14.5), 1MG and 4MG cross the bridge (18.5)
And if we consider that it indeed takes the same time for 1MG to carry people, why can’t 4MG carry 5MG when they go together and make the actual fastest solution be 11 minutes?
Any resources to train with?
Put out the torch and wait 20 minutes. Once your night vision is back, cross however you'd like.
The answer to question in the thumbnail photo of this video is 12. Since two people constitute a GROUP as long as they are interacting and sharing a common goal, “4” & “1” cross three times thus 6 people have crossed the bridge. The fastest group time is 12 minutes.
With 1, 4, 5, 8 the answer should be 19
With 1, 4, 5, 8, 9, 12, it should be 41
And with 1, 2, 5, 8 should be 17, though there must be some trickery with the fastest 2 being so much faster (there was).
Results got by making the 1 minute person be in all groups, to take the return trips.
But I haven't checked with paper.
Gotta make another torch baby
Der Rote Günter hat seine Piratenkarriere kurz unterbrochen und das Paper geschrieben. 😅
Since the return journey is 1 minute I just added 1 to the the first and second journeys 5+6+8=19
I can code a brute-force finder faster than mathematicians took to generalize a solution.
Nice puzzle, duly shared.
Wait. If they know they need to cross the bridge, they aren't really "lost" are they?
Also, that bridge has obvious ropes that could be used to cross the bridge without a torch.
Third, leave 8 min beyond. Jenkins does not contribute around the office anyway.
Fastest person strategy cannot work in large groups because the exhaustion of the fastest one.