Your goal is to check whether a completed Minesweeper board is valid. This means that each number is a correct count of mines in cells adjacent to it, including diagonals. The board does not wrap around.

As usual, you should give a function or program, and shortest code in bytes wins.

See also past challenges to generate, solve, and fully implement Minesweeper.

Input:

A single string like this: 02X2 13X2 X211.

  • The rows of the minesweeper board are given separated by spaces. So, the above represents the 3x4 board:

    02X2
    13X2
    X211

  • Each cell is a character: X for a mine, or a number 0 through 8.

  • All rows have the same length.

  • There are at least 3 rows and 3 columns.

  • The input doesn't start or end with a space, but you may include a newline at the end if you wish.

Output:

A consistent Truthy on correct boards, and a consistent Falsey value on incorrect boards. Consistent means that all Truthy outputs are the same and all Falsey outputs are the same.

Test cases

Each line is a separate test case.

True:

02X2 13X2 X211
XXXX XXXX XXXX XXXX
XX4X2 5X6X4 XX6XX 4XX54 2X4XX

False:

02X2 13X2 X212
XXXX XXXX X7XX XXXX
XX5X2 5X6X4 XX6XX 4XX54 2X5XX
  • You should probably specify the consistent falsy output must be distinct from the consistent truthy output ;-) – John Dvorak Dec 13 '14 at 6:45
  • @JanDvorak That should be implied by them being Truthy and Falsey respectively. – xnor Dec 13 '14 at 7:23
  • Not really. "truthy" and "falsy" are just two labels that you're letting us define. I can see no restriction they be actually truthy or falsy respectively in the language we use. The only word that may require them to be distinct is the "indicating" verb. I'm not sure it counts as a spec (it's still forbidden as a standard loophole, though). – John Dvorak Dec 13 '14 at 7:29
  • 4
    @JanDvorak 'truthy' and 'falsy' are actually somewhat common terms if I'm not mistaken basically used to describe things (not necessarily bools) that evaluate to true or false when typed to bools. For example 0 is generally falsy and 1 is generally truthy. – KSab Dec 13 '14 at 7:30
  • 1
    @JanDvorak Nope, Truthy/Falsey has to match correct/incorrect. – xnor Dec 13 '14 at 7:42

10 Answers 10

Python 2, 132 129 128

def f(s):w=s.find(' ');E=dict(enumerate(s));return all(E[i]in' X'+`sum(E.get(i+d/3*~w+d%3+w,5)>'O'for d in range(9))`for i in E)

I used enumerate in a golf...and even used range elsewhere in the same program. Clearly something is wrong here.

Edit: Iterate over dict(enumerate(s)) rather than enumerate(s), so enumerate does not need to be called twice.

  • What a clever use of ~! And of dictionaries to make out-of-bounds indexing work right. – xnor Dec 16 '14 at 3:03
  • @xnor Your comment about the ~ operator ironically made me notice I was using it twice for no reason at all, where using it only once would obviously accomplish the same thing. I thought the dictionary part was funny, thanks. – feersum Dec 16 '14 at 3:48

Pyth, 43

Jhxzd!f-@zT+" X"`sm/:+*JNztd+d2\Xm+T*kJU3Uz

Try it here.

Explanation:

  • Jhxzd: This is the location of the first space in the input + 1. (z in the input, d is space.) It is the separation in the input between vertically adjacent cells on the board.
  • !f: This is the logical not (!) of a filter (f), which will be True if and only if the expression is falsy for every element of the sequence.
  • -@zT: Take the character at location T (the lambda variable) from the input, and remove any appearances of: (This will be truthy if the character is not removed, and falsy if it is.
  • +" X": Remove space, X, and
  • `: Repr of
  • sm: sum of map to
  • / \X: count of "X" in
  • :+*JNz: The slice of the input prefixed by J dummy characters
  • td+d2: From d-1 to d+2.
  • m+T*kJU3: For d in [T, T+J, T+2*J].
  • Uz For T in range(len(input)).
  • 7
    Downvoters: Why the downvotes? – isaacg Dec 13 '14 at 21:52

APL (NARS2000) (74)

{~0∊(G>9)∨G=(⍴G)↑{+/∊9<⍵∘⌷¨G∘.⊖(G←2-⍳3)∘.⌽⊂Z}¨⍳⍴Z←G↑⍨2+⍴G←¯1+⎕D⍳⊃⍵⊂⍨⍵≠' '}

Also works in Dyalog APL if ⎕ML is set to 3.

Explanation:

  • ⊃⍵⊂⍨⍵≠' ': split on the spaces and use the lists to form a matrix.
  • G←¯1+⎕D⍳: find the index in ⎕D for each value, subtract 1, and store this in G. (⎕D contains the digits, any non-digit will turn into 10).
  • Z←G↑⍨2+⍴G: add two lines and columns of zeroes at the edge of the matrix, to deal with the wraparound
  • {...}¨⍳⍴Z: for each position in Z, find the amount of bombs in the Moore neighbourhood of that position:
    • G∘.⊖(G←2-⍳3)∘.⌽⊂Z: rotate Z left, right, up, down, left-up, right-up, left-down, and right-down.
    • ⍵∘⌷¨: for each of these, find the element at in each of these rotated matrices
    • +/∊9<: count how many elements are higher than 9 (this is the amount of bombs).
  • (⍴G)↑: remove the added lines of zeroes again,
  • G=: check whether each element in G is equal to the amount of bombs surrounding that position (this should be true for all non-bomb squares),
  • (G>9)∨: and check whether the elements in G are higher than 9 (these are the bombs).
  • ~0∊: return 1 if the resulting matrix contains no zeroes (=all squares are either bombs or the correct number), and 0 if it does.
  • Did you count bytes or characters? You should count bytes. – Tim S. Dec 13 '14 at 14:56
  • 5
    @TimS.: There are loads of 1-byte APL encodings, here's one. – marinus Dec 13 '14 at 19:17

C#, 321 320 305

bool s(string B){var L=B.Split(' ').Select(s=>' '+s+' ').ToList();var b=new string(' ',L[0].Length);L.Insert(0,b);L.Add(b);Func<int,int,IEnumerable<int>>E=Enumerable.Range;return E(1,b.Length-2).All(x=>E(1,L.Count-2).All(y=>L[y][x]=='X'||L[y][x]-'0'==E(x-1,3).Sum(X=>E(y-1,3).Sum(Y=>L[Y][X]=='X'?1:0))));}

First attempt golfing anything, and I know that C# isn't the ideal language.

I hope writing an instance method is allowed, otherwise add another 7 characters for static.

Spaced out:

bool s(string B) {
    var L = B.Split(' ').Select(s => ' ' + s + ' ').ToList();
    var b = new string(' ', L[0].Length);
    L.Insert(0, b);
    L.Add(b);
    Func<int, int, IEnumerable<int>> E = Enumerable.Range;
    return E(1, b.Length - 2).All(x =>
        E(1, L.Count - 2).All(y =>
            L[y][x] == 'X' ||
            L[y][x] - '0' == E(x - 1, 3).Sum(X =>
                E(y - 1, 3).Sum(Y =>
                  L[Y][X] == 'X' ? 1 : 0))));
}

Using Linq saves some space compared to for loops, but it's harder to debug.

I learned a few things like converting char => int by subtracting '0'.

It seemed simpler to pad out the board with spaces so iterating over it would be easier.

  • 1
    Can't you just replace -'0' with -48. Works for me and saves a few bytes for various 'X' and ' ' – Roman Gräf Oct 23 '16 at 10:29

Python 2, 121

def f(B):n=B.find(' ')+1;R=range(len(B));print all(B[I]in' X'+`sum(2>I%n-i%n>-2<I/n-i/n<2<B[i]>'W'for i in R)`for I in R)

This is heavily inspired by feersum's answer. The order of the day is overkill: rather than checking for mines in the 9 neighbors of the cell, check every single cell to see whether it's a neighboring mine.

We check if two cells are neighbors with 2>r>-2<c<2, where r and c are the row and column differences of cells, equivalent to {r,c}<{-1,0,1}. These coordinates are computed from the cell indices I and i as c=I%n-i%n and r=I/n-i/n. It's more efficient to index directly into the string and extract rows and columns than to convert it to a 2D object like a list of lists. The mine check is B[i]>'W', equivalent here to B[i]=='X'.

Using enumerate would have saved two characters over the ugly range(len(B)) except that it returns an iterator object which does not support two nested loops through it.

  • I think a negative modulus should work for n; then you could use ~B.find. – feersum Dec 16 '14 at 16:11
  • @feersum Unfortunately, that messes up the / because it rounds negatives downward too. – xnor Dec 18 '14 at 4:01

Python 2, 140

s=input();w=s.index(' ')+1
print all(c in'X 'or(int(c)==sum(s[max(0,a-1):max(0,a+2)].count('X')for a in[i-w,i,i+w]))for i,c in enumerate(s))

JavaScript (ES6), 135 133 125 122

f=s=>s.split(" ")[e="every"]((l,i,a)=>[...l][e]((c,j)=>!(-[-1,0,k=1][e]((y,m,q)=>q[e](x=>k+=(a[i+y]||0)[j+x]=="X"))-c+k)))

Provide input to the function as a string:

f("XX4X2 5X6X4 XX6XX 4XX54 2X4XX");

For an explanation, see the old version, below. The new version replaces the for loops with every calls, and uses the variable e="every" to do someArray[e](...) instead of someArray.every(...).

Also, the counter k is now indexed at 1 so that the k+=... expression is always truthy, in order to keep the every loop running. We eliminate that extra 1 by subtracting the true result (which numerically coerces to 1) returned by the every operation [-1,0,k=1][e](...).


Old version:

f=s=>s.split(" ").every((l,i,a)=>[...l].every((c,j)=>{q=[-1,k=0,1];for(y of q)for(x of q)k+=(a[i+y]||0)[j+x]=="X";return c=="X"||k==c}))

Code with spaces and comments:

f=s=>s.split(" ")                 // split on spaces
      .every((l,i,a)=>             // for every line
                                   //     l: line string, i: line number, a: whole array
          [...l].every((c,j)=>{    // for every character
                                   //     c: character, j: index in string
              q=[-1,k=0,1];        // define counter k=0 and q=[-1,0,1]
              for(y of q)          // use q to loop adjacent spaces
                  for(x of q)

                      k+=              // add the following boolean to k:

                          (a[i+y]      //   from line number i+y...
                                 ||0)  //   (or a dummy zero, to prevent lookups on undefined)
                          [j+x]        //   ...get index j+x from the above value...
                                =="X"; //   ...and compare it to "X"

              return !(k-c)     // after the loop, this character passed if
                                // the char equals the number of counted X's (so k-c is 0)
                                // or it is an X itself (so `k-c` is NaN)
          })
      )

The JavaScript every array method takes a callback and applies the callback to every element of the array. If any callback returns a falsey value, the every call returns false.

Booleans in JS are coerced to 1 or 0 when part of an addition. For each surrounding space, we "add" the boolean result of comparing its value to X and then add that value to the counter k in the expression k += (... == "X"). Therefore, k contains a count of the number of surrounding Xs, because true counts as 1 and false counts as 0.

  • Instead of c=="X" try !c/1, which saves you a huge amount of a whooping pair of bytes! If it fails, try !!c/1. The reasoning is that 'X'/1 => NaN, and NaN is falsie. You check if c=='X', why not try to check if it isn't false? – Ismael Miguel Dec 15 '14 at 23:32
  • @IsmaelMiguel That evaluates the same as (!c)/1, which doesn't help, unfortunately; I'd need to have the parentheses for !(c/1), which cost 2. Also, 0/1 is falsey, so the invalid input "0X" would have the incorrect result true. The best I can do while still respecting zeroes is to combine the two conditions into a negated phrase, like !(+c+1&&k-c), but that's the same length as what I already have. – apsillers Dec 16 '14 at 2:10
  • @IsmaelMiguel Thanks for getting me thinking about it though -- I've realized that !(k-1-c) tests both conditions, because if k matches c (minus the 1 offset), then the negation makes the 0 true, and if c is not a number, we get NaN and the negation is also true. – apsillers Dec 16 '14 at 3:24
  • You really were hungry! You ate 10 bytes since the initial code! I really like the solution you came up with. +1 for your solution! – Ismael Miguel Dec 16 '14 at 9:10

CJam, 70 65 63 bytes

1l_S#):L)S*+:Q{Ii33/2%[0~1LL)L(L~)L~_))]W):Wf+Qf='X/,(scI==&}fI

This can be golfed a lot.

Gives 1 for a valid board and 0 for an invalid board.

Test cases

{-1:W;
1l_S#):L)S*+:Q{Ii33/2%[0~1LL)L(L~)L~_))]W):Wf+Qf='X/,(scI==&}fI
}6*]N*

