20
\$\begingroup\$

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:

  1. Assume that the input will not be sorted, and you must do so on your own (if you need to)
  2. The number of people in the puzzle is not fixed at 4 (N >= 1)
  3. Every group and individual crossing must have a torch. There is only one torch.
  4. Each group must consist of a maximum of only 2 people!
  5. No, you may not jump off the bridge and swim to the other side. No other tricks like this ;).
\$\endgroup\$
  • \$\begingroup\$ As found by xnor below, be sure to test cases like 1 3 4 5, which should return 14 not 15. \$\endgroup\$ – gladed Mar 18 '16 at 18:42
  • \$\begingroup\$ 1 4 5 6 7 has a similar problem. 25 vs. 26 \$\endgroup\$ – Sherlock9 Mar 18 '16 at 19:08
  • 1
    \$\begingroup\$ This seems like an odd question, but what are the minimum and maximum number of people in the puzzle? While working on my solutions, I noticed that they only handle 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\$ – Sherlock9 Mar 19 '16 at 17:14
  • \$\begingroup\$ @Sherlock9 Assume your solution must work for N >= 1 \$\endgroup\$ – baseman101 Mar 19 '16 at 18:08
  • \$\begingroup\$ The test cases show that we can use the length as a parameter, but can you make that more clear in the rules? Is the input allowed to be the array of times and the number of people, or are just the times allowed? \$\endgroup\$ – Sherlock9 Mar 22 '16 at 10:42
8
\$\begingroup\$

Python 3, 100 99 bytes

a recursive solution

f=lambda s:s[0]+s[-1]+min(2*s[1],s[0]+s[-2])+f(s[:-2])if s.sort()or 3<len(s)else sum(s[len(s)==2:])

Thanks to @xnor for this paper

Thanks to @lirtosiast save 2 bytes, @movatica save 1 bytes and to @gladed pointing at that my previous solution doesn't work

use the following trick to evaluate something in lambda function s.sort() or s here we compute sort and return the result of the test s.sort()or len(s)>3

Ungolfed

def f(s):
    s.sort()                                   # sort input in place
    if len(s)>3:                               # loop until len(s) < 3
        a = s[0]+s[-1]+min(2*s[1],s[0]+s[-2])  # minimum time according to xnor paper
        return  a + f(s[:-2])                  # recursion on remaining people
    else:
        return sum(s[len(s)==2:])              # add last times when len(s) < 3

Results

>>> f([3, 1, 6, 8, 12])
29
>>> f([1, 2, 5, 8])
15
>>> f([5])
5
>>> f([1])
1
>>> f([1, 3, 4, 5])
14
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ You can save 1 byte and change len(s)==2 to len(s)<3 \$\endgroup\$ – Mr Public Mar 16 '16 at 12:27
  • \$\begingroup\$ @MrPublic you find a bug, I changed the solution it's s[0]*(len(s)==2) not (s[0]*len(s)==2) with the bug f([1]) -> 0 that why we can't replace by <3 thanks \$\endgroup\$ – Erwan Mar 16 '16 at 13:11
  • \$\begingroup\$ This paper has an expression for the optimal time that's the min of multiple possibilities. Are you sure your solution is optimal in all cases? \$\endgroup\$ – xnor Mar 17 '16 at 3:23
  • \$\begingroup\$ @xnor wow it seems that I have the optimal solution I use the expression in Lemma 3 A5:22 \$\endgroup\$ – Erwan Mar 17 '16 at 6:57
  • 1
    \$\begingroup\$ @movatica update with you suggestion \$\endgroup\$ – Erwan Jul 27 '19 at 14:30
4
\$\begingroup\$

Python 2, 119 114 112 119 110 100 95 bytes

I have been advised to separate my answers out.

A solution using Theorem 1, A2:09 of this paper xnor linked. To quote the paper (changing it to zero-indexing): The difference between C_{k-1} and C_k is 2*t_1 - t_0 - t_{N-2k}.

lambda n,t:t.sort()or(n-3)*t[0]*(n>1)+sum(t)+sum(min(0,2*t[1]-t[0]-t[~k*2])for k in range(n/2))

Ungolfing:

def b(n, t): # using length as an argument
    t.sort()
    z = sum(t) + (n-3) * t[0] * (n>1) # just sum(t) == t[0] if len(t) == 1
    for k in range(n/2):
        z += min(0, 2*t[1] - t[0] - t[-(k+1)*2]) # ~k == -(k+1)
    return z
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ are you sure we can assume that length can be an argument ? \$\endgroup\$ – Erwan Mar 22 '16 at 10:13
  • \$\begingroup\$ @Erwan The example test cases seem to allow it. I'll ask \$\endgroup\$ – Sherlock9 Mar 22 '16 at 10:40
