## Story

There are four warriors, they need to go through a dark tunnel. Tunnel is very narrow, every time only can let two warriors through, and there are lot of dangerous traps. Fortunately, they have a lamp that can illuminate the tunnel to avoid being trapped by the trap.

In order to pass this tunnel, they need five steps:

1. Two people go through the tunnel with the lamp
2. And then one people come back with the lamp
3. And then two people go through the tunnel with the lamp
4. And then one people come back with the lamp
5. And then two people go through the tunnel with the lamp
 
Each warrior has his own walking speed, we need to calculate the shortest time they have to cross the tunnel.
 
For example:
 
Four warriors is `a,b,c,d`. Their speed are `[3,4,5,6]`. It means they need 3 minutes, 4 minutes, 5 minutes and 6 minutes to cross the tunnel. The shortest crossing time should be 21 minutes, the method is as follows:
 
```
a and b go through the tunnel  ---> Spend 4 minutes
(Time spent should be calculated by the person who is slow)
a come back                    ---> Spend 3 minutes
a and c go through the tunnel  ---> Spend 5 minutes
a come back                    ---> Spend 3 minutes
a and d go through the tunnel  ---> Spend 6 minutes
```
Do you have any other better way?
 
## Task
Complete function `shortestTime()` that accepts 1 argument: `speed` that are the spent time of four warriors. Returns the shortest time that all warriors go through the tunnel.
 
**Note: The method in example above is not always the best way.**

## Example

Difficulty: introductory

Starter code:

def shortest_time(speed):
	

Solutions:
def shortest_time(speed):
    a,b,c,d = sorted(speed)
    return a+b+d + min(2*b, a+c)

from itertools import combinations

def shortest_time(xs, ys=[]):
    if len(xs) == 2:
        return max(xs)
    result = 999999999
    for i, j in combinations(range(len(xs)), 2):
        m = max(xs[i], xs[j])
        xs2 = xs[:i] + xs[i+1:j] + xs[j+1:]
        ys2 = ys + [xs[i], xs[j]]
        for k, y in enumerate(ys2):
            result = min(m + y + shortest_time(xs2+[y], ys2[:k] + ys2[k+1:]), result)
    return result

shortest_time=lambda a:a.sort()or a[0]+a[1]+min(2*a[1],a[0]+a[2])+a[3]

def shortest_time(speed):
    import itertools
    from collections import Counter
    times=[]
    for elem in itertools.combinations(speed,2):   
        end1 = [x for x in elem] 
        base1 = list((Counter(speed)-Counter(end1)).elements())             
        for i in itertools.combinations(end1,1):            
            base2 = [x for x in base1+[i[0]]]   
            if sum(end1)!= 2*end1[0]:
                end2 = [x for x in end1 if x != i[0]]
            else:
                 end2 = [end1[0]]   
            for j in itertools.combinations(base2,2):                                            
                end3 = [x for x in end2 +[j[0],j[1]]]
                base3 = list((Counter(base2)-Counter(j)).elements())
                for k in itertools.combinations(end3,1):             
                    base4 = [x for x in base3+[k[0]]]                             
                    times += [max(elem)+ i[0]+max(j)+k[0]+max(base4)]                                                                                               
    return min(times)

from math import inf
from itertools import chain, combinations, combinations_with_replacement

# thanks to "The capacity-C torch problem" by Roland Backhouse, Hai Truong
# https://www.sciencedirect.com/science/article/pii/S0167642315000118

def shortest_time(speed: [int]):
    forward_trips_num = 3       # for len(speed) == 4
    best_time = inf
#     path = []
    for forward_trips in combinations_with_replacement(list(combinations(speed, 2)), forward_trips_num):
        # not all people made at least one forward trip
        if any(list(chain(*forward_trips)).count(s) < speed.count(s) for s in set(speed)):
            continue
        sum_forward = sum([max(trip[0], trip[1]) for trip in forward_trips])     # time of all forward trips
        sum_return = 0                                                           # time of all return trips
        # number of return trips for each speed
        # (if there are several people with equal speed, the sum of all their return trips);
        returns = {s: 0 for s in set(speed)}
        for s in set(speed):
            # for every person the number of forward trips is one more than the number of return trips
            returns[s] += sum([trip.count(s) for trip in forward_trips]) - speed.count(s)
            sum_return += returns[s]*s

        if best_time > sum_forward+sum_return:
            best_time = sum_forward + sum_return
#             path = list(forward_trips) + list(chain(*[[(s,)]*returns[s] for s in set(speed)]))
#     print(path)
    return best_time

def shortest_time(speed):
    speed.sort()
    [a,b,c,d]=speed
    return min(a+3*b+d,2*a+b+c+d)

def shortest_time(speed):
    speed.sort()
    return speed[0]+speed[1]+speed[3] + min(2*speed[1],speed[0]+speed[2])

def shortest_time(speed):
    speed.sort()
    o = 3*speed[1]+speed[0]+speed[3]
    t = sum(speed[1:])+(len(speed)-2)*speed[0]
    return o if o<=t else t

def shortest_time(speed):
    
    copy = speed
    copy.sort()
    y = copy[0] + copy[1] * 3 + copy[3]
    minimum = copy.pop(0)
    answers = list()
    x = sum(copy) + minimum * (len(copy)-1)
    answers.append(x)
    answers.append(y)
    
    return min(answers)

def shortest_time(speed):
    speed = sorted(speed)
    return min(speed[1]*3+speed[0]+speed[3],speed[0]+sum(speed))