You are going to be planting pumpkins soon, and you are preparing your supplies. Pumpkins come in all sorts of sizes and have their sizes written on the seed bag. A pumpkin that is size n will grow to be n units wide. However pumpkins need their space.
If a pumpkin is stuck between two other pumpkins with not enough space to reach its full size it will be ruined. So you want to make a program that takes a plan of how you are going to plant your pumpkins and determines if there is enough space for all the pumpkins.
As input it will take a list of non-negative integers. A zero will represent space with no pumpkins planted, and a positive number will represent that a pumpkin of that size will be planted there. So for example:
[0,0,0,1,0,0,0,0,0,5,0,0,0,6,0,0]
There are three pumpkins planted here of sizes 1
, 5
and 6
.
A pumpkin will grow to fill as much space as is given, but it can't detach from it's root, and it can't grow past the fence (the start and end of the list).
So for example in the above the 5 pumpkin could grow as follows:
[0,0,0,1,0,0,0,0,0,5,0,0,0,6,0,0]
^^^^^^^^^
Since that is 5 units wide and contains the place we planted it. But it can't grow like:
[0,0,0,1,0,0,0,0,0,5,0,0,0,6,0,0]
^^^^^^^^^
Because even though that is 5 units wide it doesn't include the root.
In perhaps a miracle of nature, pumpkins will push each other out of the way if they get in space they need. So for example if the 5
starts growing to the right, the 6
will push it back to the left since it needs that space.
Ultimately this means if there is a valid way for the pumpkins to grow without ruining each other they will.
It's only when there isn't enough space at all will a pumpkin get ruined.
So in the example everything is ok, this plan works:
[0,0,0,1,0,5,5,5,5,5,6,6,6,6,6,6]
But here:
[6,0,0,0,0,3,0,0,0,0,0]
There's not enough space for the 6
to grow even when the 3
grows as far to the right as possible
Task
Take as input a non-empty list of non-negative integers. Output whether that list is a working plan. You should output one of two distinct values if it is a working plan and the other if it is not.
This is code-golf so the goal is to minimize the size of your source code as scored in bytes.
Test cases
[1] -> True
[0,0] -> True
[3] -> False
[3,0] -> False
[3,0,0,2,0] -> True
[0,3,0,4,0,0,0] -> True
[0,0,1,0,3,1,0,0] -> False
[0,0,0,1,0,0,0,0,0,5,0,0,0,6,0,0] -> True
[6,0,0,0,0,3,0,0,0,0,0] -> False
[0,0,5,0,0,1] -> True
[2,0,2] -> False
[0,0,2,2] -> False
[2,2,0,0] -> False