7
\$\begingroup\$

Introduction

There is a group of people that have to cross a rickety bridge that can only support two people at a time. It is a dark and foggy night, but unfortunately, the group only has one lamp. The bridge must be crossed by an individual or pair that is holding the lamp. When a pair is traveling together, they must move at the pace of the slower individual.

The goal is to write a function that takes the travel time of each individual and outputs the minimum travel time of the group.


Example

If the input list is [1, 2, 5, 10], the output should be 17, because the minimum crossing time is this order:

1 and 2 cross together  (2 minutes)
1 crosses back          (1 minute)
5 and 10 cross together (10 minutes)
2 crosses back          (2 minutes)
1 and 2 cross together  (2 minutes)

and 2 + 1 + 10 + 2 + 2 = 17.


Data

input             | output
------------------+-------
[1]               | 1
[1,2]             | 2
[1,2,3]           | 6
[1,2,3,4]         | 11
[1,2,3,4,5]       | 16
[1,2,3,4,5,6]     | 22
[1,2,3,4,5,6,7]   | 28
[1,2,3,4,5,6,7,8] | 35
[1,2,5,10]        | 17
[1,1,1,1]         | 5
[1,1,1,1,1]       | 7
[2,3,5,7,11]      | 29
[3,1,4,1,5]       | 13
[2,1,7,1,8]       | 15

Challenge

Given a list of travel times, output the minimum amount of time it takes to cross the bridge.

This is , so the shortest code in bytes wins.

\$\endgroup\$
2
  • \$\begingroup\$ Are there complexity requirements? (Can I brute-force the solution?) \$\endgroup\$ Aug 22, 2018 at 18:36
  • 5
    \$\begingroup\$ Unfortunately, this is an exact duplicate of the question linked, as the answers on that challenge are valid and competitive for this one as well. Well written challenge though! \$\endgroup\$ Aug 22, 2018 at 19:07

0

Browse other questions tagged or ask your own question.