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
[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
2 answers
Python 3.8+, 219 bytes
Short version:
from itertools import combinations as c
def m(w):
for k in range(n:=len(w)):
for y in c(range(n),k+1):
s=[0]*n
for x in y:
for r in range(w[x]):
s[max(0,x-r)]=s[min(n-1,x+r)]=1
if all(s):return k+1
Longer version with the tests.
from itertools import combinations
def umbrellas(values):
n = len(values)
for k in range(n):
for xs in combinations(range(n), k+1):
shadow = [False] * n
for x in xs:
for r in range(values[x]):
shadow[max(0, x-r)] = shadow[min(n-1, x+r)] = True
if all(shadow):
return k + 1
known_results = [
("214141131", 2),
("92132421", 1),
("11111111", 8),
("513131116", 2),
]
for nums, result in known_results:
res = min_shield([int(ch) for ch in nums])
print(nums, result, res)
Python 3.8, 117 bytes
def f(l):
r,s,t=0,0,0
while s<len(l):_,s,t,r=[t:=max(t,(s+i+h)*(h>i))for i,h in enumerate(l[s:])],t,0,r+1
return r
The idea is to find the left-most uncovered spot, find the umbrella that cover as many spots to the right as possible. Repeat until no more uncovered spot.
I'm sure this can be golfed further.
0 comment threads
1 comment thread