Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Minesweeper is a logic game found on most OS's. The goal of the game is to determine where the mines are on a grid, given numbers indicating the number of mines around that spot.

Given a grid size, and a set of mines, generate the Minesweeper grid for that set of mines.

Input: Two integers indicating the grid size, and an undefined number of integers indicating the mine positions. Positions will be given as (column position, row position), and the indexes will start at row 1.

Output: The Minesweeper grid. If there are no mines around a block, print an x. For each new row, print a newline. Please output all mines as an asterisk *. Do not leave any whitespace between the values in the row when printing.

Test Cases:

Input "5 5 1 3 3 5 2 4":

xxxxx
11xxx
*21xx
2*21x
12*1x

Input "3 4 3 1 1 4 2 3 3 2":

x2*
13*
2*2
*21

Shortest code wins.

share|improve this question
    
Are we safe to assume all inputs will have an even number of args? i.e. 5 5 1 will never be passed? –  Gaffi Jun 26 '12 at 17:17
    
@Gaffi: Yep. The input will always be valid input. –  beary605 Jun 26 '12 at 22:45
    
The spec currently leaves the reader to deduce from the examples that the positions use 1-based indexes and that row 1 is at the top. (Or is the latter, at least, negotiable?) –  Peter Taylor Jun 27 '12 at 9:17
    
@PeterTaylor: Yep. I guess I should make it more obvious. –  beary605 Jun 27 '12 at 14:18
1  
No problem. I'm still determined to find a way to shave a couple of characters off and regain the lead though. :-) –  Gareth Jun 30 '12 at 7:06
show 2 more comments

11 Answers

up vote 7 down vote accepted

GolfScript 122 98 94 93 91 88 87 85 82 81 80 71

~]2/(\:m;~\:w*,{[.w%)\w/)]:^m\?)42{m{^*~-.*@@-.*+3<},,72or 48+}if}%w/n*

Online demos:

Test Case 1: link

Test Case 2: link

share|improve this answer
    
!!{a}{b}if uses one character more than necessary. '*' can be replaced with 42 because you're putting it in an array and then stringifying the array. Similarly you can use ASCII codes for the other output characters and save a character with or to handle the special case. –  Peter Taylor Jun 27 '12 at 9:28
    
@PeterTaylor Wow, !!{a}{b}if was really stupid indeed. :) It's funny what high-level mistakes you can do while concentrated on details. I cannot figure out what you meant by using or. –  w0lf Jun 27 '12 at 11:16
    
Indeed! Coming back to a problem after time helps too. When I wrote a couple of code dissections for my GolfScript blog I spotted considerable improvements. With respect to my last suggestion, after ,, you have a number. You want to convert it to the corresponding string (or ASCII code) unless it's 0, in which case you want x. The ASCII codes for digits are sequential and run from 48. x is ASCII 120, which is 72+48. So you can do 72or 48+ and save a character over the string-based approach. –  Peter Taylor Jun 27 '12 at 11:47
    
@PeterTaylor Great! Before you answered I managed to reduce that part to .48 120if+, but your or trick is two chars shorter. –  w0lf Jun 27 '12 at 11:57
    
@w0lf Gah! Just when I think I've got the lead back! –  Gareth Jun 28 '12 at 13:22
add comment

J, 124 116 112 101 87 86 85 84 83 82 79 76 75 72 68 characters

'0x'charsub|:1":3 3(+/@,+9*4&{@,);._3[1(}.x)}0$~2+>{.x=._2<\".1!:1[1

Found what I was looking for - a way to get rid of the spaces (1":) - and finally I'm competitive. Now I just need to figure out the empty set of mines problem.

Takes input from the keyboard.

Edit

New version makes use of a side effect of 1": - numbers larger than 9 are replaced by *.

share|improve this answer
    
I've noticed two things: 1. It prints spaces instead of 0, not x; 2. Fails if the set of mines is empty (ex: 10 10 - should print an empty 10x10 board, but returns |length error) –  w0lf Jun 27 '12 at 13:10
    
But othwerwise it works, so +1. –  w0lf Jun 27 '12 at 13:21
    
@w0lf Ah, I was still thinking of the first draft of the question - in that version x just represented a space. I didn't notice that it had changed. Hmm, never thought that the set of mines would be empty...I'll have to work on that. –  Gareth Jun 27 '12 at 13:27
    
now I see that the question has been edited. I had not seen the old revision. :) –  w0lf Jun 27 '12 at 14:13
    
