How many umbrellas to cover the beach?

Question

You work at a beach. In the afternoon, the sun gets quite hot and beachgoers want to be shaded. So you put out umbrellas. When you put out umbrellas you want to shade the entire beach, with as few umbrellas as possible.

Umbrellas come in many sizes. However, larger umbrellas are susceptible to being pulled away by the wind, so in the morning you have to go to the beach and do a soil test. The soil test tells you, for each spot on the beach, the size of the largest umbrella that could be safely placed.

So after your soil test, you get back a list of positive integers. For example:

[2,1,3,1,3,1,1,2,1]

Each number represents the maximum radius of an umbrella that can be placed at that location. A radius \$r\$ umbrella covers itself, and \$r-1\$ spots to both its left and right.

For example a radius 3 umbrella covers:

• itself
• the two spaces directly adjacent to it,
• the two further spaces adjacent to those,

Your task is to write a computer program which takes the results of the soil test as a list of positive integers, and gives back the minimum number of umbrellas required to cover all the spots on the beach.

For example if the soil test gives back [2,1,4,1,4,1,1,3,1], then you can cover the beach with 2 umbrellas:

            X X X X X
X X X X X X X   |
      |         |
 [_,_,4,_,_,_,_,3,_]

So the output of the program should be 2.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Test cases

[9,2,1,3,2,4,2,1] -> 1
[9,9,9,9,9,9,9,9] -> 1
[1,1,1,1,1,1,1,1] -> 8
[2,1,4,1,4,1,1,3,1] -> 2
[5,1,3,1,3,1,1,1,6] -> 2
[4,1,1,3,1,1] -> 2

Answer 1

Charcoal, 30 27 26 bytes

Ｗ‹↨υ⁰Ｌθ⊞υ⌈Ｅθ∧‹⁻λ↨υ⁰κ⁺λκＩＬυ

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

Ｗ‹↨υ⁰Ｌθ

Until all of the beach has been covered, ...

⊞υ⌈Ｅθ∧‹⁻λ↨υ⁰κ⁺λκ

... filtering on those umbrellas whose left end is not to the right of the first uncovered index, pick the one that maximises the next uncovered index.

ＩＬυ

Output the number of umbrellas used.

Edit: Saved 1 byte by porting @tsh's optimisation. Example: Take the input [1,4,1,1,3,1,1]. Initially, five umbrellas lie to the right of index 0, the valid two being the 1 at index 0 itself, and the 4 at index 1, which also covers indices 1 to 4. The maximum next uncovered index is therefore 5, obtained by choosing the 4. The 1 at index 6 is the only umbrella to the right of index 5, and the maximum next uncovered index is therefore 7, obtained by choosing the 3. This completes the coverage of the beach using two umbrellas.

A port of @Jonas' J solution was also 27 bytes:

ＵＭθＥ謋↔⁻μκιＷ⌈⌊θ«→≧×⌊θθ»Ｉ⊕ⅈ

Attempt this Online! Link is to verbose version of code. Explanation:

ＵＭθＥ謋↔⁻μκι

Convert each umbrella into a list of 0s and 1s where the 0s are the locations that are covered.

Ｗ⌈⌊θ«

Repeat until opening an umbrella will cover the beach.

→

Keep count of the number of umbrellas opened.

≧×⌊θθ

Zero out the locations covered by the largest remaining umbrella.

»Ｉ⊕ⅈ

Output the number of umbrellas required.

Previous 30-byte brute force solution:

Ｉ⌊ＥΦＸ²Ｌθ⬤θ⊙θ‹↔⁻μξ×ν﹪÷ιＸ²ξ²Σ⍘ι²

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

     ²                          Literal integer `2`
    Ｘ                           Raised to power
       θ                        Input array
      Ｌ                         Length
   Φ                            Filter over implicit range
         θ                      Input array
        ⬤                       All indices satisfy
           θ                    Input array
          ⊙                     Any value satisfies
               μ                Inner index
                ξ               Innermost index
              ⁻                 Difference
             ↔                  Absolute value
            ‹                   Is less than
                     ι          Outer value
                    ÷           Integer divided by
                       ²        Literal integer `2`
                      Ｘ         Raised to power
                        ξ       Innermost index
                   ﹪            Modulo
                         ²      Literal integer `2`
                 ×              Multiplied by
                  ν             Innermost value
  Ｅ                             Map over implicit range
                            ι   Current value
                           ⍘    Convert to base
                             ²  Literal integer `2`
                          Σ     Take the sum (i.e. popcount)
 ⌊                              Take the minimum