Input

02X2 13X2 X211
XXXX XXXX XXXX XXXX
XX4X2 5X6X4 XX6XX 4XX54 2X4XX
02X2 13X2 X212
XXXX XXXX X7XX XXXX
XX5X2 5X6X4 XX6XX 4XX54 2X5XX

Output

1
1
1
0
0
0

Try it online here

JavaScript (ES6) 98

Using some to apply a function to each character of the string.
The function returns

  • false if blank
  • NaN if 'X' (repeatedly subtracting values from a non numeric char like 'X' gives NaN)
  • A numeric value of 0 if there are the right number of adiacent 'X', else non 0.
    The inner check is made using map just because it's shorter than forEach

some returns true at the first truthy value (in this case, nonzero) meaning a failed check. The result is negated to give a more recognizable true/false.

F=v=>![...v].some(
  (x,p)=>x!=' '&&[1,-1,l=v.search(' '),-l,++l,-l,++l,-l].map(q=>x-=v[p+q]=='X')|x
)

Test In FireFox / FireBug console

;["02X2 13X2 X212","XXXX XXXX X7XX XXXX","XX5X2 5X6X4 XX6XX 4XX54 2X5XX"
,"02X2 13X2 X211","XXXX XXXX XXXX XXXX","XX4X2 5X6X4 XX6XX 4XX54 2X4XX","111 1X1 111"]
.forEach(t => console.log(t, F(t)))

