javascript - 扫雷算法解决方案

Question

这是一个关于this的问题codefight 调用。

要求参赛者检查以二维数组表示的扫雷场是否有效。

详细信息: 扫雷游戏板的每个单元格可以是:

• 一个地雷(显示为 9)
• 或代表其周围单元格中地雷数量的数字 (当该单元格在至少一个 Angular 上与该单元格相遇时，该单元格被视为围绕另一个单元格)(显示为 0 - 8)

我的方法(有效):

• 遍历所有项目
• 检查邻居是否有地雷(如果有的话，计算地雷的数量)
• 将找到的地雷数量与图 block 上的数量进行比较
• 如果数字不相等则返回false，否则继续

有人可以向我解释一下这种方法是如何工作的吗？

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)
           )
     )

我了解多少:

• g 是二维数组，代表场
• .some 将测试，如果数组中的元素将通过测试
• r 是字段中的单行
• c 是每一行中的每个元素
• i 和 j 是什么？柜台？
• 什么是d？
• 编写如此隐秘的代码有什么好处？

Answer 1

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
   ))

所以它基本上会检查某些字段是否不是地雷(字段<9)并且递归函数成功。递归函数从 0 到 9 并处理以下步骤:

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

( 如果您对 ~-(d/3) 感到疑惑，它会执行以下操作:

0-2: ~-([0,1,2]/3) = ~-0 = -(-0)-1 = -1
3-5: ~-([3,4,5]/3) = ~-1 = -(-1)-1 = 0
6-8: ~-([6,7,8]/3) = ~-2 = -(-2)-1 = 1

)

所以基本上函数将通过这种模式(0 是 field ，X 是当前检查的位置)

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

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

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

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

...

然后如果有地雷 (>8)，它会从字段中减去 1(真)。所以如果字段是 4 并且周围有 4 个地雷，它会做 4-1-1-1-1，所以整个是 0，这是假的:

两个例子(字段是中间那个):

9 9 9
9 4 1
1 1 0

所以递归函数将返回 0 (falsy) ( 4-1-1-1-1)

9 9 9
2 4 1
0 0 0

这将返回 1(真实)(4-1-1-1)

所以这个递归函数可以重命名为countaroundiswrong:

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

因此，如果有地雷，并且周围的计数是错误的，则发现了一些字段并且整个事情都是真的，倒置并且结果是错误的。一种非神秘的方式:

function countaroundiswrong(mainarray,field,col,row){
 for(var x=-1;x<2;x++){
  for(var y=-1;y<2;y++){
    if(mainarray[row+x] && mainarray[row+x][col+y]){
      if(mainarray[row+x][col+y] >8){
         field--;
      }
    }
   }
  }
  return field;
}