Haskell中Enigma编码机的时钟样式计数器

Question

我正在尝试编写Enigma编码机的程序。我已经设法让转子和反射器工作良好，但正在努力解决转子前进。

对于任何不熟悉这一点的人。一个Enigma机器由3个替代密码的转子和一个包含13对字符的反射器组成。为了对字符进行编码，首先由第一个转子对其进行编码，然后将由此编码的字符传递到第二个转子，然后依此类推地通过另一个转子到达反射器，该反射器将这个新字符与其配对的字符交换。然后，以相反的方式通过转子对该成对字符进行反向编码，直到最终得到一个编码字符。

在对单个字符进行编码之前，旋转体被移位。如果你有一条很长的消息，在任何东西被编码之前，第一个转子被移动了一处，然后这个字符通过系统并进行编码。然后，在第二字符被编码之前，第一转子再次移位。转子不断地移动，直到它再次到达起始点。在第25个字符被编码之后，第一个转盘到达它开始的位置，但是现在第二个转盘移动了一个位置。然后第一个转子又转了26次，第二个转子又转了一圈。当第二个转子转动26次时，第三个转子转动一次。这将一直发生，直到达到252525，此时它们将重置回00 0，并且循环再次开始。这让我想起了一个被分成小时、分钟和秒的时钟，其中秒在不停地转动，分钟变慢了，而小时变得非常慢。

我知道这可能可以用模运算来编程，但我看不出怎么做？因此，任何帮助都将不胜感激。

Answer 1

从机器的角度来看，转子是两样东西：

• 它是一个从一个符号到另一个符号的函数
• 它可以前进到另一个函数

我们可以为它写一个类似这样的类型：

newtype Symbol = Symbol {representation :: Int}

data Rotor = Rotor {
    transformation :: Symbol -> Symbol,
    next :: Rotor
}

如果机器从反射中知道对称性，它可能是这样的

data Rotor = Rotor {
    forward :: Symbol -> Symbol,
    backward :: Symbol -> Symbol,
    next :: Rotor
}

(你也可以使用像[(Symbol -> Symbol,Symbol -> Symbol)]这样的东西)

现在，我们如何构建一个Rotor？让我们得到一个例子转子的定义，IC。

rotorICdefinition = map symbol $ "DMTWSILRUYQNKFEJCAZBPGXOHV"

现在，symbol需要有Char -> Symbol类型。像这样的东西应该可以。

symbol :: Char -> Symbol
symbol x = Symbol $ ord x - ord 'A'

ord中有一堆神奇的东西。它已经知道字母表的顺序了。例如：

Prelude Data.Char> map ord "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
[65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90]

接下来，我们希望能够根据它的定义来制作一个转子

rotorIC :: Rotor
rotorIC = makeRotor rotorICdefinition

所以makeRotor的类型应该是

makeRotor :: [Symbol] -> Rotor

我们可以把它定义为

makeRotor definition = makeRotor' 0
    where
        makeRotor' steps = Rotor {
            forward = forwardLookup steps,
            backward =  reverseLookup steps,
            next = makeRotor' ((steps+1) `mod` symbolModulus)
        }
        forwardLookupTable = array (minBound, maxBound) (zip symbols definition)
        reverseLookupTable = array (minBound, maxBound) (zip definition symbols)
        forwardLookup = lookup forwardLookupTable
        reverseLookup = lookup reverseLookupTable
        lookup lookupTable steps = (lookupTable !) . Symbol . (`mod` symbolModulus) . (+ steps) . representation 

这里发生了很多事情。我们正在制作一个无限的转子，每个转子都比前一个旋转了一步，从一个旋转了0步的转子开始。makeRotor'中的steps正在跟踪它被旋转了多少步。Rotor由forward和backward变换组成，这两个变换都考虑了转子旋转的步数。next的转子是一样的，只是多转了一步。为了防止整数最终溢出，我们将它的模取为存在的符号数量symbolModulus。(有更有效的方法可以做到这一点)。这两个查找基于一次构建的查找表，根据definition将范围(minBound, maxBound)中的每个符号映射到它应该是什么。lookup本身就是接受输入，加上步数，取符号个数的模，然后返回查找表中那个位置的值。

这需要我们定义新出现的minBound、maxBound、symbols和symbolModulus

instance Bounded (Symbol) where
    minBound = symbol 'A'
    maxBound = symbol 'Z' 

symbolModulus = (representation maxBound) - (representation minBound) + 1

-- This could have some other definition
symbols = map symbol $ "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

我们将添加一个小UI，并将整个程序放在一起：

module Main (
    main
) where

import Data.Char
import Data.Array -- requires array package
import System.IO

