Categories
Functional Programming - Scala Random

Virtual Enigma Machine Implementation

After watching a video on numberphile thought it would be interesting to implement a virtual version on the Enigma cipher machine.

Step 1: Install Scala and Eclipse IDE for Scala.

http://www.scala-lang.org/downloadshttp://scala-ide.org/

Step 2: Review the numberphile video and how the Enigma machine works

Step 3: Implement each function of the machine

  1. Rotors
    • Rotor choices, rotors have different circuitry (0-24) – static value for each message
    • Initial rotor combination (0-25) – static value for each message
    • Rotor increment – Faster rotor, middle rotor, slow rotor
  2. Plug board
    • 10 wires
    • swapping 2 letters
    • static value for each message

Step 4: Write an interface between the functions and a basic interface (text?)

Step 5: Test!

Conclusion: Using Scala (trying anyway) the implementation is not very complex. What is more difficult is replicating the original machines where the output character could not equal the input character. The limitation Turing used to crack the machines. Might see if I can implement that later then test out the cracking method. Not sure how easy it would be to break the current implementation…

CODE (EnigmaMachine.scala, EnigmaMachine.class):

 

 

// Virtual reconstruction of what the enigma machines did
// The replication is of the improved version where the input could result in the same output

object EnigmaMachine {
//////////////// ENCRYPTION/DECRYPTION FUNCTIONS \\\\\\\\\\\\\\\\\\\\\
    //to replicate the simple machine circuit chars are converter to 0 - 25
    def convertMessageToSimpleInt(rawInput: String):List[Int] = {
        val userMessage = rawInput.toUpperCase
      (for (x <- userMessage) yield if (x != 32) (x.toInt - 65) else 26).toList
    }
    
    //for all integers in the list, convert
    def convertMessageToString(input: List[Int]): String = {
      (for (x <- input) yield if (x == 26) " " else (x + 65).toChar).mkString
    } 
    
    def enigmaGo(rotorChoices: List[Int], rotorPositions: List[Int], inputMessage: List[Int], encrypt: Boolean): List[Int] = {    
      // incrementing the rotors is dont based on the number of previous chars.. instead of the previous position
      def incrementRots(nth: Int): List[Int] = {
        val rot0 = (rotorPositions(0) + nth) % 26 //fast rotor
        val rot1 = (rotorPositions(1) + (nth / 26)) % 26 //medium rotor
        val rot2 = (rotorPositions(2) + ((nth / 26) /26)) % 26 //slow rotor
        List(rot0, rot1, rot2)
      }
      //applies the rotor encryption then the scramble board
      def transmuteElement(element: Int, rotPosApp: List[Int]): Int = {
        val rotorTotal = rotorList(rotorChoices(0))(rotPosApp(0)) +
              rotorList(rotorChoices(1))(rotPosApp(1)) +
              rotorList(rotorChoices(2))(rotPosApp(2)) 
        
      def scramble(inputVal:Int):Int = plugMap1.find(x => (x._1 == inputVal) || (x._2 == inputVal)) match {
            case Some(y) => if (y._1 == inputVal) y._2 else y._1 
          case None => inputVal
      }
        if (element == 26) element
        else if (encrypt) (scramble(element) + rotorTotal) % 26 else { 
            //decrypt is a bit messy atm :( 
            if (element - (rotorTotal % 26) < 0) scramble(element - (rotorTotal % 26) + 26) else scramble(element - (rotorTotal % 26))
          }     
      }
      
      //Accumulator hold the input and output lists, when input list is empty, return output.. also tail recursive
      def enigmaAccu(remInput: List[Int], rotPos: List[Int], accumOutput: List[Int]): List[Int] = {
              if (remInput.isEmpty) accumOutput
            else enigmaAccu(remInput.tail, incrementRots(accumOutput.length), accumOutput:+(transmuteElement(remInput.head, rotPos)))
      }
      
      enigmaAccu(inputMessage, rotorPositions, Nil) //start the process
    }
////////////////////   \\\\\\\\\\\\\\\\\\\\\\\\\
    
//////////////// UI STUFF \\\\\\\\\\\\\\\\\\\\\
    def useMachine(rotorChoices: List[Int], rotorStartVals: List[Int], activity: String) = {
            spamLine
            val inputMessage = convertMessageToSimpleInt(askInput("Please enter a message to be " + activity + ", use only a-z: "))
            val resultingMessage = enigmaGo(rotorChoices, rotorStartVals, inputMessage, if (activity == "encrypted") true else false)
            spamLine
            println("Your message has been " + activity + ": ")
        println(convertMessageToString(resultingMessage))
            spamLine
            exit(0)
    }