Ｉ                               Cast to string
                                Implicitly print

Answer 2

C89, 89 bytes

-11 bytes thanks to @Martin Kealey

int m,i,x;f(v,n)int*v;{for(i=n;i--;m=abs(m-i)<x?x+i:m)x=v[i];return m>=n?m=0,1:1+f(v,n);}

Try it online!

int m, i, x;
int f(int *v, int n)
{
    for(i=n; i--;)
    {
        extern int abs();
        x = v[i];
        if (abs(m-i) < x) m = x+i;
    }
    
    if (m>=n){
        m = 0;
        return 1;
    }
    else { 
        return 1 + f(v, n);
    }
}

Answer 3

05AB1E, 16 13 bytes

-3 thanks to @KevinCruijssen

gDδα›æʒøOß}øg

Try it online!

Explanation

g         # push the length
D         # twice
δα        # create the 2D array a[i][j] = abs(i-j)
›         # compare each value to the correct value in the input
æ         # take the powerset
ʒ         # and keep sets such that:
 ø         # if transposed
 O         # and summed
 ß         # the minimum value
}         # (is 1)
ø         # transpose
g         # and return the length

Requiring that the minimum is 1 is valid because in an optimal solution exactly one umbrella covers the leftmost position.

Transposing and then taking the length finds the minimum length, due to the way transposing works on different-sized arrays.

δ›Å\ really feels like it can be shorter, but I can't find anything.

Answer 4

R, 61 bytes

f=\(b,p=l,l=sum(b|1))sum(if(p>0)1+f(b,min((1:l-b)[1:l+b>p])))

Attempt This Online!

Ungolfed code

f=function(b,p=1){ # begin at position p=1
    l=length(b)
    s=1:l-b+1 # start positions of umbrellas
    e=1:l+b-1 # end positions of umbrellas
    if(p>l)0  
    else 1+f(b,max(e[s<=p])+1) 
              # update position to 
              # furthest end of umbrella  
              # with start before current position
}

Answer 5

J, ^{36 34 33 31} 33 bytes

