javascript - 如何计算网格上所有可能的路径

Question

我最近在 brillant.org 的 Instagram 帐户上看到了一张挑战照片:

说明: 机器人随机走 4 步(不能走对 Angular 线)。

最有可能降落在哪个区域？

显然，机器人有 4⁴ = 256 条可能的路径。 我尝试编写一个程序(Javascript)来解决该问题，但我的方法不起作用。 实际上，我没有在这里展示有用的代码，因为我很早就陷入了困境。

所以我的问题是: 您将如何编写一个程序来:

1. 检查所有 256 条可能的路径

2. 告诉我有多少 (%) 降落在哪个区域

Answer 1

这是一个非常酷的问题! 感谢您让我发现了 brillant.org 的 Instagram 帐户。 因此，我将按以下步骤进行:

1. 编写一个函数来计算所有可能的重复排列 (n^k)
2. 生成一个 map ，在其中执行第 1 步中计算出的所有可能的移动
3. 检查机器人最后一步将着陆的区域并将其存放
4. 根据第 3 步中的计数计算百分比

第一步本身就是一个问题，它不属于这个范围。您可以在此处使用或修改代码:https://rosettacode.org/wiki/Permutations_with_repetitions

然后，为了生成 map ，我简单地使用了一个数组:

const map = [
  0, 0, 0, 0, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 0, 0, 0,
  0, 0, 1, 1, 2, 1, 1, 0, 0,
  0, 1, 1, 2, 2, 2, 1, 1, 0,
  1, 1, 3, 3, 2, 3, 3, 1, 1,
  0, 1, 1, 3, 3, 3, 1, 1, 0,
  0, 0, 1, 1, 3, 1, 1, 0, 0,
  0, 0, 0, 1, 1, 1, 0, 0, 0,
  0, 0, 0, 0, 1, 0, 0, 0, 0,
];

这是您提供的图像的表示，每个区域都标有不同的数字，我们稍后将重复使用。

此时我定义了一个包含 4 种可能的移动的数组:

const moves = [
  -1,  // left 
   1,  // right,
  -9,  // top
   9,  // bottom
];

这些值表示沿注释中写入的方向移动所需的偏移量:我想左和右是不言自明的。对于顶部和底部，由于我们使用数组作为“矩阵”，因此我们基本上需要将 y 值转换为数组中的索引值。公式很简单:index = x + y * width，这意味着如果您想指定 y 来向上移动一个单元格您有 -1 * 9，向下 移动是 1 * 9。

出于同样的原因，机器人的起始位置(在 map 中心)计算如下:4 + 4 * 9。

现在我用排列函数计算所有可能的移动组合:

const allmoves = permutationsWithRepetition(4, moves);

并创建一个数组来存储结果:

let results = [0, 0, 0, 0];

之后，我只是迭代所有可能的移动数组，并计算移动结束时的位置:

for (let j = 0; j < allmoves.length; j++) {
  // set the robot's initial position at the center
  // before executing any moves' list
  let pos = 4 + 4 * 9;

  // calculate the new position using the current moves
  for (let i = 0; i < moves.length; i++) {
    let move = allmoves[j][i];
    pos += move;
  }

  // now `map[pos]` points to a number between 1 and 3
  // that identify the area where the robot is.
  // we use that number as index of the results
  // to increment its value.
  // Notice that it's impossible land to any 0 area
  // if we start from the center and we can only perform
  // 4 moves.
  // We use that number as `index` for our `results`
  results[map[pos]]++;
}

现在在结果中，您将看到机器人最终到达哪个区域的次数:

console.log(results); // [0, 60, 100, 96]

如上所述，给定起始位置和机器人在任何 0 区域着陆的移动次数是不可能的，因此第一个索引的值将为 0。 您可以看到它在区域 1(橙色区域)着陆了 60 次，在区域 2 100 次(最小区域，绿色/浅绿色区域)，在区域 3 区域着陆了 96 次(蓝色/紫色区域) )。

此时您可以计算百分比(次/总计 * 100)并以正确的格式显示:

// we skip the first element of results since
// it's not an area (and we'll be always 0)
for (let k = 1; k < results.length; k++) {
  console.log(k, `${(results[k] /  allmoves.length * 100).toFixed(2)}%`)
}

你会得到:

1 "23.44%"
2 "39.06%"
3 "37.50%"

您还可以进行经验检查，实际上随机生成一万个移动，并使程序应用这些移动而不是所有移动，您会发现最终总是以相似的数字结束(显然，但这也是数学的有趣部分，请验证这确实是您所期望的!)。

这里的工作代码也实现了 permutation code在开头提到的，来自rosettacode.org，以及这篇文章中解释的代码:https://codepen.io/zer0/pen/RwWPZmE

(需要打开控制台才能看到结果)