Implement the Enigma Machine

Question

The Enigma machine is a fairly complex cipher machine used by the Germans and others to encrypt their messages. It is your job to implement this machine*.

Step 1, Rotation

Our enigma machine has 3 slots for rotors, and 5 available rotors for each of these slots. Each rotor has 26 different possible positions (from A to Z). Each rotor has a predefined notch position:

Rotor  Notch
------------
1      Q
2      E
3      V
4      J
5      Z

On keypress the following steps occur:

1. The rotor in Slot 1 rotates
2. If the rotor in Slot 1 moves past its notch, then it rotates the rotor in Slot 2.
3. If the rotor in Slot 2 is in its notch (but didn't just move there), both rotor 2 and 3 rotate once.

If we are using rotors 1,3,5 and they are in positions P,U,H then the sequence of positions is: P,U,H > Q,U,H > R,V,H > S,W,I

Step 2, Substitution

Each of the rotors performs a simple character substitution. The following is a chart of each of the rotors in the A position:

  ABCDEFGHIJKLMNOPQRSTUVWXYZ
  --------------------------
1 EKMFLGDQVZNTOWYHXUSPAIBRCJ
2 AJDKSIRUXBLHWTMCQGZNPYFVOE
3 BDFHJLCPRTXVZNYEIWGAKMUSQO
4 ESOVPZJAYQUIRHXLNFTGKDCMWB
5 VZBRGITYUPSDNHLXAWMJQOFECK
R YRUHQSLDPXNGOKMIEBFZCWVJAT

Rotor 1 in position T is PAIBRCJEKMFLGDQVZNTOWYHXUS, which would substitute the letter C for I.

After the three rotors perform their substitution, the reflector is hit (listed as R above). It performs its own substitution, and then reflects the signal back through the rotors. The rotors then perform a reverse substitution in reverse order.

Reverse substitution means that instead of Rotor 1 substituting A with E, it substitutes E with A

Slots are filled with rotors 1,2,3 all in position A. The letter Q follows the path Q>X>V>M through the rotors. M reflects to O, which then follows the reverse path of O>Z>S>S. Therefore, A is substituted with S.

Input/Output

You are passed:

1. A list of 3 rotors (as integers)
2. A list of 3 starting rotor positions (as letters)
3. A string that needs to be encrypted.

You can assume that your input will be well formed, and all characters will be uppercase letters, no spaces.

You must return the encrypted string.

You can optionally accept the rotors, notches, and reflectors as input. For those that don't can take off 95 bytes from their score, as 95 = ceil(log2(26 letters ^(26*6 rotors +5 notches))/8 bytes)

Test cases

Rotor Position Input              Output
4,1,5 H,P,G    AAAAAAAAA          PXSHJMMHR
1,2,3 A,A,A    PROGRAMMINGPUZZLES RTFKHDOCCDAHRJJDFC
1,2,3 A,A,A    RTFKHDOVZSXTRMVPFC PROGRAMRXGVGUVFCES
2,5,3 U,L,I    GIBDZNJLGXZ        UNCRAUPSCTK

My implementation can be found on Github. I've tested it, but I may have bugs in my implementation (which would mean that my test cases are likely wrong).

_{*I've tried to make this as accurate as possible, but due to the variations between machines, I may have some details wrong. However, your task is to implement what I've described, even if I'm inaccurate. I'm not including the plugboard for simplicity}

Answer 1

Jelly, 42 38 37 bytes

="⁵Ḣ€Ṗ1;ṙ@"µɼ⁶ṭØAiịɗƒµ®Ṛi@ịØAɗƒ
ḷ⁹©Ç€

Try it online!

Verify each test case

This is extremely liberal with the input format. It takes input in the following way:

• The three rotors (the strings, not the numbers) as the first command line argument, each rotated so that the starting points are the first characters
• The message as the second command line argument
• The 3 specific notches as the third command line argument
• The reflector as the fourth command line argument

In the above TIO link, the Footer converts a triple of numbers (the rotors) into the rotor strings, then rotates them to the correct order, so that you don't have to do it yourself.

However, for 45 bytes we can have a program which takes input in the following way:

• The message, on STDIN
• The three rotors (as the strings) as the first command line argument
• The 3 specific notches as the second command line argument
• The reflector as the third command line argument
• The three starting points for the rotors as the fourth command line argument

Again, the Footer converts the rotors from integers to the corresponding strings.

Finally, if we want to go all the way and just accept 3 inputs (the rotors, as integers, the starting positions and the message (thus have -95 to our score)), we get a score of 44

---

How it works

As they all use the same underlying algorithm, I'll just explain the 38 byte version in full, and I'll cover how the other two versions adapt the inputs to match the shortest version. For this explanation: M is the message, R are the three rotor strings, N are the notches, F is the reflector and C is the value in the register (initially 0).

ḷ⁹©Ç€ - Main link. Takes M on the left and R on the right
 ⁹    - Yield R
  ©   - And copy it into the register. C = R
ḷ     - Discard R and yield M
    € - Over each character in M:
   Ç  -   Call the helper link
        Implicitly output the final result

="⁵Ḣ€Ṗ1;ṙ@"µɼ⁶ṭØAiịɗƒµ®Ṛi@ịØAɗƒ - Helper link. Takes a character X on the left

="⁵Ḣ€Ṗ1;ṙ@"µɼ                   - Rotate the rotors
            ɼ                   - Yield C, run the following on it, save the result to C:
           µ                    -   Initially, C = R, the list of rotors
  ⁵                             -   Yield the notches, N
 "                              -   Pair each notch with each rotor, then:
=                               -     Vectorised equality
   Ḣ€                           -   Take the head of each
                                      This yields a triple of bits [a, b, c]
                                      which indicate which rotor hits its notch
     Ṗ                          -   Remove c as rotor 3 has no affect
      1;                        -   Prepend 1 as rotor 1 always moves; [1, a, b]
          "                     -   Pair 1 with rotor 1, a with rotor 2 and b with rotor 3,
                                        then for each pair:
        ṙ@                      -     Rotate the rotor if the bit is 1

             ⁶ṭØAiịɗƒ           - Send the character through the rotors
             ⁶                  - Yield the reflector F
              ṭ                 - Tack it to the end of the rotors, call this C'
                   ɗ            - Group the previous 3 links into a dyad f(U, L):
                                   where U is a character and L a list of characters
               ØA               -   "ABC...XYZ"
                 i              -   Index of U in the alphabet
                  ị             -   Index into L
                    ƒ           - Starting with X, reduce C' by the dyad f(U, L)
                                  As C is a triple of lists of characters, this returns
                                  A = f(f(f(f(X, C[1]), C[2]), C[3]), F), a single character

                     µ®Ṛi@ịØAɗƒ - Send A back through the rotors
                     µ          - Begin a new link with A as the argument
                             ɗ  - Group the previous 3 links into a dyad g(U, L)
                        i@      -   Index of U in L, i
                          ịØA   -   i'th letter of the alphabet
                      ®         - Yield C
                       Ṛ        - Reverse C
                              ƒ - Starting with A, reduce rev(C) by the dyad g(U, L)
                                      This yields g(g(g(A, C[3]), C[2]), C[1]),
                                      which is our intended result

How the other 2 work

The 45 byte version

Taking a look at the code, we notice that the only thing that's changed is that the last line is now

ṙ"©⁶O_65¤ṛɠÇ€

The difference between this version and the 37 byte version is how the rotors are taken as input:

The three rotors (the strings, not the numbers) as the first command line argument, each rotated so that the starting points are the first characters

The three rotors (as the strings) as the first command line argument

The new bits here just rotate the rotors for us and take M from STDIN:

ṙ"©⁶O_65¤ṛɠÇ€ - Main link. Takes R on the left
        ¤     - Create a nilad:
   ⁶          -   The 3 starting points of the rotors
    O         -   Converted to char points
     _65      -   Minus 65
 "            - Zip with each rotor:
ṙ             -   Rotate the rotor that many steps
  ©           - Save this to the register
          ɠ   - Read M from STDIN
         ṛ    - Discard the rotors and yield M
           ǀ - Call the helper link on each character of M

The 139 byte version

Let's take a look at the full code:

="³ị“QEVJZ”¤Ḣ€Ṗ1;ṙ@"µɼ“¡ƝḋœṚṗḶw⁸Aß`’œ?ØA¤ṭØAiịɗƒµ®Ṛi@ịØAɗƒ
ị“F.⁻wṣḊ£tọḅɱ“¥AṡḌỴịk⁼UH9“Ñɱ½#Ẋʋẹ¹⁼UṢ“KzBpñÇḅẊẎḳḣ“¡j5ɼ}ṡỴb\£BṆ’œ?ØAṙ"©⁴O_65¤ṛɠÇ€

Try it online!

This is very similar to our 45 byte version. In fact, here's what's different in the first lines, with everything that is unchanged, replaced with .

..³ị“QEVJZ”¤..........“¡ƝḋœṚṗḶw⁸Aß`’œ?ØA¤.................

Furthermore, you'll note that the end of the first line is ṙ"©⁴O_65¤ṛɠÇ€, which is the first line of the 45 byte version, meaning that there are really only three changes. In this case, those changes are because of the changes to the input system. Here's the first 2:

• ⁴ \$\to\$ ³ị“QEVJZ”¤. Rather than take the notches as input, we use the rotor list (³) to ịndex into the string of notches “QEVJZ”. The ¤ is simply a precedence marker, telling the program to treat this as a constant

• ⁵ \$\to\$ “¡ƝḋœṚṗḶw⁸Aß`’œ?ØA¤. Again, this is changing an input into program data, the reflector in this case. ¤ Once again acts as a precedence marker. However, we have 3 new commands here:

  • œ? is a dyad which takes 2 arguments - on the left, an integer x, and on the right a string, s - and returns the x'th permutation of s
  • ØA we've already encountered, and is the uppercase alphabet. In this context, it acts as the right argument to œ?
  • “¡ƝḋœṚṗḶw⁸Aß`’ is the compressed integer \$383316524290458478707255597\$, which is the left argument to œ?

  Together, this returns the \$383316524290458478707255597\$th permutation of the uppercase alphabet, or the string "YRUHQSLDPXNGOKMIEBFZCWVJAT"

The final change is the entire start of the last line:

ị“F.⁻wṣḊ£tọḅɱ“¥AṡḌỴịk⁼UH9“Ñɱ½#Ẋʋẹ¹⁼UṢ“KzBpñÇḅẊẎḳḣ“¡j5ɼ}ṡỴb\£BṆ’œ?ØA

Here, we have a list of massive compressed numbers:

“F.⁻wṣḊ£tọḅɱ“¥AṡḌỴịk⁼UH9“Ñɱ½#Ẋʋẹ¹⁼UṢ“KzBpñÇḅẊẎḳḣ“¡j5ɼ}ṡỴb\£BṆ’

Each “ marks the beginning of a new compressed number, and the entire list is

[67892310845892591685803413, 5023890671354916271018308, 16834429128340685633834184, 72949485053238139997554738, 340670280577577536609579431]

We then take the three integers which correspond to the three rotor inputs with ị, and then use œ?ØA to generate the alphabet permutations we want for each rotor. Finally, these permutations are fed into the rest of the program, already covered above.

Answer 2

Python 3, 403 bytes

I think this is working correctly. The rotors passed to it:

def z(p,o,m,f,g,h):
 O=ord;b=lambda a:a[1:]+a[:1];d=lambda a:chr(a+O('A'));e=lambda a:O(a)-O('A');i=[list(g[i-1])for i in p];j=[f[i-1]for i in p];i=[x[e(y):]+x[:e(y)]for x,y in zip(i,o)];k=[]
 for l in m:
  if i[0][0]==j[0]:i[1]=b(i[1])
  elif i[1][0]==j[1]:i[1]=b(i[1]);i[2]=b(i[2])
  i[0]=b(i[0]);c=l
  for n in i:c=n[e(c)]
  c=h[e(c)]
  for n in reversed(i):c=d(n.index(c))
  k+=[c]
 return''.join(k)

f is the notch, g is the rotors and h is the reflector.

Ungolfed:

shift = lambda rotor: rotor[1:] + rotor[:1]
letter = lambda num: chr(num + ord('A'))
number = lambda chr: ord(chr) - ord('A')


def encode(rotors, rotorStart, message, defaultRotors, reflector, rotorNotchPositions):
    usedRotors = [list(defaultRotors[i - 1]) for i in rotors]
    notches = [rotorNotchPositions[i - 1] for i in rotors]
    usedRotors = [rotor[number(offset):] + rotor[:number(offset)] for rotor, offset in zip(usedRotors, rotorStart)]

    sub = []

    for char in message:
        # print([''.join(rotor) for rotor in usedRotors])
        if usedRotors[0][0] == notches[0]:
            usedRotors[1] = shift(usedRotors[1])
        elif usedRotors[1][0] == notches[1]:
            usedRotors[1] = shift(usedRotors[1])
            usedRotors[2] = shift(usedRotors[2])

        usedRotors[0] = shift(usedRotors[0])

        c = char
        for rotor in usedRotors:
            c = rotor[number(c)]
        c = reflector[number(c)]
        for rotor in reversed(usedRotors):
            c = letter(rotor.index(c))
        sub += [c]
        print([''.join(rotor) for rotor in usedRotors], char, c, message)

    return ''.join(sub)

rotorNotchPositions = 'QEVJZ'
*defaultRotors, reflector = [
    #ABCDEFGHIJKLMNOPQRSTUVWXYZ#
    "EKMFLGDQVZNTOWYHXUSPAIBRCJ",  # 1
    "AJDKSIRUXBLHWTMCQGZNPYFVOE",  # 2
    "BDFHJLCPRTXVZNYEIWGAKMUSQO",  # 3
    "ESOVPZJAYQUIRHXLNFTGKDCMWB",  # 4
    "VZBRGITYUPSDNHLXAWMJQOFECK",  # 5
    "YRUHQSLDPXNGOKMIEBFZCWVJAT"   # R
]

#             Rotor       Position        Input                 Output
assert encode((4, 1, 5), ('H', 'R', 'G'), 'AAAAAAAAA',
              defaultRotors, reflector, rotorNotchPositions) == 'PXSHJMMHR'
assert encode((1, 2, 3), ('A', 'A', 'A'), 'PROGRAMMINGPUZZLES',
              defaultRotors, reflector, rotorNotchPositions) == 'RTFKHDOCCDAHRJJDFC'
assert encode((1, 2, 3), ('A', 'A', 'A'), 'RTFKHDOVZSXTRMVPFC',
              defaultRotors, reflector, rotorNotchPositions) == 'PROGRAMRXGVGUVFCES'
assert encode((2, 5, 3), ('U', 'L', 'I'), 'GIBDZNJLGXZ',
              defaultRotors, reflector, rotorNotchPositions) == 'UNCRAUPSCTK'

I think this is working, but it produces a different output, due to what (I think) is a bug in the reference impl.