Saturday, May 31, 2014

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:

Dijkstras Algorithm for shortest path:

Or, here's a more complete implementation.

Thursday, May 29, 2014

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.

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

Monday, May 5, 2014

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).

Monday, April 28, 2014

Fabric is cool.

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

Tuesday, January 21, 2014

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
  3. if (inputs[i].keyCode == MOUSE_LEFT) {;
  4. Comment out the Mouse.Press line, and replace it with a Keyboard.print
  5. if (inputs[i].keyCode == MOUSE_LEFT) {
      Keyboard.print("Hello World.");
  6. 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

  //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 routines. Keyboard.write(KEY_RETURN);

Monday, January 20, 2014

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:


Then Unzip the driver to the IDE's hardware directory:
unzip -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:
Move it your home/sketchbook's
mv hardware/Makey ~/sketchbook/hardware/


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).