1D Shikaku Validation

Question

Shikaku is a 2D puzzle. The basic rundown of it is that a rectangular grid has some numbers in it, and you want to partition the grid into rectangular components such that each component contains exactly one number which is the number of grid squares in that component.

This challenge involves a 1D simplification of this: it is a line of N squares with K numbers \$\{a_1, a_2, \cdots, a_K\}\$, and a solution would be a division of the line into K partitions such that each partition contains \$a_i\$ squares. However, in this simplification, not all squares need to be used.

Challenge

Given a list of N numbers (where 0 is an empty square), determine if a valid solution to that problem exists.

Truthy Cases

(_ is a blank; it will be given as 0 in the input. you may not take the input as an index:element mapping)

 _ _ 3 _ _ 5 _ _ 3 _ _
([   ] [       ] [   ])

 2 _ _ _ _ 6 _ _ _ 4 _ _
([ ] [         ] [     ])

 _ 5 _ _ _ 3 _ _ _ _ _ 4
([       ] [   ] [     ])

 _ _ 2 _ _ _ _ 4 _ _
(  [ ]       [     ])
(    [  ]  [     ]  ) just to give 2 examples

Falsy Cases

_ _ 2 _ 4 _
_ 3 _ _ 5 _ _ 3 _
_ _ 5 _ _ _ 3
_ 2 _ 2 _ 2 _ 3

Rules and Specifications

Input can be taken as any convenient way to take a list of numbers. You can input it as a string with _ for blanks as well; etc. Any reasonable method; however, you may not change the general structure of the input as a list.

Output is a true/false value. Any truthy/falsy value is acceptable. The true/false value does not have to be consistent across cases, but your program must give the same exact answer for the same test case every run, and please specify how truthy/falsy is distinguished if it's not conventional. For example, you can output 1 for a true case and 2 for another, and 0 for false cases, but the first case must always yield 1 every time, and the second must give 2 every time.

