Play 1D minesweeper

Question

Your input is an array of integers in the range [-1,4]. An array element of -1 means that there might be a bomb in that position. A non-negative element means that there is not a bomb in that position and also the numeric value tells how many bombs there are within distance 2.

For example, if we have the following array: [1,2,-1,-1,4,-1,-1,-1,1] it's possible to infer that every -1 except the last one contains a bomb.

Your task is to take indicate which -1 for sure doesn't contain a bomb by outputting it's index (0 or 1 based). There is always at least one guranteed bombfree square (and thus the input length is at least two). You can use another number instead of -1 to represent an unknown square. If there are multiple possibilities output at least one of them. Shortest code wins.

To reiterate, you have to be certain that the index you output cannot contain a mine. If you were clearing mines IRL, you probably would also like to know that you won't accidentally step on one.

Test cases

[-1,0] -> 0
[0,1,-1,-1] -> 2
[-1,-1,-1,0] -> 1 or 2
[1,-1,-1,-1,2] -> 1
[-1,2,-1,-1,4,-1,-1] -> 0
[-1,-1,3,-1,-1,2,2,-1] -> 3
[2,-1,-1,-1,2,-1,-1,-1,2] -> 3 or 5
[-1,-1,1,-1,-1,-1,-1,1,0] -> 6
[-1,-1,1,-1,-1,2,-1,-1,2,-1,-1,2,-1,1] -> 0 or 1

Answer 1

Charcoal, 55 48 47 bytes

≔⌕Ａθ±¹ηＦＥＸ²ＬηΦη﹪÷ιＸ²μ²Ｆ⬤θ∨‹κ⁰⁼κＬΦι›³↔⁻μλ≔⁻ηιηＩη

Try it online! Link is to verbose version of code. Outputs all possible bombfree positions. Explanation:

≔⌕Ａθ±¹η

Create a list of all the positions of -1s in the input.

ＦＥＸ²ＬηΦη﹪÷ιＸ²μ²

Create all possible mine layouts and loop over them.

Ｆ⬤θ∨‹κ⁰⁼κＬΦι›³↔⁻μλ

If for all non-negative values there are the correct number of mines within a distance of 2, then...

≔⁻ηιη

... remove the positions that might have a mine.

Ｉη

Output the positions that didn't have a mine.

Answer 2

Pari/GP, 110 bytes

a->forvec(v=[[k=0,1]|i<-s=a],i=1;[t+1|t<-a,polcoef(Polrev(v)*Pol([1,1,5,1,1]),i++)!=t]||s+=v);[k|t<-s,t<0*k++]

Try it online!

1-indexed.

Ungolfed:

{ a ->                              /* Define a function with argument a: */
    s = a;                          /* Let s = a. */
    forvec(v = [[0, 1] | i <- a],   /* Let v loops over all binary vectors with length #a. */
        if(                         /* If */
            prod(i = 1, #a,         /* for all i in range 1..#a */
                a[i] == -1 ||       /* a[i] is -1 or */
                polcoef(            /* the coefficient of x^(i + 1) in */
                    Polrev(v)       /* the polynomial with coefficients v */
                    * Pol([1 ,1, 5, 1, 1]),     /* times (1 + x + 5*x^2 + x^3 + x^4) */
                    i + 1
                ) == a[i]           /* equals a[i] */
            ),
            s += v                  /* Then add v to s */
        )
    );
    [k | k <- [1..#a], s[k] == -1]  /* Find all k in range 1..#a such that s[k] is -1 */
}

Answer 3

Wolfram Language (Mathematica), 102 bytes

Position[#+Total@Cases[{0,1}~Tuples~Tr[1^#],v_/;MatchQ[ListConvolve[{1,1,5,1,1},v,3,0],#/.-1->_]],-1]&

Try it online!

A port of my PARI/GP answer. 1-indexed.

Answer 4

JavaScript (ES6), 127 bytes

The output is 0-indexed.

a=>a.findIndex((v,i)=>!~v&[...Array(1<<a.length)].every((_,k)=>a.some((v,j)=>~v*(g=x=>x+3?g(x-1)-(!~a[x+=j]&k>>x|x==i):v)(2))))

Try it online!

---

JavaScript (ES6), 118 bytes

Slightly shorter but stack-overflows on the last test case.

a=>a.findIndex((v,i)=>!~v&(h=k=>k>>a.length||a.some((v,j)=>~v*(g=x=>x+3?g(x-1)-(!~a[x+=j]&k>>x|x==i):v)(2))&h(-~k))())

Try it online!

Answer 5

JavaScript (Node.js), 112 bytes

a=>eval("for(i=k=-1;j=4*--i;~a[k]|i>>k&!a.some(v=>((j&9)+(j/2&9))*9/8&7^v|(j/=2)&2&&~v)&&(i=2**a.length,k++))k")

Try it online!

// for each cell `k`
// for each possible mine placement `i`
// convert `i` to binary, the nth lsb  means nth cell is a mine
for(i=k=0;++i<2**a.length;)
  if(
    // Current cell is not unknown, or
    ~a[k]|
    // current mine placement have a mine on position `k`, and
    i>>k&
    // it is a valid mine placement
    !a.some(v=>
      // (mine count is incorrect or current is mine) and current is not -1
      ((j&9)+(j/2&9))*9/8&7^v|(j/=2)&2&&~v,j=i*4)
  // we try next `k`
  )i=0,k++;

Answer 6

Python NumPy, 127 bytes

lambda L:where(L<-sum((T:=r_[:1<<(l:=len(L))]>>(a:=c_[:l])&1)*~any(((5//-~abs(a-a.T<<1)@T).T-L)*~L,1),1))[0]
from numpy import*

Attempt This Online!

Old Python NumPy, 134 bytes (@alephalpha)

def f(L):t=len(L);T=c_[:1<<t]>>r_[:t]&1;return where(L<-sum(T[~any((T@triu(tril(L**0,2),-2)+4*T-L)*(L+1),1)],0))[0]
from numpy import*

Attempt This Online!

Old Python NumPy, 141 bytes

def f(L):m=L<0;t=sum(m);T=c_[:1<<t]>>r_[:t]&1;v=any((T@triu(tril(L**0,2),-2)[m]-L)*~m,1);return where(m)[0][~any(T[~v],0)]
from numpy import*

Attempt This Online!

Old Python NumPy, 149 bytes

def f(L):m=L<0;M=triu(tril(L**0),-2);t=sum(m);T=c_[:1<<t]>>r_[:t]&1;v=any((T@(M^M.T)[m]-L)*~m,1);return where(m)[0][~any(T[~v],0)]
from numpy import*

Attempt This Online!

Brute-force approach using matrix algebra. Takes a numpy array and returns the indices (0-based) of all safe squares.

Matrix T contains all patterns of bombs at -1 positions as columns. triu(tril... is essentially an adjacency matrix capturing the geometry of hint/bomb squares. By multiplying T with this matrix we get for each pattern in T the corresponding pattern of hints it would generate. A square is safe if each pattern of bombs where it is set creates a pattern of hints that is not the given one.

Answer 7

05AB1E, 38 bytes

®Qƶ0K<ÐUæʒXðrKǝ₂S.øü5ʒÅsd}εÅsy®¢Q}P}˜K

Outputs all possible results.

Inspired by @Neil's Charcoal answer.

Try it online or verify all test cases or try it online with added debug-lines.

Explanation:

®Qƶ0K<        # Get a list of (0-based) indices of the -1s:
              # (05AB1E unfortunately lacks a builtin for this..)
®Q            #  Check for each value in the (implicit) input-list if its equal to -1
  ƶ           #  Multiply each (0 or 1) check by its 1-based index
   0K         #  Remove all 0s
     <        #  Decrease the 1-based indices to 0-based indices
Ð             # Triplicate this list of bomb-indices
 U            # Pop and store one of them in variable `X`
 æ            # Pop another one and get its powerset
  ʒ           # Filter this powerset by:
              #  (implicitly push the current powerset-list)
   X          #  Push list `X` with the bomb-indices
    ð         #  Push a space character
     r        #  Reverse so the stack-order goes to space, `X`, powerset-list
      K       #  Remove the values of the powerset-list from bomb-indices list `X`
       ǝ      #  Replace those bombs with spaces in the (implicit) input-list,
              #  to mark those bombs as duds
        ₂S.ø  #  Surround this list with leading/trailing [2,6]
              #  (any leading/trailing pair that isn't -1 would be fine here)
   ü5         #  Pop and push all overlapping quintuplets
     ʒ        #  Filter this list of quintuplets by, keeping those where:
      Ås      #   The middle item
        d     #   is a non-negative integer (so neither a -1 bomb nor " " dud)
     }ε       #  After the inner filter: map over the remaining quintuplets
       Ås     #   Check if the middle item
            Q #   is equal to
         y®¢  #   the amount of -1 bombs
      }P      #  After the map: check if all were truthy by taking the product
  }˜          # After the filter: flatten the list of powersets that were truthy
    K         # Remove those from the bomb-indices list we've triplicated at the start
              # (after which the result is output implicitly)

Answer 8

Python3, 580 bytes:

def r(d,p,v):
 d,c=eval(str(d)),[]
 for i in p:
  if 0<=i and i<len(d)and d[i]<0:d[i]=v;c+=[1]
 return c and[d]
def f(d,c=0):
 def g(d,c,o,u):
  if o==1:
   for i in r(d,[c-1],u)+r(d,[c+1],u):yield from f([*i],c+1)
   return
  for i in r(d,[c-2,c-1],u)+r(d,[c+1,c+2],u):yield from f([*i],c+1)
 if len(d)==c:yield d;return
 if d[c]in[2,1,0]:yield from g(d,c,d[c],[-2,-3][d[c]==0])
 else:yield from f(d,c+1)
def F(d):
 v={}
 for i in f(d):
  if -3 in i:return i.index(-3)
  for j,k in enumerate(i):
   if k==-2:v[j]=v.get(j,0)+1
 return min(v,key=lambda x:v[x])if v else d.index(-1)

Try it online!

Answer 9

Python 3, 408404 bytes

e=enumerate
def v(m):
 for i,u in e(m):
  if u>-1 and m[max(0,i-2):i+3].count(-2)>u:return 0
 return 1
def p(m):
 for i,u in e(m):
  if u>0 and m[max(0,i-2):i+3].count(-2)<u:return 1
 return 0
def b(m):
 r=[]
 for i,u in e(m):
  if u==-1:t=m.copy();t[i]=-2;r+=b(t)if p(t)else[t]if v(t)else[]
 return r
def s(m):
 t=b(m)
 for i,u in e(m):
  if u==-1:
   n=1
   for u in t:
    if u[i]==-2:n=0
   if n:return i

Try it online!

Saved 4 bytes with suggestion from Neil