# Recover boolean cells from windowed sums

## Background

In Minesweeper, you will often encounter a horizontal or vertical wall of one's and two's (not yet revealed cells are marked as ?):

... 1 1 1 1 2 2 2 1 2 1 1 ...
... ? ? ? ? ? ? ? ? ? ? ? ...
... A B C D E F G H ...


It is equivalent to a problem of recovering zeros and ones in a boolean array when only windowed sums of size 3 are given, where a zero means a safe cell and a one means a mine:

A + B + C = 1
B + C + D = 1
C + D + E = 1
D + E + F = 2
E + F + G = 2
F + G + H = 2
...


If you focus on CDEF, you can logically determine that C should be zero and F should be one. If C were 1, it would mean D + E = 0, which is impossible due to D + E + F = 2. (Remember that all variables are booleans.)

## Challenge

This challenge is an extension of this problem to arbitrary window size.

Given n windowed sums with window size k, recover the n+k-1 boolean cells in the original array as much as possible. It is possible that some cells cannot be determined by the given information; those cells should be marked as such in the output.

The input is the number k and an array (or any ordered collection) of n integers between 0 and k inclusive. The output is an array of zeros, ones, and unknowns, which can be represented as any three distinct values of your choice. You can assume the input is valid, n and k are at least 2, and it has at least one corresponding boolean array.

Standard rules apply. The shortest code in bytes wins.

## Test cases

The output format uses ? for unknown.

k = 2

sums   =  0 0

sums   =  0 1 2 1 0
answer = 0 0 1 1 0 0

sums   =  1 1 1 1 1 1 1
answer = ? ? ? ? ? ? ? ?

sums   =  1 1 1 1 1 1 0 1 1
answer = 0 1 0 1 0 1 0 0 1 0

sums   =  1 1 2 1 1 1
answer = 1 0 1 1 0 1 0
---

k = 3

sums   =   1 1 1 2 2 2
answer = ? ? 0 ? ? 1 ? ?

sums   =   3 2 1 0 1 2 3
answer = 1 1 1 0 0 0 1 1 1

sums   =   1 1 1 2 2 2 2 1 1
answer = 1 0 0 1 0 1 1 0 1 0 0

sums   =   2 2 2 2 2 2 2 1
answer = 1 ? ? 1 ? ? 1 ? ? 0

sums   =   2 1 2
answer = 1 0 1 0 1
---

k = 4

sums   =    1 2
answer = 0 ? ? ? 1

sums   =    3 2 1
answer = 1 1 ? ? 0 0

sums   =    1 1 2 1 1
answer = 0 0 1 0 0 1 0 0

sums   =    1 1 2 2 2 3
answer = 0 0 ? ? 0 1 ? ? 1

• I don't know Brachylog, but this problem feels well-suited for it Jul 20, 2020 at 2:13
• Imaginary bonus for any solution that takes time linear in the input size. Jul 22, 2020 at 6:56

# Jelly, 23 18 bytes

L+’Ø.ṗ+⁴\⁼¥Ƈ⁸ZṢ€Q€


Try it online!

-5 bytes thanks to @Jonathan Allan

Uses [0,1] as ?, [0] as 0, and [1] as 1.

### How?

Brute force of all possible boolean matrices.

L+’Ø.ṗ+⁴\⁼¥Ƈ⁸ZṢ€Q€
Ø.               # [0,1]
ṗ              # Cartesian power:
L+’                 # Length of answer = length of sums + k - 1
Ƈ          # Filter by:
+⁴\⁼¥             # n-wise overlapping sums are equal to
⁸           # the given sums
Z      # Get the lists of all possibilities for each position (some binary list)
Ṣ€    # Sort each possibility list (0s then 1s)
Q€  # Take unique entries from every possibility ([0],[1],or [0,1])

• -5 bytes: L+’Ø.ṗ+⁴\⁼¥Ƈ⁸ZṢ€Q€ (1. inline the helper - I just used reduce (\) to make it two links (¥), but four (ʋ) would work with your helper I think; 2. a more terse way to get the final results from the possibilities found - this one gives [0], [1], or [0,1]). TIO Jul 20, 2020 at 13:43
• @JonathanAllan I tried ʋ, and it did not work. I'm not sure why; it's not part of an LCC or anything Jul 20, 2020 at 19:20
• I think that's because the dyad-nilad ṡ⁴ is treated as one link during the parsing there (a dyad with one argument defined) so it would want ɗ (which works). I do often find myself trying different chain-forming quicks in such situations, I should probably read the interpreter code. Jul 21, 2020 at 12:08

# Brachylog, 39 bytes

Bit frustrating, as a nice attempt that inverts the moving window with ~{sᶠ↙L} does not work. So this is basically just brute-force.

{tL&lʰ+-₁~l.{0|1}ᵐsᶠ↙L+ᵐ~h?∧}ᶠ\{=h|∧2}ᵐ


Try it online!

### How it works

