defcraft

Two useful scripts

2010-12-05T11:23:00.004-07:00

Here are two Ruby scripts that I find useful. Both of them have been tested under Ruby 1.9.2p0. The first is mv_ldown: it moves the most recently downloaded file (from ~/Downloads) into the current directory.

#! /usr/bin/env ruby
src = Dir[File.expand_path('~/Downloads/*')].
  sort_by { |x| File.mtime(x) }.
  last
abort("nothing in ~/Downloads dir") unless src
dest = File.join(File.absolute_path('.'), File.basename(src))
abort("#{dest} already exists") if File.exists?(dest)
File.rename(src, dest)
puts "#{File.basename src} to ."

The second is sl: it just like the command "ln -s SRC DEST", but you don't have to remember the order of the parameters. The file that exists is the source and the other, the destination.

#! /usr/bin/env ruby
require 'fileutils'
abort("Usage: sl SRC DEST") unless ARGV.length == 2
a, b = ARGV
if File.exists?(a) && File.exists?(b)
  abort("Both #{a} & #{b} exists")
elsif File.exists?(a)
  src, dest = a, b
elsif File.exists?(b)
  src, dest = b, a
else
  abort("Neither #{a} nor #{b} exists")
end
src = File.absolute_path src
abort("#{src} not a file") unless File.file?(src)
dest = File.absolute_path dest
system("ln -s #{src} #{dest}")

Extracting phone numbers from Outlook Msg Files

2010-03-03T19:51:00.006-07:00

Recently, I had to extract phone numbers from a bunch of Outlook .MSG files (see here and here).

Looking for an open source solution, I came across MsgParser. It almost did what I needed. (I just had to modify a "protected" field and make it "public" -- I needed to access it from a driver program; there might be a easier way to do this -- maybe make the driver program "run" from the same package as MsgParser and it'll have access to the protected field...) But downloading its dependencies was a bit of a pain.

So here is a Ruby script that does all that for you. You specify a directory where the Outlook .MSG files are. It'll extract all the phone numbers from them and print it. Tested under OS X Leopard; needs curl & java to be installed. Run: ruby msg_extractor.rb MSGS_DIR.

# Released under the GNU GPL.
# http://www.gnu.org/copyleft/gpl.html

require 'fileutils'

DOWNLOADS = %w{
  http://auxilii.com/msgparser/download/msgparser-1.6.zip
  http://www.freeutils.net/source/jtnef/jtnef-1_6_0.zip
  http://apache.ziply.com/poi/release/bin/poi-bin-3.6-20091214.tar.gz
  http://www.trieuvan.com/apache/ant/binaries/apache-ant-1.8.0-bin.zip }

JCLASS = 'MyMsgParser'
JAVA_INPUT = 'My.msg'
JAVA = <<END
  import java.util.*;
  import com.auxilii.msgparser.*;
  import com.auxilii.msgparser.attachment.*;
  public class #{JCLASS} {
    public static void main(String[] args) throws Exception{
      MsgParser msgp = new MsgParser();
      Message msg = msgp.parseMsg("#{JAVA_INPUT}");
      // UNUSED
      String fromEmail = msg.getFromEmail();
      String fromName = msg.getFromName();
      String subject = msg.getSubject();
      String body = msg.getBodyText();
      String longString = msg.toLongString();
      // We modify source of msgparser to make
      // properties public
      Iterator it = msg.properties.keySet().iterator();
      while (it.hasNext()) {
       String key = (String) it.next();
       Object val = msg.properties.get(key);
        System.out.println(key + ": " + val);
      }
    }
  }
END

class MsgExtractor
  def initialize(msgs_dir)
    @msgs_dir = msgs_dir
    @cp = '.:msgparser-1.6/dist/msgparser-1.6.jar:' + 
          'poi-3.6/poi-3.6-20091214.jar:lib/tnef.jar'
    download
    javac
  end
  
  def download
    DOWNLOADS.each do |u|
      b = File.basename(u)
      if !File.exists?(b)
        puts "downloading #{u}"
        `curl --silent -O #{u}` unless File.exists?(b)
      end
      next if File.exists?("#{b}.zipped")
      puts "unpacking #{b}"
      case b
      when /zip$/; `unzip -o #{b}`
      when /gz$/;  `gzip -dc #{b} | tar -xpvf -`
      end
      FileUtils.touch("#{b}.zipped")
    end
  end
  
  def javac
    modify_msgparser
    @cp.split(':').each do |f|
      abort("#{f} doesn't exist") unless File.exists?(f) 
    end
    open("#{JCLASS}.java", "w") { |f| f.write(JAVA) }
    `javac -classpath #{@cp} #{JCLASS}.java`
  end
  
  def modify_msgparser
    jp = 'msgparser-1.6/src/main/java/com/auxilii/msgparser/Message.java'
    old1 = 'protected Map<String,Object> properties ' + 
           '= new HashMap<String,Object>();'
    new1 = old1.dup
    new1['protected'] = 'public'
    modified = File.read(jp)
    return if modified[new1]
    modified[old1] = new1
    puts "modifying #{jp}..."
    open(jp, 'w') { |f| f.write(modified) }
    FileUtils.cd('msgparser-1.6') do
      puts "rebuilding msgparser"
      `../apache-ant-1.8.0/bin/ant jar`
      FileUtils.mv 'dist/msgparser.jar', 'dist/msgparser-1.6.jar'
    end
  end
  
  def run(&extract_by)
    result = []
    Dir[File.join(@msgs_dir, '*.msg')].each do |f|
      b = File.basename(f)[0..-5]
      puts "extracting #{b}"
      FileUtils.cp(f, JAVA_INPUT)
      out = `java -classpath #{@cp} #{JCLASS}`
      data = extract_by.call(out)
      next if data.nil?
      break if $INTERRUPTED
      result << [b, data]
    end
    result.sort
  end
end

$INTERRUPTED = false

def main
  unless ARGV[0]
    abort("Usage: ruby msgs_extractor.rb msgs_dir")
  end
  tmp = ARGV[1] || "msgs_extractor"
  Dir.mkdir tmp rescue nil
  msgs_dir = File.expand_path ARGV[0]
  Dir.chdir tmp
  extractor = MsgExtractor.new(msgs_dir)
  trap("INT") { $INTERRUPTED = true; puts; }
  result = extractor.run { |o| o.scan /\d{7,20}/ } # extract phone numbers
  result.each { |n, ph| puts("%20s: %s" % [n, ph.join(", ")]) }
end

if $0 == __FILE__
  main
end

Don't Make Me Think

2009-10-14T21:50:00.005-07:00

I loved Don't Make Me Think. It takes you inside the mind of the user (of your website). And it tells you who they are, what they expect and what confuses them. And the golden rule is, of course, don't make them think.

Some videos

2009-10-11T14:57:00.005-07:00

Lately, I've been watching some cool videos on software development. Here they are, along with my notes on them:

UI Fundamentals for Programmers, by Ryan Singer.

Base UI on a Model
Be explicit and use a lot of language.
Break screens out w/ REST
Least Effective Difference
Screen -- design from the inside out
Flows - think about actions. Split
every action into 3:
 1. start: how to i get to it?
 2. middle: post note.
 3. end: where do it go afterwards?
Fonts:
Small sizes, < 10px, Verdana. But not so good for larger sizes.
Lucida Grande lot

Why marketing is too important to be left to the marketing department, by Seth Godin.

Ideas that spread, win.
Build marketing into the software.
Make it connect.
TV thinking -- average products for average people.
If you're gonna interrupt everyone, you'll have a product everyone will 
will wanna to buy.
You're solving a problem that most people don't think that they have.
Clutter is not your friend.
You deal with clutter by making more clutter.

Do something totally different.
And people will talk about it.
At the edges, people wait in line.

Don't force new medium, but
build stuff that fits the new medium.

You are in the story telling business.

Hard to make money in the middle.

The new way:
(1) be remarkable -- encourages people to talk about it
(2) tell a story about it
(3) THEY spread the word
(4) and THEY come for another story

Build a tribe: help people connect
with each other.
Build a tribe: stand up for something
remarkable.

Manuel Blum's Advice to new Grad Students

2009-09-21T01:18:00.002-07:00

I liked this collection of advice to grad students. Some quotes:

Books are not scrolls. [...] Permit yourself to open a book and start reading from anywhere. In the case of mathematics or physics or anything especially hard, try to find something anything that you can understand.
Consider writing what you read as you read it. This is especially true if you're intent on reading something hard.
I once asked Umesh Vazirani how he was able, as an undergraduate at MIT, to take 6 courses each and every semester. He said that he knew he didn't have the time to work out his answers the hard way. He had to find a shortcut. You see, Umesh understood that problems often have short clever solutions.

Hacker News bookmarklet

2009-09-08T12:25:00.006-07:00

A bookmarklet for Hacker News.
It helps you read comments. It does 4 things:

sort by root comment, newest to oldest (byParent)
sort by latest reply in comment thread, newest to oldest (byReply)
shows you how many people have replied to your comment (example "4 replies")
updates page with new comments and marks them as such (reload)

Here is the bookmarklet: hn.js

Here it is under bitbucket: hnjs

Sorting restructures the DOM. Only the reload function hits the server. Of course any changes to the HTML will break this badly. I've tested this with FF 3.5 & Safari 4 under OS X. And under latest Chrome in WinXP.

37signals on business & software

2009-08-08T17:51:00.004-07:00

Lately I've been enjoying these videos by 37signals: 37signals.speaks. So refreshing to see these guys talk about business and what makes good software.

Numbers everyone should know

2009-07-06T23:09:00.002-07:00

Numbers everyone should know from Jeff Dean's talk at Stanford:

L1 cache reference 0.5 ns
Branch mispredict 5 ns
L2 cache reference 7 ns
Mutex lock/unlock 100 ns
Main memory reference 100 ns
Compress 1K bytes with Zippy 10,000 ns
Send 2K bytes over 1 Gbps network 20,000 ns [.02 ms]
Read 1 MB sequentially from memory 250,000 ns
Round trip within same datacenter 500,000 ns
Disk seek 10,000,000 ns
Read 1 MB sequentially from network 10,000,000 ns [10 ms]
Read 1 MB sequentially from disk 30,000,000 ns
Send packet CA to Netherlands to CA 150,000,000 ns

From Cuong Do's Youtube Scalability talk:

Page rendering time: keep less than 100 ms

There are also some interesting number on Wikipedia's Google platform page.

from Getting Real, the book

2009-05-24T17:15:00.001-07:00

From Getting Real the amazing book by 37signals:

The best designers and the best programmers aren’t the ones with the best skills, or the nimblest ﬁngers, or the ones who can rock and roll with Photoshop or their environment of choice, they are the ones that can determine what just doesn’t matter. That’s where the real gains are made.

Ruby Object Model

2009-05-22T19:47:00.003-07:00

These are my notes from Dave Thomas's Ruby Object Model.

# Ruby Object Model
# http://www.engineyard.com/blog/community/scotland-on-rails/page-2/

# everything is an object
# object is a class
# class is an object

# self:
#  - current object
#  - where instance vars are found
#  - default receiver for methods calls

# changes in self changes ruby's view of the universe
# by: methods calls & class/module definitions

animal = "cat"
puts animal.upcase

# find animal object -> find table of methods -> call method
# class => object that has a table of methods
# every single method call works exactly the same way

puts animal.object_id
# if can't methods in 1st table => goes to parent 
# (superclass of the object)

# Object toplevel in Ruby 1.8, BasicObject in Ruby 1.9
# If no matching methods found in ruby, you are back
# to original object and look for method_missing method.

def animal.speak
  puts "meaow"
end

animal.speak

# --- SELF changes on method call

# Method lookup -> one right and one up
# So the above object instance method sits 
# one to the right of that particular object.
# So a newly created class just for the animal
# object is anonymous. But when asked what class
# the above object belongs to, it says string,
# and not the newly created anonymous class.
# AKA, singleton class or metaclasss or eigenclass
# How is the animal.speak method defined?
# (1) Ruby sets "self" to the cat string object -- self
#     set to the receiver
# (2) Looks for the method in the method table associated
#     with that object (look in self's class for the object)
# (3) If not found, scan for method_missing
# (4) Eventually find some method & invoke it & when done,
#     restores original value of self.
#
# If a method call in Ruby doesn't have an explicit
# receiver -- then Ruby doesn't reset self -- self
# stays the same & no need to pop back at the end.

# So the method "puts" is a private method in Object (actually
# in Kernel), so you can only call it with an implicit receiver,
# not an explicit one.

class String
  puts "in string"
end

begin
  "hi".puts
rescue NoMethodError
  puts "puts is private"
end

# In Ruby class definitions are executable code.
puts "===class defn"
puts "toplevel #{self}"
class << self
  puts "class << self's #{self}"
end
class A
  puts "class A's #{self}"
end
module B
  puts "module B's #{self}"
end

# When you define a class like "class A; end",
# Ruby creates a brand new class and assigns that
# to the constant A.

# When excuting a class or module definition, self
# is set to the class or module object. Why? You can
# do "def self.a" for class methods (or old school
# ruby programmers using "def A.a"); But ruby doesn't
# have class methods (or static methods), all methods
# are the same. These methods are just defined on the class.
# It inserts a singleton class on that particular class object.

# To do metaprogramming in Ruby:
# - Instance variables are looked up in self
# - Methods are looked up in self's class

# these 2 are the same:
def animal.do
  puts "doing"
end
# "class << animal" means open up the singleton class of this object
# self is set to that singleton class
class << animal
  puts "class << animal: #{self}"
  def do
    puts "doing"
  end
end

class N
  # opening up the meta/singleton class and dumping all the
  # methods defined there
  class << self
    # class methods
  end
end

# This doesn't work
class F
  @a = 10 # self is class object
  def f
    @a # self is the instance 
  end
  def F.f # this work
    @a
  end
  
  class << self # this also works
    attr_accessor :f
  end
  
end

class Y; end
class Z < Y; end
# the Y in "Z < Y" is an expression
wxyz = Y
class Z < wxyz; end # same as above

a = Struct.new(:a, :b, :c) # creates a class object on the fly
puts a.new(1,2,3) 
# Struct is just a data holder

class T < Struct.new(:a, :b)
end

# include Module in a class, then invoke the instance methods
# of the module with class as the receiver
# It doesn't add the methods; any instance methods define
# in class overrides the module methods, even if it is included
# after the method definition.

module M
  def speak; puts :no; end
end

class AM
  def speak; puts :ok;  end
  include M
end

am = AM.new.speak

# include => singleton as immediate parent of my class
# and its methods are methods of my module

# hierarchy => singleton, class, module

Notes from Alex Martelli's talk @ Pycon 2009

2009-04-18T15:20:00.003-07:00

My notes from Alex Martelli's talk @ Pycon 2009: video here.

http://pycon.blip.tv/file/1957071/
watched on April 18, 2009
abstraction as leverage
by alex martelli
========================
abstraction is something you can't avoid
abstraction is leverage - by working at the higher level
 you can do a lot with so little (layers & layers)
leverage can crush you if things go wrong
so if you need care to USE abstraction,
 you need double layer of care to PRODUCE abstraction
all abstraction's leak (spolsky's law) -- where you must
 get to some of the level below
