Python Vigenère cipher …

I think a lisp would have fewer brackets…

>>> from itertools import cycle
>>> def encode(k,s): return (k+s) % 127
...
>>> def decode(k,s): return (s-k) % 127
...
>>> def cipher(f,k,s):
... return ''.join(map(chr,map(f,cycle(map(ord,k)),map(ord,s))))
...
>>> cipher(encode,"password","Hello, World!")
'9G``g\x1c\x13<`T`X\x19'

>>> cipher(decode,"password",_)
'Hello, World!'
>>>

a simpler / generic cipher

A simplification of the Vigenère cipher produces a generic cipher that can also produce Vernam (one time pad) encodings (although the key should be random, as long as the message and only used once…)


module Ciphers where
import Data.Char (ord,chr)
import Data.Bits (xor)

vigenereEncode :: Int -> Int -> Int
vigenereEncode kn sn = (kn + sn) `mod` 127

vigenereDecode :: Int -> Int -> Int
vigenereDecode kn sn = (sn - kn) `mod` 127

oneTimePad :: Int -> Int -> Int
oneTimePad = xor

cipher :: (Int -> Int -> Int) -> String -> String -> String
cipher f k s map chr $ zipWith f ks ms
   where ks = concat . repeat . map ord $ k
         ms = map ord s

Vigenère cipher

As I am learning Haskell I thought I would have a bash at producing a version of the Vigenère cipher.

-- encodes using ASCII table, 0 -> 127

module Vigenere where

import Data.Char (ord,chr)

lengthInt :: [a] -> Int
lengthInt = fromIntegral . length

-- the two main functions

vigenereEncode :: [Char] -> [Char] -> [Char]
vigenereEncode key str = cipher encode 127 key str

vigenereDecode :: [Char] -> [Char] -> [Char]
vigenereDecode key str = cipher decode 127 key str

-- the actual difference between encoding and decoding is (tiny)

encode :: Int -> Int -> Int -> Int
encode limit kn sn = (kn + sn) `mod` limit

decode :: Int -> Int -> Int -> Int
decode limit kn sn = (sn - kn) `mod` limit

-- the encode / decode function are passed to the cipher

cipher :: (t -> Int -> Int -> Int) -> t -> [Char] -> [Char] -> [Char]
cipher f limit key str =
    map chr $ zipWith (f limit) numKey numStr
       where numKey = take (lengthInt str) $ concat (repeat $ map ord key)
             numStr = map ord str

and in action… (`it` is used to call the return of the last function)


*Vigenere> vigenereEncode "#YOLO" "Now... This is EXCITING!!!"
"qIGz}Qy$59\ETBy9@oh2\DC3\SYN$l(\ETBmpD"
*Vigenere> vigenereDecode "#YOLO" it
"Now... This is EXCITING!!!"

Quickly summing a sequence.

Whenever I needed to sum a sequence of numbers, I would often often resort to the in-built sum function that can be used on lists and ranges, (Python, Haskell, Clojure, Erlang…), but what about if you needed to sum a large range? like

from 192 to 987654321, or perhaps from 7 to 777777777 incrementing by 5 ?

Is it really a good idea to type something like this?

sum(range(7, 777777778,5))
# as pythons range is silly

My laptop is old and the above example takes about 4 seconds!

Have you ever heard of Gauss and his quick sequence summation? My girlfriend told me about it a week ago… It’s fantastic! This is my take on it… written in Python for universal understanding.


>>> def step_sum(mn,mx,step):
...     amax = mx - (mx - mn) % step
...     return (mn + amax) * ((1 + ((amax - mn) / step)) / 2)
... 
# amax -> largest number =< mx that is divisible by step.

>>> step_sum(1,10,1) == sum([1,2,3,4,5,6,7,8,9,10])
True
>>> step_sum(7,7777,5) == sum(range(7,7778,5))
True
>>> step_sum(18726,91382764879138647518725487321538289307,36257)
1.151613442501577e+71
>>> # im not going to even try to do that using sum and range!

