kdb programming challenge – Minesweeper

Happy New Year everyone! I hope everyone had a very good holiday and wouldn’t it be great to start the new year with a big bang right?? It has been a while since the last challenge and I’m sure my fans are dreading for one 🙂 Ok, enough of messing around. Let’s get down to business!

I’m sure everyone is familiar with the Minesweeper game. In this challenge, we are not making the game itself but just the grid. The best thing is that this challenge has 2 parts! Here are the followings:

1) Create a function that generates a random mine grid. (m n dimension with approximately x chance of mine spawns). For example:

// 3 x 3 grid with roughly 50{e673f69332cd905c29729b47ae3366d39dce868d0ab3fb1859a79a424737f2bd} chance of mine spawns
q)f[3 3;0.5]
" xx"
"x x"
" x"
q)avg"x"=raze f[3 3;0.5]
0.5555556
q)avg"x"=raze f[3 3;0.1]
0.1111111

2) Create another function that populates the grid with clues indicating number of mines around the neighboring cells. For example:

q)g f[3 3;0.5]
"2xx"
"x5x"
"13x"
q)g f[2 3;0.5]
"13x"
"x3x"

I find this challenge quite interesting. There are some nice techniques that can be used in this challenge. But of course I’ll let you crack on and hope you enjoy this challenge as much as I do! Answers to follow up by the end of this month!

[showhide type=”post1″ more_text=”Show Solution” less_text=”Solution” hidden=”yes”]

Solution 1

For the first part, there are few ways to get the grid. I will show 2 approaches here and both of them have the basic technique, we start with an array of empty char, set the location of the mines and use # to convert the array back to a matrix.

1) We multiply the percentage with the total dimension of the grid, round it and use that number to randomly pick the location of the mines.

f:{x#@[c#"";neg["j"$y*c]?c:prd x;:;"x"]}

2) Use Monte Carlo method to get the location of mines

f:{x#" x"y>prd[x]?1.}

Solution 2

This part can be a bit tricky. Most common approach is to find all the indices of the empty char, then for each of them, find all the neighboring indices, sum all the mines and apply the result back to the empty char. But this can be inefficient when the grid gets bigger.

In order to get around this, we can use the Game of Life technique shown in this blog. This technique is pretty fast of the to the neighboring cells. One example is as follow:

g:{.Q.n[sum"x"=count[x 0]#''raze 2((prev;::;next)@'\:)/x]^x}

count[x 0]#''raze 2((prev;::;next)@'\:)/x is the part to get to the neighboring cells. First iteration gets the location of (-1 0;0 0;1 0). Then the second iteration gets the rest of the location of neighboring cells ((-1 -1;-1 0;-1 1);(0 -1;0 0;0 1);(1 -1;1 0;1 1)).

Once that is done, we just sum the number of mines and this automatically arrange the result in the grid. Since the number of mines never gets above 8, we can get the string of the numbers by indexing .Q.n (a bit of cheat doesn’t hurt 🙂 ). Then we just fill the result back to the original grid (remember that empty char is null, so fill will replace them with the result while leaving the mines untouched).

I hope you enjoy the challenge. It is nice to look at another aspect of q to solve puzzles like this one. My favorite is still the Game of Life technique, nice and elegant. What is yours? 🙂 Until next time!
[/showhide]