often you sometimes want abstractions to leak!
(like distributed filesystems)
abstractions can slow you down -- latest research:
 "to abstract is to procrastinate"; more abstract
 the "todo" is, the more the students will procrastinate
things way in past are more abstracted that more
 recent ones
to achieve, think Concrete: what's the next 1 thing,
 i'm going to do
interaction design: "Joe Blow" vs "the user"
37signals: prefer action over abstraction
all abstraction leak because: "the map is not
 the territory"; before you can abstract,
 you must see the details; before you can withdraw,
 you must stand close; abstract only you know
 all the details (which won't be possible), so
 be flexible and humble!
TCP/IP abstraction leak: designed in an era when
everyone was friendly
Need to understand several layers below and above
(Filesystem: below layers => device drivers,
 above layers => how are other programmers consume
 the apis)
Knuth: programmer is mostly to shift levels of
abstraction from low to high; see things simutaneously
at both low & high level
Jason Fried: copying skips understanding;
understanding is how you grow; you have to understand
why something works or why something is how it is;
when you copy you miss that; (You just copy the high
level abstractions blindly)
Jeff Atwood: don't reinvent the wheel unless you plan
of learning more abt wheels
Bottleneck -- if you remove it you have a glass!
Google App engine -- counting how many reads & writes
Find bottleneck (where everything must go thru) and
monkey patch that; problamatic
App Engine provide hooks to do same thing!
(Q&A: answer: focus on making things easier
 to recover when they break, instead of trying
 to protect everything)

Mercurial & bitbucket

2009-04-10T12:33:00.003-07:00

I'm starting to use Mercurial for version control and I really like it. Also, I got a bitbucket.org account: sri and put up my first project there: ccspendings, a very simple program that tell you where you spend your credit card money (currently supports Juniper credit card). It'll generate some useful charts using the Google Charts API. Here is an example of how much I spend on Gas:

Guido van Rossum Python Quote

2009-04-06T16:47:00.004-07:00

At the very end of Python.Org's Webmaster mailing list's auto-reply text, a quote by Guido van Rossum on how to code in Python:

The joy of coding Python should be in seeing short, concise, readable
classes that express a lot of action in a small amount of clear code --
not in reams of trivial code that bores the reader to death.
--GvR

Greasemonkey Search helper

2009-02-19T23:16:00.003-07:00

Here is a handy Greasemonkey script: it allows you to search for the selected text in a background tab. This is useful because it won't distract from what you reading right now. And you have different keys are associated with different searches....

Alt-A - searches Amazon.com
Alt-G - search Google.com
Alt-W - searches Wikipedia.org
Alt-Y - searches YouTube.com
Alt-N - searches GoogleNews.com
Alt-R - searches RottenTomatoes.com

// ==UserScript==
// @name           Sri's Stuff
// @namespace      http://defcraft.org
// @description    Sri's Stuff
// @include        *
// ==/UserScript==

// Created-On: Jun 28, 2007
// Description:
//
// o Selection Search:
//   Make a selection and hit "G" or "A" to
//   search either Google or Amazon. Search opens
//   in background Tab.


(function () {
    
  function kpHandler(event) {
    var letter = String.fromCharCode(event.charCode);
    var sel = document.getSelection();

    if (!event.altKey || sel.length == 0)
      return;

    switch (letter) {
    case "a": case "Ã¥": // Alt-A
      doAmazonSearch(sel); 
      break;

    case "g": case "Â©": // Alt-G
      doGoogleSearch(sel);
      break;
      
    case "w": case "âˆ‘": // Alt-W
      doWikipediaSearch(sel);
      break;
      
    case "Â¥": // Alt-Y
      doYoutubeSearch(sel);
      break;
      
    case "Ëœ": // Alt-N
      doGoogleNewsSearch(sel);
      break;
      
    case "Â®": // Alt-R
      doRottenTomatoesSearch(sel);
      break;
    }
  }


  // == User actions ============================
  
  function doRottenTomatoesSearch(sel) {
    var url = "http://www.rottentomatoes.com/" + 
              encodeURIComponent(sel);
    GM_openInTab(url);
  }
  
  function doGoogleNewsSearch(sel) {
    var url = "http://news.google.com/news?hl=en&ned=&q=" + 
              encodeURIComponent(sel) +
              "&btnG=Search+News";
    GM_openInTab(url);
  }
  
  function doYoutubeSearch(sel) {
    var url = "http://www.youtube.com/results?search_type=&search_query=" + 
              encodeURIComponent(sel) + "&aq=f";
    GM_openInTab(url);
  }
  
  function doWikipediaSearch(sel) {
    var url = "http://en.wikipedia.org/wiki/Special:Search?search=" +
              encodeURIComponent(sel) + "&sourceid=Mozilla-search";

    GM_openInTab(url);
  }

  function doAmazonSearch(sel) {
    var url = 'http://www.amazon.com/exec/obidos/external-search/' + 
              '?field-keywords=' + encodeURIComponent(sel) +
              '&mode=blended&tag=mozilla-20&sourceid=Mozilla-search';

    GM_openInTab(url);
  }


  function doGoogleSearch(sel) {
    var url = 'http://www.google.com/search?q=' +
              encodeURIComponent(sel) +
              '&ie=utf-8&oe=utf-8&aq=t' +
              '&rls=org.mozilla:en-US:official&client=firefox-a';

    GM_openInTab(url);
  }

  document.addEventListener('keypress',  kpHandler, false);

})();

palindromic pangram -- the simple way

2009-01-31T00:35:00.001-07:00

# sri, Sun Apr 13 15:05:56 PDT 2008
#
# A simple way to find palindromic pangrams.
# Completes in under 10 secs for the word list given
# by ITA software.
#
# The Algorithm: I find small palindromes (1-word & 2-word
# palindromes) and hook them up together. Example:
# if you have 1-word palindromes: "aa", "bb", & "cc", then
# aabbccccbbaa is a palindrome that contains all the characters
# a, b & c. It, by no means, produces an efficient
# palindrome. It also works for the dict file under OS X.
# So I really didn't need to find out 3-word palindroms,
# which seems much harder....

import string, sys

left = set(string.ascii_lowercase)
words = [x[:-1] for x in open(sys.argv[1]).readlines()]
        # use below for certain dicts that have many 1-letter words
        # if len(x) > 2]
         
wordset = set(words)
result = []
prefix = {}
suffix = {}

for word in words:
    for i in xrange(len(word)):
        pre = word[:i+1]
        if pre not in prefix:
            prefix[pre] = []
        prefix[pre].append(word)
        suf = word[-(i+1):]
        if suf not in suffix:
            suffix[suf] = []
        suffix[suf].append(word)  

def ispal(s):
    i = 0
    j = len(s)-1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

def words_containing(words, chars):
    for word in words:
        if any(c in word for c in chars):
            yield word

def markpal(*words):
    result.append(' '.join(words))
    for c in result[-1]:
        if c in left: left.remove(c)

# THIS IS BROKEN:
def smallest_pal(items):
    def score(x):
        x = x.replace(' ', '')
        uniques = len(set(x))
        return int(100 * uniques / len(x))
    items = sorted(items, key=score, reverse=True)
    left = set(string.ascii_lowercase)
    result = []
    for item in items:
        if not any(c in item for c in left):
            continue
        result.append(item)
        for c in item:
            if c in left: left.remove(c)
            
    print 'shortest pal:', 2 * len(''.join(result).replace(' ', ''))
    print '|'.join(result)
    print '|'.join(reversed(result))


# we don't care abt making the palindrome small
# we'll try do that later
for word in words:
    if ispal(word): markpal(word)
print 'left over from 1-word pals:', left

# figuring out 2-word palindromes is very simple;
# try to "mirror" the characters on both sides
# and 1-st test if its forms a palindrome and
# then check to see if its in the word list
for word in words_containing(words, left):
    for i in xrange(len(word)):
        pre = ''.join(reversed(word[-(i+1):]))
        #if ispal(pre+word) and prefix.has_key(pre): BUG!
        if ispal(pre+word) and pre in wordset:
            markpal(pre, word)
        suf = ''.join(reversed(word[:i+1]))
        #if ispal(word+suf) and suffix.has_key(suf): BUG!
        if ispal(word+suf) and suf in wordset:
            markpal(word, suf)
if not left:
    # print things out nicely so i can quickly check result visually
    print 'found palindromic pangram:', 2*sum(len(x) for x in result)
    output = []
    for c in string.ascii_lowercase:
        for word in result:
            if c in word:
                output.append((c, word))
                break
    for (c, w) in output:
        print "[%s] %s" % (c, w)
    #smallest_pal(result)
else:
    print 'no solution found'

left over from 1-word pals: set(['j', 'q', 'z'])
found palindromic pangram: 914
[a] aa
[b] aba
[c] civic
[d] dad
[e] deed
[f] deified
[g] aga
[h] aha
[i] bib
[j] raj ajar
[k] deked
[l] ala
[m] ama
[n] ana
[o] bob
[p] pap
[q] ta qat
[r] ere
[s] sagas
[t] otto
[u] alula
[v] ava
[w] awa
[x] oxo
[y] eye
[z] feeze ef

ITA software -- Sling Blade Runner

2009-01-27T10:46:00.001-07:00

The Puzzle by ITA Software:

How long a chain of overlapping movie titles, like Sling Blade Runner, can you find?

And the date is a list of movie titles provided by movielens. And here is my solution with the resulting output:

import collections, time

starttime = time.time()
titles = [x.strip() for x in open('MOVIES.LST.txt') if x.strip()]

# Add titles to beginnings such that, beginnings[T] = list of titles
# that start with some suffix of title T.
beginnings = collections.defaultdict(list)
ends = collections.defaultdict(list)
begs = collections.defaultdict(list)
for t in titles:
    s = t.split()
    for i in range(len(s) - 1):
        end = ' '.join(s[-i-1:])
        ends[end].append(t)
        beg = ' '.join(s[:i+1])
        begs[beg].append(t)
for k in [k for k in ends if k in begs]:
    for t in ends[k]:
        beginnings[t].extend( begs[k] )

titles.sort(key=lambda t: len(beginnings[t]), reverse=True)
for t in beginnings.keys():
    # if reverse is set to False, then the longer results don't
    # show up that quickly. 
    beginnings[t].sort(key=lambda t: len(beginnings[t]), reverse=True)

best = []
try:
    for t in titles:
        states = collections.deque()
        states.append( (set([t]), [t]) )
        while states:
            seen, state = states.popleft()
            last = state[-1]
            for x in beginnings[last]: # remember beginnings is a defaultdict
                if x in seen:
                    continue
                seen2 = seen.copy()
                seen2.add(x)
                newstate = (seen2, state + [x])
                states.appendleft(newstate) # KEY!!
                if len(newstate[1]) > len(best):
                    best = newstate[1]
except KeyboardInterrupt:
    print

print '\n'.join(best)
print '--'
print len(best)
print 'elapsed secs', time.time()-starttime

Q AND A
A KISS BEFORE DYING
DYING YOUNG
YOUNG GUNS
GUNS OF THE MAGNIFICENT SEVEN
SEVEN YEARS IN TIBET
TIBET CRY OF THE SNOW LION
LION OF THE DESERT
DESERT HEARTS
HEARTS OF DARKNESS A FILMMAKERS APOCALYPSE
APOCALYPSE NOW
NOW YOU SEE HIM NOW YOU DONT
DONT BOTHER TO KNOCK
KNOCK OFF
OFF THE MAP
MAP OF THE HUMAN HEART
HEART CONDITION
CONDITION RED
RED RIVER
RIVER OF NO RETURN
RETURN OF THE FLY
FLY AWAY HOME
HOME ALONE
ALONE IN THE DARK
DARK BLUE WORLD
WORLD TRADE CENTER
CENTER STAGE
STAGE FRIGHT
FRIGHT NIGHT
NIGHT FALLS ON MANHATTAN
MANHATTAN MURDER MYSTERY
MYSTERY ALASKA
ALASKA SPIRIT OF THE WILD
WILD IN THE STREETS
STREETS OF FIRE
FIRE ON THE MOUNTAIN
THE MOUNTAIN MEN
MEN CRY BULLETS
BULLETS OVER BROADWAY
BROADWAY DANNY ROSE
ROSE RED
RED HEAT
HEAT AND DUST
DUST TO GLORY
GLORY ROAD
ROAD GAMES
GAMES PEOPLE PLAY NEW YORK
NEW YORK COP
COP LAND
LAND OF THE DEAD
DEAD MAN ON CAMPUS
CAMPUS MAN
MAN TROUBLE
TROUBLE EVERY DAY
DAY OF THE WOMAN
WOMAN ON TOP
TOP GUN
GUN CRAZY
CRAZY PEOPLE
PEOPLE WILL TALK
TALK RADIO
RADIO DAYS
DAYS OF HEAVEN
HEAVEN CAN WAIT
WAIT UNTIL DARK
DARK CITY
CITY OF JOY
JOY RIDE
RIDE THE HIGH COUNTRY
COUNTRY LIFE
LIFE WITH FATHER
FATHER OF THE BRIDE
BRIDE OF THE WIND
THE WIND AND THE LION
THE LION KING
KING RAT
RAT RACE
RACE WITH THE DEVIL
THE DEVIL RIDES OUT
OUT TO SEA
SEA OF LOVE
LOVE AND SEX
SEX AND THE OTHER MAN
MAN ON FIRE
FIRE IN THE SKY
SKY HIGH
HIGH SPIRITS
SPIRITS OF THE DEAD
DEAD BANG
BANG BANG YOURE DEAD
DEAD MAN
MAN OF THE HOUSE
HOUSE PARTY
PARTY MONSTER
MONSTER IN A BOX
BOX OF MOON LIGHT
LIGHT OF DAY
DAY FOR NIGHT
NIGHT ON EARTH
EARTH GIRLS ARE EASY
EASY MONEY
MONEY FOR NOTHING
NOTHING PERSONAL
PERSONAL BEST
BEST FRIENDS
FRIENDS AND LOVERS
LOVERS AND OTHER STRANGERS
STRANGERS WHEN WE MEET
MEET JOE BLACK
BLACK DOG
DOG RUN
RUN SILENT RUN DEEP
DEEP BLUE
BLUE STEEL
STEEL DAWN
DAWN OF THE DEAD
DEAD OF NIGHT
NIGHT MOTHER
MOTHER NIGHT
NIGHT AND THE CITY
CITY OF ANGELS
ANGELS WITH DIRTY FACES
FACES OF DEATH 4
4 LITTLE GIRLS
GIRLS JUST WANT TO HAVE FUN
FUN AND FANCY FREE
FREE WILLY 2 THE ADVENTURE HOME
HOME ALONE 3
3 NINJAS KICK BACK
BACK TO SCHOOL
SCHOOL OF ROCK
ROCK N ROLL HIGH SCHOOL
HIGH SCHOOL HIGH
HIGH CRIMES
CRIMES OF PASSION
PASSION IN THE DESERT
DESERT BLUE
BLUE CAR
CAR 54 WHERE ARE YOU
YOU CAN COUNT ON ME
ME WITHOUT YOU
YOU CANT TAKE IT WITH YOU
YOU LIGHT UP MY LIFE
MY LIFE WITHOUT ME
ME MYSELF I
I NEVER PROMISED YOU A ROSE GARDEN
GARDEN STATE
STATE FAIR
FAIR GAME
GAME OF DEATH
DEATH SHIP
SHIP OF FOOLS
FOOLS RUSH IN
IN PRAISE OF OLDER WOMEN
WOMEN IN LOVE
LOVE LIFE
LIFE OR SOMETHING LIKE IT
IT HAD TO BE YOU
YOU ONLY LIVE ONCE
ONCE AROUND
AROUND THE BEND
BEND OF THE RIVER
THE RIVER WILD
WILD THINGS
THINGS TO COME
COME AND GET IT
IT HAPPENED ONE NIGHT
ONE NIGHT STAND
STAND IN
IN GODS HANDS
HANDS ON A HARD BODY
BODY AND SOUL
SOUL FOOD
FOOD OF LOVE
LOVE WALKED IN
IN OLD CALIFORNIA
CALIFORNIA SPLIT
SPLIT SECOND
SECOND BEST
BEST OF THE BEST
THE BEST OF EVERYTHING
EVERYTHING RELATIVE
RELATIVE FEAR
FEAR X
X THE MAN WITH THE X RAY EYES
EYES OF AN ANGEL
ANGEL BABY
BABY SECRET OF THE LOST LEGEND
LEGEND OF THE LOST
THE LOST BOYS
BOYS ON THE SIDE
SIDE OUT
OUT COLD
COLD FEVER
FEVER PITCH
PITCH BLACK
BLACK HAWK DOWN
DOWN WITH LOVE
LOVE AND DEATH
DEATH WISH V THE FACE OF DEATH
DEATH WISH
WISH UPON A STAR
STAR TREK THE MOTION PICTURE
PICTURE BRIDE
BRIDE OF THE MONSTER
MONSTER HOUSE
HOUSE OF DRACULA
DRACULA DEAD AND LOVING IT
IT TAKES TWO
TWO MUCH
MUCH ADO ABOUT NOTHING
NOTHING BUT TROUBLE
TROUBLE IN PARADISE
PARADISE ROAD
ROAD HOUSE
HOUSE OF FRANKENSTEIN
FRANKENSTEIN AND THE MONSTER FROM HELL
HELL UP IN HARLEM
HARLEM RIVER DRIVE
DRIVE ME CRAZY
CRAZY AS HELL
HELL NIGHT
NIGHT AND DAY
DAY OF THE DEAD
THE DEAD GIRL
GIRL IN THE CADILLAC
CADILLAC MAN
MAN OF THE YEAR
YEAR OF THE DRAGON
DRAGON SEED
SEED OF CHUCKY
----
231
elapsed secs 101.631449938

Great Paul Graham quote...

2009-01-18T13:12:00.000-07:00

Just brilliant:

So we just finished a new round of optimizations as part of our ongoing quest to prove that with sufficient caching you can serve arbitrarily large numbers of requests with arbitrarily slow languages.
-- Paul Graham, on releasing a new version of Hacker News

Opening Python files (and other source files) "in-browser" in Firefox 3.0+

2009-01-16T01:52:00.007-07:00

If Firefox keeps annoying you with a Download dialog box, when you drag/drop Python source files into the browser window, do the following: go to your Firefox profiles directory (for Mac OS X, it is under ~/Library/Application Support/Firefox/Profiles/xyz.default), open up the mimeTypes.rdf file and (carefully) delete all references to "x-python". After a restart, things should work fine! Sample junk found in mimeTypes.rdf (there were several of these):

  <RDF:Description RDF:about="urn:mimetype:text/x-python"
                   NC:fileExtensions="py"
                   NC:description=""
                   NC:value="text/x-python"
                   NC:editable="true">
    <NC:handlerProp RDF:resource="urn:mimetype:handler:text/x-python"/>
  </RDF:Description>

py.edit.js -- a simple Python editor in Javascript

2008-12-01T13:00:00.002-07:00

Here is a simple "editor" that I made over a weekend: py.edit.js. It runs on top of Google App Engine. It does simple things such auto indent/auto dedent of Python code as you type it in, evaluation of the code, and ability to output as text or HTML. There is also a "bookmarklet" mode -- which users can drag onto their menubar of their browser, and click on it to open up a "editor" mini-window on the current page that they are viewing.

Google challenge

2008-07-18T22:44:00.002-07:00

From the Ruby Forum: http://www.ruby-forum.com/topic/156473#new

There is an array A[N] of N integers. You have to compose an array Output[N] such that Output[i] will be equal to the product of all the elements of A[] except A[i]. Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Note: Solve it without the division operator and in O(n).

Here is my Python version. Note any difference between this implementation and those discussed in the Ruby Forum?

# http://www.ruby-forum.com/topic/156473#new
_input = [4, 3, 2, 1, 2]

after = []
before = []

t = 1
for x in _input:
    before.append(t) 
    t *= x

t = 1
for x in reversed(_input):
    after.append(t)
    t *= x
after.reverse()

for x, y in zip(before, after):
    print x * y

word-find.lisp

2008-05-13T00:33:00.005-07:00

I wrote this in 2004. Given a set of words, it generates word finder puzzles & also generates a solution for that puzzle. See the bottom of this post for an example. From what I remember, the most fun part of this tiny lisp program was writing the WALKING-ALONG macro, listed below.

Given a set of words, you need to place all the words inside the words rectangle, and fill the rest with junk characters. And the word should be placed in some random spot, going in a random direction. So while constructing the puzzle, I really don't care about the direction or the spot. I try to do those randomly. And this macro helps with that process.

(defmacro walking-along ((var array &key (direction (required-argument))
                              start-x start-y)
                         &body body)
  `(block nil
     (let ((.x. ,start-x) (.y. ,start-y))
       (symbol-macrolet ((,var (aref ,array .y. .x.)))
         (loop
           (unless (array-in-bounds-p ,array .y. .x.)
             (return))
           ,@body
           (ecase ,direction
             (:UP      (decf .y.))
             (:DOWN    (incf .y.))
             (:LEFT    (decf .x.))
             (:RIGHT   (incf .x.))
             (:DL-UP   (decf .x.) (decf .y.))
             (:DL-DOWN (decf .x.) (incf .y.))
             (:DR-UP   (incf .x.) (decf .y.))
             (:DR-DOWN (incf .x.) (incf .y.))))))
    (values)))

;;; word-find.lisp -- 
;;;
;;; Author: <sri -at- asu -dot- edu>
;;; Date: 2004-02-25T16:56:51
;;;
;;; Ideas:
;;;
;;;  o All the characters in the array should be part of a word.
;;;    Find words  that are randomly made up due to the intersection
;;;    of all the words and add it to the list of words.
;;;  o Difficulties:  either have a large matrix with small words, or so
;;;    similar words (characters)  that overlap.
;;;  o Try circular ones [for the array].
;;;
;;; [Tested and implemented under
;;;  CMU Common Lisp CVS Head 2003-10-03 00:16:55]
;;;
;;; This code is
;;;     Copyright (c) 2004 by Sriram Thaiyar.
;;; The terms are: You may do as you please with this code, as long as
;;; you do not delete this notice or hold me responsible for any outcome
;;; related to its use.


(defmacro walking-along ((var array &key (direction (required-argument))
                              start-x start-y)
                         &body body)
  `(block nil
     (let ((.x. ,start-x) (.y. ,start-y))
       (symbol-macrolet ((,var (aref ,array .y. .x.)))
         (loop
           (unless (array-in-bounds-p ,array .y. .x.)
             (return))
           ,@body
           (ecase ,direction
             (:UP      (decf .y.))
             (:DOWN    (incf .y.))
             (:LEFT    (decf .x.))
             (:RIGHT   (incf .x.))
             (:DL-UP   (decf .x.) (decf .y.))
             (:DL-DOWN (decf .x.) (incf .y.))
             (:DR-UP   (incf .x.) (decf .y.))
             (:DR-DOWN (incf .x.) (incf .y.))))))
    (values)))

(defun elts-at (array x y length direction)
  (let ((elts '())
        (i -1))
    (walking-along (e array :direction direction :start-x x :start-y y)
      (when (= (incf i) length)
        (return))
      (push e elts))
    (nreverse elts)))

(defun (setf elts-at) (new array x y direction &optional (length (length new)))
  (let ((i -1) (positions '()))
    (walking-along (e array :direction direction :start-x x :start-y y)
      (when (= (incf i) length)
        (return))
      (let ((elt (elt new i)))
        (setq e elt)
        (push (list elt .x. .y.) positions)))
    positions))

(defparameter *directions*
  '(:UP :DOWN :LEFT :RIGHT :DL-UP :DL-DOWN :DR-UP :DR-DOWN))

(let ((dirs nil)
      (null-returned nil))
  (defun random-direction (&optional reset)
    (when (or reset null-returned)
      (setq dirs (copy-list *directions*)
            null-returned nil))
    (if (and (null dirs) (null null-returned))
        (progn
          (setq null-returned t)
          nil)
        (let ((dir (nth (random (length dirs)) dirs)))
          (setq dirs (delete dir dirs))
          dir)))
  )

(defparameter *colors*
  '(:RED :BLUE :GREEN :ORANGE :PURPLE :GRAY :BROWN :PINK))

(let ((cols nil))
  (defun random-color ()
    (when (null cols)
      (let ((*directions* *colors*)) ;This is code reuse ;)
        (push (random-direction t) cols)
        (loop
          (let ((next (random-direction)))
            (when (null next)
              (return))
            (push next cols)))))
    (pop cols))
  )


;;; Return values for RANDOM-FIT & FORCE-FIT:
;;;  (<seq> <col> (<c0> <x0> <y0>) ...)

(defun random-fit (seq array width height)
  (let ((x (random width))
        (y (random height))
        (len (length seq)))
    (loop
      (let ((dir (random-direction)))
        (when (null dir)
          (return nil))
        (let ((old (elts-at array x y len dir)))
          (when (and (every (complement #'characterp) old)
                     (= (length old) len))
            (return
              (list* seq
                     (random-color)
                     (setf (elts-at array x y dir) seq)))))))))

(defun force-fit (seq array)
  (let ((open-spaces '())
        (dim (array-dimensions array)))
    (dotimes (x (car dim))
      (dotimes (y (cadr dim))
        (dolist (dir *directions*)
          (let ((count 0))
            (walking-along (e array :direction dir :start-x x :start-y y)
              (if (characterp e)
                  (return)
                  (incf count)))
            (push (list count x y dir)
                  open-spaces)))))
    (setq open-spaces
          (sort open-spaces #'> :key #'first))
    (let ((len (length seq)))
      (setq open-spaces
            (delete-if (lambda (n) (< n len)) open-spaces :key #'first))
      (when open-spaces
        (let ((x (nth (random (length open-spaces)) open-spaces)))
          (list* seq
                 (random-color)
                 (setf (elts-at array (second x) (third x) (fourth x))
                       seq)))))))

(defvar *error-on-nonfit* nil)

(defun wordfind-simple (words width height)
  (setq words (sort (copy-seq words) #'< :key #'length))
  (let ((array (make-array (list height width) :initial-element nil))
        (solution '()))
    (dolist (word words)
      (dotimes (i 15 (let ((x (force-fit word array)))
                       (if x
                           (push x solution)
                           (when *error-on-nonfit*
                             (error "Unable to fit ~A in ~S" word array)))))
        (let ((x (random-fit word array width height)))
          (when x
            (push x solution)
            (return)))))
    (dotimes (i (array-total-size array))
      (unless (characterp (row-major-aref array i))
        (setf (row-major-aref array i)
              (char "ABCDEFGHIJKLMNOPQRSTUVWXYZ" (random 26))))
      (setf (row-major-aref array i)
            (char-upcase (row-major-aref array i))))
    (values array solution)))


(defun generate-html (array solution output)
  (let ((words (mapcar #'car solution))
        (solution-pathname
         (make-pathname
          :defaults output
          :name (concatenate 'string (pathname-name output) "-sol"))))
    (flet
      ((generate-html-1 (&optional solution-p)
         (with-open-file (stream (if solution-p solution-pathname output)
                                 :direction :output
                                 :if-exists :supersede)
           (html (:stream stream)
            (head ()
             (title () (if solution-p "Word Finder: Solution" "Word Finder")))
            (body ()
             (strong () "Words: ")
             (if solution-p
                 (maplist (lambda (elts)
                            (format t "<font color=\"~A\">~A</font>~@[, ~]"
                                    (cadar elts)
                                    (string-capitalize (caar elts))
                                    (cdr elts)))
                          solution)
                 (format t "~{~A~^,&nbsp; ~}"
                         (mapcar #'string-capitalize words)))
             (br ())
             (p (:align :center)
              (table (:border t :width 100 :cellpadding 5)
               (when solution-p
                 (dolist (x solution)
                   (destructuring-bind (word color . positions)
                       x
                     (declare (ignore word))
                     (dolist (pos positions)
                       (let ((x (cadr pos)) (y (caddr pos)))
                         (unless (char-equal (car pos) (aref array y x))
                           (error "Characters don't match"))
                         (setf (aref array y x)
                               (cons color (car pos))))))))
                   (let ((dim (array-dimensions array)))
                     (dotimes (x (car dim))
                       (tr ()
                        (dotimes (y (cadr dim))
                          (td (:align :center)
                           (let ((elt (aref array y x)))
                             (if (consp elt) ;Solution and part of word
                                 (format t
                                         "<strong><font color=\"~A\">~C</font>~
                                          </strong>"
                                         (car (aref array y x))
                                         (char-upcase (cdr (aref array y x))))
                                 (format t "~C" (aref array y x)))))))))))
             (br ())
             (unless solution-p
               (p (:align :center)
                (a (:href (namestring solution-pathname)) "Solution"))))))))
      (generate-html-1)
      (generate-html-1 t)
      (values))))

(defun make-wordfind (&key (total-words 300) (width 20) (height 20)
                           (dict #p"/etc/alternatives/dictionary")
                           (output #p"word-find.html"))
  (let ((*error-on-nonfit* nil)
        (words '()))
    (if (or (stringp dict) (pathnamep dict))
        (with-open-file (stream dict)
          (let ((count 0))
            (loop
              (when (> count total-words)
                (return))
              (file-position stream (random (file-length stream)))
              (loop
                (let ((next (read-char stream nil nil)))
                  (cond ((null next) (return))
                        ((char= next #\Newline)
                         (let ((word (read-line stream nil nil)))
                           (when (> (length word) 0)
                             (push word words)
                             (incf count))
                           (return)))))))))
        (setq words dict))
    (multiple-value-bind (array solution)
        (wordfind-simple words width height)
      (generate-html array solution output))
    (values)))

Here is a sample output & its solution:

Words: Supercomputers, Contribution, Conditioners, Incendiaries, Imprecisely, Talkatively, Playgrounds, Subchannels, Congressman, Chronograph, Spiritual, Toryizes, Coverage, Rainfall, Climbing, Hostile, Dumping, Adjoin, Foils, Sighs, Casey

bowling.py

2008-04-13T22:39:00.005-07:00

One Saturday morning, I had the urge to learn the scoring rules for the game of bowling. This program resulted from that. Guido, here, talks about his bowling program that uses a simple data structure: list of lists to represent frames. I do the same.

# Sat March 22, 2008 (9am)
# bowling.py -- calculates scores, doesn't enforce rules

# create new instance for each player.
# Public API: knocked_down(npins)
# just invoke that -- will automatically deduce
# which frame you are in.
class BowlingGame(object):
    def __init__(self):
        self.f = [[None, None] for x in range(12)]
        self.cf = 0 # current frame

    def knocked_down(self, npins):
        f = self.f[self.cf]
        if f[0] is None:
            f[0] = npins
        else:
            f[1] = npins
        if npins == 10 or f[1] is not None:
            self.cf += 1

    def get_score(self):
        total = 0
        complete = True
        for i, f in enumerate(self.f):
            if i > 9:
                break
            elif f[0] is None: # hasn't bowled this frame
                break
            elif f[0] == 10: # strike
                if self.f[i + 1][0] is None and \
                   (self.f[i + 1][1] is None or self.f[i + 2][0] is None):
                    complete = False
                    break
                # strike -- next 2 bowls (both of which can be in the same frame!)
                total += 10 + self.f[i + 1][0]
                if self.f[i + 1][1] is None:
                    total += self.f[i + 2][0]
                else:
                    total += self.f[i + 1][1]
            elif f[1] is None: # hasn't bowled 2nd bowl
                complete = False
                break
            elif f[0] + f[1] == 10: # spare
                if self.f[i + 1][0] is None:
                    complete = False
                    break
                total += 10 + self.f[i + 1][0]
            else:
                total += f[0] + f[1]            
        return total, complete


#
# Tests
#
def reporterror(actual, expected):
    if actual != expected:
        print 'actual: %s\nexpected: %s' % (actual, expected)
        raise Exception

def test1():
    game = BowlingGame()
    game.knocked_down(7)
    game.knocked_down(2)
    reporterror(game.get_score()[0], 9)

def test2():
    game = BowlingGame()
    for i in range(12):
        game.knocked_down(10)
    reporterror(game.get_score()[0], 300)

def test3():
    import random
    for i in range(1000):
        bowls = [random.randint(0, 4) for i in range(20)]
        game = BowlingGame()
        for b in bowls:
            game.knocked_down(b)
        reporterror(game.get_score(), (sum(bowls), True))

# wikipedia data:
# http://en.wikipedia.org/wiki/Ten-pin_bowling#Rules_of_play
def test4():
    game = BowlingGame()
    map(game.knocked_down, [10, 10, 4, 2])
    reporterror(game.get_score(), (46, True))
def test5():
    game = BowlingGame()
    map(game.knocked_down, [7, 3, 4, 2])
    reporterror(game.get_score(), (20, True))
def test6():
    game = BowlingGame()
    map(game.knocked_down, [10, 3, 6])
    reporterror(game.get_score(), (28, True))

def test7():
    game = BowlingGame()
    for i in range(10):
        game.knocked_down(10)
    game.knocked_down(7)
    game.knocked_down(1)
    reporterror(game.get_score(), (285, True))

def t():
    for i in range(100):
        try:
            name = "test%d" % (i+1)
            fn = globals()[name]
            print "testing", name
        except KeyError:
            break
        else:
            fn()

if __name__ == "__main__":
    t()

done with this blog (at least for a while)

2008-02-14T23:18:00.001-07:00

it is time to try other things!

Email a directory

2008-02-08T01:09:00.001-07:00

This is how I email a directory to myself -- I cd to the directory and type this command there. Also, I set up a Gmail filter and put unique words into this script that the filter will recognize. So the directory will be tarred, gzipped and sent to my Gmail account and will arrive in a specific label. Works with Python 2.5

#! /usr/bin/env python2.5
# -*- Python -*-

import os
import datetime
import smtplib
import tarfile
import mimetypes
from email import Encoders
from email.MIMEBase import MIMEBase
from email.MIMEMultipart import MIMEMultipart
import tempfile
import getpass, socket


me = getpass.getuser() + '@' + socket.gethostname()
if not getpass.getuser() or not  socket.gethostname():
    print "Can't set email From"
    sys.exit(1)


def main():
    dirname = os.path.basename(os.getcwd())
    try:
        preferredname = raw_input('Default: [%s]\nPreferred Name: ' %
                                  dirname)
    except (KeyboardInterrupt, EOFError):
        pass
    else:
        dirname = preferredname.strip()

    
    to = "YOUR-EMAIL-ADDRESS"
    archive_name = os.path.join(tempfile.gettempdir(),
                                "%s.tar.gz" % dirname)
    now = datetime.datetime.today()    

    print "Creating message..."
    msg = MIMEMultipart()
    msg["Subject"] = "%s %s Backup [%d-%02d-%02d]" % (
        socket.gethostname(), dirname, now.year, now.month, now.day)
    msg["From"] = me
    msg["To"] = to
    # message has body:
    # this can be used to direct this backup email to a Gmail Filter
    # YOUR GMAIL FILTER WORD
    msg.preamble = "%s %s Backup" % (socket.gethostname(), dirname)
    msg.epilogue = ""

    if os.path.exists(archive_name):
        os.remove(archive_name)

    print "Creating gzipped-tar file..."
    tar = tarfile.open(archive_name, "w:gz")
    tar.add(".")
    tar.close()


    print "Attaching MIME to message..."
    ctype, encoding = mimetypes.guess_type("%s.tar.gz" % dirname)
    maintype, subtype = ctype.split("/", 1)
    mime = MIMEBase(maintype, subtype)
    fp = open(archive_name, "rb")
    mime.set_payload(fp.read())
    fp.close()
    Encoders.encode_base64(mime)
    mime.add_header('Content-Disposition', 'attachment',
                    filename=os.path.basename(archive_name))
    msg.attach(mime)

    print "Sending message..."
    s = smtplib.SMTP()
    s.connect()
    s.sendmail(me, [to], msg.as_string())
    s.close()

    os.remove(archive_name)


if __name__ == "__main__":
    main()

Quick: my Macbook Pro and Pulley

2007-12-19T01:47:00.000-07:00

I got my Macbook Pro on Sunday, December 16 2007. Loving it so far! Still waiting for the David Pogue's Mac OS X Leopard: The Missing Manual, which should arrive tomorrow.

So, I've been kinda annoyed with Google Reader and have been wanting to create my own Reader -- I'm calling it pulley. More details as I start to work on it. I've been doing way too much talking and reading pointless tech news websites, and random stuff and not enough coding, hacking. All that ends today!

The Feyerabend Project & Gerry Sussman

2007-12-12T19:36:00.000-07:00

From The Feyerabend Project -- which I think was started by Richard P. Gabriel -- a quote by Gerry Sussman:

Computer Science is in deep trouble. Structured design is a failure. Systems, as currently engineered, are brittle and fragile. They cannot be easily adapted to new situations. Small changes in requirements entail large changes in the structure and configuration. Small errors in the programs that prescribe the behavior of the system can lead to large errors in the desired behavior. Indeed, current computational systems are unreasonably dependent on the correctness of the implementation, and they cannot be easily modified to account for errors in the design, errors in the specifications, or the inevitable evolution of the requirements for which the design was commissioned. (Just imagine what happens if you cut a random wire in your computer!) This problem is structural. This is not a complexity problem. It will not be solved by some form of modularity. We need new ideas. We need a new set of engineering principles that can be applied to effectively build flexible, robust, evolvable, and efficient systems.

In the design of any significant system there are many implementation plans proposed for every component at every level of detail. However, in the system that is finally delivered this diversity of plans is lost and usually only one unified plan is adopted and implemented. As in an ecological system, the loss of diversity in the traditional engineering process has serious consequences for robustness.

This fragility and inflexibility must not be allowed to continue. The systems of the future must be both flexible and reliable. They must be tolerant of bugs and must be adaptable to new conditions. To advance beyond the existing problems we must change, in a fundamental way, the nature of the language we use to describe computational systems. We must develop languages that prescribe the computational system as cooperating combinations of redundant processes.

feedparser_debug.py

2007-12-12T03:07:00.000-07:00

I love Mark Pilgrim's feedparser. But sometimes I want to see how a feed is parsed by feedparser. Here is a hack for that. Here is an example & the source: feedparser_debug. I append the source below.

import feedparser, cgi, textwrap

html = """
<html>
<head>
<style>
body {
 margin: 30px;
}
table {
 border: solid 1px;
}
.bozo {
 background: pink;
 padding: 2px;
 margin-bottom: 15px;
}
.type {
 color: gray;
 font-size: 11px;
}
</style>
</head>
<body>
%s
</body>
</html>
"""

table = """
<table cellspacing=2 cellpadding=2>
%s
</table>
"""

def bozo(m):
    return '<div class="bozo">%s</div>' % m

def tr(k, v, typ, descend_path):
    if descend_path:
        tooltip = descend_path[0]
        for x in descend_path[1:] + [k]:
            if x.startswith('['):
                tooltip += x
            else:
                tooltip += '.' + x
        tooltip = 'title="%s | %s"' % (
            tooltip,
            typ.__name__)
    else:
        tooltip = ''
    return ('<tr><td %s valign=top>%s<br/><span class="type">%s</span>' +
            '</td><td valign=top>%s</td>') % (
        tooltip,
        k,
        typ.__name__,
        v)

def enumerate_seq(seq, sorted_keys=None):
    if isinstance(seq, list):
        for idx, val in enumerate(seq):
            yield '[%s]' % idx, val
    elif isinstance(seq, (feedparser.FeedParserDict, dict)):
        for attr in (sorted_keys or sorted(seq.keys())):
            try:
                val = getattr(seq, attr)
            except AttributeError:
                val = seq[attr]
            yield attr, val


def htmlize(obj, sorted_keys=None, descend_path=[]):
    if isinstance(obj, (feedparser.FeedParserDict, dict, list)):
        res = []
        for attr, val in enumerate_seq(obj, sorted_keys):
            res.append(tr(attr,
                          htmlize(val, descend_path=descend_path+[attr]),
                          type(val),
                          descend_path))
        return table % '\n'.join(res)
    else:
        #if isinstance(obj, unicode):
        #    obj = obj.encode('ascii', 'xmlcharrefreplace')
        escaped = cgi.escape(repr(obj))
        wrapped = textwrap.wrap(escaped)
        link = ''
        if isinstance(obj, (unicode, str)):
            if obj.startswith('http://') or obj.startswith('https://'):
                if len(wrapped) < 200:
                    link = ' <a href="%s">[link]</a>' % obj
        return '\n<br/>'.join(wrapped) + link

def main(url):
    f = feedparser.parse(url)
    keys = sorted(f.keys())
    keys.remove('entries')
    keys.append('entries') # place it last
    sub = htmlize(f, keys, ['f'])
    if f.bozo:
        sub = bozo(str(f.bozo_exception)) + sub
    h = html % sub
    return h

if __name__ == '__main__':
    h = main('http://defcraft.blogspot.com/feeds/posts/default')
    open('test.html', 'w').write(h)

Just for fun: jumbled to un-jumbled

2007-11-28T15:17:00.000-07:00

Just for fun:

>>> jumble('Now is the Time for all Good Men to come to the aid of their Country...',0)
Now is the Time for all Good Men to come to the aid of their Country... 
-----------------------------------------------------------------------
Noo rf rot Thai wmr dda Guot Mct tf iehe hi tyo ino eo eloes Ceotnml...
Noo rf rot Thai wmr dda Guot Mct tf iehe ho tyo ino eo eloes Ceitnml...
Noo rf rot Thai wmr dda Guot Mct hf iehe to tyo ino eo eloes Ceitnml...
Noo rf rot Tiah wmr dda Guot Mct hf iehe to tyo ino eo eloes Ceitnml...
Noo rf rot Tiah wmr dda Guot Mct hf iehe to tyo ino eo eloes Ceitnml...
Noo rf rot Tiih wmr dda Guot Mct hf iehe to tyo ano eo eloes Ceitnml...
Noo rs rot Tiih wmr dda Guot Mct hf iehe to tyo ano eo eloef Ceitnml...
Noo rs rot Timh wmr dda Guot Mct hf iehe to tyo ano eo eloef Ceitnil...
Noo rs rot Timh wmr dda Guot Mct hf iehe to tyo ano eo eloef Ceitnil...
Noo rs rot Timh wmr add Guot Mct hf iehe to tyo ano eo eloef Ceitnil...
Noo is rot Timh wmr add Guot Mct hf iehe to tyo ano eo eloef Ceitnrl...
Noo is rot Timh wmr ado Guot Mct hf iehe to tyo and eo eloef Ceitnrl...
Noo is rot Timh wmr ado Guot Mct hf iehe to tyo and eo eloef Ceintrl...
Noo is rot Timh wmr ado Guot Mct hf nehe to tyo aid eo eloef Ceintrl...
Noo is rot Timh wmr ado Guot Mct hf nohe to tyo aid ee eloef Ceintrl...
Noo is rft Timh wmr ado Guot Mct ho nohe to tyo aid ee eloef Ceintrl...
Nou is rft Timh wmr ado Goot Mct ho nohe to tyo aid ee eloef Ceintrl...
Nou is rfe Timh wmr ado Goot Mct ho nohe to tyo aid ee tloef Ceintrl...
Nou is rfe Timh wmf ado Goot Mct ho nohe to tyo aid ee tloer Ceintrl...
Nou is rfe Timh wmf adl Goot Mct ho nohe to tyo aid ee tooer Ceintrl...
Nou is ree Timh wmf adl Goot Mct ho nohe to tyo aid ef tooer Ceintrl...
Nou is ree Timh wmf adl Goot Mct ho nohe to tyo aid of toeer Ceintrl...
Nou is ree Timh wmf adl Goot Mct ho nohe to tyo aid of toeer Ceintrl...
Nou is ree Timh wmf adl Goot Mct ho nohe to tyo aid of toeer Ceintrl...
Nou is ree Timh wmf adl Goot Mcn ho tohe to tyo aid of toeer Ceintrl...
Nou is ree Timh wmf adl Goot Mcn ho tohe to tyo aid of toeer Ceintrl...
Nou is ree Timh fmw adl Goot Mcn ho tohe to tyo aid of toeer Ceintrl...
Now is ree Timh fmu adl Goot Mcn ho tohe to tyo aid of toeer Ceintrl...
Now is ree Timh fmu adl Goot Mcn oo tohe to tyo aid of theer Ceintrl...
Now is ree Timh fmi adl Goot Mcn oo tohe to tyo aid of theer Ceuntrl...
Now is ree Timh fmi adl Goot Mcn oo tohe to tlo aid of theer Ceuntry...
Now is ree Timh fmi adl Goot Mcn oo tohe to tle aid of theer Country...
Now is ree Timh fhi adl Goot Mcn oo tome to tle aid of theer Country...
Now is ree Timh fli adl Goot Mcn oo tome to the aid of theer Country...
Now is rce Timh fli adl Goot Men oo tome to the aid of theer Country...
Now is rce Timh fli adl Goot Men oo tome to the aid of theer Country...
Now is rce Timh fli adl Goot Men oo tome to the aid of theer Country...
Now is rhe Timc fli adl Goot Men oo tome to the aid of theer Country...
Now is rhe Time fli adl Goot Men oo tome to the aid of thecr Country...
Now is rhe Time flc adl Goot Men oo tome to the aid of their Country...
Now is rhe Time flt adl Goot Men oo come to the aid of their Country...
Now is rhe Time flt atl Good Men oo come to the aid of their Country...
Now is the Time flr atl Good Men oo come to the aid of their Country...
Now is the Time flr aol Good Men to come to the aid of their Country...
Now is the Time for all Good Men to come to the aid of their Country...
Now is the Time for all Good Men to come to the aid of their Country...
Now is the Time for all Good Men to come to the aid of their Country...
Now is the Time for all Good Men to come to the aid of their Country...

Here is the code:

import random, string

class JumbledString(object):
    def __init__(self, original):
        self.original = list(original)
        self.remaining = list(original)
        # positions in self.jumbled that are
        # still available
        self.available = range(len(original))
        self.jumbled = self.jumble(original)

    # jumbling up all doesn't look too good.
    # let's try jumbling up only ascii lowercase.
    def jumble(self, st):
        tmp = []
        ins = []
        for (i, c) in enumerate(st):
            if c not in string.ascii_lowercase:
                self.available.remove(i)
                self.remaining.remove(c)
                ins.append((i, c))
            else:
                tmp.append(c)
        random.shuffle(tmp)
        for (i, c) in sorted(ins):
            tmp.insert(i, c)
        return tmp

    def is_done(self):
        return len(self.remaining) == 0

    def findall(self, char, string):
        res = [i for (i, c) in enumerate(string) if c == char]
        random.shuffle(res)
        return res

    def find_in_jumbled(self, char):
        res = [i
               for (i, c) in enumerate(self.jumbled)
               if c == char and i in self.available]
        assert res, "can't find char in find_in_jumbled!"
        random.shuffle(res)
        return res[0]

    def rand_swap(self):
        choice = random.choice(self.remaining)
        self.remaining.remove(choice)
        for pos in self.findall(choice, self.original):
            if pos in self.available:
                self.available.remove(pos)
                if self.jumbled[pos] == choice:
                    return pos, pos
                swappos = self.find_in_jumbled(choice)
                tmp = self.jumbled[pos]
                self.jumbled[pos] = choice
                self.jumbled[swappos] = tmp
                return pos, swappos
        assert False, "this can't happen in rand_swap!"

    def get_jumbled(self):
        return ''.join(self.jumbled)


def jumble(sentence, print_marker=True):
    print sentence, '\n', '-'*len(sentence)
    i = 1
    j = JumbledString(sentence)
    while not j.is_done():
        a, b = j.rand_swap()
        print j.get_jumbled()
        if print_marker:
            print marker(len(sentence), min(a, b), max(a, b))
        i += 1
        assert i < 2*len(sentence) # just for safety

def marker(slen, a, b):
    if a == b:
        return ' '*a + '^' + ' '*(slen-a-1)
    else:
        return ' '*a + '^' + '-'*(b-a-1) + '^' + ' '*(slen-b-1)

What programming language should I start with?

2007-10-23T04:13:00.001-07:00

Over on news.ycombinator.com, someone asked the question:

What programming language should I start with?

This was my response:

Here are the languages that have big communities: Perl, Python, Ruby, PHP, Javascript, C#/VB.NET and Java.

Subscribe to lots of blogs from each community. (Many of them have planet aggregators like "Planet Python" and "Planet Ruby".) Also visit local user groups, wherever your are.

Read/visit them for a while -- say a month or two. Whichever community makes you go, "wow, that's cool" -- join that community and learn the language. You can also interact with those communities via Google Groups.

Lots of people will say -- "that's easy" or "this is elegant" or "that language sucks". Feel free to ignore them.

And the response to my response, which I really liked :-)

Excellent advice. Non-religious, informative, and true.

my dot emacs: Shift to Control

2007-07-24T06:11:00.000-07:00

I can still remember my left pinky hurting badly, from pressing the Control key to invoke commands in Emacs. But then I swapped Shift & Control. And I've been happy ever since. Shift is in a perfect location (not too far below like Control) and is on both sides of the keyboard -- this even on the worst keyboards that I had to endure while in college.

Now, some things break when you do this. Control-Space sets the mark (and still does), but Shift-Space doesn't -- it simply inserts a space. Control-G can break out of infinite loops in Emacs Lisp -- Shift-g can't do that (unless you modify the quit_char in src/keyboard.c before building Emacs). Also, typing upcase or capitilized characters are a bit harder -- especially because I move my entire hand off the keyboard to hit the Control key -- no more use of the pinky in unnatural positions! And when you cut-n-paste, upper case characters run commands!! (Although, I haven't needed it, this shouldn't be too hard to overcome -- you can setup things so that a keypress swaps Control & Shift, and then pastes the contents of the clipboard, and the re-swaps them again.)

Despite the problems, this has been worth it for me. And here is the code for all this. I think this is all the code -- I haven't really looked at it since I wrote it about 6 years ago. This works on both Windows and Linux (I think, this will really work everywhere...):

;;; control becomes shift and vice-versa. when this happens certain
;;; things are broken: c-space sets mark, however shift-space doesn't
;;; anymore.  for esc, use alt (press this with the thumb, which
;;; doesn't do *anything* except hit the damn space bar) plus the key.
;;; expriment: 04:29PM Friday November 23 2001.  hopefully, things
;;; will be much easier this way.
;;; to do: change esc-c-f to esc-F.  also need to be careful about
;;; esc-ctrl- like esc-ctrl-. and esc-ctrl-backspace. how to
;;; fix these.  also since i usually type a lowercase word and want to
;;; upcase or capatilize it afterwards, make those commands default to the
;;; previous word.

;;; Another idea:  make keyboard-translate-table buffer local so that
;;; in certain modes, like gnus, we can operate normally (or maybe
;;; change it during an entry and exit hook.

(defun keyboard-translate-swap (a b)
  (keyboard-translate a b)
  (keyboard-translate b a))

(defvar previous-keyboard-translate-table nil)

(defun normalize-keyboard ()
  (interactive)
  (setq previous-keyboard-translate-table keyboard-translate-table
        keyboard-translate-table nil))

(defun revert-keyboard ()
  (interactive)
  (setq keyboard-translate-table previous-keyboard-translate-table))

;;; Emacs Manual, "Translating Input Events"
(setq keyboard-translate-table
      (make-char-table 'keyboard-translate-table nil))

;;; Swap Control- and uppercase letters.
(let ((ctrl 1) (upcase-beg (1- ?A)) (letters 26))
  (while (<= ctrl letters)
    (keyboard-translate-swap ctrl (+ upcase-beg ctrl))
    (setq ctrl (1+ ctrl))))

And this piece of code quickly upcases or capitalizes the previous word that you just typed. I have it bound to F6:

(defvar my-correct-case-last-arg nil)

(defun my-correct-case (arg)
  (interactive "p")
  (let ((fn (cond ((eq last-command 'my-correct-case)
                   (setq arg my-correct-case-last-arg)
                   'capitalize-word)
                  (t (setq my-correct-case-last-arg arg)
                     'upcase-word))))
    (save-excursion
      (funcall fn (- arg)))))

These days I run Emacs via Putty from a Windows machine. This is how I cut-n-paste in Putty -- when you right click on the terminal, Putty sends the contents of the clipboard to the terminal. There are 2 parts to this: the Emacs part and the shell part. First, I have to suspend Emacs and go to the shell, where is type the alias c:

alias c='echo Hit Ctrl-C to end; cat > ~/x'

Next, back in Emacs, I hit F10 -- this function is bound to that key:

(defun my-paste ()
  (interactive)
  (if (not (file-exists-p "~/x"))
      (message "~/x doesn't exist")
    (insert-file-contents "~/x")
    (message "Pasted contents of ~/x")))

Firefox Greasemonkey hack

2007-07-05T04:41:00.000-07:00

Firefox Greasemonkey hack: sri-goog-amazon.user.js. (make sure you know what you're doing if you install this...) Select a piece of text with your mouse and hit one of these keys:

ALT-A: searches Amazon.com for the selected text, in a background tab
ALT-G: does the above with Google.com

Also, without any selection, ALT-A and ALT-G will take you to Amazon.com & Google.com respectively.

strftime helper

2007-06-22T16:33:00.000-07:00

I can never remember the syntax for strftime -- so I wrote a little helper for it: strftime_helper.py, which uses pii.py (see previous post, Extending Python's Interactive Interpreter). Here is an interactive session with it:

>>> pd
===============================================================================
= pd help =

localet, localed, localedt  - Locale Time, Locale Date, Locale Date & Time
hh24, hh, mm, ss, am, pm    - 24-Hour, Hour, Minute, Second, Am, Pm
dow, dom, doy               - Day Of {Week, Month, & Year} respectively
swoy, mwoy                  - Week Of Year considering either Sunday or Monday
                                as first day of week
yy, yyyy                    - Year without century & Year with century
tz                          - Timezone
mon..sun, monday..sunday    - Weekday in Abbrev or Long form
jan..dec, january..december - Month in Abbrev or Long form

? localet hh24:mm:ss, pm
2007-06-22 19:36:53 formats to
19:36:53 19:36:53, PM
'%X %H:%M:%S, %p'
? jun dom, yyyy (it's a sunday)
2007-06-22 19:38:51 formats to
Jun 22, 2007 (it's a Friday)
"%b %d, %Y (it's a %A)"
? [ENTER] or Control-D
>>> _
"%b %d, %Y (it's a %A)"

Things to note:

although the new format directives are easier to remember (dom of day of the month, any of mon, tue, wed, ..., sun for a short weekday name, any of january, feburary, ..., december for a long month name, tz for timezone), a help screen is printed out each time you type pd
you end the interactive session with pd by hitting Ctrl-D or by passing it a empty line. The _ variable will be set to the result of pd: the actual format control that strftime interprets

Given Python's friendliness to newbies, there should be a newbie.py supplied with the standard distribution that "simplifies" many such tasks for newbies...

Extending Python's Interactive Interpreter

2007-06-17T01:04:00.001-07:00

[The code for all this is here: pii.py]

Update: I've only tried this under Linux; the special commands doesn't seem to work under IDLE. Also, you need to execfile pii.py, and not import it...

I've written some code to help the interactive interpreter accept simple commands. Commands like "ls" and those like "cd ~/tmp". Commands without arguments -- simple commands -- can be Python objects. But for those with arguments (special commands), we need a little magic: when there is a space between a command and its argument ("cd ~/tmp"), Python raises a SyntaxError. And the SyntaxError contains the problematic line:

>>> try:
...   eval('a b')
... except SyntaxError, s:
...   print repr(s.text)
...
'a b'

So we simply "catch" the error and extract the command that needs to be executed and execute it. The two hook functions, sys.displayhook and sys.excepthook are necessary to make this happen. sys.displayhook is needed to display the simple commands & sys.excepthook is needed to extract out the special commands and run them. We replace both the hooks like so:

def mydisplayhook(value):
    if value is not None:
        # this'll only invoke simplecmds (or
        # cmds that install themselves in
        # __builtins__) -- the specialcmds are
        # executed in myexcepthook
        if isinstance(value, SimpleCmd):
            out = value()
            if out:
                print out
        else:
            __builtins__._ = value
            print repr(value)
sys.displayhook = mydisplayhook

def myexcepthook(type, value, tb):
    # imports giving rise to syntaxerror shouldn't
    # be considered a s cmds
    if type is SyntaxError and value.filename=='<stdin>':
        # might be a cmd of ours
        line = value.text
        # if user is entering a multiline expr
        # (line[0]!=' ') -- they indent everything
        # other than first line -- don't consider
        # that a cmd
        if line and line[0] not in ' \t':
            cmd = value.text.split()[0]
            if cmd in specialcmds:
                fn = specialcmds[cmd]
                arg = line[len(cmd):]
                fn(arg)
                return
    traceback.print_exception(type, value, tb)
sys.excepthook = myexcepthook

Two points:

Special commands receive a single string -- it is up to the command to split it into multiple arguments, if necessary
also, simple commands sit in the __builtins__ namespace, so even if you replace it, you can get it back by saying "del command-name")

Here is the whole thing. It sits in my pythonrc file. You can download it here.

import sys, os, datetime, traceback, commands


specialcmds = {}
allcmds = []

class CmdMeta(type):
    def __init__(cls, name, bases, dict):
        super(CmdMeta, cls).__init__(cls, name, bases, dict)
        if name == 'Cmd': return
        simplecmds = {}
        specials = {}
        inst = cls()
        inst.install(specials, simplecmds)
        for k in simplecmds:
            setattr(__builtins__, k, SimpleCmd(simplecmds[k]))
        allcmds.append((name, cls, inst, simplecmds, specials))
        specialcmds.update(specials)

class Cmd(object):
    __metaclass__ = CmdMeta

class SimpleCmd(object):
    def __init__(self, func):
        self.func = func
    def __call__(self):
        result = self.func()
        if result:
            return str(result)

def myexcepthook(type, value, tb):
    # imports giving rise to syntaxerror shouldn't
    # be considered as cmds
    if type is SyntaxError and value.filename=='<stdin>':
        # might be a cmd of ours
        line = value.text
        # if user is entering a multiline expr
        # (line[0]!=' ') -- they indent everything
        # other than first line -- don't consider
        # that a cmd
        if line and line[0] not in ' \t':
            cmd = value.text.split()[0]
            if cmd in specialcmds:
                fn = specialcmds[cmd]
                arg = line[len(cmd):]
                fn(arg)
                return
    traceback.print_exception(type, value, tb)
sys.excepthook = myexcepthook


# reloading this file shouldn't mess up prev value
try:
    __builtins__._
except AttributeError:
    __builtins__._ = None


def mydisplayhook(value):
    if value is not None:
        # this'll only invoke simplecmds (or
        # cmds that install themselves in
        # __builtins__) -- the specialcmds are
        # executed in myexcepthook
        if isinstance(value, SimpleCmd):
            out = value()
            if out:
                print out
        else:
            __builtins__._ = value
            print repr(value)
sys.displayhook = mydisplayhook

And here are some commands:

#
# Commands:
#
class MyCmds(Cmd):
    def install(self, specialcmds, simplecmds):
        simplecmds['cmds'] = self.allcmds
    def doc(self, x):
        return getattr(x, '__doc__') or '(no doc)'
    def allcmds(self):
        "prints out all the cmds"
        print "all commands\n", 65*'='
        cmds = []
        for (name, cls, inst, simplecmds, specialcmds) in allcmds:
            simple = set(simplecmds.keys())
            specials = set(specialcmds.keys())
            both = simple & specials
            simple -=  both
            specials -= both
            for k in both:
                cmds.append((k, 'both', self.doc(simplecmds[k])))
            for k in specials:
                cmds.append((k, 'special', self.doc(specialcmds[k])))
            for k in sorted(simple):
                cmds.append((k, 'simple', self.doc(simplecmds[k])))
        cmds.sort()
        for x in cmds:
            print '%-6s  %-7s    %s' % x
        

class MyReload(Cmd):
    def install(self, specialcmds, simplecmds):
        simplecmds['rl'] = self.doit
    def doit(self):
        "reloads your pythonrc startup file"
        path = os.environ.get('PYTHONSTARTUP')
        if not path:
            print "can't find your pythonstartup"
        else:
            execfile(path, globals())


class MyPwd(Cmd):
    def install(self, specialcmds, simplecmds):
        simplecmds['pwd'] = simplecmds['cwd'] = self.getcwd
    def getcwd(self):
        "prints the current working directory"
        return os.getcwd()

class MyCD(Cmd):
    def __init__(self):
        self.popdirs = []
    def install(self, specialcmds, simplecmds):
        simplecmds['popd'] = self.popd
        simplecmds['cd'] = specialcmds['cd'] = self.cd
    def popd(self):
        "changes back to directory from which we came"
        if self.popdirs:
            self.cd(self.popdirs.pop(), False)
        else:
            print 'nothing to pop back to'
    def cd(self, dir=None, insert=True):
        "changes to a given directory or user home; resolves ~ to user home"
        if not dir:
            import user
            dir = user.home
        dir = os.path.expanduser(dir.strip())
        if not os.path.isdir(dir):
            print 'not a dir:', dir
        else:
            if insert:
                self.popdirs.append(os.getcwd())
            os.chdir(dir)
            print 'changed to', dir

class MyHelp(Cmd):
    def install(self, specialcmds, simplecmds):
        specialcmds['h'] = self.help
    def help(self, x):
        "prints help to a given thing"
        help(x.strip())

class MyLs(Cmd):
    def install(self, specialcmds, simplecmds):
        specialcmds['ls'] = self.ls
        simplecmds['ls'] = self.ls
    def ls(self, dir=''):
        """run the unix command 'ls -l'"""
        dir = os.path.expanduser(dir.strip() or '.')
        print commands.getoutput('ls -l %s' % dir)

flatten in Python

2007-06-06T23:11:00.000-07:00

Here it is:

# non-recursive flatten
# requires Python 2.5 or above
def flatten(lists):
    from collections import deque
    items = deque(lists)
    while items:
        top = items.popleft()
        if isinstance(top, list):
            items.extendleft(reversed(top))
        else:
            yield top

This is the test script flatten.py with some data on performance:

# non-recursive flatten
# requires Python 2.5 or above
def flatten(lists):
    from collections import deque
    items = deque(lists)
    while items:
        top = items.popleft()
        if isinstance(top, list):
            items.extendleft(reversed(top))
        else:
            yield top

def flatten_r(list_of_lists):
    if list_of_lists == []:
        return []
    elif isinstance(list_of_lists, list):
        result = []
        for x in list_of_lists:
            for y in flatten_r(x):
                result.append(y)
        return result
    else:
        return [list_of_lists]


# from skencil
from types import ListType
def flatten2(list):
    result = []
    for item in list:
        if type(item) == ListType:
            result = result + flatten2(item)
        else:
            result.append(item)
    return result

def count_flatten_len(x):
    if isinstance(x, list):
        return len(x)
    else:
        count = 0
        try:
            while True:
                x.next()
                count += 1
        except StopIteration:
            return count


#
# Test data:
#
t1 = [1, [2, 3, [4, 5, [[[6], 7], [[8, 9]]]]]]
t2 = [t1, [[t1], [[[t1]], t1, [[[[[t1, 'n']]], t1, t1, t1]], 'a']]]
t3 = [t2, [[t2, [t2, [[t2, [[t2, t2, t2,
                             [[[t2, [[t2, t2, t2, [[[[t2]]]]]]]]]]]]]]]]]
t4 = [[[t3, t3, [[t3, [[[t3, [[t3, [[[t3, [[[t3, t3]]]]]]]]]]]]]]]]
t5 = ['first', [[[t4, [[[t4, [[[[t4, [[[t4, 'mid']]], t4]]], t4]], t4, ]],
      t4, [[t4]]]]], 'last']


def rectest():
    global t5
    t5 = []
    for i in range(100000):
        t5 = [t5, i]

if __name__ == "__main__":
    def indent(s):
        lines = s.split("\n")
        spaces = 4 * ' '
        return "\n".join(spaces+line for line in lines)
    
    import commands

    sep = '=='*20

    # Sanity check:
    a1 = list(flatten(t5))
    a2 = flatten_r(t5)
    a3 = flatten2(t5)
    assert a1[0]=='first' and a1[-1]=='last' and a1==a2 and a2==a3
    
    cmd = ("python -mtimeit -v -n 1 -r 2 -s 'import flatten as F' '%sF.%s(F.t5)'")
    for funcname in ('flatten_r', 'flatten2', 'flatten'):
        print funcname
        out = commands.getoutput(cmd % ('', funcname))
        print indent(out)
        print sep

    print sep
    print 'recursion test'
    for funcname in ('flatten_r', 'flatten2', 'flatten'):
        print funcname
        status, out = commands.getstatusoutput(cmd % ('F.rectest(); ', funcname))
        if status:
            # recursion error (?)
            out = out.split("\n")[-1]
        print indent(out)
        print sep


"""
python -mtimeit -v -n 1 -r 2 -s 'import flatten as F'
'print F.count_flatten_len(F.flatten(F.t5))'


Output from a single run:
========================================

$ python2.5 flatten.py
flatten_r
    raw times: 3.61 3.1
    1 loops, best of 2: 3.1 sec per loop
========================================
flatten2
    raw times: 0.58 0.545
    1 loops, best of 2: 545 msec per loop
========================================
flatten
    raw times: 1.81e-05 4.05e-06
    1 loops, best of 2: 4.05 usec per loop
========================================
========================================
recursion test
flatten_r
    RuntimeError: maximum recursion depth exceeded in cmp
========================================
flatten2
    RuntimeError: maximum recursion depth exceeded in cmp
========================================
flatten
    raw times: 0.283 0.3
    1 loops, best of 2: 283 msec per loop
========================================
"""

visualize.rb

2007-05-20T05:30:00.000-07:00

Here is a small script (visualize.rb) that helps me visualize the Structure of Ruby code. Before I jump into the source, I want to see the "big" picture of things. This script helps me with that. [There is a small bug with the script -- see the source for more details.]

Here it is being run on itself:

module Visualize
  class Construct
    def initialize
    def self.fromtree
    def to_a
    def same
    def merge
    def pp
  class SourceFile
    def initialize
    def collect_requires
    def collect_tokens
    class StatementModifier
      def initialize
    def mark_statement_modifiers
    def getname
    def gather
    def pp
    def merge
  class SourcePackage
    def initialize
    def pp
def opt?
def print_tokens
def main

And here is the code structure of Capistrano:

module Capistrano
  class ServerDefinition
    def initialize
    def <=>
    def eql?
    def hash
    def to_s
  class Command
    def self.process
    def initialize
    def process!
    def stop!
    def logger
    def open_channels
    def replace_placeholders
    def extract_environment
...
...
   class RemoteDependency
      def initialize
      def directory
      def writable
      def command
      def gem
      def or
      def pass?
      def message
      def try
def depend

convert.lisp

2007-05-16T22:30:00.000-07:00

I rewrote convert.rb in Common Lisp; [basically it allows you to convert files from one format to another -- say, PostScript files to PDF; I need this as I sometimes work on Windows machines but want read a online papers -- this runs as a CGI program on my personal server] you can get the whole thing here. It works under CMUCL version 19d. I had forgotten how much fun it is to write programs in Common Lisp! First, some HTML macros:

(progn
  (defmacro html-tag (tag attributes end-tag-p &body body)
    `(progn
       ,(if end-tag-p
            `(format t "<~A~{ ~A=~S~}>" ',tag  (list ,@attributes))
            `(format t "<~A~{ ~A=~S~}/>" ',tag (list ,@attributes)))
       (let ((result (multiple-value-list (progn ,@body))))
         (when (and (null (rest result)) (stringp (first result)))
           (princ (first result)))
         ,(when end-tag-p `(format t "</~A>" ',tag))
         (values))))
         
  (defmacro do-tag (tag &optional end-tag-p)
    `(defmacro ,tag (attributes &body body)
       `(html-tag ,',tag ,attributes ,',end-tag-p ,@body)))


  (do-tag html t)
  (do-tag head t)
  (do-tag title t)
  (do-tag h3 t)
  (do-tag form t)
  (do-tag input)
  (do-tag b t)
  (do-tag i t)
  (do-tag br)
  (do-tag a t)
  (do-tag hr)

  )

Next, we need to decode URLs:

(defvar *url-decoders*
  '(("24" . #\$)
    ("26" . #\&)
    ("2B" . #\+)
    ("2C" . #\,)
    ("2F" . #\/)
    ("3A" . #\:)
    ("3B" . #\;)
    ("3D" . #\=)
    ("3F" . #\?)
    ("40" . #\@)
    ("20" . #\Space)
    ("22" . #\")
    ("3C" . #\<)
    ("3E" . #\>)
    ("23" . #\#)
    ("25" . #\%)
    ("7B" . #\{)
    ("7D" . #\})
    ("7C" . #\|)
    ("5C" . #\\)
    ("5E" . #\^)
    ("7E" . #\~)
    ("5B" . #\[)
    ("5D" . #\])
    ("60" . #\`)
    ))


(defun decode-url (url)
  (flet ((quit () (return-from decode-url nil)))
    (with-output-to-string (out)
      (with-input-from-string (in url)
        (loop (let ((char (or (read-char in nil nil) (return))))
                (if (not (char= char #\%))
                    (princ char out)
                    (let ((next (or (read-char in nil nil) (quit))))
                      (if (char= next #\%)
                          (princ #\% out)
                          (let ((next2 (or (read-char in nil nil) (quit))))
                            (princ (or (cdr (assoc (concatenate 'string
                                                                (string next)
                                                                (string next2))
                                                   *url-decoders*
                                                   :test #'string-equal))
                                       (quit))
                                   out)))))))))))

Here is CGI-WELCOME & CGI-MAIN; they use the HTML macros defined above:

(defun cgi-main ()
  (flet ((get-params ()
           (let* ((qs (cdr (assoc :query_string ext::*environment-list*)))
                  (ps (and qs (position #\& qs)))
                  (parts (if ps
                             (list (subseq qs 0 ps) (subseq qs (1+ ps)))
                             (list qs)))
                  (params (mapcan (lambda (x)
                                    (let ((p (position #\= x)))
                                      (and p (list (cons (subseq x 0 p)
                                                         (subseq x (1+ p)))))))
                                  parts))
                  (url (cdr (assoc :url params :test #'string-equal)))
                  (zip-only (cdr (assoc :zip_only params :test #'string-equal))))
             (values (and url (plusp (length url)) (decode-url url))
                     (string-equal zip-only :on))))
         (print-cmds (cmd)
           ;; force-output to show user this info in their browser
           ;; while the command is still running -- works under Apache
           (princ "Running: ") (b () cmd) (br ()) (force-output))
         (print-cgi-header ()
           (let ((newline (coerce '(#\Return #\Newline) 'string)))
             (format t "Content-Type: text/html~A~A" newline newline))))

    (let ((original-dir (default-directory))
          (*shell-before* #'print-cmds)
          (url)
          (zip-only))
      (multiple-value-setq (url zip-only) (get-params))
      (print-cgi-header)
      (if (not url)
          (cgi-welcome)
          (letf (((default-directory) (tmpdir)))
            (html ()
              (head () (title () "convert.lisp"))
              (shell "wget -q '~A'" url)
              (multiple-value-bind (name error)
                  (ignore-errors (convert (or (newest)
                                              (error "couldn't download ~S" url))
                                          zip-only))
                (cond (error (princ "An error occurred: ")
                             (br ())
                             (b () (apply #'format nil
                                          (simple-condition-format-control
                                           error)
                                          (simple-condition-format-arguments
                                           error))))
                      (t (hr ())
                         (let ((base (subseq name
                                             (1+ (position #\/ name :from-end t)))))
                           (shell "cp ~A ~A/data/" base (namestring original-dir))
                           (data-file-link base)))))))))))

(defun cgi-welcome ()
  (html ()
    (head () (title () "convert.lisp"))
    (h3 () "convert.lisp -- convert files to different formats")
    (form (:method "get" :action "convert.sh")
      (princ "url: ")
      (input (:type "textfield" :name "url" :size 100))
      (princ " ")
      (input (:type "checkbox" :name "zip_only"))
      (princ "[zip only] ")
      (input (:type "submit" :value "Convert")))
    (h3 () "available converters [they are searched in order]:")
    (dolist (x *all-converter*)
      (multiple-value-bind (name cp exts doc cmds)
          (decode-converter x)
        (declare (ignore cp cmds))
        (b () (string-downcase name))
        (princ " -- ")
        (i () doc)
        (princ " [exts: ")
        (format t "~{~A~^, ~}" exts)
        (princ "]")
        (br ())))
    (h3 () "converted files [newest first]:")
    (let ((converted-files (mapcar (lambda (x) (cons (or (file-write-date x) 0) x))
                                   (ignore-errors (directory  "data/")))))
      (dolist (x (sort converted-files #'> :key #'car))
        (data-file-link (cdr x))
        (br ())))
    (br ())
    (br ())
    (a (:href "convert.lisp-txt") "{mysrc}")))

And finally, the SHELL function that executes the different programs needed to convert files:

(defvar *shell-before*)

(defun shell (cmd &rest args)
  (let ((cmd (apply #'format nil cmd args)))
    (when (boundp '*shell-before*) (funcall *shell-before* cmd))
    (ext:run-program "/bin/bash"
                     (list "-c" cmd))))

Dancing Links in Python

2007-05-07T23:45:00.000-07:00

Last December I was reading Knuth's Dancing Links paper and decided to implement the Algorithm X in Python.

Here is the description of Algorithm X from Wikipedia:

...is a recursive, nondeterministic, depth-first, brute-force algorithm that finds all solutions to the exact cover problem represented by a matrix A consisting of 0s and 1s.

It can be downloaded here.

# What is the matrix? It is a helper class
# for exact cover below.
class Matrix:
    def __init__(self, list_of_lists):
        self.m = [list_elt[:] for list_elt in list_of_lists]
        self.unique = object()

    def copy(self):
        new = Matrix(self.m)
        for r in new.m:
            for i in range(len(r)):
                if r[i] == self.unique:
                    r[i] = new.unique
        return new
    
    def delcol(self, i):
        for r in self.m:
            r[i] = self.unique

    def delrow(self, i):
        row = self.m[i]
        for j in range(len(row)):
            row[j] = self.unique

    def empty(self):
        for r in self.m:
            for x in r:
                if x != self.unique:
                    return False
        return True

    # Select first column with lowest number of 1s.
    # Also, returns the number of 1s found in the
    # column.
    def selcol(self):
        i = -1
        s = -1
        for colidx in range(len(self.m[0])):
            colitems = [r[colidx] for r in self.m]
            if all(x==self.unique for x in colitems):
                continue
            t = colitems.count(1)
            if s == -1 or t < s:
                s = t
                i = colidx
        return i, s

# == Algorithm X  ======================================================
                
class ExactCover:
    def X(self, matrix):
        if matrix.empty():
            return []

        result = self.__X(matrix.copy())
        if result:
            all_answers = []
            for answer in result:
                all_answers.append([matrix.m[rowidx]
                                    for rowidx in answer])
            return all_answers
        else:
            return []

    def __X(self, matrix):
        # 1. Select 1st column with lowest
        #    number of 0s.
        c, s = matrix.selcol()
        if s == 0:
            return []

        # 2. Pick rows that have 1s in the
        #    above column.
        possible_rows = [(i, r) for (i, r) in enumerate(matrix.m) if r[c] == 1]
        random.shuffle(possible_rows)
        
        answers = []
        # 3. For each such row:
        for rowidx, r in possible_rows:
            new = matrix.copy()

            for i, item in enumerate(r):
                # - pick columns that have 1s
                #   in them
                # 4. For each such col:
                if item == 1:
                    for j, item2 in enumerate([r[i] for r in new.m]):
                        # - delete rows that have a 1
                        #   in that column
                        if item2 == 1:
                            new.delrow(j)
                    # - delete that column
                    #   [this was a bug before;
                    #    it used to be above the
                    #    for loop right after the
                    #    "item == 1" expr]
                    new.delcol(i)

            if new.empty():
                answers.append([rowidx])
            else:
                # - recur on the sub-matrix
                result = self.__X(new)
                for x in result:
                    x.append(rowidx)
                    answers.append(x)

        return answers

        
# == Tests ==========================================

def test_exact_cover():
     e =  [[1, 0, 0, 1, 0, 0, 1],
           [1, 0, 0, 1, 0, 0, 0],
           [0, 0, 0, 1, 1, 0, 1],
           [0, 0, 1, 0, 1, 1, 0],
           [0, 1, 1, 0, 0, 1, 1],
           [0, 1, 0, 0, 0, 0, 1]]
     m = Matrix(e)
     res = ExactCover().X(m)
     if res == [[[0, 1, 0, 0, 0, 0, 1],
                 [0, 0, 1, 0, 1, 1, 0],
                 [1, 0, 0, 1, 0, 0, 0]]]:
         print "test pass"
     else:
         print "test fail"

N-based Python list

2007-04-23T14:01:00.000-07:00

Solving http://www.answermysearches.com/python-subclassing-list-to-make-it-n-based/251/ (with some light testing)

class n_based_list(list):
    def __init__(self, startidx, items):
        self.start = startidx
        list.__init__(self, items)

    def idx(self, i):
        return i - self.start

    def insert(self, i, x):
        return list.insert(self, self.idx(i), x)

    def pop(self, i):
        return list.pop(self, self.idx(i))

    def __getslice__(self, i, j):
        return list.__getslice__(self, self.idx(i), j)

    def _handle_slice(self, s):
        return slice(self.idx(s.start or self.start),
                     s.stop,
                     s.step)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return list.__getitem__(self, self._handle_slice(i))
        return list.__getitem__(self, self.idx(i))

    def __setitem__(self, i, x):
        if isinstance(i, slice):
            return list.__setitem__(self, self.handle_slice(i), x)
        return list.__setitem__(self, self.idx(i), x)

    def __delitem__(self, i):
        if isinstance(i, slice):
            return list.__delitem__(self, self._handle_slice(i))
        return list.__delitem__(self, self.idx(i))
    
    def enumerate(self):
        for i, elt in enumerate(self):
            yield i+self.start, elt
            
def test_n_based_list():
    l = n_based_list(1, ['a', 'b', 'c', 'd'])
    assert l[1] == 'a'
    assert l[0] == 'd' # yuck!
    assert l[2] == 'b'
    assert l[3] == 'c'
    assert l[4] == 'd'

    assert l.pop(1) == 'a'
    assert l == ['b', 'c', 'd']
    l.insert(1, 'a')
    assert l[1] == 'a'

    assert l[1:3] == ['a', 'b', 'c']
    assert l[1::2] == ['a', 'c']
    del l[::2]
    assert l == ['b', 'd']
    new_l = n_based_list(1, ['a', 'b', 'c', 'd'])
    assert list(new_l.enumerate()) == [(1, 'd'),
                                       (2, 'a'),
                                       (3, 'b'),
                                       (4, 'c')]

a merge problem

2007-04-12T13:28:00.000-07:00

from here: http://blog.dowski.com/2007/04/12/a-sorting-problem/

from collections import defaultdict

def my_order(ordered, others):
    tmp = defaultdict(list)
    losers = []
    # process others so that,
    # 'id_new', 'id_old' become
    # tmp['id'] = ['id_new', 'id_old']
    for o in others:
        p = o.rfind("_")
        if p == -1:
            losers.append(o)
        else:
            # if o is 'id_new',
            # o[:p] will be 'id'
            tmp[o[:p]].append(o)
    final = []
    for o in ordered:
        final.append(o)
        if o in tmp:
            final.extend(tmp[o])
    return final + losers

my_order(['id', 'age', 'zzyzx', 'bar', 'spam_eggs'],
         ['id_old', 'id_new', 'bar_foo', 'spam_eggs_ham'])

gives
['id', 'id_old', 'id_new', 'age', 'zzyzx',
 'bar', 'bar_foo', 'spam_eggs', 'spam_eggs_ham']

Fluid Strings

2007-03-18T17:27:00.000-07:00

I just completed a piece of software — one part of the software sends text messages to cell phones. Each text message consists of several fields. And each field has a maximum limit on how long it can be. So if a field is longer than its limit, then it is cutoff. However, if the field smaller than its limit, then all the other fields should take up space that this field "gives up" — so, other fields can become longer than their limits in the final output. Here is what I did:

class FluidString(object):
    
    def __init__(self, actual, limit, prefix="", suffix=""):
        self.actual = actual
        self.limit = limit
        self.prefix = prefix
        self.suffix = suffix

    def increase_limit_by(self, amt):
        self.limit += amt

    def __str__(self):
        # adding newline is a hack, specific for my app,
        # where I want each fluid string to be
        # contained in a seperate line

        t = len(self.prefix) + len(self.suffix)
        if self.limit < t:
            return self.actual[:self.limit]
        
        s = self.actual[:self.limit-1-t]
        return self.prefix + s + self.suffix + "\n"


    # returns non-negative integer:
    def chars_left_over(self):
        return max(self.limit - len(str(self)), 0)

Fluid strings are assembled by containers:

# right now just fits pieces fluidly;
# if any piece underflows, other pieces
# evenly get what's left over.

class Container(object):
    
    def __init__(self, *items):
        self.strings = list(items)
        
    def add(self, fs):
        self.strings.append(fs)
        
    # unused:
    def on_underflow_of(self, target, *fs_pairs):
        pass
    
    def render(self):
        # find fluid strings that are underflowing.
        # split all those free spaces among strings that
        # are likely to overflow.

        anyleft = [x.chars_left_over() for x in self.strings]
        freespace = sum(anyleft)
        
        # how many to split freespace with:
        # `if not x': it means that the fluid string
        # will likely overflow. so split space among
        # those likely to overflow
        count = anyleft.count(0) #sum(1 for i in anyleft if i==0)
        
        if freespace and count:
            amount = freespace / count
            for i, x in enumerate(self.strings):
                if not anyleft[i]:
                    x.increase_limit_by(amount)

        final = "".join(str(x) for x in self.strings)
        #assert len(final) == sum(x.limit for x in self.strings)
        return final

    @staticmethod
    def test():
        c = Container()
        c.add(FluidString("01234567890123456789", 10))
        c.add(FluidString("asdf", 20))
        c.add(FluidString("hello world how are you", 10))
        return c.render()

Here is an usage sample (it is also above):

    def test():
        c = Container()
        c.add(FluidString("01234567890123456789", 10))
        c.add(FluidString("asdf", 20))
        c.add(FluidString("hello world how are you", 10))
        return c.render()

The output is:

01234567890123456
asdf
hello world how a
[newline]

(Note how the first & third FluidString added, shows more than its limit allows it — extra 7 characters each + 2 newlines.)

The Computer Revolution Hasn't Happened Yet

2007-02-24T18:09:00.000-07:00

Notes of Alan Kay's 1997 OOPSLA talk via Lambda-the-Ultimate.

Alan Kay On OOP

As things become more and more complex,
the architecture will dominate material.

Learning is an act of creation.
Something happens to you that
wasn't there before.

When encountering a creative, novel idea.
Reaction by the user.
Metaphor

Joke -- ha ha.
Science -- Aha!
Art -- ahhh...

You need to have something
blue, to have blue thoughts.

23:00
HTML pre-supposes that there
should be a browser that should
understand its format.
(worst ideas since ms-dos!)
+ He is talking about executable
programs? Like lisp images.
You should read it in. It should
travel with the things it needs.

Why study of Biology is interesting?
Build a dog house. Now build something
similar, but 100 times larger.
Propotions will be unwieldly and
the thing collapes.
Not so for cells.
They can even grow by factors
of 1 millions. And so how do
they do this is important?
Because we want to build
complex computer systems --
which we haven't been able
to do.

39:00
Object can act as anything.
So they encapsulate a computer.
Useful: take a powerful thing
and not lose it but partitioning
it up.
[Java, C++ think that they are helping
the programmer by making this new
thing (oop) look like the old thing,
but they are hurting the programmer,
but making it difficult for the programmer
to understand what's really powerful
about this metaphor.]

45:00
Building Complex Systems.

59:00 We still don't know how to design,
build systems.

Let's not make what we don't know
into a religion!

We need to constantly think, think and
think about what's important.
And we have to our systems let us get
to the next levels of abstractions
as we come to them. (Earlier he
was talking about how there were
many different implementation of
Smalltalk when at Xerox. The old
implementation were good at bootstrapping
new implementations -- these new
implementations were built to support
the new abstractions Alan and his
collegues came to know about. And I
guess the dynamicsm of Smalltalk made
this possible.)

Squeak -- not an attempt to give the world
a free Smalltalk -- but an attempt to give
the world a bootstrapping mechanism much
better that smalltalk. SO when you play
with squeak -- think of how you can
obselete the damn thing!

Look for blue thoughts.
Play your system grand than what they
seem to be right now.

New import

2007-02-11T21:09:00.000-07:00

OK, imported all posts from http://89seasons.blogspot.com — hopefully nothing broke. If it did, please feel free to keep both the pieces!

orange4.py -- an interpreter for a Lisp like lang in Python

2006-12-09T15:01:00.000-07:00

Orange4.py [as text] implements a Lisp like language in Python. I make use of Python tuples to represent the source code. Here is the Y Combinator:

(using('ycomb x proc arg fact fnarg n'),
 (let, ((ycomb, (olambda, (x,),
                 ((olambda, (proc,),
                    (x, (olambda, (arg,), ((proc, proc), arg)))),
                  (olambda, (proc,),
                    (x, (olambda, (arg,), ((proc, proc), arg))))))),),
  (let, ((fact, (olambda, (fnarg,),
                  (olambda, (n,),
                    (oif, (eq, n, 0),
                          1,
                          (multiply, n,
                                     (fnarg, (minus, n, 1))))))),),
   (pr, "hi"),
   (pr, ((ycomb, fact), 10)),
   ((ycomb, fact), 10))))

Yeah, the syntax is UGLY, and to make this tuples-as-source work (since Python would complain about variables in "(olambda, (b, c, d), ...)", you have to say something like, "(using('b c d'), (olambda, (b, c, d), ...)". Also, you need to be careful about singleton tuples in Python: so you can't write "(let, ((a, 20)), ...)"; you need to say: "(let, ((a, 20),), ...)".

using is defined as:

class using:
    def __init__(self, string):
        for name in string.split():
            if name in globals():
                print "Warning: `%s' already defined, ignoring it" % name
            else:
                globals()[name] = var(name)

And here are EVAL and APPLY, named OEVAL and OAPPLY so that they don't conflict with the Python builtins of the same name:

def oeval(x, env=None):
    if trace: print 'oeval', x, env

    if isinstance(x, var):
        return env_lookup(x, env)
    elif not isinstance(x, tuple):
        return x

    if isinstance(x[0], using):
        x = x[1]

    fn   = x[0]
    args = x[1:]

    if fn == OIF:
        if oeval(args[0], env) == NIL:
            return oeval(args[2], env)
        else:
            return oeval(args[1], env)

    elif fn == OLAMBDA:
        return (CLOSURE, args[0], args[1:], env)

    elif fn == LET:
        bindings = args[0]
        newenv = dict((var.name, oeval(val, env))
                      for (var, val) in bindings)

        return oevalis(args[1:], [newenv, env])

    else: # function application
        # global env is the python global env,
        # so we don't need to evaluate fn (i think).
        return oapply(oeval(fn, env),
                      tuple(oeval(arg, env) for arg in args))

# since we are applying fns, args are evalled
def oapply(fn, args):
    def err(type):
        error("%s %s, %s" % (
            type,
            (fn.name if isinstance(fn, var) else fn),
            args))

    if not isinstance(fn, tuple):
        if fn == GT:
            if args[0] > args[1]:
                return TRUE
            return NIL

        elif fn == PR:
            print args[0]
            return NIL

        elif fn == PLUS:
            return args[0] + args[1]

        elif fn == MINUS:
            return args[0] - args[1]

        elif fn == EQ:
            # args should just be numbers
            if args[0] == args[1]:
                return TRUE
            return NIL

        elif fn == MULTIPLY:
            return args[0] * args[1]

        else:
            err("unknown function")

    # user-defined functions:
    elif fn[0] == CLOSURE:
        if trace: print 'calling closure', fn, args

        formal_params, body, env_when_defined = fn[1:]
        actual_params = args

        if len(formal_params) != len(actual_params):
            err("wrong number of args")
        newenv = dict(zip((x.name for x in formal_params),
                          actual_params))
        # lexical scoping
        return oevalis(body, [newenv, env_when_defined])

        # return oevalis(body, [newenv, env])
        # the above specifies dynamic scoping (i think!)
        # env, should be an env passed
        # to this oapply fn.

    else:
        err("unknown function")

readable MD5

2006-11-09T21:01:00.000-07:00

I've written an implementation of the MD5 algorithm mainly for human consumption. Most implementations that I've seen, seem to derive from the RFC's sample implementation, which is optimized for performance and so isn't that readable.

readable-md5.lisp [as text] [its written in Common Lisp and has been tested with CMUCL and CLisp]

...programs must be written for people to read, and only incidentally for machines to execute.
— Structure and Interpretation of Computer Programs

My first Ruby program

2006-10-28T13:05:00.000-07:00

I decided to learn Ruby and Rails — now I need to get books on both (damn that DHH and his contagious enthusiasm)

Below are some snippets from my first Ruby program: convert.rb. It is a CGI program, that converts PostScript, TeX, CWEB and a couple of other formats to PDF. It also converts .tar.gz, .tar.bz2 and other compressed files to .zip.

[Note: I wrote this program flipping back and forth between the PixAxe1 and a bunch of other online resources — so forgive me if it isn't in the spirit of Ruby.]

Ruby blocks are cool!!!

def ignore_errors &block
  begin
    block.call
  rescue Exception => e
    e
  end
end

def with_tmpdir &block
  result = nil
  original = Dir.pwd
  tmp = tmpname # creates a temporary name (not safe)
  begin
    Dir.mkdir tmp
    Dir.chdir tmp
    result = block.call original
  ensure
    Dir.chdir original
  end
  FileUtils.rm_rf tmp
  result
end

and it is quiet easy to create DSLs:

# converters operate like so:
# 3 args: first, a symbol naming the converter;
# second, a regexp that if matched the third arg
# is executed: which is a block that takes one
# argument -- a local filename
# the converter should return true or nil:
# true to continue and try other converters;
# nil to return -- as this is the final one.

defconverter(:ps, /\.ps$/) { | x |
  sh "ps2pdf #{x}"
  nil
}

defconverter(:cweb, /\.w$/) { | x |
  sh "cweave #{x} - #{x}.tex"
  sh "tex #{x}.tex"
  sh "dvips #{x}.dvi"
  sh "ps2pdf #{x}.ps"
  nil
}

Finally, CGI.rb's HTML output facility make the code elegant (I wish that, optionally, you could output to a stream...)

  cgi.out {
    cgi.html("PRETTY" => " ") {
      cgi.head { cgi.title { 'convert.rb' } } +
      cgi.body {
        cgi.h3 { 'convert.rb — convert file to PDF or ZIP' } +
        cgi.form('get', $0) {
        cgi.b { 'url:' } +
        cgi.text_field('url', '', 150) + ' ' +
        cgi.submit + cgi.br +
        cgi.checkbox('zipitup') + ' zip it up? ' +
        cgi.small { '[with this turned on, you can convert
                     unix archive formats (like .tar.gz, .tar.bz2,
                     ...) to .zip format]' }

      ...
      ...
      ...
      [snipped]

Here are some initial thoughts:

I was surprised at how easily and quickly I was able to develop the program
calling methods (those that don't take args and those that take a single arg) without parenthesis is quiet refreshing:
(Before this, looking at Ruby from the "outside", this convention was disturbing — "How do I pass a function to another function" — but I didn't encounter that problem with this program because it seems to me that you pass in closures (blocks) to other functions...)

compare method.to_a.to_s to method.to_a().to_s()
sh "rpm2cpio #{x} | cpio -dimv --no-absolute-filenames"
love the short, nicely named methods: FileUtils.rm_rf tmp
ability to specify integer as 100_000_000 is nice

flowering.py

2006-10-15T13:59:00.000-07:00

I've been playing with a Paint-like program on my 6600 (with Python for Series 60). The cool things is after I paint a picture, I can take a screenshot of it and use that image as the background for my phone. To paint the second pic (the first one is similar), you first gravitate (bounce ball), then pretend you are Bob Ross (hit zero key) (remember Bob Ross's paintings? occasionally, before starting, he would put an oval cut out over the actual canvas he was painting on — after he was done, he would remove the cutout and all of a sudden the painting itself would be oval shaped..), then realize that you really don't need to be him (hit zero key again) and finally start gravitating once again. Here are some flowerings:

The program, flowering.py isn't well polished:

# sri, oct 15, 2006
# under mit license
# used Nokia's ball.py example as reference implementation;
# Menu Key: allows you to select type of brush
# Exit: exit app
# Hash Key (#): take a pic
# Star Key (*): for fun!

import appuifw, graphics, e32
from key_codes import *

class Keyboard:
    def __init__(self):
        self.state = {}
        self.downs = {}

    def handle_event(self, event):
        code = event.get("scancode", False)
        if event["type"] == appuifw.EEventKeyDown:
            if not self.is_down(code):
                self.downs[code] = self.downs.get(code, 0) + 1
            self.state[code] = 1
        elif event["type"] == appuifw.EEventKeyUp:
            self.state[code] = 0

    def is_down(self, scancode):
        return self.state.get(scancode, 0)

    def pressed(self, scancode):
        if self.downs.get(scancode, 0):
            self.downs[scancode] -= 1
            return True
        return False

# --------------------------------------------------------------------

gravitate = False  # brush it a  bouncing ball
justpaint = False  # brush is a brush, OK?

def do_gravitate():
    global gravitate, justpaint
    gravitate = True
    justpaint = False
def do_justpaint():
    global justpaint, gravitate
    justpaint = True
    gravitate = False

appuifw.app.menu = [
    (u"Gravitate", do_gravitate),
    (u"Just paint", do_justpaint)
    ]
keyboard = Keyboard()

running = True
def quit():
    global running
    running = False
appuifw.app.exit_key_handler = quit

appuifw.app.screen = "full"
appuifw.app.body = c = appuifw.Canvas(
    event_callback=keyboard.handle_event)

call_me_bob_ross = 0
radius = min(c.size)/2
xcenter, ycenter = c.size[0]/2, c.size[1]/2

topleft = (xcenter-radius,
           ycenter-radius)
bottomright = (xcenter+radius,
               ycenter+radius)

# ball stuff:
position = [0, 0]
velocity = [0, 0]
acceleration = 0.05
gravity = 0.03

c_size = c.size
#oldposition = position

# ball color stuff:
coloridx = 0
allcolors = []
tmp = (0, 32, 64, 128, 255)
for r in tmp:
    for g in tmp:
        for b in tmp:
            allcolors.append((r, g, b))
allcolors_len = len(allcolors)

# --------------------------------------------------------------------

while running:
    coloridx += 1
    if coloridx >= allcolors_len:
        coloridx = 0

    c.point(position,
            allcolors[coloridx],
            width=15)

    if call_me_bob_ross%2 != 0:
        c.ellipse(((0,0), c.size),
                  outline=(255, 0, 0), # red,
                  width=1)

    e32.ao_yield()

    if gravitate:
        # -----------------------------------------------------
        velocity[0] *= 0.999
        velocity[1] *= 0.999
        velocity[1] += gravity
        oldposition = position
        position[0] += velocity[0]
        position[1] += velocity[1]

        if position[0] > c_size[0]:
            position[0] = c_size[0] - (position[0] - c_size[0])
            velocity[0] = -1.00 * velocity[0]
            velocity[1] =  1.00 * velocity[1]
        if position[0] < 0:
            position[0] = -position[0]
            velocity[0] = -1.00 * velocity[0]
            velocity[1] =  1.00 * velocity[1]
        if position[1] > c_size[1]:
            position[1] = c_size[1] - (position[1] - c_size[1])
            velocity[0] =  1.00 * velocity[0]
            velocity[1] = -1.00 * velocity[1]
        if position[1] < 0:
            position[1] = -position[1]
            velocity[0] =  1.00 * velocity[0]
            velocity[1] = -1.00 * velocity[1]

        if keyboard.is_down(EScancodeLeftArrow):
            velocity[0] -= acceleration
        if keyboard.is_down(EScancodeRightArrow):
            velocity[0] += acceleration
        if keyboard.is_down(EScancodeDownArrow):
            velocity[1] += acceleration
        if keyboard.is_down(EScancodeUpArrow):
            velocity[1] -= acceleration
        # -----------------------------------------------------
    else:
        # just paint
        if keyboard.is_down(EScancodeLeftArrow):
            position[0] -= 1
        if keyboard.is_down(EScancodeRightArrow):
            position[0] += 1
        if keyboard.is_down(EScancodeDownArrow):
            position[1] += 1
        if keyboard.is_down(EScancodeUpArrow):
            position[1] -= 1

    # common actions:
    if keyboard.pressed(EScancodeHash):
        if call_me_bob_ross%2 != 0:
            c.ellipse(((0,0), c.size),
                      outline=(255, 255, 255),
                      width=100)
        img = graphics.screenshot()
        img = img.resize((174, 143), keepaspect=1)
        img.save(u"E:\\screenshot.jpg")
    elif keyboard.pressed(EScancodeStar):
        c.clear()
    elif keyboard.pressed(EScancode0):
        call_me_bob_ross += 1

Sierpinski — in ASCII, in Python

2006-10-10T17:58:00.000-07:00

I wrote this in the fall of 2004 (I was taking a class with one of the best teachers I've ever had and she gave this as a bonus on an exam — this fractal was on her t-shirt and she asked its name). (this works under python 2.4)

>>> print_triangle(get_sierpinski(5))

                               /\
                              /__\
                             /\  /\
                            /__\/__\
                           /\      /\
                          /__\    /__\
                         /\  /\  /\  /\
                        /__\/__\/__\/__\
                       /\              /\
                      /__\            /__\
                     /\  /\          /\  /\
                    /__\/__\        /__\/__\
                   /\      /\      /\      /\
                  /__\    /__\    /__\    /__\
                 /\  /\  /\  /\  /\  /\  /\  /\
                /__\/__\/__\/__\/__\/__\/__\/__\
               /\                              /\
              /__\                            /__\
             /\  /\                          /\  /\
            /__\/__\                        /__\/__\
           /\      /\                      /\      /\
          /__\    /__\                    /__\    /__\
         /\  /\  /\  /\                  /\  /\  /\  /\
        /__\/__\/__\/__\                /__\/__\/__\/__\
       /\              /\              /\              /\
      /__\            /__\            /__\            /__\
     /\  /\          /\  /\          /\  /\          /\  /\
    /__\/__\        /__\/__\        /__\/__\        /__\/__\
   /\      /\      /\      /\      /\      /\      /\      /\
  /__\    /__\    /__\    /__\    /__\    /__\    /__\    /__\
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\


# under mit license
#! /usr/bin/env python
#
# N = 4:
#                /\
#               /__\
#              /\  /\
#             /__\/__\
#            /\      /\
#           /__\    /  \
#          /\  /\  /\  /\
#         /__\/__\/__\/__\
#        /\              /\
#       /__\            /__\
#      /\  /\          /\  /\
#     /__\/__\        /__\/__\
#    /\      /\      /\      /\
#   /__\    /  \    /__\    /__\
#  /\  /\  /\  /\  /\  /\  /\  /\
# /__\/__\/__\/__\/__\/__\/__\/__\
#
# N = 3:
#        /\
#       /__\
#      /\  /\
#     /__\/__\
#    /\      /\
#   /__\    /__\
#  /\  /\  /\  /\
# /__\/__\/__\/__\
#
# N = 2:
#    /\
#   /__\
#  /\  /\
# /__\/__\
#
# N = 1:
#  /\
# /__\
#
# N = 0: (trivial case)
#
import sys

# returns a list of lines where
# each line contains a 2-element list:
# a character and a position
def get_sierpinski(n):
    assert n >= 0

    if n == 0:
        return []

    if n == 1:
        return [[['/', 1], ['\\', 2]],                       #  /\
                [['/', 0], ['_', 1], ['_', 2], ['\\', 3]]]   # /__\

    # ok, a bit more complicated:
    # let's assemble top part and the bottom parts seperately
    # check out the N=4 example above
    # there are 3 big triangles: the top one sits on the "spikes"
    # of the bottom two.
    # but those 3 triangles are made of 3 smaller triangles,
    # where the top of the small triangle sits on the bottom
    # 2, and so on...
    top, bottom = [], []
    for line in get_sierpinski(n-1):
        t, bl, br = [], [], []
        for (character, start) in line:
            t.append([character, start+2**(n-1)])
            bl.append([character, start])       # left triangle
            br.append([character, start+2**n])  # right triangle
        top.append(t)
        bottom.append(bl + br)
    return top + bottom

def print_triangle(triangle):
    for line in triangle:
        current_column = 0
        for (character, start) in line:
            while current_column != start:
                sys.stdout.write(" ")
                current_column += 1
            sys.stdout.write(character)
            current_column += 1
        sys.stdout.write("\n")


if __name__ == "__main__":
    size = 3
    if sys.argv[1:]:
        size = int(sys.argv[1])
    print_triangle(get_sierpinski(size))

Google Calendar w/ Python on Nokia 6600

2006-10-07T19:58:00.000-07:00

I, recently: downloaded Python for my Nokia 6600 and also started using Google Calendar. After seeing Google Calendar's SMS interface I made it a little easier to use from my cell: (this works under nokia 6600 and python for s60 2nd edition, 1.3.1)

# under mit license
# Oct 6, 2006; sri
import appuifw, time, messaging

gcal_sms_addr = "48368"
monthnames = [u"Jan", u"Feb", u"Mar", u"Apr", u"May", u"Jun",
              u"Jul", u"Aug", u"Sep", u"Oct", u"Nov", u"Dec"]

def gsend(x):
    x = unicode(x)
    messaging.sms_send(gcal_sms_addr, x)
    print "Message sent\n", x

# spits out messages like
# "nov 2 2108 12:00pm try out ruby" to gcal
def create_new():
    now = time.time()
    year, month, day, hour, min = time.localtime(now)[:5]

    date = appuifw.query(u"Date:", "date", now)
    if date is None:
        return
    ttime = appuifw.query(u"Time:", "time", float(3600*hour+60*min))
    if ttime is None:
        return
    event = appuifw.query(u"Event:", "text")
    if not event:
        return

    year2, month2, day2 = time.localtime(date)[:3]
    hour2, sec2 = divmod(int(ttime), 3600)
    min2, _ = divmod(sec2, 60)

    if hour2 >= 12:
        ampm = "pm"
    else:
        ampm = "am"

    gevent = "%s %d %d %d:%02d%s %s" % (
        monthnames[month2-1],
        day2,
        year2,
        hour2,
        min2,
        ampm,
        event)
    gsend(gevent)

def next_event():
    gsend("next")
def todays_events():
    gsend("day")
def tommorows_events():
    gsend("nday")

def main():
    # Currently available Google calendar
    # actions via SMS
    menuitems = [(u"Create new", create_new),
                 (u"Next", next_event),
                 (u"Today's", todays_events),
                 (u"Tommorow's", tommorows_events)]
    
    sel = appuifw.popup_menu([x[0] for x in menuitems],
                             u"GCal actions")
    if sel is None:
        return
    menuitems[sel][1]()

if __name__ == "__main__":
    main()