Longest Common Substring Algorithms

Given strings "ABAB" and "BABA"...

A dynamic programming style algorithm constructs a matrix of the substring lengths.

    |   |   | A | B | A | B |
    |   | O | O | O | O | O |
    | B | O | O | 1 | O | 1 |
    | A | O | 1 | 0 | 2 | 0 |
    | B | O | 0 | 2 | 0 | 3 |
    | A | O | 1 | 0 | 3 | 0 |

In this matrix, the 5th column tests the substring ABA of the ABAB sequence. So cell [5, 5] compares ABA to BAB ... the lcs is BA, length 2.

The other approach is to construct a generalized suffix tree for the strings, then find the deepest internal nodes which have leaf nodes from all the strings in the subtree below it.

A Simple Suffix Tree Implementation:

	"""http://goo-apple.appspot.com/article/2e8d3c6a-2c38-48b9-96c6-240b4ded253a"""
	class Node:
	def __init__(self, start, substr):
	self.start = start
	self.substr = substr
	self.branches = {}
	def insert_into_tree(subroot, suffix, start):
	prefix_len = len(subroot.substr)
	new_suffix = str(suffix[prefix_len:])
	if(len(subroot.branches) == 0):
	left_child = Node(subroot.start, "")
	right_child = Node(start, new_suffix)
	subroot.branches[""] = left_child
	subroot.branches[new_suffix] = right_child
	else:
	for (substr, node) in subroot.branches.items():
	if len(substr) > 0 and new_suffix.startswith(substr):
	insert_into_tree(node, new_suffix, start)
	break
	else:
	new_child = Node(start, new_suffix)
	subroot.branches[new_suffix] = new_child
	def build_suffix_tree(t_str):
	len_str = len(t_str)
	i = len_str - 1
	root = Node(len_str, "")
	while i >= 0:
	insert_into_tree(root, str(t_str[i:]), i)
	i -= 1
	return root
	def display_all_suffix(subroot, suffix_s_prefix, level = 0):
	if len(subroot.branches) == 0:
	print suffix_s_prefix, level
	return
	for (substr, node) in subroot.branches.items():
	display_all_suffix(node, suffix_s_prefix + substr, level + 1)
	root = build_suffix_tree("BCABC")
	display_all_suffix(root, "")

view raw suffix_tree.py hosted with ❤ by GitHub

Dijkstras Algorithm for shortest path:

	"""
	Dijkstra's algorithm for shortest paths.
	http://code.activestate.com/recipes/577343-dijkstras-algorithm-for-shortest-paths/)
	- dijkstra(G, s) finds all shortest paths from s to each other vertex.
	- shortest_path(G, s, t) uses dijkstra to find the shortest path from s to t.
	The input graph G is assumed to have the following representation:
	- A vertex can be any object that can be used as an index into a dictionary.
	- G is a dictionary, indexed by vertices.
	- For any vertex v, G[v] is itself a dictionary, indexed by neighbors of v.
	- For any edge v->w, G[v][w] is the length of the edge.
	"""
	from priodict import priorityDictionary
	def dijkstra(graph, start, end=None):
	final_distances = {}
	predecessors = {}
	estimated_distances = priorityDictionary()
	estimated_distances[start] = 0
	for vertex in estimated_distances:
	final_distances[vertex] = estimated_distances[vertex]
	if vertex == end:
	break
	for edge in graph[vertex]:
	path_distance = final_distances[vertex] + graph[vertex][edge]
	if edge in final_distances:
	if path_distance < final_distances[edge]:
	raise ValueError("Better path to already-final vertex")
	elif edge not in estimated_distances or path_distance < estimated_distances[edge]:
	estimated_distances[edge] = path_distance
	predecessors[edge] = vertex
	return final_distances, predecessors
	def shortest_path(graph, start, end):
	"""
	Find a single shortest path from the given start vertex to the given end,
	output as list of vertices in order along the shortest path.
	"""
	final_distances, predecessors = dijkstra(graph, start, end)
	path = []
	while 1:
	path.append(end)
	if end == start:
	break
	end = predecessors[end]
	path.reverse()
	return path
	if __name__ == "____main__":
	pass
	# G = {'s':{'u':10, 'x':5}, 'u':{'v':1, 'x':2}, 'v':{'y':4},
	# 'x':{'u':3, 'v':9, 'y':2}, 'y':{'s':7, 'v':6}}
	# The shortest path from s to v is ['s', 'x', 'u', 'v'] and has length 9.

