The inspiration for this code golf puzzle is the Bridge and Torch problem, in which d people at the start of a bridge must all cross it in the least amount of time.
The catch is that at most two people can cross at once, otherwise the bridge will crush under their weight, and the group only has access to one torch, which must be carried to cross the bridge.
Each person in the whole puzzle has a specified time that they take to walk across the bridge. If two people cross together, the pair goes as slow as the slowest person.
There is no set number of people that must cross the bridge; your solution MUST work for any value of d.
You needn't use standard input for this problem, but for the sake of explaining the problem, I will be using the following input and output format for the explanation. The first number, d, is the number of people at the start of the bridge. Then, the code will scan for d numbers, each representing the speed of a person.
The code output will be the LEAST amount of time required to cross everyone from the start of the bridge to the end of the bridge, while meeting the criteria explained earlier.
Here are some input cases and output cases and the explanation for the first input case. It is up to you to derive an algorithm from this information to solve the problem in the fewest bytes of code possible.
input
4
1 2 5 8
output
15
To reach this output, the people must cross in the following way.
A and B cross forward (2 minutes)
A returns (1 minute)
C and D cross forward (8 minutes)
B returns (2 minutes)
A and B cross forward (2 minutes)
Here's another test case to guide you along your way.
input
5
3 1 6 8 12
output
29
Rules:
- Assume that the input will not be sorted, and you must do so on your own (if you need to)
- The number of people in the puzzle is not fixed at 4 (N >= 1)
- Every group and individual crossing must have a torch. There is only one torch.
- Each group must consist of a maximum of only 2 people!
- No, you may not jump off the bridge and swim to the other side. No other tricks like this ;).
1 3 4 5
, which should return 14 not 15. \$\endgroup\$1 4 5 6 7
has a similar problem. 25 vs. 26 \$\endgroup\$N >= 2
people (meaning, oddly enough that it's extra work to handle the trivial case of "1 person needs to cross"), so some clarification on this point would be great. Thanks in advance. \$\endgroup\$