haskell - 水平、垂直和对角线上的数字相乘

Question

我目前正在研究一个项目欧拉问题(www.projecteuler.net)，但遇到了一个绊脚石。其中一个问题提供了一个 20x20 的数字网格，并要求直线上 4 个数字的最大乘积。这条线可以是水平的、垂直的或对角线。

使用程序语言解决这个问题我没有任何问题，但我首先解决这些问题的部分动机是获得更多经验并学习更多 Haskell。
截至目前，我正在阅读网格并将其转换为整数列表列表，例如 -- [[Int]]。这使得水平乘法变得微不足道，并且通过转置这个网格，垂直也变得微不足道。

对角线给我带来了麻烦。我已经想到了几种可以使用显式数组切片或索引来获得解决方案的方法，但它似乎过于复杂和笨拙。我相信这里可能有一个优雅、实用的解决方案，我很想听听其他人能想出什么。

Answer 1

我不同意可贵的唐·斯图尔特。鉴于问题的组合性质以及问题大小仅为 20x20 的事实，列表列表将足够快。你最不想要的就是使用数组索引。相反，我建议您扩展 Richard Bird 在其著名的 sudoku solver 中开发的技术。 .更具体地说，我建议以下内容:

编写一个给定序列的函数，返回所有长度为 4 的连续子序列。

编写一个给定网格的函数，返回所有行。

编写一个给定网格的函数，返回所有列。

编写一个给定网格的函数，返回所有对角线。

有了这些功能，您的解决方案将很容易。但正如你提到的对角线并不是那么明显。什么是对角线？
让我们看一个例子:

X . . . . .
. X . . . .
. . X . . . 
. . . X . .
. . . . X .
. . . . . X

假设您使用 drop函数，然后从第 0 行删除 0 个元素，从第 1 行删除 1 个元素，依此类推。这就是你的结果:

X . . . . .
X . . . .
X . . . 
X . .
X .
X

对角线的元素现在形成了你剩下的三角形的第一列。更好的是，你留下的每一列都是原始矩阵的对角线。进行一些对称变换，您将能够轻松枚举任意大小的方阵的所有对角线。用你的“长度为 4 的连续子序列”函数来敲击每一个，Bob 就是你的叔叔!

对于那些可能被卡住的人来说，更多细节:

这个问题的关键是组合。对角线分为四组。我的例子给出了一组。要得到其他三个，将相同的函数应用于镜像、转置和转置的镜像。

Transpose 是一个单行函数，无论如何您都需要它来干净地恢复列。

镜像比转置更简单——想想你可以使用 Prelude 中的哪些功能。

对称法会给每条主对角线两次；幸运的是，问题表明可以重复对角线。