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)
Showing posts with label python. Show all posts
Showing posts with label python. Show all posts
18 April 2009
Notes from Alex Martelli's talk @ Pycon 2009
My notes from Alex Martelli's talk @ Pycon 2009: video here.
10 April 2009
Mercurial & bitbucket
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:
06 April 2009
Guido van Rossum Python Quote
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
31 January 2009
palindromic pangram -- the simple way
# 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
27 January 2009
ITA software -- Sling Blade Runner
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 AA 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
01 December 2008
py.edit.js -- a simple Python editor in Javascript
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.
18 July 2008
Google challenge
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
13 April 2008
bowling.py
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()
08 February 2008
Email a directory
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()
12 December 2007
feedparser_debug.py
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)
28 November 2007
Just for fun: jumbled to un-jumbled
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)
22 June 2007
strftime helper
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...
17 June 2007
Extending Python's Interactive Interpreter
[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)
06 June 2007
flatten in Python
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
========================================
"""
07 May 2007
Dancing Links in Python
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:
It can be downloaded here.
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"
23 April 2007
N-based Python list
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')]
18 March 2007
Fluid Strings
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:
Fluid strings are assembled by containers:
Here is an usage sample (it is also above):
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.)
09 December 2006
orange4.py -- an interpreter for a Lisp like lang in Python
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")
15 October 2006
flowering.py
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
10 October 2006
Sierpinski — in ASCII, in Python
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))
Subscribe to:
Posts (Atom)