如何在方格表中查找指定数字所属分块tile的索引

问题描述 #

现有一个8x8的方格表，共64个单元格，每个单元格存放按行填充的连续数字：

| 0| 1| 2| 3| 4| 5| 6| 7|
| 8| 9|10|11|12|13|14|15|
|16|17|18|19|20|21|22|23|
|24|25|26|27|28|29|30|31|
|32|33|34|35|36|37|38|39|
|40|41|42|43|44|45|46|47|
|48|49|50|51|52|53|54|55|
|56|57|58|59|60|61|62|63|

我们将表格拆分为若干个包含4个单元格的tile分块，拆分效果如下：

index:0    index:1      index:12  index:15
| 0| 1|    | 2| 3|      |48|49|   |54|55|
| 8| 9| ,  |10|11| .... |56|57| , |62|63|

需要实现一个方法，传入指定数字后返回该数字所属tile分块的索引，示例返回值如下：

getTileIndexFor(8, ...)  // 返回 0
getTileIndexFor(11, ...) // 返回 1
getTileIndexFor(62, ...) // 返回 15
getTileIndexFor(55, ...) // 返回 15

现有代码框架如下，要求方法支持自定义numbersPerTileSide（分块边长，示例值为2，支持任意2的倍数）、numbersPerTableSide（表格边长，示例值为8，要求为numbersPerTileSide的整数倍）：

function getTileIndexFor(number, ...) { 
  // ????
}
 
let tiles = [/* 分块数组，每个分块是由 { numberWithCoords } 组成的数组 */]
let numbersPerTileSide  = 2 // 即2x2分块，共4个单元格，支持任意2的倍数
let numbersPerTableSide = 8 // 支持任意为numbersPerTileSide倍数的取值

// 生成0到63的8x8数字表
let tableOfNumbers = [...Array(numbersPerTableSide * numbersPerTableSide).keys()]
    
tableOfNumbers.forEach((index) => {
    let x = index % numbersPerTableSide
    let y = Math.floor(index / numbersPerTableSide)

    // 存储当前数字及其在表格中的x、y坐标
    let numberWithCoords = { number: index, x, y  }

    let tileIndex = getTileIndexFor(number, ...)

    // 分块不存在则初始化
    tiles[tileIndex] = tiles[tileIndex] || []

    // 将当前数字存入对应分块
    tiles[tileIndex].push(numberWithCoords) 
})

console.log(tiles)

预期输出结果如下：

[
  [
    { number: 0, x: 0, y: 0 },
    { number: 1, x: 1, y: 0 },
    { number: 8, x: 0, y: 1 },
    { number: 9, x: 1, y: 1 }
  ],
  ....,
  [
    { number: 54, x: 6, y: 6 },
    { number: 55, x: 7, y: 6 },
    { number: 62, x: 6, y: 7 },
    { number: 63, x: 7, y: 7 }
  ]
]

解决方案 #

实现逻辑 #

1. 先通过数字计算出它在表格内的横纵坐标x、y
2. 计算每行的分块总数：tilesPerRow = numbersPerTableSide / numbersPerTileSide
3. 计算当前坐标所属的横向分块索引：tileX = Math.floor(x / numbersPerTileSide)
4. 计算当前坐标所属的纵向分块索引：tileY = Math.floor(y / numbersPerTileSide)
5. 最终分块索引 = 纵向分块索引 × 每行分块数 + 横向分块索引

完整实现代码 #

可以直接复用框架中已经计算好的x、y坐标，避免重复运算：

function getTileIndexFor(x, y, numbersPerTileSide, numbersPerTableSide) {
  const tilesPerRow = numbersPerTableSide / numbersPerTileSide;
  const tileX = Math.floor(x / numbersPerTileSide);
  const tileY = Math.floor(y / numbersPerTileSide);
  return tileY * tilesPerRow + tileX;
}
 
let tiles = []
let numbersPerTileSide  = 2
let numbersPerTableSide = 8

let tableOfNumbers = [...Array(numbersPerTableSide * numbersPerTableSide).keys()]
    
tableOfNumbers.forEach((index) => {
    let x = index % numbersPerTableSide
    let y = Math.floor(index / numbersPerTableSide)

    let numberWithCoords = { number: index, x, y  }
    let tileIndex = getTileIndexFor(x, y, numbersPerTileSide, numbersPerTableSide)

    tiles[tileIndex] = tiles[tileIndex] || []
    tiles[tileIndex].push(numberWithCoords) 
})

console.log(tiles)

如果希望方法只接收数字作为入参，也可以把坐标计算逻辑放到方法内部：

function getTileIndexFor(number, numbersPerTileSide, numbersPerTableSide) {
  const x = number % numbersPerTableSide;
  const y = Math.floor(number / numbersPerTableSide);
  const tilesPerRow = numbersPerTableSide / numbersPerTileSide;
  const tileX = Math.floor(x / numbersPerTileSide);
  const tileY = Math.floor(y / numbersPerTileSide);
  return tileY * tilesPerRow + tileX;
}

// 调用方式
let tileIndex = getTileIndexFor(index, numbersPerTileSide, numbersPerTableSide)

两种实现都完全符合要求，测试示例返回值和预期一致。

内容的提问来源于stack exchange，提问作者user2272048