34
\$\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\$
3
  • \$\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, 2015 at 17:46
  • \$\begingroup\$ @ThomasKwa An end delimiter sounds fine for TI-BASIC and other languages that have weird newline limitations. \$\endgroup\$ Sep 29, 2015 at 17:53
  • \$\begingroup\$ Do any answer use the numbers in input? \$\endgroup\$
    – l4m2
    Mar 22 at 1:24

7 Answers 7

24
\$\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\$
4
  • 7
    \$\begingroup\$ I'm scared - this is amazing. \$\endgroup\$
    – Deusovi
    Sep 29, 2015 at 8:42
  • \$\begingroup\$ You sir, have just broken the system. +1! May I ask where you found this theory? \$\endgroup\$
    – GamrCorps
    Sep 29, 2015 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, 2015 at 16:27
  • \$\begingroup\$ Bravo! I would of never of thought of that. \$\endgroup\$
    – GamrCorps
    Sep 29, 2015 at 18:17
13
\$\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\$
1
  • \$\begingroup\$ Really neat, +1 \$\endgroup\$
    – MKII
    Sep 29, 2015 at 9:00
9
\$\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\$
3
\$\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\$
1
\$\begingroup\$

Scala 3, 405 bytes

A port of @Level River St's Ruby answer in Scala.

405 bytes, it can be golfed more.


Golfed version. Attempt This Online!

def t(s:String):String={val l=s.split("\n");val h=l.length;val w=l.headOption.map(_.length).getOrElse(0)
(0to h-1).map{y=>(0to w-1).map{x=>l(y)(x)match{case'*'=>c(l,x,y).toString case _=>"*"}}.mkString}.mkString("\n")}
def c(l:Array[String],x:Int,y:Int):Int={val o=for{dy<- -1 to 1;dx<- -1 to 1;if y+dy>=0&&y+dy<l.length&&x+dx>=0&&x+dx<l(y+dy).length}yield(dx,dy)
o.count{case(dx,dy)=>l(y+dy)(x+dx)!='*'}}

Ungolfed version. Attempt This Online!

object Main {
  def main(args: Array[String]): Unit = {
    val board = "**212*32\n333*33**\n1*22*333\n222222*1\n*33*2232\n2**22*2*"
    println(transformBoard(board))
  }

  def transformBoard(s: String): String = {
    val lines = s.split("\n")
    val height = lines.length
    val width = lines.headOption.map(_.length).getOrElse(0)

    (0 until height).map { y =>
      (0 until width).map { x =>
        lines(y)(x) match {
          case '*' => countMines(lines, x, y).toString // Count surrounding numbers if it's a mine
          case _   => "*" // Turn every non-mine cell into a mine, mimicking the Ruby logic
        }
      }.mkString
    }.mkString("\n")
  }

  def countMines(lines: Array[String], x: Int, y: Int): Int = {
    val offsets = for {
      dy <- -1 to 1
      dx <- -1 to 1
      if y + dy >= 0 && y + dy < lines.length && x + dx >= 0 && x + dx < lines(y + dy).length
    } yield (dx, dy)

    offsets.count { case (dx, dy) =>
      val char = lines(y + dy)(x + dx)
      char != '*' // Count everything that is not a mine
    }
  }
}
\$\endgroup\$
0
\$\begingroup\$

Vyxal 3 j, 28 bytes

ᵛƛ•=[ð|•]:Þȯᵛᵛ•CZᵗZᵛᵛ₳•c¿•]“

Try it Online!

wish vectorize modifier deep vectorized

input is a 2d list of characters

ᵛƛ•=[ð|•]:Þȯᵛᵛ•CZᵗZᵛᵛ₳•c¿•]“­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢⁡⁤‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏⁠⁠‎⁡⁠⁢⁣⁣‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁢⁢⁣‏⁠‎⁡⁠⁢⁢⁤‏⁠‎⁡⁠⁢⁣⁡‏⁠‎⁡⁠⁢⁣⁢‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁢⁣⁤‏‏​⁡⁠⁡‌­
ᵛƛ      ]                     # ‎⁡map over each character
  •=[                         # ‎⁢is it a mine?
     ð|•]                     # ‎⁣if yes, replace with a space. if no, replace with a mine
         :                    # ‎⁤push two copies of the inverse mines
          Þȯ                  # ‎⁢⁡grid neighbors
            ᵛᵛ•C              # ‎⁢⁢counts of mines around each cell
                ZᵗZ           # ‎⁢⁣zip each mine count with the inverted mine locations
                   ᵛᵛ₳    ]   # ‎⁢⁤reduce each pair by
                      •c¿•    # ‎⁣⁡if it contains a mine, set it to a mine, otherwise take the number
                           “  # ‎⁣⁢join on nothing, j flag joins on newlines
💎

Created with the help of Luminespire.

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

Uiua, 53 bytes

⍜☇≡(⟨@*◌|⊢°⋕/+¬⟩°⊂=@*)1⍉≡(↘⊟.¯1↻)☇1⊞⊟.0_1_¯1¤⬚@*↙+1△.

Try it in the pad!

Port of Dennis's CJam answer.

\$\endgroup\$

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.