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.

• xnor: I'm unclear what's allowed for to represent True/False outputs. It sounds like they still have to be Truthy/Falsey, but your suggestion to "declare that None and positive integers mean 'False' and 0 means 'True' " on Riolku's Python answer seems to mix Python's Truthy/Falsey values for the two cases. Does at least one of True/False need to correspond to a single fixed output? Presumably you don't want the loophole of just outputting the input as a solution with the claim "Only outputs that fit the problem criterion count as Truthy."
• hyperneutrino: @xnor I basically mean that the output must never change between runs of the same input, and you must be able to define two disjoint sets of possible outputs, one set being truthy and one set being falsy.
• xnor: Right, but what's stopping me from submitting the identity function, and saying the two disjoint subsets for true/false happen to be those defined by the challenge validation condition?
• hyperneutrino: @xnor Hmm, good point. I didn't think of that. I'm going to update it so that valid outputs (other than things like nothing / failure like with your submission) only "primitive-like" datatypes can be output, like numbers or booleans, since that doesn't break any existing solutions
• Night2: Can input use a character (not number) for blanks? For example _?

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.

• Arnauld: Welcome to Code Golf!
• 79037662: Can p and x be changed to p*x?
• 79037662: Can the c=0,p=0 in the parameters be replaced with c=p=0 in the function body? -5 bytes with these changes: tio.run/##XU1BDoMgEDzLK/aILQettgdb@heiEEkM3RBsbdK/U1CoSdmwOzM7A/…
• Riolku: I was trying to think of a better way to do p and x, thanks! Also moving it into the function body is something I had considered but not tried... thanks as well.
• hyperneutrino: By abusing my output formatting, you could just return p at the end and declare that None and positive integers mean "False" and 0 means "True"

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€ẈỊẠƲƇðẈẋ`€F9a=ðƇ

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€ẈỊẠƲƇðẈẋ`€F9a=ðƇ - 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
 9 - 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)