    def getRotorChoices(s1:String, p: String => Boolean):List[Int] = {
        val slot0 = getUserInput(s1 + "fast slot: ", "Entry Invalid.", p).mkString
        val slot1 = getUserInput(s1 + "medium slot: ", "Entry Invalid.", p).mkString
        val slot2 = getUserInput(s1 + "slow slot: ", "Entry Invalid.", p).mkString
        List(slot0.toInt,slot1.toInt,slot2.toInt)
    }
    
    def spamLine = println("##############################################")
    
    def askInput(statement: String) = { 
      val input = readLine(statement)
      if (input == "") "99" else input
    }
    
    def askAgain(statement: String, f: => String) = {
        println(statement)
        f
    } 
    
    def inputVals(f1: => String, f2: => String) = Stream.cons( f1, Stream.continually(f2))
    
    def getUserInput(s1: String, s2: String, p:String => Boolean) = inputVals(askInput(s1), askAgain(s2, askInput(s1))).find(p)
////////////////////   \\\\\\\\\\\\\\\\\\\\\\\\\
    
//////////////// MAIN \\\\\\\\\\\\\\\\\\\\\ 
        def main(args: Array[String]) {
            println("### WELCOME TO THE ENIGMA MACHINE! ###" )
            // GET INITIAL MACHINE SETTINGS FROM USER 
            // ROTOR PLACEMENT CONFIG
            val rotorChoices = getRotorChoices("Choose rotor (0 - 4) for ", x => (x.toInt >= 0 && x.toInt < 5)) 
            // ROTOR START VALS 
            val rotorStartVals =  getRotorChoices("Choose rotor START VAL (0 - 25) for ", x => (x.toInt >= 0 && x.toInt < 25))
            // PLUG MAP
            println("There is only 1 plug map option at present:") 
            println(plugMap1.toString.drop(4))
            //ENCRYPT OF DECRYPT - ONLY RELEVENT FOR GUI TEXT.. bleh not quite need to reverse circuit manually
            val userChoice = getUserInput("Press 1 to encrypt, 2 to decrypt: ", "Entry Invalid.", x => (x == "2" || x == "1"))
            userChoice.mkString match {
              case "1" => useMachine(rotorChoices, rotorStartVals, "encrypted") 
              case "2" => useMachine(rotorChoices, rotorStartVals, "decrypted")
              case default => exit(0)
            }
    }
////////////////////   \\\\\\\\\\\\\\\\\\\\\\\\\

//////////////// CONSTANTS \\\\\\\\\\\\\\\\\\\\\
    val rotorList = List(List(6, 17, 4, 3, 23, 22, 21, 5, 0, 19, 20, 11, 16, 9, 13, 24, 18, 1, 8, 2, 7, 10, 12, 14, 25, 15)
    ,List(2, 7, 23, 12, 13, 15, 18, 1, 8, 11, 0, 3, 10, 5, 24, 4, 17, 19, 6, 9, 20, 14, 25, 21, 16, 22)
    ,List(23, 1, 19, 18, 0, 10, 3, 8, 9, 21, 2, 12, 13, 14, 24, 6, 20, 16, 11, 17, 15, 7, 4, 25, 22, 5)
    ,List(21, 22, 16, 2, 18, 20, 15, 9, 5, 1, 17, 10, 3, 6, 0, 13, 11, 23, 4, 12, 19, 8, 7, 25, 24, 14)
    ,List(25, 3, 11, 7, 5, 15, 24, 10, 21, 6, 12, 17, 8, 23, 2, 18, 19, 14, 4, 0, 20, 9, 22, 1, 16, 13))
    
    val plugMap1 = List((3,7),(11,16),(18,24),(17,9),(21,19),(14,13),(0,12),(1,25),(22,20),(4,6))
////////////////////   \\\\\\\\\\\\\\\\\\\\\\\\\
}
Categories
Functional Programming - Scala

Functional Programming in Scala – Week 7

The final week of the course brought together all of the previous concepts and capabilities to leverage lazy evaluation.

Structural Inductions on trees can be conducted in a number of ways. Obviously they are all bound by logic and I was somewhat confused by the level of detail that this topic was covered on. Perhaps because this concept is not readily available in imperative languages.

Streams was the next topic and one that was used extensively in the week 7 assignment.

((1000 to 10000) filter isPrime)(1)

Above is very inefficient as it finds all prime numbers between 1000 and 10,000, whilst only using element 0 and 1 from the results.

A good solution is to avoid evaluating all of the numbers in the list from 1000 to 10,000 is the .toStream function.

((1000 to 10000).toSteam filter isPrime)(1)
Example of a stream implementation in Scala
Example of a stream implementation in Scala

Lazy evaluation was demonstrated next, its importance paralleled to that of streams

Week 7 lectures

Week 7 assignment source – first pass, lots of problems

Categories
Functional Programming - Scala

Functional Programming in Scala – Week 6

Week 6 was the second last week in the course and focused on Collections. For collections that are not generally going to have linear type access, Vectors are a more apt collection.

