26
\$\begingroup\$

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
\$\endgroup\$
7
  • \$\begingroup\$ For the second testcase, 2 would be a valid output, right? If there were to be no bomb in index 2, then there would be no bomb within two spaces from the first element, and one bomb (the last one) in the vicinity of the second element. \$\endgroup\$
    – ophact
    Feb 23, 2022 at 16:49
  • \$\begingroup\$ @ophact Whoops, fixed \$\endgroup\$
    – AnttiP
    Feb 23, 2022 at 16:50
  • 2
    \$\begingroup\$ This is harder than I thought lol \$\endgroup\$
    – Seggan
    Feb 23, 2022 at 16:55
  • 1
    \$\begingroup\$ can we use another number for the -1 indicator? \$\endgroup\$
    – Jonah
    Feb 24, 2022 at 1:20
  • 1
    \$\begingroup\$ @Jonah Sure, I'll allow it \$\endgroup\$
    – AnttiP
    Feb 24, 2022 at 4:25

9 Answers 9

6
\$\begingroup\$

Charcoal, 55 48 47 bytes

≔⌕Aθ±¹ηFEX²LηΦη﹪÷ιX²μ²F⬤θ∨‹κ⁰⁼κLΦι›³↔⁻μλ≔⁻ηιηIη

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

≔⌕Aθ±¹η

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

FEX²LηΦη﹪÷ιX²μ²

Create all possible mine layouts and loop over them.

F⬤θ∨‹κ⁰⁼κLΦι›³↔⁻μλ

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.

Iη

Output the positions that didn't have a mine.

\$\endgroup\$
2
  • \$\begingroup\$ can you teach me charcoal? this is godly (nice use of bitmask!) \$\endgroup\$
    – DialFrost
    Feb 25, 2022 at 2:30
  • \$\begingroup\$ @DialFrost Actually the bitmask turned out to be a red herring - my original approach was to build up a set of those positions that might have a mine, but because Charcoal doesn't have sets, I used a bitmask instead. I then golfed the code to use a bitmask of those positions that don't have a mine and removing mines as I find them. However as Charcoal has a list difference operator, I can use a list with this approach, saving me 7 bytes. \$\endgroup\$
    – Neil
    Feb 25, 2022 at 8:24
2
\$\begingroup\$

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 */
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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++;
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
1
0
\$\begingroup\$

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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You can use m[:] instead of m.copy(). \$\endgroup\$
    – Neil
    Feb 24, 2022 at 9:47
  • 1
    \$\begingroup\$ m*1 is even shorter \$\endgroup\$
    – pxeger
    Feb 24, 2022 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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