32
\$\begingroup\$

Minesweeper is a popular computer game that you have probably wasted time playing where you try to reveal the cells that are mines in a rectangular grid based on hints of how many neighboring mines each non-mine cell has. And in case you haven't played it, do so here.

A nifty mathematical fact about a Minesweeper grid (a.k.a. board) is that:

A board and its complement have the same mine total number. (Proof)

That is to say that if you have a completely revealed Minesweeper grid, the sum all the numbers on that grid, i.e. the mine total, will equal the mine total of the complement of the grid, which is the grid where every mine has been replaced with a non-mine and every non-mine replaced with a mine.

For example, for the Minesweeper grid

**1..
34321
*2**1

the mine total is 1 + 3 + 4 + 3 + 2 + 1 + 2 + 1 = 17.

The grid's complement is

24***
*****
3*44*

which has mine total 2 + 4 + 3 + 4 + 4 = 17 again.

Write a program that takes in an arbitrary Minesweeper grid in text form where * represents a mine and 1 through 8 represent the number of mines adjacent to a non-mine cell. You can use . or 0 or (space) to represent cells with no mine neighbors, your choice. You can assume that the input grid will be correctly marked, i.e. each non-mine cell will accurately denote the total number of mines immediately adjacent to it orthogonally or diagonally.

Your program needs to print the complement of the grid in the same format (using the same ., 0, or as you expected in the input).

The shortest code in bytes wins.

  • Instead of a program you may write a function that takes the input grid as a string and prints or returns the complement grid.
  • A trailing newline in the input or output is fine, but there should be no other characters besides those that form the grid.
  • You can assume a 1×1 grid will be the smallest input.

Test Cases

All inputs and outputs could be swapped as the complement of the complement is the original grid. The grids can be rotated as well for further test cases.

Input:

111
1*1
111

Output:

***
*8*
***

Input:

.

Output:

*

Input:

*11*1.1**1...1***1.....1*****1..........

Output:

1**2***11*****1.1*******1...1***********

Input: (Cut The Knot example)

**212*32
333*33**
1*22*333
222222*1
*33*2232
2**22*2*

Output:

24***4**
***7**64
*8**7***
******8*
4**7****
*33**5*3
\$\endgroup\$
  • \$\begingroup\$ TI-BASIC cannot accept an empty line of input. Is using an end delimiter (for example ?) on the line after the final line of the board acceptable, or could I take the number of input lines through the command line? \$\endgroup\$ – lirtosiast Sep 29 '15 at 17:46
  • \$\begingroup\$ @ThomasKwa An end delimiter sounds fine for TI-BASIC and other languages that have weird newline limitations. \$\endgroup\$ – Calvin's Hobbies Sep 29 '15 at 17:53
12
\$\begingroup\$

Pyth, 39 38 bytes

j.es.eh-+K\*l-s:RtWYY+Y2:+K.zk+k3KZb.z

Try it online: Demonstration

The main algorithm is really straightforward. I simply iterate over each cell, take the surrounding 3x3 box (or smaller when the cell is at the border) and print a star or the number of non-stars in that box.

Explanation:

j.es.eh-+K\*l-s:RtWYY+Y2:+K.zk+k3KZb.z  implicit: .z = list of input strings
 .e                                 .z  map each index k, line b of .z to:
    .e                             b      map each index Y, char Z of b to:
         K\*                                assign "*" to K
                         +K.z               insert K at the front of .z
                        :    k+k3           slice from k to k+3
               :RtWYY+Y2                    take the slice from Y-1 or 0 
                                            to Y+2 for each line
              s                             join, this gives the 3x3 rectangle
                                             (or smaller on the border)
             -                   K          remove all "*"s
            l                               take the length
        +K                                   "*" + ^
       -                          Z         remove Z from this string
      h                                     and take the first char
                                            (if cell=mine take the number, 
                                             otherwise take the number)
  s                                       join the chars of one line
j                                       join by newlines
\$\endgroup\$
  • \$\begingroup\$ Really neat, +1 \$\endgroup\$ – MKII Sep 29 '15 at 9:00
22
\$\begingroup\$

CJam, 58 57 bytes