{tL&lʰ+-₁~l.{0|1}ᵐsᶠ↙L+ᵐ~h?∧}ᶠ
{                           }ᶠ find all solutions:
tL&                           store the window size as L
lʰ+-₁                      length of input + window size - 1
~l.                   the output has this as length
{0|1}ᵐ             and contains only 0's and 1's
sᶠ↙L         get all windows of length L
+ᵐ       that summed
~h?    result in the input array
∧   return the output defined earlier
\{=h|∧2}ᵐ
\                              transpose the solutions
{     }ᵐ                      map over each position
=h                           either all solutions are equal, then return first
|∧2                        or return 2 (should be equivalent to ∨2 but isn't)


# Dyalog APL, 4844 43 bytes

{0 1⍳(+/÷≢)¨↓s[;⍸⍵≡⍤1⍉⍺+⌿s←2⊥⍣¯1⍳2*⍺+≢1↓⍵]}


Try it online!

This program uses 2 to represent ?, and this program is run using ⎕IO←0. This is basically a brute force algorithm, and could probably be golfed.

• Welcome to PPCG! Nice first answer. Jul 22, 2020 at 15:56
• Thank you, Szewczyk.
Jul 22, 2020 at 16:03

# Python 3, 168 bytes

import itertools
lambda k,s:[[q[0],"?"][len(set(q))>1]for q in zip(*[z for z in itertools.product((0,1),repeat=len(s)+k-1)if[sum(z[i:i+k])for i in range(len(s))]==s])]


Fairly straightforward: brute forces over all possible binary sequences of length n+k-1, collecting all the results, and then aggregating by position, replacing with a "?" if there's multiple possibilities for a given position.

The only clever saving here is in the last step where I use zip() to join all the results together by position, and then using len(set(q))>1 to tell whether or not there's multiple possibilities for a position.

Ungolfed:

import itertools

def recover(k,sums):
def window_sum(seq):
return [sum(seq[i:i+k]) for i in range(len(sums))]
valid = []
for poss in itertools.product((0,1), repeat=(len(sums)+k-1)):
if window_sum(poss) == sums:
valid.append(poss)
ans = []
for by_position in zip(*valid):
if len(set(by_position)) == 1:
ans.append(by_position[0])
else:
ans.append("?")
return ans


# Charcoal, 45 bytes

≔⁺⊖θＬηζ⭆ＥζＥΦＥＸ²ζ◧⍘λ²ζ⬤η⁼ν№✂λξ⁺θξ¹1Σ§λι∧⌈ι∨⌊ι?


Try it online! Link is to verbose version of code. Explanation:

≔⁺⊖θＬηζ


Calculate the length of the result up-front, saving a byte.

⭆Ｅζ


Loop over each desired output.

ＥΦＥＸ²ζ


Count all possible binary patterns...

◧⍘λ²ζ


... generating padded base 2 strings...

⬤η⁼ν№✂λξ⁺θξ¹1


... keeping only those with the correct window totals...

Σ§λι


... keep only the current bit. (Yes, we throw away all of the other results each time. That's code golf for you. If you want efficiency, well I guess you're looking at more like 57 bytes.)

∧⌈ι∨⌊ι?


Of those bits, if their maximum is 0 or minimum is not 0 then print that otherwise print ?.

# 05AB1E, 24 bytes

1ÝDIgI+<ãʒ'üI«.VO¹Q}øÅAk


Port of @fireflame241's Jelly answer, so make sure to upvote him!

Outputs -1 for ?.

Try it online or verify all test cases. (Feel free to remove the 1('?:ï in the footer of the test suite - which converts all -1 to "?" - to see the actual output.)

Explanation:

1Ý         # Push a list [0,1]
D        # Duplicate it
Ig      # Push the first input-list, and pop and push its length
I+    # Add the second input-integer k
<   # Decrease it by 1
ã  # Get the cartesian product of [0,1] with the length+k-1
ʒ          # Filter this list of potential windows by:
'ü       '#  Push character "ü"
I«      #  Append the input k to it
.V    #  Execute it as 05AB1E code
#   üN creates overlapping sublists of size N
O   #  Sum each overlapping sublist
¹Q #  And check if it's equal to the first input-list
}ø         # After the filter: zip/transpose the remaining lists
ÅA       # Get the arithmetic mean of each inner list
k      # Use it to index into the [0,1] list, which results in -1 if it isn't in the
# list for the decimal values
# (after which the result is output implicitly)


# Ruby, 113 112 bytes

->k,n{(a=0,1).product(*[a]*z=n.size+k-2).select{|x|n==x.each_cons(k).map(&:sum)}.transpose.map{|x|x.minmax.sum}}


Try it online!

Returns false cells as 0, unknowns as 1, and true cells as 2.

Also, this doesn't use new fancy numerical block variables from Ruby 2.7, so that it's still runnable on TIO.

# JavaScript (ES6),  127 126  121 bytes

Expects (k)(array). Returns a string, using 123 instead of 01?.

k=>F=(a,i=w=a.length+k-1)=>i--?F(a,i)+(g=n=>n--&&!a.some(h=(v,j)=>++x%~k?h(v-=n>>j&1,j+1):v,x=0)<<(n>>i&1)|g(n))(2<<w):''


Try it online!

### Commented

k =>                         // outer function taking k
F = (                        // main function taking:
a,                         //   a[] = input array
i =                        //   i = counter initialized to ...
w = a.length + k - 1       //   w = length of output array
) =>                         //
i-- ?                        // decrement i; if it was not equal to 0:
F(a, i) +                  //   prepend the result of a recursive call to F
( g = n =>                 //   g is a recursive function taking a counter n:
n-- &&                 //     decrement n; stop if it was equal to 0
!a.some(h = (v, j) =>  //     otherwise, for each v at position j in a[]:
++x % ~k ?           //       increment x; if it's not equal to 0 modulo k + 1:
h(                 //         do a recursive call to the callback of some():
v -= n >> j & 1, //           subtract the j-th bit of n from v
j + 1            //           increment j
)                  //         end of recursive call
:                    //       else:
v,                 //         stop recursion and return v