User12547645 User12547645 - 1 year ago 96
Javascript Question

Minesweaper algorithm solution

this is a question about this codefight callenge.

The contestant is asked to check if a minesweeper field, represented as a 2D-Array is valid.

Details:
Each cell of Minesweeper gameboard can be:


  • a mine (appears as 9)

  • or a number representing the number of mines in its surrounding cells
    (a cell is considered as surrounding another cell when this cell meets that cell on at least 1 corner) (appears as 0 - 8)



My approach (which works):


  • loop through all items

  • check neighbors for mines (and count number of mines, if there are any)

  • compare number of found mines with number on tile

  • return false, if numbers are unequal, else continue



Could someone please explain to me how this approach works?

minesweeper1 = g =>
!g.some((r,i) =>
r.some((c,j) =>
c < 9 && (f = d => d-- ? f(d) - ((g[i + ~-(d/3)] || 0)[j + d%3 - 1] > 8) : c)(9)
)
)


How much I understand:


  • g is the 2D-array, representing the field

  • .some will test, if an Element in the array will pass a test

  • r are the single single rows in the field

  • c is every single element in each row

  • What are i and j? Counters?

  • What is d?

  • what is the advantage of writing code so cryptic?


Answer Source
minesweeper1 = mainarray => // an arrow function, that gets the two d array passed
!mainarray.some((row,rownumber) =>
  row.some((field,columnumber) =>//checking the 2d array if some of the fields
        field < 9 && (//is not a mine
          recursive = d => //and the magic recursive function is true
            d-- 
            ? recursive(d) /* get the value of one lower d*/ - ((mainarray[rownumber + ~-(d/3)] || 0)[columnnumber + d%3 - 1] > 8) /* subtract one if this magic is true */
             : field//if d=-1 it returns field
         )(9)//the starting point of the recursive function d=9
   ))

So it basically checks, if some of the fields is not a mine (field<9) and the recursive function successes. The recursive function goes from 0 to 9 and processes the followig steps:

field //the current value as start value

//d=0
- (mainarray[rownumber - Math.floor(d/3)-1][columnnumber + d%3 ] >8)
//d=1
 - (mainarray[rownumber - Math.floor(d/3)-1][columnnumber + d%3 ] >8)
//...
//repeat until d=9

So basically the function will go through this pattern ( 0 is field , X is the currently checked position)

d=0
X - -
- 0 -
- - -

d=1
- X -
- 0 -
- - -

d=2
- - X
- 0 -
- - -

d=3
- - -
X 0 -
- - -

...

And then if theres a mine (>8) it substracts 1 (true) from field. So if the field is 4 and there are 4 mines around, it will do 4-1-1-1-1, so the whole thing is 0, which is falsy:

Two examples (field is the middle one):

9 9 9
9 4 1
1 1 0

So the recursive function will return 0 (falsy) ( 4-1-1-1-1)

9 9 9
2 4 1
0 0 0

This will return 1 (truthy) (4-1-1-1)

So this recursive function could be renamed to countaroundiswrong :

!mainarray.some((row,rownumber) =>
  row.some((field,columnumber) =>
    fieldismine() && countaroundiswrong()
  )
)

So if theres a mine, and the count around is wrong, theres some field found and the whole thing is true, gets inverted and the result is false.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download