Haskell中的高阶函数谜题求解函数

柴郡

我正在尝试用金字塔重建一个谜语:

图1

金字塔的最后一层是数字从1到n的排列,其中n是字段数。然后,不在最低层中的所有其他字段都是该数字对角线下方数字的总和。

所以我想做一个函数,当给定左边的谜语时,返回右边的解。我打算通过枚举类似这样的层来做到这一点:

列举金字塔

对于各层,我做了一个自定义数据类型:

data Layer = One | Two | Three | Four | Five | Six
deriving (Eq,Ord,Enum,Show)

和其他类型:

type LayerDepth = Layer
type FieldNumber = Int
type FieldContent = Int
type FieldAssignment = (FieldNumber -> FieldContent)
type PyramidRiddle = FieldAssignment
type PyramidSolution = FieldAssignment
type PyramidSolutions = [PyramidSolution]

和功能:

solveRiddle :: LayerDepth -> PyramidRiddle -> Pyramidsolutions

对于所示的示例,我将创建类型为(FieldNumber-> FieldContent)的匿名函数:

fieldAssignment1 = \n -> if (n==6) || n==8) then 3 else 0

此功能将用数字3标记第6和第8字段

然后调用: solveRiddle Four fieldAssignment1 ->> [pyramidSolution1, pyramidSolution2]

Four means four layers, and PyramidSolutions is the list of FieldAssignments that has a solutions of the riddle

My problem:

I would somehow need to return a function that will given the field assignment calculate the permutations in the last layer and based on that assign the numbers to the rest of fields.

Somehow like this:

pyramidSolution1 = \n -> case n of 1 -> 18
                                   2 -> 11 
                                   3 -> 7
                                   4 -> 7 
                                   5 -> 4 
                                   6 -> 3 
                                   7 -> 4 
                                   8 -> 3 
                                   9 -> 1 
                                  10 -> 2
                                   _ -> 0 

and

pyramidSolution2 = \n -> case n of 1 -> 20
                                   2 -> 12 
                                   3 -> 8
                                   4 -> 7 
                                   5 -> 5 
                                   6 -> 3 
                                   7 -> 4 
                                   8 -> 3 
                                   9 -> 2 
                                  10 -> 1
                                   _ -> 0 

But what is the best way to approach this?

How do I assign a permutation of the numbers and know how to place them that the number up is the sum of the numbers bellow?

What is the best way to implement the anonymous function pyramidSolution1 and pyramidSolution2 into the code above?

chepner

I'd simplify this a little. A layer is a list of numbers:

type Layer = [Int]
-- e.g. [4,3,1,2]

A rule is a list of fixed assignments to some elements.

data Must = Any | Only Int  -- Yes, it's just Maybe with different labels

type Rule = [Must]
-- e.g. [Any,Only 3,Any,Any]

You'll need a function that can generate a layer from the one below it:

nextLayer :: Layer -> Layer
nextLayer = undefined
-- nextLayer [4,3,1,2] == [7,4,3]

以及根据有效规则检查图层的功能

isLayerValid :: Rule -> Layer -> Bool
isLayerValid = undefined
-- isLayerValid [Any,Any,Only 3] [1,2,3] == True
-- isLayerValid [Any,Any,Only 3] [1,3,2] == False

谜语只是规则列表:

type Riddle = [Rule]
riddle :: Riddle
riddle = [[Any, Only 3, Any, Any], [Any, Any, Only 3], [Any, Any], [Any]]

一个解决方案是从某个基础开始的层列表。

type Pyramid = [Layer]
pyramid :: Layer -> Pyramid
pyramid [] = []
pyramid base = base : pyramid (nextLayer base)
-- pyramid [4,3,1,2] == [[4,3,1,2],[7,4,3],[11,7],[18]]

一个正确的解决方案是一个验证对一个给定的谜语:

isValidFor :: Riddle -> Pyramid -> Bool
isValidFor [] [] = True
isValidFor (r:rs) (x:xs) = isLayerValid r x && isValidFor rs xs
-- isValidFor riddle (pyramid [4,3,1,2]) == True
-- isValidFor riddle (pyramid [1,3,4,2]) == False

现在的诀窍是生成所有潜在的解决方案

permutations :: [Int] -> [[Int]]
permutations ns = undefined

-- e.g. allSolutions = map pyramid (permutations [1..n])

并使用解决方案测试对其进行过滤:

solutions :: Riddle -> [Pyramid]
solutions r = filter (isValidFor r) (map pyramid (permutations [1..length r]))
-- solutions riddle == [pyramid [4,3,1,2], pyramid [4,3,2,1]]

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章