Lemon Candy and Dynamic Programming

Over at TheDailyWtf, hidden among some comments was an interesting dynamic programming problem:

Consider this problem:

George bought a sack of 100 pieces of candy at the store. 90 of the pieces are lemon flavored and ten are cherry flavored. Of the two, George prefers the lemon flavored candies.

Every day George randomly picks a piece of candy out of the bag. If it is lemon flavored, he eats it and puts the bag away for the next day.

But if the candy he chose is cherry flavored, he puts it back in the bag and then randomly picks a candy out of the bag and eats it regardless of the flavor. In other words, he’ll only put a piece of candy back at most once per day.

What are the odds that when one piece of candy remains, it will be lemon flavored?

I posed the problem at a company where I used to work. All but one person tried to do it recursively. The remaining person tried to do it using an Excel spreadsheet!!!

Maybe I (and some of the other posters on that thread) are morons, but Excel (or in my case, OpenOffice) seemed like a fine way to solve it, so I did.

Read more about the Lemon-Cherry problem, and download the speadsheets used to solve it

Advertisements

Git-svn clone the last few revisions

It can be awfully tempting to make some changes to an existing open-source project [1]. Some of that excitement diminishes when one realizes how long a git-svn clone will take on a large project repo, like Python. The gain git-svn gives you in terms of quick history lookup is taken as cost in the beginning.

Instead, we can do a “shallow-copy” to get the last few revisions. It seems that you need to use actual revisions numbers for the first argument to -r, but I could be wrong. I tried using HEAD~1000:HEAD

$ git-svn clone http://svn.python.org/projects/python/trunk/ python-dev -r 65000:HEAD.

If you find this is *still* taking too long, try canceling, changing into the directory and issue a:

$ git svn fetch

Good luck all!

Notes

  1. Finally got my first one into python, #4568: remove limitation in varargs callback example.

The Hassle of Unicode (and Getting On With It in Python)

Let’s face facts.

  1. Unicode is a hassle [1]
  2. Not using unicode is a hassle, especially if you have one of thoese “weirdo” languages, and *gasp*, you want to read text *in your own language*.

I was faced with a simple task.  Take some text, process it, and print out some results (in JSON).  This should be trivial, and in a world where programming
was invented by a multinational consortium, and designed from the first day to be compatible with all text, maybe it would be.  Instead we have a world with a rich history of mutual incompatibility.

Find out how I solved this in Python


Simple “object-db” using JSON and python-sqlite

As part of a much larger project, I have a group of “snapshots” of a complicated data structure.   I need to save these in a persistent way, and continue to have access to them, when needed.  My solution is to output the snapshots as JSON, and store them into a sqlite database*, where they will be persistent on disk as “jlobs” (json large objects).

This “sqlite as object-db”  has several advantages:

  1. atomic transactions,
  2. easy database replication,
  3. jlob can easily change format without affecting schema
  4. very light runtime requirements.

Building off of the sqlite3 manual, it is easy to see how to  extract the json back *out* of the database.

There are  drawbacks to this approach, of course:

  1. you’re responsible for building and maintaining tables indexing any queryable elements of your jlob, if you want to be able to access them using SQL.
  2. sql normalization purists will throw up when they look at your schema

(*Note: if you are on centos 5, and do not have access to Python 2.5, make sure that you install python-sqlite2, for example from one of these rpms) rather than updating your python-sqlite in place.  BAD THINGS WILL HAPPEN, including breaking yum. )

#!/usr/bin/python
import sys
if sys.version_info >= (2,5):
    import sqlite3
else:
    from pysqlite2 import dbapi2 as sqlite3

try:
    import json
except ImportError:
    import simplejson as json

sqlite3.register_converter("json", json.loads)

conn = sqlite3.connect(":memory:",   \
    detect_types=sqlite3.PARSE_DECLTYPES|sqlite3.PARSE_COLNAMES)
c = conn.cursor()
c.row_factory = sqlite3.Row  # fields by name
d = conn.cursor()  # normal row

json_string = json.dumps( dict(a=1,b=[1,2,3]))
conn.execute('''
    create table snapshot(
          id INTEGER PRIMARY KEY AUTOINCREMENT,
          mydata json);
    ''')
conn.execute('''
    insert into snapshot values
       (null, ?)''', (json_string,))

R1 = c.execute("select * from snapshot").fetchone()['mydata']
R2 = d.execute("select * from snapshot").fetchone()[1]
R3 = conn.execute("select * from snapshot").fetchone()[1]

assert R1==R2==R3 == {'a': 1, 'b': [1, 2, 3]}, "all should be equal"