2
\$\begingroup\$

Ruby, 94 133 97 96 101 96 99 bytes

I have been advised to separate my answers out.

This is a solution based on the algorithm described in A6:06-10 of this paper on the Bridge and Torch Problem.

Edit: Fixing a bug where a=s[0] is not yet defined when a is called at the end if s.size <= 3.

->s{r=0;(a,b,*c,d,e=s;r+=a+e+[b*2,a+d].min;*s,y,z=s)while s.sort![3];r+s.reduce(:+)-~s.size%2*s[0]}

Ungolfing:

def g(s)
  r = 0
  while s.sort![3]      # while s.size > 3
    a, b, *c, d, e = s  # lots of array unpacking here
    r += a + e + [b*2, a+d].min
    *s, y, z = s        # same as s=s[:-2] in Python, but using array unpacking
  end
  # returns the correct result if s.size is in [1,2,3]
  return r + s.reduce(:+) - (s.size+1)%2 * s[0]
end
|improve this answer|||||
\$\endgroup\$
2
+200
\$\begingroup\$

APL (Dyalog Extended), 39 bytes

{2≥≢⍵:⊃⍵⋄(⊃∘⌽+⊃+(∇1↓⊢)⌊(∇2↓⊢)+2×2⊃⌽)⍵}∨

Try it online!

A tacit function which includes a recursive dfn.

How it works: the idea

My solution is based on subproblem analysis. Given the crossing times \$ t_1, t_2, \cdots, t_n \$ sorted in ascending order, there are two possibly optimal ways to help the worst person cross the bridge:

  1. \$ (t_1, t_n) \rightarrow t_1 \$: net effect is \$ t_n \$ crossing, and the cost is \$ t_n + t_1 \$.
  2. \$ (t_1, t_2) \rightarrow t_2 \rightarrow (t_{n-1}, t_n) \rightarrow t_1 \$: net effect is \$ t_{n-1} \$ and \$ t_n \$ crossing, and the cost is \$ t_1 + 2t_2 + t_n \$.

Let's say \$ T_k \$ be the optimal time to cross the first \$k\$ people. Then, for the first \$k\$ people crossing, we can choose between "use (1) and let \$ k-1 \$ remaining people cross" and "use (2) and let \$ k-2 \$ remaining people cross", which becomes

$$ \begin{aligned} T_k &= \min(T_{k-1} + t_n + t_1, T_{k-2} + t_1 + 2t_2 + t_n) \\ &= t_1 + t_n + \min(T_{k-1}, T_{k-2} + 2t_2) \end{aligned} $$

How it works: the code

{2≥≢⍵:⊃⍵⋄(⊃∘⌽+⊃+(∇1↓⊢)⌊(∇2↓⊢)+2×2⊃⌽)⍵}∨
                                      ∨  ⍝ Descending sort to get [t_n .. t_1]
{                                    }   ⍝ Pass on to recursive function

 2≥≢⍵:⊃⍵  ⍝ Base case: If input length ≤ 2, return the first element
          ⍝   [t_1] → t_1, [t_2 t_1] → t_2

 (⊃∘⌽+⊃+(∇1↓⊢)⌊(∇2↓⊢)+2×2⊃⌽)⍵  ⍝ Recursive case
        ( 1↓⊢)                 ⍝ Choice 1: Drop 1 to get [t_{n-1} .. t_1]
         ∇                     ⍝           Recursive call to get T_{n-1}
               (∇2↓⊢)          ⍝ Choice 2: Drop 2 and recurse to get T_{n-2}
                     +2×2⊃⌽    ⍝           and add 2×t_2
              ⌊                ⍝ Minimum of two choices
  ⊃∘⌽+⊃+                       ⍝ Add common terms t_1 and t_n

Using DP to solve the recursive problem costs a few more bytes:

APL (Dyalog Extended), 44 bytes

⊃⊃(+∘(⊃∘⌽+⊃⌊2∘⊃+2×2⊃⌽),⊢)/(¯2∘↓,∘⊂0~⍨¯2∘↑)∨⎕

Try it online!

A full program.

How it works: the code

∨⎕  ⍝ Descending sort the given array

(¯2∘↓,∘⊂0~⍨¯2∘↑)  ⍝ Set up the initial element for reduce
                  ⍝ e.g. [12 8 6 3 1] → [12 8 6 (3 1)]
           ¯2∘↑   ⍝ Take the last two elements
                  ⍝   If input length is 1, ↑ becomes "overtake" and yields [0 n]
        0~⍨       ⍝ Remove zeros to undo "overtake"
       ⊂          ⍝ Enclose to make it the initial item
 ¯2∘↓,∘           ⍝ Append to the original array with last two elements dropped