0WX]2m*qN/{'*f+z}2*f{\~@m<fm<W<}:..+{W<{_'*#'*@'*-,?}/N}/

Input should not end with a linefeed. Output contains 0 for cells without nearby mines.

Try it online in the CJam interpreter.

Idea

We start by padding the input matrix with one row and one column of asterisks.

For input

*4*
**2

this results in

*4**
**2*
****

Now we generate all possible modifications that result of rotating the rows and columns 0, -1 or 1 units up/left:

*4** **** **2* **4* **** ***2 4*** **** *2**
**2* *4** **** ***2 **4* **** *2** 4*** ****
**** **2* *4** **** ***2 **4* **** *2** 4***

We discard the "padding locations" from each rotation, i.e.,

*4* *** **2 **4 *** *** 4** *** *2*
**2 *4* *** *** **4 *** *2* 4** ***

and form a single matrix by concatenating the corresponding characters of each rotation:

******4** 4*******2 **24*****
*******4* *4****2** 2***4****

The first character of each position is its original character.

  • If it is a non-asterisk, it has to be replaced with an asterisk.

  • If it is an asterisk, the number of non-asterisks in that string is the number of neighboring mines.

How it works

0WX]2m*   e# Push the array of all vectors of {0,-1,1}^2.
qN/       e# Read all input from STDIN and split at linefeeds.
{'*f+z}2* e# Append a '*' to each row and transpose rows with columns. Repeat.
f{        e# For each vector [A B], push the modified input Q; then:
  \~      e#   Swap Q with [A B] and dump A and B on the stack.
  @m<     e#   Rotate the rows of Q B units up.
  fm<     e#   Rotate each row of the result A units left.
  W<      e#   Discard the last row.
}         e# This pushes all nine rotations with Manhattan distance 1.
:..+      e# Concatenate the corresponding characters for each position.
{         e# For each row:
  W<      e#   Discard the character corresponding to the last column.
  {       e#   For each remaining string:
    _'*#  e#     Find the first index of '*' in a copy.
    '*    e#     Push '*'.
    @'*-, e#     Count the non-asterisks in the string.
    ?     e#     Select '*' if the index is non-zero, the count otherwise.
  }/      e#
  N       e#   Push a linefeed.
}/        e#
\$\endgroup\$
  • 7
    \$\begingroup\$ I'm scared - this is amazing. \$\endgroup\$ – Deusovi Sep 29 '15 at 8:42
  • \$\begingroup\$ You sir, have just broken the system. +1! May I ask where you found this theory? \$\endgroup\$ – GamrCorps Sep 29 '15 at 16:03
  • 9
    \$\begingroup\$ @IonLee This one is all me. It's a pretty simple idea, really: Instead of checking the cells around a given cell, we move the entire grid around and observe what falls into the cell. \$\endgroup\$ – Dennis Sep 29 '15 at 16:27
  • \$\begingroup\$ Bravo! I would of never of thought of that. \$\endgroup\$ – GamrCorps Sep 29 '15 at 18:17
7
\$\begingroup\$

Ruby, 119

->s{w=1+s.index('
')
s.size.times{|c|t=0;9.times{|i|(s+?**w*2)[c+i/3*w-w+i%3-1]<?0||t+=1}
print [t,?*,'
'][s[c]<=>?*]}}

Ungolfed in test program:

f=->s{
  w=1+s.index("\n")                          #width of board
  s.size.times{|c|                           #iterate through input
    t=0;                                     #number of digits surrounding current cell
    9.times{|i|                              #iterate through 3x3 box (centre must be * if this ever gets printed.)
      (s+"*"*w*2)[c+i/3*w-w+i%3-1]<"0"||t+=1 #copy of s has plenty of * appended to avoid index errors
    }                                        #add 1 every time a number is found.
  print [t,"*","\n"][s[c]<=>"*"]             #if * print t. if after * in ACSII it's a number, print *. if before, it's \n, print \n
  }
}


f['**212*32
333*33**
1*22*333
222222*1
*33*2232
2**22*2*']
\$\endgroup\$
2
\$\begingroup\$

Octave, 76

m=@(s)char(conv2(b=(cell2mat(strsplit(s)'))~='*',ones(3),'same').*~b-6*b+48)

Explanation

  • Convert input string to matrix of strings using strsplit and cell2mat.

  • Get the logical matrix containing 1 where there is no * in the original matrix.

  • Take its convolution with a 3x3 matrix of 1's.

  • Mask it with the inverse logical matrix and put * in place of the mask.

  • Note: Cells with no mine neighbors are represented as 0.

Execution

>> m(['**100' 10 '34321' 10 '*2**1'])   %// `10` is newline
ans =

24***
*****
3*44*

>> m(['24***' 10 '*****' 10 '3*44*'])
ans =

**100
34321
*2**1
\$\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.