Determining the right collection type to use is not so difficult when they are arranged logically.
Determining the right collection type to use is not so difficult when they are arranged logically.

Using the Sequence classes allows the inheritance on useful operations:

scala_sequence_operations
Sequence sub classes inherit some useful operations

Week 6 Lectures

Week 6 assignment source (again this was a quick and dirty job and is far from complete marks)

 

Categories
Functional Programming - Scala

Functional Programming in Scala – Week 5

Week 5 – Lists, investigate a ‘fundamental’ data structure in functional programming. The recursive nature of lists in Scala makes them quite different from arrays. This tied in with the power of pattern matching and the recursive nature of function programming gives credibility to the ‘fundamental’ label.

Pattern matching on lists is a powerful tool
Pattern matching on lists is a powerful tool

Sorting of lists was covered in good detail and in addition to list1.head and list1.tail more functions were revealed:

scala_list_functions
Some key functions for lists

Week 5 Lectures

Week 4 and Week 6 assignments were considered higher work load than others thus there was no assignment for week 5

Categories
Functional Programming - Scala

Functional Programming in Scala – Week 4

Week 4 continued to delve into polymorphism with a focus on Types and Pattern Matching. Generalizing functions to accept multiple parameter types is a clear highlight of Scala.

scala_polymorphism
generic functions in scala

Pattern matching was a topic of week 4 that was used in every subsequent week. Case statement with pattern matching appears to be another staple of Scala.

Number(1) match {
  case Number(n) => n
  case Sum(e1, e2) => eval(e1) + eval(e2)
} + eval(Number(2))

Week 4 lectures

Week 4’s assignment of implementing the Huffman coding compression algorithm was a good practical example of Scala’s power. Note my source has a number of errors in it.

Week 4 Assignment source

Categories
Functional Programming - Scala

Functional Programming in Scala – Week 3

Week 3 looked at the object oriented aspects of Scala. The evaluation of encapsulated data was the most interesting part of week 3,

The lectures went into details about some more of the ‘syntactic sugar’ of Scala.

Abstraction of classes in Scala was explained clearly in the lectures too.

The assignment for week 3 demonstrated Scala’s ability to implement sort, filtering, and union operations in just a few lines.

Polymorphism in Scala was also described. The use of types and traits was shown to enabled different ‘flavors’ of functions.

Week 3 lectures

Week 3 assignment source

scala_class_heirarchy
Class heirarchy in Scala
Categories
Functional Programming - Scala

Functional Programming in Scala – Week 2

Week 2 delved more into tail recursion but more broadly review higher order functions. Looking at perhaps the key characteristic of functional programming languages we found that functions are treated as first class values. Meaning like any other values, functions can be passed as a parameter and returned as a results. This becomes important later in the course and in real world applications where the resolution of values can be deferred until the optimal time.

Another key point of functional programming was introduced, immutable values.  How immutable values related to distributed and parallel programming was touched on briefly. Odersky elaborates on this in the following presentation:

 

The concept of currying was also explained. In essence the passing of functions to functions in the interest of simplifying and generalizing code. These concepts and some of the different function types are details that have not stuck with me very well since the course. I guess that happens when you don’t write a lot of code in a language then leave if for e few months.

Week 2’s assignment was relatively straight forward and followed the contents of the weeks lectures.

Week 2 Assignment code

Week 2 Lectures 

 

Categories
Functional Programming - Scala

Functional Programming in Scala – Week 1

Started and completed this course in the second half of 2012. Thought revisiting the material and uploading the weekly assignments would be a good idea. Week 1 looked at basic functions and evaluations. The recursive nature of functional programming was alluded to, particularly in the assignment.

The basics of (x <- 0 to y) and other scala language specifics such as scoping and structure can all be reviewed in the weeks source code.

I signed up for this course after watching a presentation by Rich Hickey, the creator of Clojure (another functional language for the JVM).

http://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hickey

weeks howework

Week 1 lecture videos: https://class.coursera.org/progfun-2012-001/lecture/8

Once of the most important concepts I took from week 1 was that of tail recursion:

  /**
   * Exercise 1
   */
  def pascal(c: Int, r: Int): Int = {
		//recursive function	
		def tFactorial(number: Int) : Int = {
		//Calculate factorial with tail recursion
  		def tfactorialWithAccumulator(accumulator: Int, number: Int) : Int = {
      	if (number == 1) accumulator
      	else tfactorialWithAccumulator(accumulator * number, number - 1)
			}
		    //start from the start!
        tfactorialWithAccumulator(1, number)
		}

	// element value is calulated using r!/(c!(r-c)!)
	if (c == 0 || c == r || r == 0 || r == 1) 1
	else		
		tFactorial(r) / (tFactorial(c) * tFactorial(r-c))
	}