Solve a Picross Row

Question

Introduction

A picross, also known as a nonogram, is a logic puzzle in which the player is given an initially blank grid and must shade in particular boxes on the grid to reveal an image. Numbers are written on the top and the left side, and they explain the image's coloration: each number corresponds to an unbroken line of shaded-in boxes in its row or column. Consider any individual row or column from this completed puzzle to see this correspondence:

Not shown in the image is the fact that one can write an "X" to indicate that a box is known not to be shaded in. Partially solving a row or column by shading in and crossing out boxes provides necessary information for the rest of the puzzle, as rows and columns usually cannot be completely solved on their own (for instance, in the image, this is only possible in the first row).

The Challenge

To take the hints for a given row along with the state of each box in the row as inputs, and output the row solved to the fullest extent possible.

---

Examples

In these examples, let 0 represent a box with an "X", 1 a shaded-in box, and 2 an unknown or unknowable (that is, blank) box.

---

This row would be input as

[1,3,7,1], [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]

and the program should output the following:

[2,2,2,2,2,2,2,2,2,2,2,1,1,2,2,2,2,2,2,2]

This output corresponds to this row, and no more information can be found:

The boxes marked 1 are always that way, no matter the arrangement of the shading. Essentially, if a box always has the same state, it must assume that state, lest the shading contradicts what is known. If there is not a unanimous agreement, then the box is unknowable and is marked 2.

---

Input: [1,3,7,1], [2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2]
Output:           [2,2,2,2,2,2,0,2,2,2,2,1,1,1,2,2,2,2,2,2]

---

Input: [6], [2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2]
Output:     [0,0,0,0,0,0,0,2,2,2,2,2,1,2,2,2,2,2,0,0,0,0,0,0,0]

If a 6-wide shading were to begin in any of the first 7 boxes, the row would have to have [6,1] or [7] as its hints, and so none of the first 7 boxes can be filled in. The same is true for the right side.

---

Input: [3], [2,0,2,2,2,2,0,2]
Output:     [0,0,2,1,1,2,0,0]

Because a 3-wide shading can only fit in the 4-wide gap in the middle, the 1-wide gaps on the edges can be turned into 0s

---

Rules

• Any three distinct symbols may be used in the place of 0, 1 and 2 so long as it is indicated which symbol corresponds to which state

• Assume the input hints and row never form an impossible combination

• This is code-golf, so the shortest program in bytes in each language wins

Answer 1

Python 2, 127 124 123 bytes

-1 byte thanks to @ovs !

l,a,b,c=input()
x=y=i=a|b|c
while i:
 if[len(z)for z in bin(i)[2:].split("0")if z]==l>i&a<1>~i&b:x&=~i;y&=i
 i-=1
print x,y

Try it online! or Verify test cases

(Timed-out in TIO for the 2nd test case, but I have verified the program on my PC.)

Reads from STDIN the list of streaks l, and 3 numbers a, b, c representing bit-masks of empty cells, filled cells, and unknown cells.
Prints to STDOUT 2 numbers, representing the bit-masks of guaranteed empty cells and guaranteed filled cells.

Answer 2

Charcoal, 129 bytes

ＳθＷΣθ«⊞υιＳθ»≔Ｅυ⁰ζ⊞ζ⁻Ｌθ⁺Συ⊖Ｌυ≔⟦⭆ζ⁺×:⊕ι×#§υκ⟧εＷ⌊ΦＬζ∧κ§ζκ«ＵＭζ⎇‹λι∧⁼λ⊖ι⊕Σ…ζι⁻κ⁼λι⊞ε⭆ζ⁺×:⊕κ×#§υλ»≔Φε⬤θ№⁺-§ι⊕μλε⭆θ§-#:⁻⬤ε⁼§λ⊕κ#⬤ε⁼§λ⊕κ:

Try it online! Link is to verbose version of code. I've used - for unknown, : for empty and # for shaded, but of course these could readily be changed to other characters. Explanation:

ＳθＷΣθ«⊞υιＳθ»

Input the runs and the known state.

≔Ｅυ⁰ζ⊞ζ⁻Ｌθ⁺Συ⊖Ｌυ

Start by putting all the spare space after the last run.

≔⟦⭆ζ⁺×:⊕ι×#§υκ⟧ε

Create a list whose entry is an image of that spacing, but with an extra space at the start and junk after the end.

Ｗ⌊ΦＬζ∧κ§ζκ«

Repeat while runs can be moved.

ＵＭζ⎇‹λι∧⁼λ⊖ι⊕Σ…ζι⁻κ⁼λι

Calculate the next permutation of runs. This is achieved by moving left the first run that can still be moved left, and then moving all the previous runs to its immediate left.

⊞ε⭆ζ⁺×:⊕κ×#§υλ»

Push an image of the new spacing to the list.

≔Φε⬤θ№⁺-§ι⊕μλε

Delete the runs that don't match the original input.

⭆θ§-#:⁻⬤ε⁼§λ⊕κ#⬤ε⁼§λ⊕κ:

Output the knowable state.

Answer 3

Wolfram Language, 155 bytes

Union@*List~MapThread~Cases[IntegerDigits[i,2,l]~Table~{i,0,2^(l=Length@#)}~Cases~#,
{0...,Splice@Riffle[1~Repeated~{#}&/@#2,0..],0...}]/.{0,1}->_/.{a_}->a&

(newline added for "readability")

Try it online!

Note: Since the version that tio.run has is apparently not the latest version (12.1), and Splice was added in it, I have added an equivalent definition.

Uses _ rather than 2 in the input to leverage built-in pattern-matching capabilities.

The method this answer uses is not very efficient, so don't try any massive inputs.

Program description:

1. Generates all sequences of 0 and 1 of the proper length: IntegerDigits[i,2,l]~Table~{i,0,2^(l=Length@#)}
2. Filter to those that match the already solved cells: ~Cases~# (super easy because I specify the input to work as a pattern)
3. Filter to those that match the row description: Cases[ ,{0...,Splice@Riffle[1~Repeated~{#}&/@#2,0..],0...}]
4. Get list of options for each position: Union@*List~MapThread~
5. Convert back to input form: /.{0,1}->_/.{a_}->a