(+∘(⊃∘⌽+⊃⌊2∘⊃+2×2⊃⌽),⊢)/  ⍝ Reduce by the logic, right to left
          2∘⊃+2×2⊃⌽       ⍝ Choice (2):
          2∘⊃+            ⍝   T_{k-2} +
              2×2⊃⌽       ⍝   2*t_2
        ⊃                 ⍝ Choice (1): T_{k-1}
   (⊃∘⌽+           )      ⍝ Common term: + t_1
 +∘                       ⍝              + t_n
                    ,⊢    ⍝ Prepend the resuting value T_k to the DP array
(                     )/  ⍝ Reduce by the function above

⊃⊃  ⍝ Remove the layering and take the first element (which is T_n)
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ -1: ⊃∘⌽⊢/ \$\endgroup\$ – Adám Feb 16 at 9:19
  • \$\begingroup\$ Nice answer. "there are two possibly optimal ways to help the worst person cross the bridge:". How do we know those are only two possibilities? \$\endgroup\$ – Jonah Feb 24 at 2:46
  • 1
    \$\begingroup\$ @Jonah It is just an observation, not a mathematically rigorous argument, but it coincides with the result on the paper linked by xnor. \$\endgroup\$ – Bubbler Feb 24 at 3:24
2
\$\begingroup\$

Python 2, 89 bytes

lambda t:t.sort()or reduce(lambda x,c:x+[min(x[-2]+x[1]*2,x[-1])+c+x[0]],t[2:],t[:2])[-1]

Try it online!

Uses the same formulation as my APL answer, except that direct reduction turns out shorter in this case. Incidentally, this wins against all the previous entries (except APL).

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Scala, 113 135 (darnit)

def f(a:Seq[Int]):Int={val(s,b)=a.size->a.sorted;if(s<4)a.sum-(s+1)%2*b(0)else b(0)+Math.min(2*b(1),b(0)+b(s-2))+b(s-1)+f(b.take(s-2))}

Ungolfed somewhat:

def f(a:Seq[Int]):Int = {
    val(s,b)=a.size->a.sorted      // Sort and size
    if (s<4) a.sum-(s+1)%2*b(0)    // Send the rest for cases 1-3
    else Math.min(b(0)+2*b(1)+b(s-1),2*b(0)+b(s-2)+b(s-1)) + // Yeah.
        f(b.take(s-2))             // Repeat w/o 2 worst
}

Tester:

val tests = Seq(Seq(9)->9, Seq(1,2,5,8)->15, Seq(1,3,4,5)->14, Seq(3,1,6,8,12)->29, Seq(1,5,1,1)->9, Seq(1,2,3,4,5,6)->22, Seq(1,2,3)->6, Seq(1,2,3,4,5,6,7)->28)
println("Failures: " + tests.filterNot(t=>f(t._1)==t._2).map(t=>t._1.toString + " returns " + f(t._1) + " not " + t._2).mkString(", "))

Not great in general, but maybe not bad for a strongly-typed language. And begrudging thanks to xnor for spotting a case I didn't catch.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This paper has an expression for the optimal time that's the min of multiple possibilities. Are you sure your solution is optimal in all cases? \$\endgroup\$ – xnor Mar 17 '16 at 3:23
1
\$\begingroup\$

Ruby, 104 95 93 bytes

I have been advised to separate my answers out.

This is a solution based on my Python 2 solution and Theorem 1, A2:09 of this paper on the Bridge and Torch Problem.

->n,t{z=t.sort!.reduce(:+)+t[0]*(n>1?n-3:0);(n/2).times{|k|z+=[0,2*t[1]-t[0]-t[~k*2]].min};z}

Ungolfing:

def b(n, t) # using length as an argument
  z = t.sort!.reduce(:+) + t[0] * (n>1 ? n-3 : 0)
  (n/2).times do each |k|
    a = t[1]*2 - t[0] - t[-(k+1)*2] # ~k == -(k+1)
    z += [0, a].min
  end
  return z
end
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Pyth, 34 bytes

W>l=SQ3=+Zs[hQ.)QhS[y@Q1+hQ.)Q;+Zs

There's probably some way to write it as a reduce or some other functional magic, but I've spent enough time doing high school programming coursework today that actually writing anything resembling good code is a nice change of pace.

Try it online!

|improve this answer|||||
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.