{{1>.#}.(OR>./)^:a:#.y>|@-/~#\y}}

Attempt This Online!

-1 thanks to Bubbler suggesting a conversion to explicit fn.

Also thanks to Bubbler for pointing out a bug when a single umbrella covers everything, which must be handled as a special case.

Inspired by Neil's idea, but with an array implementation.

Consider the example 2 1 4 1 4 1 1 3 1:

• y>|@-/~#\y For each entry in the list, this shows what the beach would look like with only that umbrella open, using a 1 0 list. The full phrase returns a binary matrix, with each row showing one "isolated umbrella" version of the beach:

  1 1 0 0 0 0 0 0 0
  0 1 0 0 0 0 0 0 0
  1 1 1 1 1 1 0 0 0
  0 0 0 1 0 0 0 0 0
  0 1 1 1 1 1 1 1 0
  0 0 0 0 0 1 0 0 0
  0 0 0 0 0 0 1 0 0
  0 0 0 0 0 1 1 1 1
  0 0 0 0 0 0 0 0 1
  

• #. Interpret those as binary numbers:

  384 128 504 32 254 8 4 15 1
  

  Conceptually, we'll still be working with 1 0 lists, but using integers will help us shorten the necessary computations.

• (...^:a:) Accumulate the results of ... until a fixed point...

• (...>./) On each iteration, we find the row with the farthest rightward span of ones, provided that span starts at the left:

  1 1 0 0 0 0 0 0 0
  0 1 0 0 0 0 0 0 0
  1 1 1 1 1 1 0 0 0  <- farthest rightward span
  0 0 0 1 0 0 0 0 0
  0 1 1 1 1 1 1 1 0  <- doesn't count since it starts with 0
  0 0 0 0 0 1 0 0 0
  0 0 0 0 0 0 1 0 0
  0 0 0 0 0 1 1 1 1
  0 0 0 0 0 0 0 0 1
  

  This row, however, is nothing but the largest integer in our list, because of how binary numbers work.

• (OR...) We then add that "farthest right" row elementwise to every row, essentially "blocking out" everything it covers from all rows. This is nothing but the bitwise OR operation. The transformation in this step corresponds to our chosen umbrella being deployed:

  1 1 1 1 1 1 0 0 0
  1 1 1 1 1 1 0 0 0
  1 1 1 1 1 1 0 0 0
  1 1 1 1 1 1 0 0 0
  1 1 1 1 1 1 1 1 0
  1 1 1 1 1 1 0 0 0
  1 1 1 1 1 1 1 0 0
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 0 0 1
  

  Then we continue. Our process will reach a fixed point (a matix of all ones) in n + 1 steps, where n is the minimum number of covering umbrellas.

• #}. So we kill one element and get the length.

• 1>. Finally, we return the max of that length and 1. This is needed for the case where a single umbrella covers the entire beach, because otherwise the algorithm above will return 0 in this case.

Answer 6

JavaScript (Node.js), 60 bytes

a=>(g=i=>a[i]&&-~g(a.reduce((m,r,j)=>j-i<r&r+j>m?r+j:m)))(0)

Try it online!

---

Python 3, 73 bytes

f=lambda a,i=0:i<len(a)and-~f(a,max(r+j for j,r in enumerate(a)if j-i<r))

Try it online!

Answer 7

Nekomata, 13 bytes

Jᵐ{x:ᵒ≈>~}aş#

Attempt This Online!

Jᵐ{x:ᵒ≈>~}aş#
J               Split the list into parts
 ᵐ{x:ᵒ≈>~}      Check that each part can be covered by an umbrella:
 ᵐ{      }          For each part:
   x:ᵒ≈                 Create a table a[i][j] = abs(i-j)
       >~               Check that there is at least one row in the table
                        that is smaller than the corresponding item in the input
          aş    Find the shortest solution
            #   Take the length

This may output the same result multiple times. For example, the input [2,1,4,1,4,1,1,3,1] can be split into [[2,1,4,1,4],[1,1,3,1]] or [[2,1,4,1,4,1],[1,3,1]], and the output is 2 in both cases.

Answer 8

JavaScript (ES6), 87 bytes

Brute force.

a=>(g=(i,b=a,v=a[i++])=>v?Math.min(g(i,b),1+g(i,b.map(q=>--i*i<v*v?0:q))):b.join``*i)``

Try it online!

Answer 9

Python, 182 bytes

-2 bytes, thanks to xigoi

lambda l:(S:={*range(L:=len(l))})and[len(c)for n in S|{L}for c in combinations([range(i-k+1,i+k)for i,k in enumerate(l)],n)if{L}.union(*({*r}for r in c))>S][0]
from itertools import*

Attempt This Online!

ungolfed code:

import itertools
def f(l):
 l=[range(i-k+1,i+k)for i,k in enumerate(l)]
 S={*range(L:=len(l))}
 for n in range(len(l)+1):
  for c in itertools.combinations(l,n):
   s=set()
   for r in c:
    s|={*r}
   if s>S: # s=S not possible as L in s\S
    return len(c)

Brute force solution, goes through all possible sets of umbrellas ordered by size and picks the first one that covers the whole range

Answer 10

JavaScript, 62 bytes

f=(a,s=0)=>a[s]?1+f(a,Math.max(...a.map((v,i)=>i-v<s&&i+v))):0

Try it online!

Greedy algorithm: pick the umbrella that covers the most spaces while including the first uncovered space.

Answer 11

sed, 424 bytes

Thank you for restricting umbrella sizes to 9, otherwise sed stops to be the natural choice for solving this thing. (-; The maximum number of umbrellas is also limited to nine; you can upgrade to the big-beach-edition for a couple of extra bytes as an in-app-purchase.

I got distracted so often, that I decided to publish this initial version solving the problem, although I'm feeling that there are still ten to twenty bytes to golf away on a rainy day.

How it works:

• loop 1 creates all possible combinations of umbrellas used or not
• loop 2 sorts those combinations by their number of umbrellas used, which is awfully slow with this approach for 2^beachsize combinations!
• loop 3 takes one combination after the other to test whether they cover the beach with those sub-elements:
  • loop 4 makes a separate line for each umbrella
  • loop 5 opens the umbrellas by couting down there size and spreading =
  • loop 6 transposes the beaches from lines to columns (this will probably only work with wet sand)
  • if there is a line without umbrella, this means sun will hit the beach, so we have to start with the next combination of loop 3
• loop 7 finally counts the number of umbrellas in the first shady combination

G
s/^/_/
:1
s/(\S*)_(\S)(\S*.)/\1-_\3\1\2_\3/
t1
:2
s/-(\S*_)/0\1#/
s/(\S*_(#*)\n)(\S*_\2#+\n)/\3\1/
t2
h
:3
s/\S*\n//
x
s/_.*/\n/
:4
s/^(-*)([0-9])(\S*.)/\1-\3\1\2_\3/
s/_\S/-_/
t4
s/-*/987654321#/
:5
s/((.)(.).*#.*)\2/\1x\3x/
s/(x=*)-/\1=/
s/-(=*)x/=\1/
s/x//g
t5
s/#./&!_/
s/\n//g
:6
s/!(.*_)([^x])/!\2\1x/
t6
s/_x*/_/g
s/!/!\n/
/__/!t6
s/!/!#/
/\n[-0]+(\n|_)/!b7
g
b3
:7
s/((.)(.).*!)\3(.*)1.*/\1\2\4/
t7
s/.*!(.).*/\1/

Try it online! Note that beaches of 8 parts or bigger will time out on TIO. Adding a g flag in the sorting part of the second loop drastically reduces execution time, but still not enough for hard cases.

Answer 12

Python3, 358 bytes

E=enumerate
F=lambda h,i,a:{*[i+j for j in range(1,a)if i+j<len(h)]+[i-j for j in range(1,a)if i-j>=0],i}
def f(h):
 q,m=[(F(h,i,a),1)for i,a in sorted(E(h),key=lambda x:x[1])[::-1]],-1
 while q:
  a,b=q.pop(0)
  if len(a)==len(h):m=b if m==-1 else min(m,b);continue
  for x,y in E(h):
   if x not in a and(m==-1or b+1<m):q=[({*a,*F(h,x,y)},b+1)]+q
 return m

Non-greedy (where is the fun otherwise?) with a basic heuristic for the sake of speed.

Try it online!

Answer 13

05AB1E, 18 17 bytes

x<Ls-ā©+æʒ˜®åP}øg

-1 byte thanks to @CommandMaster.

Try it online or verify all test cases.

Explanation:

x<      # Calculate the width of each umbrella:
x       #  Double each value in the (implicit) input-list (without popping)
 <      #  Decrease each by 1
Ls-ā©+  # Convert each to 1-based ranges it can cover:
L       #  Convert each inner value to a [1,value]-ranged list
 s-     #  Subtract the values of the input-list from each value of the lists
   ā +  #  Add the 1-based indices
    ©   #  And also store the list of 1-based indices in variable `®`
æʒ˜®åP} # Get all combinations of umbrellas that cover the entire beach:
æ       #  Get the powerset of this list of lists
 ʒ    } #  Filter it by:
  ˜     #   Flatten the list of lists
   ®åP  #   Check whether it contains all 1-based indices of value `®`
øg      # Output the least amount of umbrellas necessary to cover the beach:
ø       #  Zip/transpose; swapping rows/columns,
        #  discarding any trailing items of unequal length lists
 g      #  Pop and push the length
        # (which is output implicitly as result)

Try it step-by-step.

Answer 14

JavaScript (SpiderMonkey), 76 bytes

f=(a,k=0,b=-1)=>a[k]?1+Math.min(...a.map((v,i)=>i>b&v+k>i?f(a,v+i,i):1/0)):0

Try it online!

Try to fix m90's error

Answer 15

APL (Dyalog Unicode), 78 bytes

⌊/b/⍨×b←{(+/⍵)×∧/(1@(∊{n(1⌈⌊)(⍳¯1+2×⍵⌷v)+⍵-⍵⌷v}¨⍵/⍳n))n⍴0}¨{⍵⊤⍨n⍴2}¨⍳¯1+2*n←⍴v

Another brute force attack. The index origin is set to 1 (⎕IO←1). The variable v contains the integer vector to be evaluated.

I have some more work to do on this one. It is a bit convoluted as it is. I think I'm missing something obvious.

Try it on TryAPL.org!

Answer 16

Ruby, 102 100 97 bytes

->l{(r=*1..l.size).find{|c|r.combination(c).any?{|x|r&x.flat_map{|a|[*a-l[-a]+1...a+l[-a]]}==r}}}

Try it online!

Thanks value ink for some good ideas (-2/-3 bytes)

Answer 17

Desmos, 169 168 bytes

L=l.count
I=[1...L]
B=mod(floor(2n/2^I),2)
k=i-l[i]
H=[1...k]0
A=[min(∑_{i=1}^Ljoin(H[k>H],[1...2l[i]-1+min(k,0)]0+1,I0)[I]B[i])B.totalforn=[1...2^L]]
f(l)=A[A>0].min

Try It On Desmos!

Try It On Desmos! - Prettified

This brute forces every single umbrella combination, so expectedly this is very slow. In fact, this took about 40 or so seconds to finish running on my computer LOL.

Also, the code is absolutely horrendous and can definitely be golfed. I mean, just look at it....

Answer 18

Raku 68 bytes

map({$^a-$^b+1..^$^a+$^b},@_.kv).combinations.grep(^@_⊆*)>>.elems.min

simple brute force approch Try it online!

Answer 19

Scala, 113 bytes

Port of @tsh's Python code in Scala.

---

Golfed version. Try it online!

def f(a:Seq[Int],i:Int=0):Int=if(i<a.length)1+f(a,(0 to a.length-1).filter(j=>j-i<a(j)).map(j=>a(j)+j).max)else 0

Ungolfed version. Try it online!

object Main {
  def f(a: List[Int], i: Int = 0): Int = {
    if (i < a.length) {
      val maxJump = (0 until a.length)
        .filter(j => j - i < a(j))
        .map(j => a(j) + j)
        .max
      1 + f(a, maxJump)
    } else {
      0
    }
  }

  def main(args: Array[String]): Unit = {
    println(f(List(9,2,1,3,2,4,2,1))) // 1
    println(f(List(1,1,1,1,1,1,1,1))) // 8
    println(f(List(2,1,4,1,4,1,1,3,1))) // 2
    println(f(List(5,1,3,1,3,1,1,1,6))) // 2
    println(f(List(4,1,1,3,1,1))) // 2
  }
}

Answer 20

Python, 200 bytes

Not a very competitive answer, but it's the best I can do with the baseline python functions.

• l: is list of the beach spaces
• r: radius of already covered spaces
• p: amount of umbrellas and the final answer

Function goes through the beach from the left, finds the right most umbrella placing which covers all uncovered space to its left and reaches the farthest right. The function then starts again with the spaces to the right of the last placed umbrella and now with info of which spaces on the left are already covered. When all spaces are covered prints out number of placed umbrellas.

Any tips for making this more streamlined are welcome, thank you.

def f(l,r=0,p=0):
    m=r
    for u in range(len(l)):
        s=l[u]-1
        if u-s-r<1 and u+s>=m:
            m=u+s
            t=u
    if m>len(l)-2: return p+1
    else: return f(l[t+1:],m, p+1)

Attempt This Online!