如何实现Thistlethwaite算法在Haskell？ [英] How to implement the Thistlethwaite's algorithm in Haskell?

问题描述

我想实现的Thistlethwaite的算法在Haskell，下面的描述中发现这里 ，但遇到了困难。

I am trying to implement the Thistlethwaite's algorithm in Haskell, following the descriptions found here, but encountered difficulties.

到目前为止，我已成功地重新present立方体，让它动随心所欲，并在终端上显示它（二维重presentation），但我想，当有麻烦降低的一般的立方体的一个可以从一个标准立方体的组中获得由移动（R，L，F，B，U 2，D 2）（符号如在链接），因为有太多的情况要考虑：如何多种颜色的向上层上是错误的导向，中间层等上这只是描述中的第一个阶段，但我在codeS发现了一个乱了，所以我一定是错过了一些东西。

So far, I have managed to represent the cube, make it move as one likes, and display it on the terminal (a 2-dimensional representation), but I got problems when trying to reduce a general cube to one which can be obtained from a standard cube by moves in the group (R, L, F, B, U2, D2) (notations as in the link), as there are too many cases to consider: how many colors on the up layer are wrongly-oriented, on the middle layer, etc. This is only the first stage in the description, but I found a mess in my codes already, so I must have missed something.

由于我不知道如果我的上述描述是清楚的，我把相关的codeS之下，这是不正确的，但指出问题。

As I am not sure if my description above is clear, I put up the relevant codes below, which are not correct, but indicate the problem.

--To intersect lists, of which the sizes are not very large, I chose to import the Data.List
import Data.List

--Some type declarations
data Colors = R | B | W | Y | G | O
type R3 = (Int, Int, Int)
type Cube = R3 -> Colors
points :: [R3] --list of coordinates of facelets of a cube; there are 48 of them.
mU :: Cube -> Cube --and other 5 moves.
type Actions = [Cube -> Cube]
turn :: Cube -> Actions -> Cube --chains the actions and turns the cube.
edges :: [R3] --The edges of cubes

criterion :: Colors -> R3 -> Bool -- determine if the edges are mis-placed.
criterion co p@(x, y, z) = case co of --W and Y are up and down faces respectively.
 R -> not (or [abs(x) == 3, abs(y) == 3])
 B -> not (or [abs(y) == 3, abs(z) == 3])
 O -> not (or [abs(x) == 3, abs(y) == 3])
 G -> not (or [abs(y) == 3, abs(z) == 3])
 _ -> True


stage1 :: Cube -> Cube 
stage1 c = turn c opes where
    wrongs = do
            res <- [[]]
            eg <- edges
            if criterion (c eg) eg
              then res
              else res ++ [eg]
    ups = filter (\(x, y, z) -> y == 3) points
    downs = filter (\(x, y, z) -> y == -3) points
    middles = filter (\(x, y, z) -> y == 0) points
    opes = do
         res <- [[]]
         case length (intersect middles wrongs) of
         0 -> case [length (intersect ups wrongs) == 0, length (intersect downs wrongs) == 0] of
            [True, True] -> res
            [True, False] -> [mD] --A quarter turn of the downside of the cube.
            [False, True] -> [mU]
            _ -> [mD, mU]
         1 -> let [(x, y, z)] = intersect middles wrongs in
                if x == 3 then case [length (intersect ups wrongs) == 0, length (intersect downs wrongs) == 0] of
                    [True, True] -> if z > 0 then [mR, mU] else [mR, mD]
                    [True, False] -> if z > 0 then [mD, mR, mU] else [mD, mR, mD]
                    [False, True] -> if z > 0 then [mU, mR, mU] else [mU, mR, mD]
                    _ -> if z > 0 then [mD, mU, mR, mU] else [mD, mU, mR, mD]
                else []

后来我意识到，上述code是错误的，因为我不能简单地做一个直角转弯U或D，它使正确的边缘，如果有的话，变得不正确的，我将讨论125 = 5 * 5 *5箱子根据有多少错误的边缘上的每一个三层的立方体，这是我认为的没有正确。

Then I realized that the above code is wrong as I cannot simply make a quarter turn U or D which makes the correct edges, if any, become incorrect, and I shall discuss 125 = 5 * 5 * 5 cases according to how many wrong edges are on each of the three layers of the cube, which I think of as not "right."

所以我的问题是如何实现的算法，可以处理这么多的情况下，在一个不错的方式？

So my question is how to implement an algorithm that can handle so many cases, in a nice way?

如果一些有关说明不清，请告诉我，让我可以解释我在做什么，什么我的问题是。

If something about the description is unclear, please tell me so that I can explain what I am doing and what my problem is.

任何意见和建议，都大大AP preciated，非常感谢提前。

Any ideas and suggestions are greatly appreciated, thanks very much in advance.

P.S。我本来想实现科尔夫的或Kociemba的算法，但事实证明，我甚至不能处理最简单的情况。

P.S. I originally wanted to implement Korf's or Kociemba's algorithms, though it turned out that I cannot even handle the simplest case.

推荐答案

一件事 - 这code：

One thing - this code:

wrongs = do
        res <- [[]]
        eg <- edges
        if criterion (c eg) eg
          then res
          else res ++ [eg]

更好写成过滤器。（\如 - ＆GT;没有（标准（C EG）EG））边

这篇关于如何实现Thistlethwaite算法在Haskell？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！