unt*_*ted 11 haskell functional-programming
我目前正在研究项目欧拉问题(www.projecteuler.net),但它有点绊脚石.其中一个问题是提供20x20的数字网格,并要求直线上4个数字的最大乘积.该线可以是水平线,垂直线或对角线.
使用过程语言我没有解决这个问题,但我首先要做的就是获得更多经验并学习更多Haskell.
截至目前,我正在网格中读取并将其转换为整数列表列表,例如 - [[Int]].这使得水平乘法变得微不足道,并且通过对该网格进行转置,垂直也变得微不足道.
对角线是给我带来麻烦的.我想到了一些方法,我可以使用显式数组切片或索引,以获得一个解决方案,但它似乎过于复杂和hackey.我相信这里可能有一个优雅,实用的解决方案,我很想听听其他人能想到的.
Nor*_*sey 10
我不同意可敬的唐斯图尔特.鉴于问题的组合性质以及问题大小仅为20x20的事实,列表列表将足够快.你想要的最后一件事是使用数组索引来应对.相反,我建议你扩展Richard Bird在其着名的数独求解器中开发的技术.更具体地说,我建议如下:
编写给定序列的函数,返回长度为4的所有连续子序列.
编写一个给定网格的函数,返回所有行.
编写一个给定网格的函数,返回所有列.
编写一个给定网格的函数,返回所有对角线.
有了这些功能,您的解决方案将变得简单.但正如你所提到的,对角线并不那么明显.什么是对角线呢？我们来看一个例子:
X . . . . .
. X . . . .
. . X . . .
. . . X . .
. . . . X .
. . . . . X
假设您使用该drop函数并从第0行中删除0个元素,从第1行中删除1个元素,依此类推.这就是你最喜欢的:
X . . . . .
X . . . .
X . . .
X . .
X .
X
对角线的元素现在形成了你留下的三角形的第一列.更好的是,你留下的东西的每一列都是原始矩阵的对角线.进行一些对称变换,您将能够轻松地枚举任何大小的方阵的所有对角线.用你的"长度为4的连续子序列"来解释每一个,鲍勃是你的叔叔!
对于那些可能被卡住的人来说更详细一点:
这个问题的关键是构图.对角线分为四组.我的例子给出了一组.要获得其他三个,请将相同的功能应用于转置的镜像,转置和镜像.
Transpose是一个单行函数,无论如何你都需要它来干净地恢复列.
镜像比转置更简单 - 想想你可以在Prelude中使用哪些功能.
对称方法将给出每个主要对角线两次; 幸运的是,问题表明重复对角线是可以的.