Output

02X2 13X2 X212 false
XXXX XXXX X7XX XXXX false
XX5X2 5X6X4 XX6XX 4XX54 2X5XX false
02X2 13X2 X211 true
XXXX XXXX XXXX XXXX true
XX4X2 5X6X4 XX6XX 4XX54 2X4XX true
111 1X1 111 true

R, 156 chars

a=b=do.call(rbind,strsplit(scan(,""),""));for(i in 1:nrow(a))for(j in 1:ncol(a))b[i,j]=sum(a[abs(i-row(a))<2&abs(j-col(a))<2]=="X");v=a!="X";all(b[v]==a[v])

With indents, spaces and line breaks, for legibility:

a = b = do.call(rbind,strsplit(scan(,""),"")) #Reads stdin and turn into a matrix
for(i in 1:nrow(a)) #Ugly, ugly loop
    for(j in 1:ncol(a))
        b[i,j] = sum(a[abs(i-row(a))<2 & abs(j-col(a))<2]=="X")
v = a!="X"
all(b[v]==a[v])

Examples:

> a=b=do.call(rbind,strsplit(scan(,""),""));for(i in 1:nrow(a))for(j in 1:ncol(a))b[i,j]=sum(a[abs(i-row(a))<2&abs(j-col(a))<2]=="X");v=a!="X";all(b[v]==a[v])
1: XX4X2 5X6X4 XX6XX 4XX54 2X4XX
6: 
Read 5 items
[1] TRUE
> a=b=do.call(rbind,strsplit(scan(,""),""));for(i in 1:nrow(a))for(j in 1:ncol(a))b[i,j]=sum(a[abs(i-row(a))<2&abs(j-col(a))<2]=="X");v=a!="X";all(b[v]==a[v])
1: XXXX XXXX XXXX XXXX
5: 
Read 4 items
[1] TRUE
> a=b=do.call(rbind,strsplit(scan(,""),""));for(i in 1:nrow(a))for(j in 1:ncol(a))b[i,j]=sum(a[abs(i-row(a))<2&abs(j-col(a))<2]=="X");v=a!="X";all(b[v]==a[v])
1: XX5X2 5X6X4 XX6XX 4XX54 2X5XX
6: 
Read 5 items
[1] FALSE

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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