view raw dijkstra.py hosted with ❤ by GitHub

Or, here's a more complete implementation.

Function Caching via Memoization

To explain memoization, see these different versions of Fibonacci:

Purely recursive. Highly inefficient. Recalculates every value for every calculation.

Iterative. Much faster.

Here is the memoization technique. A 'cache' dictionary of { (args) : (return_val), } is created. This allows us to quickly locate and reuse any value that has already been calculated.

	fib_vals = {1:1, 2:1}
	def fib(n):
	if n <= 2:
	return 1
	if n in fib_vals:
	return fib_vals[n]
	else:
	fib_vals[n] = fib(n - 1) + fib(n - 2)
	return fib_vals[n]

view raw fibo_memo_basic.py hosted with ❤ by GitHub

Here is the same memoization design, implemented as a decorator.

	def memoize(func):
	"""Decorator for memoization via 'cache' dictionary."""
	cache = {}
	def memoed_func(*args):
	if args not in cache:
	cache[args] = func(*args)
	return cache[args]
	memoed_func.cache = cache
	return memoed_func
	@memoize
	def fib(n):
	"""Demos use of memoization decorator. """
	if n <= 2:
	return 1
	else:
	return fib(n-1) + fib(n-2)

view raw memo_decorator.py hosted with ❤ by GitHub

Update Evernote in Wine on Ubuntu

Wine on Ubuntu has problems running the Evernote updates. You get something like: "Evernote was already installed by another user...." The 'find/remove regedit keys' method, described here, and here, did not work for me. I didn't find the reversed the digits in regedit. Well, I only use wine for Evernote. So I used this subtle technique to remove all wine installation. (Don't do this if you have other Wine apps you are keeping.)

sudo apt-get purge wine
rm -rf ~/.wine
sudo apt-get install wine

Then ran the Evernote installer as usual (from files, rt-click on installer).

Fabric is cool.

