25
\$\begingroup\$

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 , I don't suppose anyone else will use a more efficient solution either...)

Scoring

  • this is ; 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!
\$\endgroup\$
5
  • \$\begingroup\$ Also, since the first input is just the length of the list, it could just be ignored right? \$\endgroup\$ – pxeger Apr 18 at 19:21
  • \$\begingroup\$ @pxeger Yes, that is allowed. \$\endgroup\$ – hyper-neutrino Apr 18 at 19:31
  • 2
    \$\begingroup\$ I am not a native speaker, but "standard loopholes apply" seem to be the opposite of what I'd expect \$\endgroup\$ – Pedro A Apr 19 at 4:33
  • 5
    \$\begingroup\$ @PedroA I suppose that statement is a bit misleading. I've just gotten lazy; usually in the past, I'd make it so "Standard Loopholes" was a link to the post about standard loopholes, so it would be "this consensus about standard loopholes applies to this post", which makes a lot more sense. I've reworded it a bit; hopefully it makes a bit more sense for someone unfamiliar with the premise or the language. You are correct though, actually. \$\endgroup\$ – hyper-neutrino Apr 19 at 4:37
  • 2
    \$\begingroup\$ 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. A slight correction: running vs. walking will not change how much rain hits you from the front if you are traveling the same distance either way. This is shown intuitively in this video \$\endgroup\$ – BioPhysicist Apr 19 at 14:26

14 Answers 14

9
\$\begingroup\$

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
    
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice approach! great explanation too \$\endgroup\$ – rak1507 Apr 18 at 20:48
9
\$\begingroup\$

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!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Here's -2 with named args. Nice first Husk answer. \$\endgroup\$ – Razetime Apr 19 at 3:52
  • \$\begingroup\$ Here's an extra -2 by shuffling things around (and using M instead of m) to avoid having to flip functions. I'll join Razetime's compliments, nice answer! \$\endgroup\$ – Leo Apr 19 at 5:38
  • \$\begingroup\$ Thanks Razetime and Leo \$\endgroup\$ – rak1507 Apr 19 at 9:44
6
\$\begingroup\$

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].

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ Don't take n for 51 bytes \$\endgroup\$ – att Apr 19 at 18:42
  • \$\begingroup\$ @att Nice find, that's a neat way to handle the recursion by chopping off the end! How about you an own answer for the bounty? \$\endgroup\$ – xnor Apr 20 at 3:20
  • \$\begingroup\$ Posted. \$\endgroup\$ – att Apr 20 at 3:59
5
+200
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ f=(n,[k,...a])=>n>0&&Math.min(f(n-1,a),f(n-2,a)+k)+k \$\endgroup\$ – l4m2 Apr 21 at 7:08
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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...

\$\endgroup\$
1
  • 1
    \$\begingroup\$ If you're doing golfy stuff like in-lining assignments inside of function calls, I'd be less confident about your real-world code too ;-) \$\endgroup\$ – Giuseppe Apr 19 at 11:24
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Very nice, thanks a lot! \$\endgroup\$ – Kirill L. Apr 28 at 14:18
0
\$\begingroup\$

Charcoal, 39 30 bytes

I⌊EΦEX²⊕LθΦ⍘ι12μ⁼ΣιLθΣEι×Iλ§θμ

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

      ²                         Literal 2
     X                          Raised to power
         θ                      Input array
        L                       Length
       ⊕                        Incremented
    E                           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
                    L            Length
  E                             Map over strings
                       ι        Current string
                      E         Map over characters
                          λ     Current character
                         I      Cast to integer
                        ×       Multiplied by
                            θ   Input array
                           §    Indexed by
                             μ  Current index
                     Σ          Take the sum
 ⌊                              Take the minimum
I                               Cast to string
                                Implicitly print

Previous less brute-forcey 39-byte version:

≔⟦υ⟦ω⟧⟧ηFθ⊞η⁺⁺§η±²2⁺§η±¹1I⌊E⊟ηΣEι×Iλ§θμ

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.

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

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

I⌊E⊟ηΣEι×Iλ§θμ

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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