Is it better to walk or run in the rain?

Question

The age-old question - is it better to walk or run? There are two trains of thought. If you run, you cause the rain to effectively hit you from the front, which increases your surface area and basically causes you to run into the raindrops, getting hit with more water. However, if you walk, you spend longer in the rain.

Actually, there is no good answer, because if the rain is about to get worse, you'd better run to get out of it even if you get hit more immediately, because you don't want to get hit by the rain later on.

In fact, if you can't predict the future, you don't actually have a good way to know what the optimal strategy is. However, we are not subject to such constraints, and can take the future as input.

Specification

You are trying to get somewhere \$N\in\mathbb{Z}_{\geq1}\$ metres away (\$N\$ will be supplied as input). However, it has started raining. For the next \$N\$ seconds, a certain amount of rain will be falling per second, and will be constant within the span of a 1-second period of time. Specifically, during the \$i\$th second (\$1\leq i\leq N\$), there will be \$a_i\in\mathbb{Z}_{\geq0}\$ units of rain. You will also be given \$\{a_1,a_2,\dots,a_N\}\$ as input. It rains the same amount at all locations across that distance, but once you reach your destination, you will no longer get hit by rain.

Now, you want to know how to get rained on the least. During each second, you must either walk or run. On the \$i\$th second, if you walk, you will move 1 metre and get hit by \$a_i\$ units of rain. If you run, however, you will move 2 metres but get hit by \$2a_i\$ units of rain. Note that if you are 1 metre from the finish, if you run, it only makes sense to be hit by half of that because you're in the shelter after the first half-second, but since \$\frac{2a_i}2=a_i\$, you can just walk instead, so you don't really need to consider this case.

What is the least amount of rain you can get hit by in order to cross those \$N\$ metres?

I/O Format

You may take \$N\$ as an input if you wish. Since it's the same as the length of the list, you're allowed to exclude it.

You may take \$\{a_1,a_2,\dots,a_N\}\$ as an input if you wish. I'm not sure how you'd solve the problem without it.

You must output a single non-negative integer, the least amount of rain (in units) that you can be hit by in order to cross those \$N\$ metres.

Example

10 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

The rain is progressively getting worse. Clearly, every second you spend outside makes the rain worse, so it's better to get hit by double the amount now than wait and get hit by the larger amount later. If you run for 5 seconds, you will move 10 metres and get hit by \$15\times2=30\$ units of rain. In comparison, if you walk for 10 seconds, you get hit by 55 units.

6 [1, 0, 1, 0, 1, 0]

The rain is acting weird. In this case, if you run for 3 seconds, you get hit by 4 units of rain. However, if you only run during the second and fourth seconds, and walk during the first and third, you still cover 6 metres, but here you only get hit by 2 units since you run during the time when the rain is stopped, and no rain doubled is still no rain.

Test Cases

7 [1, 0, 2, 5, 3, 0, 0]           -> 11
1 [1]                             -> 1
6 [2, 5, 5, 2, 3, 1]              -> 18
1 [5]                             -> 5
3 [3, 3, 5]                       -> 9
9 [1, 0, 3, 1, 1, 1, 3, 2, 3]     -> 9
5 [3, 2, 0, 0, 0]                 -> 5
7 [3, 1, 4, 4, 3, 5, 3]           -> 19

You can generate more test cases here; the input accepts the max \$N\$ and the max \$a_i\$. It's also an ungolfed reference implementation (the move function) (I could have probably figured out a DP relation to solve this more efficiently, but I was too lazy, and since it's code-golf, I don't suppose anyone else will use a more efficient solution either...)

Scoring

• this is code-golf; since you are writing on your umbrella and have limited space, your code must be as short as possib- wait, you had an umbrella? [...]
• standard loopholes are forbidden as usual
• have fun and happy golfing!

Answer 1

J, ^{44 39} 27 bytes

#{0,[:<./]+/\@#~1+2#:@i.@^#

Try it online!

^{-12 after reading rak1507's clever idea!}

Using 3 3 5 as an example:

• 1+2#:@i.@^# One plus all binary numbers from 0 to 2^<length>-1

  1 1 1
  1 1 2
  1 2 1
  1 2 2
  2 1 1
  2 1 2
  2 2 1
  2 2 2
  

• ]...#~ Use each of those as a mask to replicate the input (trailing zeros are just fill):

  3 3 5 0 0 0
  3 3 5 5 0 0
  3 3 3 5 0 0
  3 3 3 5 5 0
  3 3 3 5 0 0
  3 3 3 5 5 0
  3 3 3 3 5 0
  3 3 3 3 5 5
  