main = go rotorIC
    where go rotor = do
            putStr "Input   : "
            hFlush stdout
            command <- getLine
            case command of
                "next" -> go (next rotor)
                [] -> return ()
                text -> case all (inRange (char minBound, char maxBound)) text of
                    True -> do
                        putStrLn . ("Forward : " ++) $ map (char . forward rotor . symbol) text
                        putStrLn . ("Backward: " ++)$ map (char . backward rotor . symbol) text
                        go rotor
                    _ -> do
                        putStrLn "Not all of the input was symbols"
                        go rotor 


newtype Symbol = Symbol {representation :: Int} deriving (Eq, Ord, Ix)

symbol :: Char -> Symbol
symbol x = Symbol $ ord x - ord 'A'

char :: Symbol -> Char
char x = chr $ representation x + ord 'A' 

instance Bounded (Symbol) where
    minBound = symbol 'A'
    maxBound = symbol 'Z' 

symbolModulus = (representation maxBound) - (representation minBound) + 1

-- This could have some other definition 
symbols = map symbol $ "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

data Rotor = Rotor {
    forward :: Symbol -> Symbol,
    backward :: Symbol -> Symbol,
    next :: Rotor
}


rotorICdefinition = map symbol $ "DMTWSILRUYQNKFEJCAZBPGXOHV"

rotorIC :: Rotor
rotorIC = makeRotor rotorICdefinition

makeRotor :: [Symbol] -> Rotor

makeRotor definition = makeRotor' 0
    where
        makeRotor' steps = Rotor {
            forward = forwardLookup steps,
            backward =  reverseLookup steps,
            next = makeRotor' ((steps+1) `mod` symbolModulus)
        }
        forwardLookupTable = array (minBound, maxBound) (zip symbols definition)
        reverseLookupTable = array (minBound, maxBound) (zip definition symbols)
        forwardLookup = lookup forwardLookupTable
        reverseLookup = lookup reverseLookupTable
        lookup lookupTable steps = (lookupTable !) . Symbol . (`mod` symbolModulus) . (+ steps) . representation 

现在我们来看几个例子。字母表的前六个字母的正向转换是rotorICdefinition的开始

Input   : ABCDEFG
Forward : DMTWSIL
Backward: RTQAONV

如果我们放在rotorICdefinition的开头，我们将得到字母表的前六个字母作为向后转换：

Input   : DMTWSIL
Forward : WKBXZUN
Backward: ABCDEFG

如果我们转到转子的下一步，我们会得到一些非常不同的东西：

Input   : next
Input   : ABCDEFG
Forward : MTWSILR
Backward: TQAONVY

但是如果我们在'A‘前面加上一个开头的字母，我们又得到了我们的定义：

Input   : ZABCDEF
Forward : DMTWSIL
Backward: RTQAONV

在转到转子上的下一步25次之后，我们回到了开始的地方：

Input   : next
(25 times total)
Input   : next
Input   : ABCDEFG
Forward : DMTWSIL
Backward: RTQAONV

Answer 2

您需要分别测试每个转子(或者您可以编写一个复杂的表达式来一次性更新它们，但这是不可读的)：

type RotorState = (Int, Int, Int)

nextState :: RotorState -> RotorState
nextState (x, y, z)
  | x == 25 && y == 25 && z == 25 = (0, 0, 0)
  | y == 25 && z == 25 = (x + 1, 0, 0)
  | z == 25 = (x, y + 1, 0)
  | otherwise = (x, y, z+ 1)

要使用，您需要一个类似以下的函数：

actUponRotor :: RotorState -> (RotorState, a)
actUponRotor r = (nextState r, undefined)

其中undefined代表对当前转子位置进行的计算(输出单个字符或接收一个字符)

如果您不喜欢显式地携带状态，则可能需要使用State monad，如下所示：

actUponRotor' :: State RotorState a
actUponRotor' = do
  changeRotorState
  return undefined

changeRotorState :: State RotorState ()
changeRotorState = modify nextState

Answer 3

您可以在命令式语言中使用Haskell的通用计数器等效项。

假设你有一些命令式代码

def f(x) {
c = 0 ;

while ( c<k ) {
    x = g(x,c) ;
    c +=1; 

return z(x);
}

Haskell版本将是

f x = f' 0 x where f' k x = z x ; f _ x = f (_+1) (g x ) 

所以你可以把转子的位置作为内部论点，就像这样。

你也可以使用模式匹配。

RotorState = (Int,Int,Int)
turnRotor :: RotorState ->RotorState
turnRotor (25, 25 , 25    )  = (0  , 0 ,  0)
turnRotor (_ , 25 , 25    )  = (_+1, 0 ,  0)
turnRotor (_ , __ , 25    )  = (_  , __+1,0)
turnRotor (_ , __  , ___  )  = (_  , __, ___+1)

玩得开心!我希望这能对你有所帮助。