Clojure: part 2

taking our recursive look up a bit further:

Passing a conditional argument to our function

(defn recursive-lookup
  [key-lst func conditional]
  (let [next-key (func (first key-lst))]
    (if (conditional next-key)
      (reverse key-lst)
      (recur (cons next-key key-lst) func conditional))))

We can write a small wrapper function like so:

(defn lookup [key the-hashmap conditional-argument]
  (recursive-lookup [key] #(the-hashmap %) conditional-argument))

Lets try it out with some new data

(def who-likes-who {"Mary" "Dave", 
                    "Dave" "Anne", 
                    "Anne" "Tim", 
                    "Tim" "Milly", 
                    "Milly", "Anette"})

We can use either partial application or a lambda function. Here we will search recursively until the hash map returns the value nil.

(lookup "Mary" who-likes-who (partial = nil))
=> ("Mary" "Dave" "Anne" "Tim" "Milly" "Anette")

(lookup "Mary" who-likes-who #(= % nil))
=> ("Mary" "Dave" "Anne" "Tim" "Milly" "Anette")

Now lets try to search from “Dave” until we get to “Milly”

(lookup "Dave" who-likes-who (partial = "Milly"))
=> ("Dave" "Anne" "Tim")

(lookup "Dave" who-likes-who #(= % "Milly"))
=> ("Dave" "Anne" "Tim")

O.K so we include “Dave” the value that we passed into the function, but we do not include “Milly”
If we wanted to include out final value we could change line five of the recursive-lookup function from:

(reverse key-lst)

to

(reverse (cons (next-key key-lst)))

Now, what about a slightly more complicated conditional. What if we wanted to recursively search until we find a name that is less than four characters?

(lookup "Milly" who-likes-who #(< (count %) 4))
=> ("Mary" "Dave" "Anne")

lets try some more

(lookup "Mary" who-likes-who #(> (count %) 4))
=> ("Mary" "Dave" "Anne" "Tim")

But if we try the following we have some problems!!!

(lookup "Mary" who-likes-who #(> (count %) 7))
=> OutOfMemoryError Java heap space  [trace missing]

Why is this? Perhaps this explains.

(count nil)
=> 0

our search function will take the value of a key value pair and count it’s length. As nil returns 0 no exception is thrown. This means that we treat `nil` as a new-key, add it to our list and try and find a value for it – which returns `nil` with a count of 0, so we treat it as a new-key, add it to out list … an infinite loop (well until we run out of heap space)!

With this in mind, we should probably change our recursive-lookup function to accomodate for this.

(defn recursive-lookup
  [key-lst search-func conditional]
  (let [next-key (search-func (first key-lst))]
    (if (or (nil? next-key)
            (conditional next-key))
      (reverse key-lst)
      (recur (cons next-key key-lst) search-func conditional))))

All we have done is stated that if the lookup value is nil or meets the conditional, return the list.

(lookup "Mary" who-likes-who #(> (count %) 7))
=> ("Mary" "Dave" "Anne" "Tim" "Milly" "Anette")

Clojure

a basic clojure function

(defn square-me [x]
  (* x x))

and a recursive key,value lookup, works as well for redis.


(ns redistestis.core
  (:require [taoensso.carmine :as car]))

(def pool
  (car/make-conn-pool))

(def spec-server1
  (car/make-conn-spec))

(defmacro wcar [& body]
  `(car/with-conn pool spec-server1 ~@body))

(defn redis-get-value
  "key -> value | nil"
  [key]
  (wcar(car/get key)))


;; below we use keys as an example of a clojure hashmap

(def keys {"foo" "bar"
           "bar" "baz"
           "baz" "faz"
           "faz" "gaz"
           "bob" "dog"})

;; this function is general purpose

(defn recursive-function-lookup
  "[key] -> function -> [return values]"
  [key-lst func]
  (let [next-key (func (first key-lst))]
    (if (nil? next-key)
      (reverse key-lst)
      (recur (cons next-key key-lst) func))))

;; a wrapper for hashmaps

(defn recursive-hashmap-lookup
  "as hashmaps are also functions this works"
  [key? hashmap]
  (recursive-function-lookup [key?] #(hashmap %)))

;; a wrapper for redis

(defn redis-recursive-lookup
  [key? redis-get-value]
  (recursive-function-lookup [key?] #(redis-get-value %)))

;; example of hashmap lookup

> (recursive-hashmap-lookup "foo" keys)
("foo" "bar" "baz" "faz" "gaz")

;; the same would work for Redis

a basic perceptron class


# basic perceptron class 

import operator

training_set = [((1, 0, 0), 1), ((1, 0, 1), 1), ((1, 1, 0), 1), ((1, 1, 1), 0)]

class Node(object):

    def __init__(self, threshold=0.5, limit=0.1, weights =[0,0,0]):
        self.threshold = threshold
        self.limit = limit
        self.weights = weights

    def train(self, training_set):
        while True:
            errors = False
            for inputs, desired in training_set:
                R = 1 if sum(map(operator.mul, inputs, self.weights)) > self.threshold else 0
                if (desired - R) != 0:
                    errors = True
                    self.weights = list(map(lambda w, i: w + self.limit * (desired - R) * i, self.weights, inputs))
            if errors == False:
                break

    def result(self, inputs):
        return 1 if sum(map(operator.mul, inputs, self.weights)) > self.threshold else 0



>>> node = perceptron.Node()
>>> node.train(perceptron.training_set)
>>> node.result( (1,0,0) )
1
>>> node.result( (1,0,1) )
1
>>> node.result( (1,1,0) )
1
>>> node.result( (1,1,1) )
0


Python and Arduino (part 1)

It’s been a while since I last played with an arduino . I think it was while making some demos for bike lazer tag (more of that to come)… There seem to be a few examples online of how to get your arduino playing with python, but most of then seem to focus on getting servos to move around – which is cool, but surely the fun to be had with an arduino is getting it to talk ‘to’ your computer.

So… with this in mind, and my little box of components that I brought with me from London, we will see what we can get going. I’m not going to put everything up here, but if you are interested in anything just drop me an email ben(at)beoliver(dot com).

Firstly, I would recommend downloading pyserial. It works with both 2.X and 3.X python. ( i will be using 2.X for the moment ).

Secondly, you are obviously going to need an arduino for this !

LETS BEGIN…

1. upload an Arduino sketch with the following :


void setup() {
Serial.begin(9600);
}

void loop() {
int sensorValue = analogRead(A0);
Serial.println(sensorValue);
}

All we are doing here is telling the Arduino to start a serial connection, and any value that is recorded on Analog pin 0 should be sent via the Serial connection.

2. after installing pyserial we will begin by writing the following:


#!/bin/env python
import serial
import time
# plug in your arduino and look in /dev
name = '/dev/tty.usbserial-A9007W1P'
baud = 9600

arduino = serial.Serial(name, baud)
time.sleep(2)
# pause as the Arduino is restarted by the serial connection
for line in arduino:
  print(line)

And there you go! you are reading the output from your arduino (this is just the same as the serial monitor in the Arduino app).

Now the first thing you might notice is that the output is read as a string. and secondly you sometimes get non numerical characters :

‘1023’
‘100?30′
‘1023’

we will write a tiny function that will test the output and return an int if possible:

def str2int(input):
  try: 
    return int(input)
  except ValueError: 
    pass

# our output can now be:
print(str2int(line))

This now means that our output can be evaluated as an integer.

KIND WORDS & FOG

I got an email the other day from Matt at Beautiful/Decay, he has written a very nice little post about In Search of Our senses. See it – here
In other news there was some crazy fog in Oslo today. I’m sure it wasn’t actually that crazy, but I enjoyed it anyway. there are some photo’s up on flickr – here