# How many umbrellas to cover the beach?

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

• Probably would be nice to have a non-trivial test case where the output is not 2. Oct 17 at 21:01
• For extra bonus points, count the number of beachgoers present and factor in the gaps necessary to create enough walkable pathways for them to get to and from their shaded spots. :-þ Oct 18 at 10:01
• For some languages, it will be relevant whether 9 is the maximum radius. I suggest yes to attract those languages. Oct 19 at 7:22
• I think a 2D version of this problem would be interesting Oct 29 at 10:36

# Charcoal, 3027 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

• Technically that's not 26 bytes. Encoding those 26 characters as UTF-8 takes 68 bytes; as UCS-2/UTF-16 takes 52 bytes; or as UTF-32/UCS-4 takes 104 bytes. Oct 20 at 2:34
• @MartinKealey Charcoal has its own codepage. Oct 20 at 6:29
• Dang, I spent ten minutes trying to find that without success, so I concluded it probably didn't exist. Sorry, and thanks for the link. Oct 20 at 6:49

## 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);
}
}

• 82 bytes in C89: f(*v,n){for(int m=0,i=n,x;i--;m=x+i>m&x>i?x+i:m)x=v[i];return m<n?1+f(v+m,n-m):1;} Oct 18 at 12:11
• Fails case 6 (411311)
– l4m2
Oct 18 at 14:48
• @AZTECCO m is initially 0 and is cleared when returning
– l4m2
Oct 19 at 8:52
• With a little bit of rearranging I get if (abs(m-i) < x) if (x > m-i) m=x+i where the second (inner) test would appear to be tautological. Oct 20 at 7:58
• Oct 20 at 19:09

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

• δ›Å\ can simply be › for -3 bytes. :) Nice approach btw! Oct 17 at 16:15
• @KevinCruijssen Wait, what??? I was sure I tested that 🤦‍♂️. Thanks! Oct 17 at 16:30
• 13 characters, not bytes. (UTF-8 encoding is 22 bytes) Oct 20 at 2:38
• @MartinKealey 05AB1E (and most other languages you see on this site with non-ASCII characters) has its own codepage, so this actually is 13 bytes. Also see this meta post regarding encodings Oct 20 at 2:49

# 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
}


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

• The current code can be written as {{#}.(OR>./)^:a:#.y>|@-/~#\y}} for 30, but it fails for 9 9 9 9 9 9 9 because the matrix is all 1s already. Oct 18 at 23:24
• Thanks, I've added a special case for 0 which I think fixes the bug. Oct 18 at 23:36
• Very nice. I tried adapting to to Charcoal and it originally took 32 bytes, but I golfed it down to 27 (matching my existing answer) by inverting the bits, which allowed me to use vectorised multiply instead of bitwise and, thus avoiding the base conversion, plus it altered my loop condition which eliminated the special case.
– Neil
Oct 19 at 0:17
• Well, it used to match my existing answer, but @tsh optimised my algorithm saving me a byte.
– Neil
Oct 19 at 7:32

# 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!

• Ah of course, you don't have to check the right side of the umbrellas, since the affected ones can't exceed i anyway, so they won't affect the maximum.
– Neil
Oct 19 at 7:34

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

# 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!

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

• s&S==S is equivalent to s>=S. Oct 17 at 21:04

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

• a.length&& can be !!a&& for -2 bytes. EDIT: Actually, a?...:0 is -3 bytes: try it online. Oct 17 at 16:31
• @KevinCruijssen usually a+a is used
– l4m2
Oct 17 at 16:41
• Produces the wrong result for [4,1,1,3,1,1]. Oct 17 at 16:53

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

# 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
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!

# 05AB1E, 18 17 bytes

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


-1 byte thanks to @CommandMaster.

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.

• Nice solution, and completely different from mine! You can use øg to find the minimum length for -1 Oct 17 at 14:52

# 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

# 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!

# 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)

• 98 bytes Oct 20 at 16:46

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

Raku 68 bytes

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


simple brute force approch Try it online!

# 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
}
}


# 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
• 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!

• You can convert the indents into one space each and remove a bunch of the spaces in the function calls and after colons to save a few bytes. If the parser lets you do it, it's valid :p Nov 15 at 14:46
• just realized @tsh did the same thing but executed times better here Nov 15 at 15:09