Recover boolean cells from windowed sums

Question

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 code-golf rules apply. The shortest code in bytes wins.

Test cases

The output format uses ? for unknown.

k = 2

sums   =  0 0
answer = 0 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

Answer 1

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])

Answer 2

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)

Answer 3

Dyalog APL, 48 ⁴⁴ 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.

Answer 4

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

Answer 5

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 ?.

Answer 6

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)

Answer 7

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.

Answer 8

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
        x = 0                //       start with x = 0
      ) << (n >> i & 1)      //     end of some(); turn true into 0; turn false into 2
                             //     if the if i-th bit of n is set, or 1 otherwise
      | g(n)                 //     bitwise OR with the result of a recursive call to g
  )(2 << w)                  //   initial call to g with n = 2 ** (w + 1)
:                            // else:
  ''                         //   end of recursion on F: return an empty string