[Fabric](http://www.fabfile.org/) is cool. More python, less Bash. For example, I can automate my django db rebuild process, like so:

	from __future__ import with_statement
	import os
	from fabric.api import local, settings, abort, sudo, env
	from fabric.contrib.console import confirm
	env.hosts = [
	# 'me@my-imac',
	'me@my-desk',
	]
	def db_exists(db='testdb'):
	if (sudo("psql -l | grep {} | wc -l".format(db), user='postgres')) != '0':
	return True
	else:
	return False
	def db_rebuild(db='testdb'):
	"""Drop, create, and sync the db."""
	## Warning.
	if not confirm("Running on {} with database {}. Proceed?".format(env.host, db)):
	print("Ok, no changes.")
	return
	## Drop the database.
	if db_exists(db):
	sudo("dropdb {}".format(db), user='postgres')
	## Create the database.
	sudo("createdb -E UTF8 -e {}".format(db), user='postgres')
	## Run django's syncdb.
	local('python ./manage.py syncdb')

view raw fabfile_db.py hosted with ❤ by GitHub

Programming Makey Makey clicks to send strings

Sending a string

One way to send a string instead of a keystroke is to modify the Mouse Button Events in the makey.ino file. To make a left mouse click send 'Hello World':

1. In the Arduino IDE, open the makey-makey.ino file.
2. In the main code file, *not* the settings.h, find the lines

if (inputs[i].keyCode == MOUSE_LEFT) {
  Mouse.press(MOUSE_LEFT);
}

3. Comment out the Mouse.Press line, and replace it with a Keyboard.print

if (inputs[i].keyCode == MOUSE_LEFT) {
  //Mouse.press(MOUSE_LEFT);
  Keyboard.print("Hello World.");
} 

4. Upload the sketch. Pin A1 is the Makey left-mouse click. Touch the Ground and Pin A1 to try it.

Sending a carriage return with button click

Modify the settings.h file this time, since only one key is being modified. For example, pin A0 defaults to a right-mouse-click...change it to send KEY_RETURN.

int keyCodes[NUM_INPUTS] = {
  // top side of the makey makey board
  KEY_UP_ARROW,      // up arrow pad
  KEY_DOWN_ARROW,    // down arrow pad
  KEY_LEFT_ARROW,    // left arrow pad
  KEY_RIGHT_ARROW,   // right arrow pad
  ' ',               // space button pad
  MOUSE_LEFT,        // click button pad
  // female header on the back left side
  'w',                // pin D5
  'a',                // pin D4
  's',                // pin D3
  'd',                // pin D2
  'f',                // pin D1
  'g',                // pin D0
  // female header on the back right side
  MOUSE_MOVE_UP,      // pin A5
  MOUSE_MOVE_DOWN,    // pin A4
  MOUSE_MOVE_LEFT,    // pin A3
  MOUSE_MOVE_RIGHT,   // pin A2
  MOUSE_LEFT,         // pin A1

  // COMMENT MOUSE_RIGHT TO REPLACE IT WITH KEY_RETURN
  //MOUSE_RIGHT      // pin A0
  KEY_RETURN         // pin A0
};

Sending a carriage in sketch code

Instead or modifying the inits, you can write it in one of the Mouse.press routines. Keyboard.write(KEY_RETURN);

Using a Makey-Makey with Ubuntu

I've spent a lot of time working with software, but had never been exposed to the basic principles of electronics. The Makey-Makey is a great introduction to the world of circuitry. Its 'cool trick' is hacking just about anything into a keyboard. There's a lot of video of folks wiring all kinds of household items into input devices.

But underlying all the fun stuff is real first look at how electronic hardware works. The Sparkfun electronic hobbyist's site has an excellent collection of tutorials presenting the fundamental science and application of electronic circuitry.

Arduino is a very popular open-source electronics prototyping platform...your local RadioShack should offer a variety of Arduino-ready components. The Makey Makey is programmed using the Arduino IDE (Integrated Development Environment). Here's how to install the Arduino IDE in Ubuntu. (I used Arduino IDE version 1.0.5, and Ubuntu version 13.10.)

First, install the Arduino IDE. The one in the Ubuntu repository worked fine for me.

sudo apt-get install arduino

This will install the IDE software to: /usr/share/arduino/

To use the Arduino IDE with Makey-Makey, you'll need to install a driver. Download the zipped driver with:

 wget https://dlnmh9ip6v2uc.cloudfront.net/tutorialimages/MaKey_MaKey_QuickStart/MaKeyMaKey-13-8-12.zip

Then Unzip the driver to the IDE's hardware directory:

unzip MaKeyMaKey-13-8-12.zip -d /usr/share/arduino/hardware

If that worked properly, you should see the Makey-Makey listed in the Board menu.

To modify basic functionality of the Makey, you'll need to grab the source code.
Get and extract the source:

wget https://dlnmh9ip6v2uc.cloudfront.net/tutorialimages/MaKey_MaKey_QuickStart/MaKeyMaKey-13-8-12.zip  

Move it your home/sketchbook's

mv hardware/Makey ~/sketchbook/hardware/

Permissions

To ensure your IDE can communicate with the Makey, add your user to the following three groups, like so:

sudo usermod -a -G dialout $USER
sudo usermod -a -G tty $USER
sudo usermod -a -G uucp $USER

Resolve Ubuntu ModemManager conflicts

For the IDE to be able to update the Makey settings, you'll need edit ModemManager blacklist settings. (This fix is taken from discussions here and here.) Using your favorite text editor, you'll need to create/edit a file at:

sudo vi /etc/udev/rules.d/77-mm-arduino-blacklist.rules

In your editor, append the following line to that file:

ATTRS{idVendor}=="1b4f", ATTRS{idProduct}=="2b74", ENV{ID_MM_DEVICE_IGNORE}="1"

Save the file.

Unplug your Makey. Close the IDE, Logout/Login. Plug Makey back in. From there, you'll be ready to reprogram your Makey, following along with the MaKey MaKey Quickstart Guide (Part 2).