Wow! Nice progress! –  w0lf Jun 28 '12 at 13:57
show 2 more comments

Mathematica - 247 chars

s[q_] :=
  Module[{d, r},
    d = ToExpression@Partition[Cases[Characters@q, Except@" "], 2];
    r = Rest@d;
    StringJoin @@@ 
    ReplacePart[
    Table[ToString@
       Count[ChessboardDistance[{i, j}, #] & /@ Reverse /@ r, 1], {i,d[[1, 2]]}, 
       {j, d[[1, 1]]}] /. {"0" -> "x"}, # -> "*" & /@ Reverse /@ r] // TableForm]

Examples:

s@"5 5 1 3 3 5 2 4"
s@"3 4 3 1 1 4 2 3 3 2"

Output:

output

ChessboardDistance computes how far each cell is from a mine, where 1 corresponds to "next to a mine". The Count of 1's yields the cell's number. Then mines (*) are inserted into array.

share|improve this answer
    
David, nice to see another Mathematica user here. I'll see if I can beat this! :-) –  Mr.Wizard Jun 28 '12 at 12:13
    
@Mr.Wizard I'll be interested in seeing your solution. Feel free to improve on mine if you like. –  David Carraher Jun 28 '12 at 13:46
add comment

Mathematica, 140 139 137

Grid[(ListConvolve[BoxMatrix@1,#,2,0]/. 0->x)(1-#)/. 0->"*"]&@Transpose@SparseArray[{##2}->1,#]&@@#~Partition~2&@@#~ImportString~"Table"&

Writing that in a more readable form:

"5 5 1 3 3 5 2 4"

ImportString[%, "Table"][[1]] ~Partition~ 2

Transpose @ SparseArray[{##2} -> 1, #]& @@ %

ListConvolve[BoxMatrix@1, %, 2, 0]

(% /. 0 -> x) (1 - %%) /. 0 -> "*" // Grid
share|improve this answer
    
Elegant! I confess I cannot understand how ListCorrelate[BoxMatrix@1, %, 2, 0] does its magic. –  David Carraher Jun 28 '12 at 14:44
    
@David I'm glad you (implicitly) asked as that's my favorite part. ListCorrelate effectively overlays the kernel (BoxMatrix@1) at each position in the grid, multiplies, and gives the sum. (ping me in mma chat if you would like an illustration) -- Your comment reminds me that ListConvolve should work here too as it is a kind of mirror image of ListCorrelate and my kernel is symmetric. That will save me a character. :-) –  Mr.Wizard Jun 28 '12 at 22:31
    
Your code incorrectly generates a mine at (5,5). "5 5" gives the dimensions of the grid. –  David Carraher Feb 7 '13 at 1:20
    
@David Thanks. You're right, but it's only in the white-space version; I somehow lost the 2 in ##2. I'll fix it now. ps: How did you come to notice this after so long? –  Mr.Wizard Feb 7 '13 at 3:12
    
Another minesweeper question, codegolf.stackexchange.com/questions/10635/…, recently appeared and I decided to give your solution another look-through. –  David Carraher Feb 7 '13 at 12:34
add comment

Python, 192 182 180 chars

I could save some if the input was comma-separated. Then the first line would be d=input() and the length 171 chars.
Having the mine coordinates 0-based rather than 1-based would also help. It cost me 8 chars to overcome.

d=map(int,raw_input().split())
m=zip(d[2::2],d[3::2])
for y in range(d[1]):print"".join((str(sum(abs(a-x-1)|abs(b-y-1)<2for a,b in m)or'x')+'*')[(x+1,y+1)in m]for x in range(d[0]))

Ungolfed version:

d=map(int,raw_input().split()) # Read whitespace terminated numbers into a list of numbers xsize,ysize = d[:2] # The first two numbers are the board size mines=zip(d[2::2],d[3::2]) # Convert items 3,4,5,6... to pairs (3,4),(5,6) representine mine coordinates

def dist(point,mine):                   # Distance between point (0-based coordinates) and mine (1-based coordinates)
    dx = abs(mine[0]-(point[0]+1))
    dy = abs(mine[1]-(point[1]+1))
    return dx | dy                      # Should be max(dx,dy), but this is close enough. Wrong for d>=2, but returns >=2 in this case.

for y in range(ysize):                  # Print lines one by one
    line_chars = [
        (str(
            sum(dist((x,y),(a,b))<2 for a,b in mines)   # Number of neighboring mines
            or 'x'                                  # 'x' instead of 0
        )
        +'*')                                       # For a single neighbor, we get "1*"
        [(x+1,y+1)in mines]                         # If a mine, get the '*', else the neighbor number
        for x in range(xsize)
    ]
    print "".join(line_chars)
share|improve this answer
add comment

Scala - 280 chars

val n=readLine split" "map{_.toInt}
val b=Array.fill(n(1),n(0))(0)
n drop 2 sliding(2,2)foreach{case Array(x,y)=>b(y-1)(x-1)=9
for{i<-(x-2 max 0)to(x min n(0)-1);j<-(y-2 max 0)to(y min n(1)-1)}b(j)(i)+=1}
b.map{r=>println(r.map{case 0=>"x"case x if x>8=>"*"case x=>""+x}mkString)}
share|improve this answer
add comment

VBA - 298 chars

Sub m(x,y,ParamArray a())
On Error Resume Next:ReDim b(x,y):For i=0 To (UBound(a)-1) Step 2:c=a(i):d=a(i+1):b(c,d)="*":For e=c-1 To c+1:For f=d-1 To d+1:v=b(e,f):If v<>"*" Then b(e,f)=v+1
Next:Next:Next:For f=1 To y:For e=1 To x:v=b(e,f):s=s & IIf(v<>"",v,"x")
Next:s=s & vbCr:Next:MsgBox s
End Sub

Skipping over errors with On Error Resume Next saved me some characters, but this still isn't nearly as good as some of the other answers. :-/

share|improve this answer
add comment

This is the beginning of a Brinfuck solution. It should be pretty readable with indention and stack comments (@ indicates the stack pointer):

>>,>,  |0|x|@y| Pop the first two characters
[>>+<<-]>>  |0|x|0|0|@y|
[<<+>+>-]<  |0|x|@y|y|0|
[  |0|x|y|@y|
  [>>+<<-]< |0|x|@y|0|0|y|
  [>>+<<-]< |0|@x|0|0|y|y|
  [>>+<<-]>> |0|0|0|@x|y|y|
  [<<+>+>-]<<  |0|@x|x|0|y|y|
  [>>+<<-]> |0|0|@x|x|y|y|
  [<< |@0|0|x|x|y|y|
    ++++++++[>+++++++++++<-]>>>>> |0|88|x|x|@y|y|
    [>+<-]< [>+<-]< [>+<-]< [>+<-]< |0|@88|0|x|x|y|y|
    [<+>-]>>-  |88|0|0|@x_1|x|y|y|
  ]<< |x x's|@0|0|0|x|y|y|
  ++++++++++>>> x's|\n|0|0|@x|y|y|
  [<+>-]>  x's|\n|0|x|0|@y|y|
  [<+>-]>  x's|\n|0|x|y|0|@y|
  [<+>-]<- |x 88s|0|x|@y_1|y|
] |@x 88s|0|x|y|

It is however far from complete and I am starting to doubt if my approach is optimal. So far it only considers the first two input characters and prints a table of Xs. For instance "43" would give you:

XXXX
XXXX
XXXX

I would love to see if somebody else has what it takes and is capable of solving this problem in Brainfuck.

share|improve this answer
    
Optimal is entirely irrelevant in my mind when dealing with BrainFuck. What interpreter specs are you targeting? Like 8-bit cells or what? I would love to see this finished. –  CMP Jun 29 '12 at 18:45
    
I think it is pretty independent from any specific intepreter? As long as the numbers isn't unreasonably big. –  paldepind Jun 29 '12 at 18:56
    
Working on a soulution, but of course it always turns out to be harder than it seems at first in Brainfuck. –  CMP Jul 2 '12 at 19:58
add comment

C++ - 454 chars

This is worse than my VBA answer, which probably means I don't know what I'm doing in C++. However, I am trying to build on what I know of C++, so here it is. If anyone has any suggestions for improvement, I'd be grateful to hear them!

#define Z for(int i=
#define Y for(int j=
#define X d[i][j]
#define W Z 0;i<x;i++){
#define V Y 0;j<y;j++){
#define U cout<<
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
int main(){using namespace std;int x,y,a,b;cin>>y>>x;string c[x][y];int d[x][y];W V X=0;}}while(cin>>b>>a){c[--a][--b]="*";Z a-1;i<=a+1;i++){Y b-1;j<=b+1;j++){if(x>i&&i>=0&&y>j&&j>=0){X=X+1;}}}}W V if(c[i][j]!="*"){if(X>0){U X;}else{U"x";}}else{U"*";}}U endl;}return 0;}
share|improve this answer
    
you don't need to return 0. And you can #include<cstdio>,#include<cstdlib>. You can even delete these two includes!. What's more, using name..... is too long, you can use std::cin, std::cout, std::string instead. –  Ray Feb 15 '13 at 18:23
    
@Ray Aye, you're right about the namespace... It's been a while since I put this together, but I'm thinking I had more std:: calls that would have made it more worth it (I think one more string would have done it). Thanks for the info about the #include lines as well. I'm no C++ expert. ;-) –  Gaffi Feb 15 '13 at 19:10
add comment

C# (691 Chars)

using System;namespace M{class P{static char C(char[][] g,int r,int c){int n=0;for(int i=r-1;i<=r+1;i++){if(i<0||i>=g.Length)continue;for(int j=c-1;j<=c+1;j++){if((j<0||j>=g[0].Length)||(i==r&&j==c))continue;if(g[i][j]=='*')n++;}}return n==0?'x':(char)(n+48);}static char[][] G(int[] p){char[][] r=new char[p[1]][];for(int i=0;i<r.Length;i++)r[i]=new char[p[0]];for(int i=2;i<p.Length;){r[p[i+1]-1][p[i]-1]='*';i+=2;}for(int i=0;i<r.Length;i++)for(int j=0; j<r[0].Length;j++)if(r[i][j]!='*')r[i][j]=C(r,i,j);for(int i=0;i<r.Length;i++){for(int j=0;j<r[0].Length;j++)Console.Write(r[i][j]);Console.WriteLine();}return r;}static void Main(string[] args){G(new int[]{3,4,3,1,1,4,2,3,3,2});}}}

Non-golfed Version:

using System;
namespace M
{
    class P
    {
        static char C(char[][] g, int r, int c)
        {
            int n = 0;
            for (int i = r - 1; i <= r + 1; i++)
            {
                if (i < 0 || i >= g.Length) continue;
                for (int j = c - 1; j <= c + 1; j++)
                {
                    if ((j < 0 || j >= g[0].Length) || (i == r && j == c)) continue;
                    if (g[i][j] == '*') n++;
                }
            }
            return n == 0 ? 'x' : (char)(n + 48);
        }

        static char[][] G(int[] p)
        {
            char[][] r = new char[p[1]][];
            for (int i = 0; i < r.Length; i++)
                r[i] = new char[p[0]];
            for (int i = 2; i < p.Length; )
            {
                r[p[i + 1] - 1][p[i] - 1] = '*';
                i += 2;
            }
            for (int i = 0; i < r.Length; i++)
                for (int j = 0; j < r[0].Length; j++)
                    if (r[i][j] != '*') r[i][j] = C(r, i, j);
            for (int i = 0; i < r.Length; i++)
            {
                for (int j = 0; j < r[0].Length; j++)
                    Console.Write(r[i][j]);
                Console.WriteLine();
            } return r;
        } 
        static void Main(string[] args) 
        { 
            G(new int[] { 3, 4, 3, 1, 1, 4, 2, 3, 3, 2 }); 
        }
    }
}
share|improve this answer
add comment

K, 175

f:{g::(y;x)#(x*y)#"x";{.[`g;x;:;"*"]}@'-1+|:'(_(#z)%2;2)#z;{if[~"0"~z;$["x"=g .(x;y);.[`g;(x;y);:;z];]]}.'i,'$s:+/'{"*"=g . x}''{,/((x-1)+!3),\:/:(y-1)+!3}.'i:,/(!x),\:/:!y;g}

.

k)f[5;5;1 3 3 5 2 4]
"xxxxx"
"11xxx"
"*21xx"
"2*21x"
"12*1x"
k)f[3;4;3 1 1 4 2 3 3 2]
"x2*"
"13*"
"2*2"
"*21"
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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