To prevent a loophole brought up thanks to @xnor, your output must be successful / failed completion as a result, numbers, booleans, or other similar "primitive-like" datatypes (basically, you cannot submit the identity function and say that the Truthy/Falsy sets are divided by this problem's specifications).

• Standard loopholes are forbidden.
• This is code-golf, therefore the shortest answer in each language wins. No answer will be accepted.

Answer 1

JavaScript (ES6),  56  52 bytes

Returns a Boolean value.

a=>![...a,1].some(x=>t>0/x?1:(t+=x-1)*x<0?t=0:0,t=0)

Try it online!

Commented

The accumulator \$t\$ is decremented whenever an empty slot is encountered. For each non-zero value \$x\$, we update \$t\$ to \$max(t+x-1,0)\$. The test fails if we reach a non-empty slot (or the end of the list) with \$t>0\$.

a =>               // a[] = input
  ![...a, 1]       // append a '1' at the end of a[] to force a last test
  .some(x =>       // for each value x in the updated array:
    t > 0 / x ?    //   if x = 0, this test is always falsy (0 / 0 -> NaN)
                   //   if x ≠ 0 and t is greater than 0:
      1            //     failed: yield 1
    :              //   else:
      (t += x - 1) //     add x - 1 to t
      * x < 0 ?    //     if t is negative and x ≠ 0:
        t = 0      //       we have accumulated more empty slots than
                   //       we can consume here: set t to 0
      :            //     else:
        0,         //       do nothing
    t = 0          //   start with t = 0
  )                // end of some(); return the opposite result

Answer 2

Python 3, 96 87 85 bytes

def f(a):
	c=p=0
	for x in a:
		if p*x:return
		p|=x;c+=1
		if c>=p>0:c=p=0
	return p

Try it online!

-5 bytes thanks to 79037662.

-6 bytes thanks to HyperNeutrino.

None and positive are falsy, 0 is truthy.

Answer 3

Python 2 via exit code, 52 bytes

n=0
for x in input()+[1]:x*n<0>_;n+=x<1or-max(x-1,n)

Try it online!

Successful completion for True, error for False.

-1 byte thanks to Arnauld.

Answer 4

PowerShell, 56 55 54 47 bytes

inspired by Arnauld's one accumulator code.

!($args+1|?{$_;$t+=$_-1}|?{$t-ge$_;$t*=$t-ge0})

Try it online!

Answer 5

Retina 0.8.2, 34 bytes

^
,
\d+
$*
\b
;
+1`,;1|1;,
;
^\W*$

Try it online! Explanation:

^
,

Prepend a , so that there's one , for each square.

\d+
$*

Convert the entries to unary.

\b
;

Surround each non-empty square with ;s.

+1`,;1|1;,
;

Each ; in turn starts eating away at the adjacent empty squares.

^\W*$

Check that there were no 1s left.

After adding the prefix and the unary conversion, .NET is actually able to solve the problem in a single regex, although it weighs in at a massive 58 bytes:

^
,
\d+
$*
^(,*(,)*(?<-2>1)*(?(2)^)(1)*(?<-3>,)*(?(3)^))*$

Try it online!

Answer 6

J, 47 bytes

[:*/2(>+.0>:[)/\[:(++(0>.0-+)*0<+-])/@|.\<:@,&1

Try it online!

Credit to Arnauld for the high-level idea.

I'll add explanation and golf more soon.

Answer 7

Jelly, 20 bytes

ŒṖT€ẈỊẠƲƇðẈẋ`€F⁹a⁼ðƇ

A monadic Link accepting a list of non-negative integers which yields a list. An empty list is falsey, a non-empty list is truthy. (The list is actually all ways which work).

Try it online! Or see a test-suite.

How?

ŒṖT€ẈỊẠƲƇðẈẋ`€F⁹a⁼ðƇ - Link: list, S
ŒṖ                   - all partitions (of S)
        Ƈ            - filter keep those for which:
       Ʋ             -   last four links as a monad:
   €                 -     for each:
  T                  -       truthy indices
    Ẉ                -     length of each
     Ị               -     insignificant (for our purposes: is in (0,1)?)
      Ạ              -     all truthy?
                   Ƈ - filter keep those for which:
         ð        ð  -   the dyadic link - i.e. f(partition, S)
          Ẉ          -     length of each
             €       -     for each:
            `        -       use left as both arguments of:
           ẋ         -         repeat (i.e. 5 -> [5,5,5,5,5])
              F      -     flatten
               ⁹     -     chain's right argument (S)
                a    -     logical AND (vectorises)
                 ⁼   -     is equal to (S)?

Answer 8

J, 28 bytes

[:*/1>1&,*([0&>.<:@+)/\.@,&0

Try it online!

Inspired by Arnauld's algorithm. 1 if a solution exists, 0 otherwise.

How it works

In order to retain intermediate values of t, I chose to use "Reduce on suffixes" /\. with the initial value appended. Given a function f, the result of f/\. looks like this:

Input array: 0 0 2 2 2 0 0 0
Index 0: 0 f 0 f 2 f 2 f 2 f 0 f 0 f 0 (right-assoc for everything)
Index 1:     0 f 2 f 2 f 2 f 0 f 0 f 0
Index 2:         2 f 2 f 2 f 0 f 0 f 0
...
Index 6:                         0 f 0
Index 7:                             0

Explanation of full code:

[:*/1>1&,*([0&>.<:@+)/\.@,&0  Right argument: 1D Shikaku grid
                              ex. 0 0 2 2 2 0 0 (expected: falsy)
                         ,&0  Append the starting value of t=0
                              ex. 0 0 2 2 2 0 0 0
                     /\.@     Reduce from right and keep intermediate values...
          (         )           (left: x, right: t, output: t')
                <:@+            Compute y = x + t - 1
           [0&>.                Compute max(0, y) x times; simply y if x = 0
                              ex. 0 1 2 1 0 -2 -1 0
      1&,*                    For each element, match the current value of x with
                              the previous value of t (including the finish),
                              counting from the right
                              ex. 0 0 0 2 0 -4 0 0
[:*/1>                        Check if all of them are zero or less

Golfing the next-t algorithm

If x is empty, decrement t; otherwise compute max(t+x-1, 0)
->
If x is empty, compute t+x-1; otherwise compute max(t+x-1, 0)
->
Compute t+x-1; if x is nonempty, apply (y => max(y, 0))
->
Compute t+x-1; apply (y => max(y, 0)) x times (assume x >= 0)