• +/\@ And scan sum each row:

  3 6 11  0  0  0
  3 6 11 16  0  0
  3 6  9 14  0  0
  3 6  9 14 19  0
  3 6  9 14  0  0
  3 6  9 14 19  0
  3 6  9 12 17  0
  3 6  9 12 17 22
  

  At this point the problem is essentially solved, because the 3rd column is "how wet we are after moving 3 meters". All we need to do now is...

• [:<./ Take the min of all rows and...

• #{0, Pluck the 3rd column.

original approach, 39 bytes

[:<./1#.[(*2-~/\0,#<.+/\)"#.1+2#:@i.@^#

Try it online!

Tries all possible combinations.

Using 3 3 5 as an example:

• 1+2#:@i.@^# One plus all binary numbers from 0 to 2^<length>-1

  1 1 1
  1 1 2
  1 2 1
  1 2 2
  2 1 1
  2 1 2
  2 2 1
  2 2 2
  

• +/\ Scan sum each row

  1 2 3
  1 2 4
  1 3 4
  1 3 5
  2 3 4
  2 3 5
  2 4 5
  2 4 6
  

• #<. Minimum of each element and input length, 3 in this case:

  1 2 3
  1 2 3
  1 3 3
  1 3 3
  2 3 3
  2 3 3
  2 3 3
  2 3 3
  

• 0, Append 0:

  0 1 2 3
  0 1 2 3
  0 1 3 3
  0 1 3 3
  0 2 3 3
  0 2 3 3
  0 2 3 3
  0 2 3 3
  

• 2-~/\0 Successive deltas:

  1 1 1
  1 1 1
  1 2 0
  1 2 0
  2 1 0
  2 1 0
  2 1 0
  2 1 0
  

• * Multiply each by the input (J dyadic hook):

  3 3 5
  3 3 5
  3 6 0
  3 6 0
  6 3 0
  6 3 0
  6 3 0
  6 3 0
  

• 1#. Sum rows:

  11 11 9 9 9 9 9 9
  

• [:<./ Minimum:

  9
  

Answer 2

Husk, 13 bytes

▼moΣ↑L¹MṘπL¹2

A (sorta) port of my APL solution, just for fun. Husk is certainly an ... interesting ... language.

-2 each from Razetime and Leo

▼moΣ↑L¹MṘπL¹2
         πL¹2     cartesian power of [1,2] of length of the list
       MṘ         replicate
 moΣ↑L¹           sum of len(input) take each list
▼                 minimum

Try it online!

Answer 3

Wolfram Language (Mathematica), 41 bytes

f[a_,b___,c_]=a+Min[b~f~c,a+f@b]
f@a_:0=a

Try it online!

Input f[a1, a2, ..., aN].

Answer 4

Python 2, 51 bytes

f=lambda h=0,*t:t and h+min(f(*t),h+f(*t[:-1]))or h

Try it online!

Essentially a port of my Mathematica answer.

Answer 5

APL (Dyalog Extended), 23 bytes

{⍺⊃0,⌊⌿+\⍵/⍤1⍨⍉1+⊤⍳2*⍺}

Takes the length as ⍺ and the array as ⍵.

{⍺⊃0,⌊⌿+\⍵/⍤1⍨⍉1+⊤⍳2*⍺}
              ⍉1+⊤⍳2*⍺   all possible combinations of 1 and 2 of length ⍺
         ⍵/⍤1⍨           replicate ⍵
       +\                cumulative sum
     ⌊⌿                  minimum reduce
 ⍺⊃0,                    take the ⍺-th item (prepend a dummy item so it works with 0 based indexing)

Try it online!

Answer 6

Python 2, 53 bytes

f=lambda n,h=0,*t:n>0and h+min(f(n-1,*t),h+f(n-2,*t))

Try it online!

Uses a kind-of sketchy splatted input format of f(N, l_1, l_2, ..., l_N).

68 bytes

lambda n,l:min(sum(l[:n-k]+sorted(l[:-k])[:k])for k in range(n/2+1))

Try it online!

An efficient solution, unlike the exponential-time solution above. Picks how many seconds k to walk, minimizing the sum of first k numbers plus the sum of the smallest n-k among them which are chosen to be doubled.

Here's a nifty recursive version:

66 bytes

f=lambda n,l:l and min(sum((l+sorted(l)+[1e999])[:n]),f(n,l[:-1]))

Try it online!

Answer 7

JavaScript (ES6),  53  52 bytes

Saved 1 byte thanks to @l4m2

Expects (n)(list).

f=(n,[k,...a])=>n>0&&Math.min(f(n-1,a),f(n-2,a)+k)+k

Try it online!

Answer 8

Python 2, 57 bytes

A direct recursive implementation of the task.

f=lambda N,a:N>0and min(f(N-x,a[1:])+x*a[0]for x in[1,2])

Try it online!

Answer 9

Jelly, 11 bytes

2ṗx@"Fṁɗ€§Ṃ

A dyadic Link accepting \$N\$ on the left and \$A\$ on the right that yields the smallest amount of rain.

Try it online! Or see the test-suite.

How?

2ṗx@"Fṁɗ€§Ṃ - Link: integer, N; list (of length N), A
2           - two
 ṗ          - (implicit range of 2 = [1,2]) Cartesian power (N)
        €   - for each (walk/run list, x):
       ɗ    -   last three links as a dyad - f(x, A):
    "       -     zip with:
   @        -       with swapped arguments:
  x         -         repeat elements
     F      -     flatten
      ṁ     -     mould like (A) (i.e. cut to length N)
         §  - sums
          Ṃ - minimum

Answer 10

Vim, 90 bytes

"aDqmdd{"cyGO0<esc>Gp:.,$sor n
Go0<esc>ggVGJ0@awwhD:s/ /+/g
0C<c-r>=<c-r>"
,<c-r>b<esc>0"bD"cpG@mq@m0C<c-r>=min([<c-r>b])

Try it online!

This is vanilla vim (TIO supports V, which is backwards compatible with vim).

Vim doesn't really do branching recursion (at least, I don't know a good way without just writing pure vimscript, and it's possible that would be shorter, but certainly less fun!), so this answer uses a method that's different from most of the existing answers.

tl;dr: Takes N followed by the list, one int per line. Finds the minimum over prefices length n-k of the sum of that prefix plus its k smallest elements.

Long version:

How?

We observe that, given a list l of length n, if we choose to run k times, we will always choose to run on the k smallest elements of the length n-k prefix of l, and we will avoid the length k suffix of l entirely. Thus, the solution can be arrived at by concatenating the length n-k prefix with the sorted version of itself, and taking the length n head of this new list which has length 2*(n-k). Once 2*(n-k) becomes smaller than n, we must stop because we can't run more than n/2 times.

"aDqmdd{"cyGO0<esc>Gp:.,$sor n
                                               " input like 3, [2, 1, 5] newline separated
"aD                                            " cut N into register a
   qm                                          " def m:
     dd{                                       " delete current line, go to top
        "cyG                                   " copy file contents into register c
            O0<esc>                            " prepend 0
                   Gp                          " go to end, paste register c below
                     :.,$sor n                 " sort the new copy of l numerically
                                               " -> [0,2,1,5,1,2,5]
Go0<esc>ggVGJ0@awwhD:s/ /+/g
Go0<esc>gg                                     " append a 0 at the end, go back to top
                                               " -> [0,2,1,5,1,2,5,0]
          VGJ                                  " join all the lines by spaces
             0@aw                              " go to the (n+1)th number
                 w                             " go one more and **exit function if we can't**
                                               " note that the prepended and appended 0 were necessary for this magic stopping condition to work
                  hD                           " go left to the preceding space and delete the rest of the line
                                               " -> '0 2 1 5'
                    :s/ /+/g                   " replace all spaces with '+'
                                               " ->'0+2+1+5'
0C<c-r>=<c-r>"                                 " eval the current line and replace it with the result
                                               " -> '8'
,<c-r>b<esc>0"bD"cpG@mq@m0C<c-r>=min([<c-r>b]) 
,<c-r>b<esc>                                   " append a comma followed by the contents of register b
                                               " -> '8,'
            0"bD                               " cut the result of that into b (accumulates)
                "cp                            " write back the original list
                   G@m                         " go to the end and recurse, causing the last element of l to get deleted at the start of m
                      q@m                      " stop defining m, then call it
                                               " now register b contains a comma separated list of the sub-results
                         0C<c-r>=min([<c-r>b]) " take the min of those and replace the current (only) line with the result

The next iteration will look like

[2,1]
-> [0,2,1,1,2,0]
-> '0 2 1 1 2 0'
-> '0 2 1 1'
-> '0+2+1+1'
-> '4'
-> '4,8,'

and finally:

[2]
-> [0,2,2,0]
-> '0 2 2 0'
-> **try to go past end of line and exit instead**

So after m terminates, the final state is

buffer: 0 2 2 0
b: 4,8,

And so the (only) line in the buffer gets replaced with the evaluation of min([4,8,]) and we have the desired output: 4.

A note on the stopping condition @aww: In the common case, what we want to do is delete everything from the n+1st number onwards, which is achieved by just @aw (and no prepending/appending 0s). However, just @aw won't cause m to exist by error if it moves at all, i.e. even if there are just two numbers ('words') on the line, so we need the second w to actually cause m to exit, hence the need to prepend 0. (We also can't decrement N before reading it because that would fail when N=1--0w doesn't move 0 words because 0 isn't a count; it moves to the beginning of the line and then moves 1 word!). The appended 0 is so that we always have something to delete even when there are exactly n numbers left, otherwise we would stop without checking the prefix of size n/2 for even n.

Answer 11

05AB1E, 14 bytes

Åœʒà3‹}εœ€*}Oß

Try it online!

Tries all combinations by looking at every permutation of every integer partition of \$N\$ which only consists of 1's and 2's. Porting rak's APL answer will probably be shorter.

Answer 12

R, 68 67 bytes

Edit: -1 byte thanks to detective work by Giuseppe

f=function(t,r,s=r[1])`if`(t>0,s+min(f(t-1,u<-r[-1]),s+f(t-2,u)),0)

Try it online!

A recursive function that pretty much follows the logic of the explanation.

Note to R golfers: I thought it should be possible to still save a byte by assigning the twice-used r[-1] to a variable at the first use (since u<-r[-1] and u together are shorter than two r[-1]s), but I just couldn't seem to make it work. Giuseppe has now managed to to make it run by just swapping the order of the arguments to min or by using a different variable name, which is rather wierd and doesn't fill me with unbounded confidence about R for my real-world work...

Answer 13

Julia 0.6, 50 44 bytes

n<r=n>0&&(!i=r[]i+(n-i<r[2:end]);min(!1,!2))

Try it online!

Thanks to MarcMush for -6 bytes.

Answer 14

Charcoal, 39 30 bytes

Ｉ⌊ＥΦＥＸ²⊕ＬθΦ⍘ι12μ⁼ΣιＬθΣＥι×Ｉλ§θμ

Try it online! Link is to verbose version of code. Explanation:

      ²                         Literal 2
     Ｘ                          Raised to power
         θ                      Input array
        Ｌ                       Length
       ⊕                        Incremented
    Ｅ                           Map over implicit range
            ι                   Current index
           ⍘                    Convert to string
             12                 Using digits `12`
          Φ    μ                Remove leading digit
    Φ                            Filter strings where
                   ι             Current string
                  Σ              Digital sum
                 ⁼               Equal to
                     θ           Input array
                    Ｌ            Length
  Ｅ                             Map over strings
                       ι        Current string
                      Ｅ         Map over characters
                          λ     Current character
                         Ｉ      Cast to integer
                        ×       Multiplied by
                            θ   Input array
                           §    Indexed by
                             μ  Current index
                     Σ          Take the sum
 ⌊                              Take the minimum
Ｉ                               Cast to string
                                Implicitly print

Previous less brute-forcey 39-byte version:

≔⟦υ⟦ω⟧⟧ηＦθ⊞η⁺⁺§η±²2⁺§η±¹1Ｉ⌊Ｅ⊟ηΣＥι×Ｉλ§θμ

Try it online! Link is to verbose version of code. Explanation:

≔⟦υ⟦ω⟧⟧η

Start with an (empty) list of ways of walking and running to get to a distance of -1 and a list of one (empty) way of walking and running to get to a distance of 0.

Ｆθ⊞η⁺⁺§η±²2⁺§η±¹1

Build up the ways of walking and running to get to distances of 1..N.

Ｉ⌊Ｅ⊟ηΣＥι×Ｉλ§θμ

For each way of walking and running to get to a distance of N, calculate the amount of rain, and output the minimum.