15
\$\begingroup\$

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
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
\$\endgroup\$
  • \$\begingroup\$ I don't know Brachylog, but this problem feels well-suited for it \$\endgroup\$ – Jonah Jul 20 at 2:13
  • 1
    \$\begingroup\$ Imaginary bonus for any solution that takes time linear in the input size. \$\endgroup\$ – user202729 Jul 22 at 6:56
5
\$\begingroup\$

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])
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ -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 \$\endgroup\$ – Jonathan Allan Jul 20 at 13:43
  • \$\begingroup\$ @JonathanAllan I tried ʋ, and it did not work. I'm not sure why; it's not part of an LCC or anything \$\endgroup\$ – fireflame241 Jul 20 at 19:20
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Allan Jul 21 at 12:08
3
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! Nice first answer. \$\endgroup\$ – Szewczyk Jul 22 at 15:56
  • \$\begingroup\$ Thank you, Szewczyk. \$\endgroup\$ – Ada Jul 22 at 16:03
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 45 bytes

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

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

≔⁺⊖θLηζ

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

⭆Eζ

Loop over each desired output.

EΦEX²ζ

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.