Predicting pumpkin planting plans' potential problems

Question

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

Answer 1

Jelly, 19 bytes

^{Hmm, I don't think we want any ṀȯLƊ on our pumpkins :( I also feel like this is beatable*!}

ŒṖṀȯLƊ⁼LƊȧTE$Ɗ€Ȧ$ƇẸ

A monadic Link accepting a list that yields 1 if a valid plan or 0 otherwise.

Try it online! Or see the test-suite.

How?

ŒṖṀȯLƊ⁼LƊȧTE$Ɗ€Ạ$ƇẸ - Link: list of integers, Plan
ŒṖ                 - all ways to partition Plan
                Ƈ  - filter keep those partitions for which:
               $   -   last two links as a monad:
             Ɗ€    -     for each part, last three links as a monad:
        Ɗ          -       last three links as a monad:
     Ɗ             -         last three links as a monad:
  Ṁ                -           maximum of the part
    L              -           length of the part
   ȯ               -           logical OR
       L           -         length of the part
      ⁼            -         equal? (1 if enough space for the largest pumpkin
                                    ignoring others in the part; 0 otherwise)
            $      -       last two links as a monad:
          T        -         truthy indices
           E       -         all equal? (1 for those parts with up to one
                                         non-zero; 0 otherwise)
         ȧ         -       logical AND (1 for good parts; 0 otherwise)
               Ạ   -     all? (1 for good partitions; 0 otherwise)
                 Ẹ - any? (1 if the plan will work; 0 otherwise)

---

* Maybe it's not that bad... This different approach is much more efficient but a couple of bytes longer (greedily grow the outermost pumpkin using outer zeros if possible) - outputs 0 if the plan is valid or 1 otherwise:

Ḋ⁸¹ƇḢ»TḟTḊ$fJḢ¤¡ṚµÐLẸ

Answer 2

Python 3, 73 72 67 bytes

f=lambda p,*v,s=0:p*s<1==f(*v,s=max(s+p,0<p or s)-1)if v else p+s<2

Try it online!

Takes input as varargs

s represents the amount of tiles a pumpkin can grow. Negative values, such as -2 mean that the pumpkin has two spaces to the left that it can grow. If s is positive, it means that this space will be occupied by a pumpkin, thus no pumpkins can grow.

Answer 3

Haskell, 55 54 bytes

-1 byte thanks to Wheat Wizard!

(!0)
(x:y)!i|x>0=i<1&&y!max(i+x-1)0|w<-i-1=y!w
_!i=i<1

Try it online!

The recursive function (!) looks at first like it should be implemented with a foldl, but the i<1&& check makes this infeasible.

Answer 4

J, ³⁵ 32 bytes

*=&(+/)0=[:(],(+{:)0&>.~0<:[)/<:

Try it online!

the idea

We'll devise an adjusted scan sum such that the number of zeros in that sum will tell us the number of possible fully grown pumpkins.

Example using 0 0 0 3 0 4 0 0 0:

• First, subtract 1:

  _1 _1 _1 2 _1 3 _1 _1 _1  (A)
  

• Also, note the locations of our input pumpkins seeds, as these indexes will require special treatment in our scan sum:

  0 0 0 1 0 1 0 0 0         (B)
  

• Now, consider the scan sum of A, but with a twist: If the sum is negative at one of the B locations, we'll reset it to 0:

  _1 _2 _3 0 _1 2 1 0 _1
           ^
           would be _1, but we reset it to 0
  

• Finally, realize what 0 means: It means a pumpkin has finished fitting into some available space. The zero reset reflects that in a configuration like:

   0   0   0   0  3  0  2  input
   0   0   3   3  3  2  2  grown pumpkins
  _1  _1  _1  _1  2 _1  1  input - 1
  _1  _2  _3  _4  0 _1  0  adjusted scan sum
  

  where the 3 pumpkin can fit entirely to the left of its seed with extra space to spare, pumpkin 2 cannot avail itself of that space.

• So, if the number of zeros in our scan-sum-with-a-twist equals the number of positive integers in our input, the input is valid.

Answer 5

JavaScript (ES6),  55  54 bytes

Returns a Boolean value.

This algorithm attempts to put each pumpkin as far as possible to the left.

a=>[...a,1].every((v,i)=>v?p=p+v>i++?p<i&&p+v:i:1,p=0)

Try it online!

---

JavaScript (ES6), 49 bytes

A port of @AnttiP's answer suggested by @AnttiP

Returns \$0\$ or \$1\$.

a=>a.every(p=>1>s*p*(s=(s+=p-1)*p<0?0:s),s=0)&s<1

Try it online!

Answer 6

Charcoal, 29 bytes

¹≔⁰η⊞θ¹Ｆθ¿ι¿‹η⁰⎚≔⌊⟦⁰⁻⊖ιη⟧η≦⊕η

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for enough space, nothing if not. Explanation:

¹

Assume there is enough space.

≔⁰η

Start with no space to the left of the patch. This variable becomes positive if there is space for a pumpkin to grow to the left or negative if a pumpkin is growing to the right.

⊞θ¹

End with no space to the right of the patch. This is handled by appending a pumpkin of size 1, which makes the calculations easier without changing the result.

Ｆθ

Loop through the patch.

¿ι

If there is a pumpkin, then:

¿‹η⁰

If a pumpkin to the left needs the space, then...

⎚

... there is a conflict, so clear the canvas.

≔⌊⟦⁰⁻⊖ιη⟧η

Otherwise, make this pumpkin grow as far to the left as it can.

≦⊕η

Otherwise, there is either less pumpkin growing to the right or more space for pumpkin to grow to the left.

Alternative formulation, also 29 bytes:

¹≔⁰η⊞θ¹Ｆθ«≦⊕η¿ι¿›η⁰≔⌊⟦⁰⁻ιη⟧η⎚

Try it online! Link is to verbose version of code. The only difference here is that the amount of space is incremented before the conditions, which just requires an adjustment to the condition and space calculation.

Answer 7

Retina 0.8.2, 55 bytes

\d+
$*
+1`\B((,)+(?<-2>1)+)1|1(1+)(,)\B
1$1$4$3
M`11
^0

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert the input to unary.

+1`

Repeatedly process the leftmost pumpkin that still needs space.

\B((,)+(?<-2>1)+)1

Match a pumpkin that can grow to the left (but only as far as its size),

|1(1+)(,)\B

... or a pumpkin that can grow to the right.

1$1$4$3

Mark that space as consumed by that pumpkin.

M`11
^0

Check that all of the pumpkins are fully grown.

Answer 8

Python 3, 108 bytes:

def f(l):
 p=s=0
 for i in l:
  if i:
   if p:return 1
   p=max(i-1-s,s:=0)
  else:s+=p<1;p-=p>0
 return p>s

Try it online!

Answer 9

05AB1E, 20 bytes

.œεεày0¢>yg)Ëy_P~]Pà

Try it online or verify all test cases.

Explanation:

Check if there is any partition for which each part satisfies one of two conditions: either all items are 0; or the maximum, length, and amount of 0s + 1 are all three the same.

.œ          # Get all partitions of the (implicit) input-list
  ε         # Map over each partition:
   ε        #  Map over each part:
    Z       #    Push the maximum (without popping)
    s0¢>    #    Swap, and count the amount of 0s + 1
    yg      #    And also push the length of the part
        )   #    Wrap all three values into a list
         Ë  #    Pop and check if all three are the same
          ~ #   OR:
    y_P     #    Check if all values in this part are 0s
]           # Close the nested loop
 P          # Product of each: Check if all parts in a partition are truthy
  à         # Pop and push max: Check if any partition is truthy
            # (after which the result is output implicitly)