Tuesday, June 25, 2013

A Django Management Command to Load CSV Data Into a Database Table




This code expects input data that looks like this:

First,Last,Age,Sex
John,Smith,26,Male
Jane,Doe,34,Female
              .
              .
              .

Assuming no irregular data, this sure is easy:

from django.core.management.base import BaseCommand, CommandError
from app.models import Profile
import csv

class Command(BaseCommand):
   def handle(self, *args, **options):
       self.stdout.write(args[0])

       with open(args[0], 'rb') as file:
           rows = csv.reader(file, delimiter=",", quotechar='"')

           for row in rows:

              if rows.line_num == 1:
                 continue

              row[3] = row[3].replace("\n", " ")

              print "First: " + row[0]
              print "Last:  " + row[1]
              print "Age:   " + row[2]
              print "Sex:   " + row[3]

              db_row = Profile(first=row[0], last=row[1], age=row[2], sex=row[3])
              db_row.save()

           # dump entire table
           for person in Profile.objects.all():
              print person


Wednesday, October 10, 2012

Linear Interpolation Calculator

Linear Interpolation
www.linterp.com Home Page


This tiny calculator is an easy way to perform linear interpolation. Once you arrive on the page you can do all of your data entry using the keyboard by using the Tab key to move between entry boxes.

The page is simple and uncluttered and offers a graphical proof of the result. The source is an example of HTML forms feeding variables into Javascript as well as basic use of the flot library (http://www.flotcharts.org/) which is built on top of jQuery. No effort has been made to validate entered values for size or legality.


Results Page

Monday, July 16, 2012

Chaco Plots Using PySide Qt Bindings with Widgets in a QVBoxLayout


This small example builds on the example found at:
http://caethan.wordpress.com/2011/09/05/chaco-plots-in-pyside/

This example can be extended to easily include multiple plots and the adjustment of
plot parameters using spin boxes.

#!/usr/bin/python

import sys
from numpy import *
from PySide.QtCore import *
from PySide.QtGui import *

app = QApplication(sys.argv)

from traits.etsconfig.etsconfig import ETSConfig
ETSConfig.toolkit = "qt4"
from enable.api import Window
from chaco.api import ArrayPlotData, Plot

class Viewer(QMainWindow):
    def __init__(self):
        QMainWindow.__init__(self)
        self.mainWidget = QWidget(self) # dummy widget to contain layout manager
        self.plotview = Plotter(self)
        self.setCentralWidget(self.mainWidget)

        self.amplitudeLabel = QLabel("Amplitude: ")
        self.amplitudeSpinBox = QDoubleSpinBox()
        self.amplitudeSpinBox.setRange(-1000000.00, 1000000.00)
        self.amplitudeSpinBox.setValue(1.00)
 
        self.plotButton = QPushButton("Plot")
        self.plotButton.clicked.connect(self.update) 
                
        self.statusBar().showMessage('Ready to rock!')
        self.setWindowTitle('sin(x)')

        x = arange(100)
        y = zeros(100) 
        self.plotview.update_data(x, y)

        layout = QVBoxLayout(self.mainWidget)
        layout.addWidget(self.amplitudeLabel)
        layout.addWidget(self.amplitudeSpinBox)
        layout.addWidget(self.plotButton)
        layout.addWidget(self.plotview.widget)
        self.setLayout(layout)

     
    def update(self):
        print "Ok"
        print self.amplitudeSpinBox.value()
        x = arange(200)
        y = self.amplitudeSpinBox.value() * sin(x)
        self.plotview.update_data(x, y)
    

class Plotter():
    def __init__(self, parent):
        self.plotdata = ArrayPlotData(x=array([]),  y=array([]))
        self.window = self.create_plot(parent)
        self.widget = self.window.control
        

    def update_data(self, x, y):
        self.plotdata.set_data("x", x)
        self.plotdata.set_data("y", y)

    def create_plot(self, parent):
        plot = Plot(self.plotdata, padding=50, border_visible=True)
        plot.plot(("x", "y"), name="data plot", color="green")
        return Window(parent, -1, component=plot)


if __name__ == "__main__":
    plot = Viewer()
    plot.resize(600, 400)
    plot.show()
    sys.exit(app.exec_())


Sunday, June 3, 2012

golang goroutine Example Sample Code



I don't think basic use of pthreads is that different in complexity from goroutines but it's neat to see lightweight threads as a built-in language feature. goroutine usage superficially looks a lot like costates in Dynamic C, a proprietary nonstandard compiler for the Rabbit series of Z80 derived CPUs from Digi International. It's a really useful feature on a single core 8-bit microcontroller that frees you having "one big loop" with brittle timing in an embedded application.

Code:

package main

import (
"fmt"
"runtime"
"time"
)


func thread1(counter chan int) {
count := 0
for {
fmt.Println("Hello from thread 1")
runtime.Gosched() // force yield
time.Sleep(5 * time.Second)

count++
counter <- count
}
}

func thread2(counter chan int) {
count := 0
for {
 fmt.Println("Hello from thread 2")
 runtime.Gosched() // force yield
 time.Sleep(5 * time.Second)

 count++
 counter <- count
}
}

func main() {
c1 := make(chan int)
c2 := make(chan int)

go thread1(c1)
go thread2(c2)

for {
  count1 := <-c1
  count2 := <-c2
  fmt.Println("main() is alive ", count1, count2)
   time.Sleep(5 * time.Second)
 runtime.Gosched() // force yield
}
}

Output:

Hello from thread 1
Hello from thread 2
Hello from thread 1
Hello from thread 2
main() is alive  1 1
Hello from thread 2
Hello from thread 1
main() is alive  2 2
main() is alive  3 3
Hello from thread 2
Hello from thread 1
main() is alive  4 4
Hello from thread 2
Hello from thread 1
main() is alive  5 5
Hello from thread 2
Hello from thread 1
main() is alive  6 6
Hello from thread 1
Hello from thread 2




Tour golang Exercise: Maps #45 WordCount Solution



This exercise from the golang tour asks for a function that will count the number of times each word appears in a string. I think of it as using a hash to contain a histogram of word frequency. The if/else could be tighter if go had a ternary operator.


Code:


package main

import "strings"
import "fmt"

func WordCount (s string) map[string]int {

    substrs := strings.Fields(s)
    fmt.Println(substrs)

    // key,value  ==> word,count
    // iterate over substrs, if key in map, value++, else create

    counts := make(map[string]int)

    for _, word := range substrs {
        _, ok := counts[word]

        if ok == true {
          counts[word] += 1
        } else {
          counts[word] = 1
        }
    }

    return counts
}

func main() {
  fmt.Println(WordCount("now is the now is the go go go it a a a a a"))
  fmt.Println(WordCount("1 2 3 11 22 33 1 2 3"))
}

Output:

[now is the now is the go go go it a a a a a]
map[now:2 the:2 go:3 a:5 is:2 it:1]
[1 2 3 11 22 33 1 2 3]
map[2:2 33:1 1:2 11:1 22:1 3:2]

Common Error:

./wordcount2.go:20: cannot convert true to type int
./wordcount2.go:20: invalid operation: ok == true (mismatched types int and bool)

This occurs when attempting: 

    ok := counts[word]

Instead of:
    
    _, ok := counts[word]

Monday, May 28, 2012

How to Drill a Hole in a Golf Ball Perfectly

1935 South Bend Heavy 9x48

Holding a golf ball for drilling is pretty difficult with common tools. The ball wants to pop out of clamps and vises. One quick and dirty solution is to drill a hole smaller than the diameter of the ball in a board and hold the ball in place using the board and your foot.

You can also build a small box to easily hold a ball for drilling at the bench vise or drill press using this concept. If you are able to hit the center of the portion of the ball exposed by the hole you will get a decent hole.

But if you want a perfectly balanced ball, you want a dead center hole. And the easiest way to drill a dead center hole is hold the ball in a three jaw chuck in a lathe. I cranked down pretty tightly on the chuck and the ball still wanted to pull out of the jaws unless the lathe was in reverse when withdrawing the drill bit. There just isn't very much contact surface.

Be sure to get solid core balls for safety, liquid core balls can eject liquid under high pressure.


Tuesday, May 22, 2012

Parse XML with Nokogiri then remove tags

Galloping Ghost of the Japanese Coast


Let's say you have an XML document containing authors.

The Nokogiri tutorial tells you can do this:

   authors = doc.xpath("//author")

And it shows you will get output like this:

   <author>Kernighan</author>
   <author>Ritchie</author>
   <author>Matsumoto</author>

How do you get rid of all those tags?

Instead of reading the Nokogiri documentation like I should have, I tried to further process this output.

A regex worked fine but you have to worry about exceptions if there are no matches. And it's ugly.

doc = Nokogiri::XML(body)

auths = []
authors = doc.xpath("//author")

for i in 0..authors.length - 1
  auths[i] = /.*<author>(.*)<\/author>.*/.match(author[i].to_s)[1]
end

I also tried string substitution, which also worked fine. I didn't test a no match case.

doc = Nokogiri::XML(body)

auths = []
authors = doc.xpath("//author")

for i in 0..authors.length - 1
  auths[i] = author[i].to_s.sub("<author>","").sub("</author>","")
end

I knew I was parsing already parsed data and thought there should be an option to suppress the tags. I received some good advice to look more closely at Nokogiri and I came up with this approach of popping Nodes off of the NodeSet.

If you need know how many Nodes there were originally you have to save a copy before the first pop.

doc = Nokogiri::XML(body)

auths = []
authors = doc.xpath("//author")    

while authors.length() > 0
  auths << authors.pop().inner_text()
end

I think there might be an approach where you can iterate over the NodeSet without worrying about length and without using pop() but I haven't figured it out yet.


Sunday, February 12, 2012

Precise Installation of a Drawer Knob on a Shaker Style Drawer Front in 6 Steps






Step 1 - Set a machinist adjustable parallel to half the vertical height: 1 1/4".




Step 2 - Use the parallel to mark the horizontal center line.




Step 3 - Use a machinist's 6" scale to mark the vertical center line.




Step 4 - Use an awl to make a center punch mark.




Step 5 - Use a brad point drill and a power drill to drill a clearance hole.
Cover the drill fixture will masking tape to protect the finish.




Step 6 - Install knob. Repeat N times.




NOTE - The drill fixture shown is a PORTALIGN from Sears. These have not been made in decades. It really creates a terrific portable drill press. All of the adjustable products that available today that look similar are complete junk. Taking off the drill chuck is pretty difficult so this Sears industrial 3/8" drill made by DeWalt is dedicated to the PORTALIGN.

Monday, January 2, 2012

Word autocorrect can be a lot like emacs abbrev-mode


Tired of typing the same stock phrases over and over again in Word? You can use a stand-in word and global search and replace when your document is finished but it's a lot more fun to watch Word automatically type for you.

For example, if you add an entry to your autocorrect dictionary as shown above, every time you type the key qnato, Word will instantly replace it with North American Treaty Organization just like emacs abbrev-mode.

If you have different groups of abbreviations for different kinds of writing you can prefix them all with the same letter or number and they will stay grouped and separate in the Word autocorrect dictionary.

Some general ideas for using this would be:

   @gg = @gmail.com
   @yy = @yahoo.com
   @me = your.name@bigcorp.com

You can also highlight an entire block of text and the entire block including all formatting can be assigned to an autocorrect  key. This would be useful for having various signature blocks, addresses and boilerplate sentences and paragraphs for business letters.

And the last thing you can do is select a photo or picture in a Word document and add an autocorrect key for it. For example if you paste a picture of The Dude into your document and add the key dude for it, every time you type dude, a picture of The Dude will be inserted.

Teachers can use this for easy clip art insertion. Any bit of art that is regularly being inserted into your documents can be assigned to a key.

You can build a dictionary with an image for every number and letter if you want for puzzle construction.

If it turns out that this a seldom used feature of autocorrect I would worry about normal.dot corruption if the images are large, especially since the art is probably stored in normal.dot.

Sunday, January 1, 2012

Samsung SyncMaster 204B Power Supply Repair

Samsung SyncMaster 204B PSU PCB


The SyncMaster 204B is a very nice 20.1" UXGA (1600x1200) panel circa 2006.
I really like this aspect ratio but everything has gone widescreen and a monitor like this is basically no longer available.

The CapXon caps bulge and fail and before complete failure the monitor flickers more and more since the caps are on the switching power supply that powers the backlights. I think only the three caps after the chopper were bulging on this unit.

See: http://en.wikipedia.org/wiki/Capacitor_plague

Opening the monitor is a PITA and you don't want to do it twice so replace all the caps the first time. Use flush cutting side cutters to cut away as much of the leads and solder as you can. Solder wick rubbed with flux and pressed into what remains will loosen the caps to the extent that they will almost fall off the PCB.

More info:

http://tinymicros.com/wiki/Samsung_SyncMaster_204B_LCD_Repair

A proper parts list is a stumbling block for some people. These parts are perfect for my board rev 0.1 as of December 2011. These are not the cheapest possible parts but the parts with the longest lifetime ratings.

Digi-key part numbers



Thursday, September 29, 2011

Prox on, Prox off: Windows Proxy On, Windows Proxy Off with PowerShell



These four files will give you the ability to switch between
having a proxy server set in Windows and not having one set 
without having to navigate a bunch of windows each time. 

Because Windows won't allow a PowerShell script to execute by 
default the scripts are called using batch files so the execution 
policy can be altered before and after calling the script.


proxyon.ps1:

set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name MigrateProxy -value 1
set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name ProxyEnable -value 1
set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name ProxyHttp1.1 -value 0
set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name ProxyServer -value 'http://10.1.10.109:3128'
set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name ProxyOverride -value '<local>'

proxyoff.ps1:

set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name MigrateProxy -value 1
set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name ProxyEnable -value 0
set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name ProxyHttp1.1 -value 0
set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name ProxyServer -value ''
set-itemproperty 'HKCU:\Software\Microsoft\Windows\CurrentVersion\Internet Settings' -name ProxyOverride -value '<local>'



poff.bat:
 
powershell {Set-ExecutionPolicy Unrestricted}
powershell "& C:\proxyoff.ps1"
powershell {Set-ExecutionPolicy Restricted}

pon.bat:

powershell {Set-ExecutionPolicy Unrestricted}
powershell "& C:\proxyon.ps1"
powershell {Set-ExecutionPolicy Restricted}
 

Thursday, August 18, 2011

Set Windows Network Settings From The Command Line Using Net Shell (netsh.exe)


If you are changing network settings repeatedly on a test system it gets old having to point and click each time. Net Shell (netsh.exe) can be called as follows from the command line:

   netsh interface ipv4 set address name="Local Area Connection" dhcp HOST_IP
   SUBNETMASK GATEWAY_IP


For example:

   netsh interface ipv4 set address name="Local Area Connection" 10.0.0.2   
   255.255.255.0 10.0.0.1

Typing this over and over will get old as well so you can make a simple batch file called
ip.bat containing:

   netsh interface ipv4 set address name="Local Area Connection" %1 %2 %3 %4

Now you can type:

   ip [dhcp | static] HOST_IP SUBNETMASK GATEWAY_IP

For example:

   ip dhcp 10.0.0.2 255.255.255.0 10.0.0.1


Of course you can just create individual batch files for each test scenario.





Dell Laptop Power Jack Repair


A common problem with laptops is that the power receptacle on the mainboard stops making a reliable connection to the barrel connector on the power brick.  Often this leads to intermittent battery charging unless the connector is in just the "right" position. Eventually the connector fails completely and the laptop will not power on.

The entire job took about three hours. Getting to the connector to desolder it is a bear. A complete disassembly was required. Thus the mountain of parts in the right side of the photo.

Some newer laptops have daughterboards containing the power receptacle so that desoldering is not necessary. Not having good desoldering equipment made it difficult to get the through holes in the mainboard clean and ready for a new connector but a cheap solder sucker and solder wick eventually did the trick.

If your laptop is worth less than the cost of a professional repair, give it a try. If your laptop is worth much more I would leave this repair to the professionals.

Friday, August 5, 2011

MIT 6.00 Problem Set 8 - Problem 2


The problem statement does not mention sorting. But sorting the entire dict would be helpful. And the comparator could be used with sorted() but since there is no mention of sorting the data set I leave it unsorted.  So this may be a completely wrong approach but I take two tuples at a time and whichever is best is added to the solution set where best is judged by the comparator.

Python Code:

def greedyAdvisor(subjects, maxWork, comparator):
    schedule = {} # initial solution
    firstSubject = {}
    odd = True
    work = 0    
    test = subjects.copy()
    for key in subjects.keys():
        if odd == True:
            firstSubject = subjects[key]
            odd = False
        else:
            odd = True
            if comparator(firstSubject, subjects[key]):
                if work + firstSubject[WORK] <= maxWork:
                    schedule[key] = firstSubject
                    work += firstSubject[WORK]
            else:
                if work + subjects[key][WORK] <= maxWork:
                    schedule[key] = subjects[key]
                    work += subjects[key][WORK]

    if test != subjects:
        print "SUBJECTS MUTATED"

    return schedule
Output:
cmpValue
Course  Value   Work
======  ====    =====
12.05   7       1
14.01   6       1
22.12   10      18
6.09    8       4
7.11    7       4
7.15    3       3
7.17    10      1
7.19    10      5
8.10    4       6
8.14    3       7
8.18    4       10

Total Value:    72
Total Work:     60

cmpWork
Course  Value   Work
======  ====    =====
12.03   2       1
14.01   6       1
22.12   8       15
6.09    8       4
7.11    7       4
7.15    3       3
7.17    10      1
7.19    10      2
8.10    4       6
8.14    3       7
8.16    2       6
8.18    4       10

Total Value:    67
Total Work:     60

cmpRatio
Course  Value   Work
======  ====    =====
12.03   2       1
12.05   7       1
14.01   6       1
22.12   10      18
6.09    8       4
7.02    3       2
7.11    7       4
7.15    3       3
7.17    10      1
7.19    10      2
8.14    3       7
8.16    2       6
8.18    4       10

Total Value:    75
Total Work:     60

MIT 6.00 Problem Set 8 - Problem 1

Python Code:

def loadSubjects(filename):
    catalog = {}
    inputFile = open(filename)
    for line in inputFile:        
        line = string.strip(line)
        lineList = string.split(line, ',')

        lineList[1] = int(lineList[1])
        lineList[2] = int(lineList[2])
        catalog[lineList[0]] = lineList[1:]
    return catalog

Wednesday, July 27, 2011

MIT 6.00 Lecture 8 - Stirling's approximation


Approximating large factorials:

import math

def stirling(n):
    return math.sqrt(2*math.pi*n) * (n/math.e)**n

if __name__ == '__main__':
    for i in range(1,20):
        s = stirling(i)
        f = math.factorial(i)
        print "stirling: %21.2f  factorial: %21d  error: %3.2f%%" % (s, f, abs(((f-s)/s)*100.0))

Output:

stirling:                  0.92  factorial:                     1  error: 8.44%
stirling:                  1.92  factorial:                     2  error: 4.22%
stirling:                  5.84  factorial:                     6  error: 2.81%
stirling:                 23.51  factorial:                    24  error: 2.10%
stirling:                118.02  factorial:                   120  error: 1.68%
stirling:                710.08  factorial:                   720  error: 1.40%
stirling:               4980.40  factorial:                  5040  error: 1.20%
stirling:              39902.40  factorial:                 40320  error: 1.05%
stirling:             359536.87  factorial:                362880  error: 0.93%
stirling:            3598695.62  factorial:               3628800  error: 0.84%
stirling:           39615625.05  factorial:              39916800  error: 0.76%
stirling:          475687486.47  factorial:             479001600  error: 0.70%
stirling:         6187239475.19  factorial:            6227020800  error: 0.64%
stirling:        86661001740.60  factorial:           87178291200  error: 0.60%
stirling:      1300430722199.47  factorial:         1307674368000  error: 0.56%
stirling:     20814114415223.14  factorial:        20922789888000  error: 0.52%
stirling:    353948328666101.12  factorial:       355687428096000  error: 0.49%
stirling:   6372804626194313.00  factorial:      6402373705728000  error: 0.46%
stirling: 121112786592294176.00  factorial:    121645100408832000  error: 0.44%

As n increases the error decreases:

n=165 error: 0.0505177446%
n=166 error: 0.0502133452%
n=167 error: 0.0499125922%
n=168 error: 0.0496154204%
n=169 error: 0.0493217663%

MIT 6.00 Lecture 8 Notes on exp()


In Lecture 8 a recursive algorithm for finding a to the b is shown. The algorithm flip-flops between two cases (even, odd) until it reaches the base case of b == 0. For odd cases the problem is reduced by one, for even cases the problem is reduced by half.

I think it can be hard to see where the final result comes from at first. What can exp() return? It can return 1, a or *a. 1 is returned for the edge case b == 0 so returning a or *a are the typical results. Any particular result is going to be of the form:

result = a*a*a .  .  .


For 2**15:

    exp3(2,15)
2*exp3(2,14)
    exp3(4,7)
4*exp3(4,6)
    exp3(16,3)
16*exp3(16,2)
    exp3(256,1)
b == 1
a: 256
result: 32768


result = 2*4*16*256 => 32768

Also notice that in the below code that the even test is (b%2)*2 == 0 not == b.

Python Code:

def exp(a,b,mult):
    print "Call %d*exp3(%d,%d)" % (mult,a,b)
    if b == 0:
        print 'b == 0'
        return 1

    if b == 1:
        print 'b == 1'
        print "a: %d" % (a)
        return a

    if (b%2)*2 == 0:
        print '\tif (b%2)*2 == 0: ',
        print "[b: %d]" % (b)
        return exp(a*a, b/2, 1)
    else:
        print "\telse              [b: %d]" % (b)
        return a*exp(a, b-1, a)

if __name__ == '__main__':
    for i in range(0,16):
        print "===> 2^%d" % (i)
        print "result: %d\n" % exp(2,i,1)

'''
exp(2,4)
  exp(2*2, 4/2)
    exp(4*4, 2/2)
    b == 1
    return 16

==> 16

exp(2,5)
  2*exp(2, 5-1)
    exp(2*2, 4/2)
      exp(4*4, 2/2)
        b == 1
        return 16

==> 16 * 2 = 32

exp(2,6)
  exp(2*2, 6/2)
    4*exp(4, 3-1)
      exp(4*4, 2/2)
        b == 1
        return 16

==> 16 * 4 = 64          
'''

Output:

===> 2^0
Call 1*exp3(2,0)
b == 0
result: 1

===> 2^1
Call 1*exp3(2,1)
b == 1
a: 2
result: 2

===> 2^2
Call 1*exp3(2,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(4,1)
b == 1
a: 4
result: 4

===> 2^3
Call 1*exp3(2,3)
        else              [b: 3]
Call 2*exp3(2,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(4,1)
b == 1
a: 4
result: 8

===> 2^4
Call 1*exp3(2,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 16

===> 2^5
Call 1*exp3(2,5)
        else              [b: 5]
Call 2*exp3(2,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 32

===> 2^6
Call 1*exp3(2,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(4,3)
        else              [b: 3]
Call 4*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 64

===> 2^7
Call 1*exp3(2,7)
        else              [b: 7]
Call 2*exp3(2,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(4,3)
        else              [b: 3]
Call 4*exp3(4,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(16,1)
b == 1
a: 16
result: 128

===> 2^8
Call 1*exp3(2,8)
        if (b%2)*2 == 0:  [b: 8]
Call 1*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 256

===> 2^9
Call 1*exp3(2,9)
        else              [b: 9]
Call 2*exp3(2,8)
        if (b%2)*2 == 0:  [b: 8]
Call 1*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 512

===> 2^10
Call 1*exp3(2,10)
        if (b%2)*2 == 0:  [b: 10]
Call 1*exp3(4,5)
        else              [b: 5]
Call 4*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 1024

===> 2^11
Call 1*exp3(2,11)
        else              [b: 11]
Call 2*exp3(2,10)
        if (b%2)*2 == 0:  [b: 10]
Call 1*exp3(4,5)
        else              [b: 5]
Call 4*exp3(4,4)
        if (b%2)*2 == 0:  [b: 4]
Call 1*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 2048

===> 2^12
Call 1*exp3(2,12)
        if (b%2)*2 == 0:  [b: 12]
Call 1*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 4096

===> 2^13
Call 1*exp3(2,13)
        else              [b: 13]
Call 2*exp3(2,12)
        if (b%2)*2 == 0:  [b: 12]
Call 1*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 8192

===> 2^14
Call 1*exp3(2,14)
        if (b%2)*2 == 0:  [b: 14]
Call 1*exp3(4,7)
        else              [b: 7]
Call 4*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 16384

===> 2^15
Call 1*exp3(2,15)
        else              [b: 15]
Call 2*exp3(2,14)
        if (b%2)*2 == 0:  [b: 14]
Call 1*exp3(4,7)
        else              [b: 7]
Call 4*exp3(4,6)
        if (b%2)*2 == 0:  [b: 6]
Call 1*exp3(16,3)
        else              [b: 3]
Call 16*exp3(16,2)
        if (b%2)*2 == 0:  [b: 2]
Call 1*exp3(256,1)
b == 1
a: 256
result: 32768

Monday, July 25, 2011

MIT 6.00 Problem Set 6 - Problem 5

LPG Delivery, Seoul

Assume worst case. pick_best_word() is going to produce 13699 candidate words to be checked against the dictionary. pick_best_word_faster() is going to produce 127 candidate words to be checked against the dictionary.

The original word list is length 83667 while the rearranged word list is length 69091. The reduction in length is from the collapse of sets of words made from the same letters into single words.

I think the bulk of the performance improvement is from the reduction in candidate words, not dictionary length or access methods.


Python Output:


>>> len(list(itertools.permutations('abcdefg', 7)))
5040
>>> len(list(itertools.permutations('abcdefg', 6)))
5040
>>> len(list(itertools.permutations('abcdefg', 5)))
2520
>>> len(list(itertools.permutations('abcdefg', 4)))
840
>>> len(list(itertools.permutations('abcdefg', 3)))
210
>>> len(list(itertools.permutations('abcdefg', 2)))
42
>>> len(list(itertools.permutations('abcdefg', 1)))
7
>>> 5040+5040+2520+840+210+42+7
13699

>>> len(list(itertools.combinations('abcdefg', 7)))
1
>>> len(list(itertools.combinations('abcdefg', 6)))
7
>>> len(list(itertools.combinations('abcdefg', 5)))
21
>>> len(list(itertools.combinations('abcdefg', 4)))
35
>>> len(list(itertools.combinations('abcdefg', 3)))
35
>>> len(list(itertools.combinations('abcdefg', 2)))
21
>>> len(list(itertools.combinations('abcdefg', 1)))
7
>>> 1+7+21+35+35+21+7
127

MIT 6.00 Problem Set 6 - Problem 4 Answer

Anhinga, Florida Everglades

This code is roughly twice as fast as the code from Problem 3. Two changes are responsible for the increased speed.

The first change is the switch from itertools.permutations() to itertools.combinations(). In Problem 3 every permutation of n letters is checked against the dictionary. Since order doesn't mater with a sorted dictionary key permutations would be redundant.


Python Code Answer:

def pick_best_word_faster(hand, rearrange_dict):
    score = 0
    high_word = ""
    perms = []
    attempts = 0
    local_hand = []

    # itertools.permutations is iterating for letters
    # that are zero count in the hash, dump the zeros
    # convert dict to list
    for k in hand.keys():
        if hand[k] > 0:
            for i in range(hand[k]):
                local_hand.append(k)

    print "local_hand: "
    print "\t",
    print local_hand
    print

    take = len(local_hand)
    
    # try for a bingo, then one less than a bingo, etc.
    while take != 0:
        perms = list(itertools.combinations(local_hand, take))
        take -= 1
    
        for letter_list in perms:
            attempts += 1
            sorted_word = ''.join(sorted(letter_list))

            if rearrange_dict.get(sorted_word, 0):         
                word = rearrange_dict[sorted_word]       
                if score < points_dict[word]:
                    score = points_dict[word]
                    high_word = word
                    print "word: %s  score: %d" % (high_word, score)

    print "------------------------------------------------------------"
             
    print "attempts: %d" % (attempts)
       
    if score < 1:
        return '.'
    else:
        return high_word



def get_word_rearrangements(word_list):
    d = {}

    for word in word_list:
        d[''.join(sorted(word))] = word

    return d


Output:


d g i i z m t
calling with:
        {'d': 1, 'g': 1, 'i': 2, 'z': 1, 'm': 1, 't': 1}
local_hand:
        ['d', 'g', 'i', 'i', 'z', 'm', 't']

word: digit  score: 7
word: timid  score: 8
word: ditz  score: 14
------------------------------------------------------------
attempts: 127
0.0350000858307
Score: 400.00  Total Score: 400.00
Turn took 0.04 seconds, 0.31 seconds remaining

g i m
calling with:
        {'d': 0, 'g': 1, 'i': 1, 'z': 0, 'm': 1, 't': 0}
local_hand:
        ['g', 'i', 'm']

word: mig  score: 6
------------------------------------------------------------
attempts: 7
0.0209999084473
Score: 285.72  Total Score: 685.71
Turn took 0.02 seconds, 0.29 seconds remaining

Final Score: 685.71



a c e j m n n
calling with:
        {'a': 1, 'c': 1, 'e': 1, 'j': 1, 'm': 1, 'n': 2}
local_hand:
        ['a', 'c', 'e', 'j', 'm', 'n', 'n']

word: nance  score: 7
word: mace  score: 8
word: jean  score: 11
word: jam  score: 12
------------------------------------------------------------
attempts: 127
0.0339999198914
Time limit exceeded.
Score: 0.00  Total Score: 0.00

c e n n
calling with:
        {'a': 0, 'c': 1, 'e': 1, 'j': 0, 'm': 0, 'n': 2}
local_hand:
        ['c', 'e', 'n', 'n']

word: ne  score: 2
------------------------------------------------------------
attempts: 15
0.0210001468658
Time limit exceeded.
Score: 0.00  Total Score: 0.00

c n
calling with:
        {'a': 0, 'c': 1, 'e': 0, 'j': 0, 'm': 0, 'n': 1}
local_hand:
        ['c', 'n']

------------------------------------------------------------
attempts: 3
0.018000125885
No legal combination possible.

Friday, July 22, 2011

MIT 6.00 Problem Set 6 Answers - Problem 3


I don't think the intent of this exercise was to write a permutation routine or to use itertools but I used itertools.  pick_best_word() is pretty much the whole assignment.

Python Code Answer:

def pick_best_word(hand, points_dict):
    score = 0
    length = 0
    high_word = ""
    perms = []
    local_hand = []
    attempts = 0

    # itertools.permutations is iterating for letters
    # that are zero count in the hash, dump the zeros
    # convert dict to list
    for k in hand.keys():
        if hand[k] > 0:
            for i in range(hand[k]):
                local_hand.append(k)
        
    print "local_hand: "
    print "\t",
    print local_hand
    print

    take = len(local_hand)
    
    # try for a bingo, then one less than a bingo, etc.
    while take != 0:
        perms = list(itertools.permutations(local_hand, take))
        take -= 1
    
        for letter_list in perms:
            attempts += 1
            word = ""
            for c in letter_list:
                word += c

            if points_dict.has_key(word):
                if score < points_dict[word]:
                    score = points_dict[word]
                    high_word = word
                    print "word: %s  score: %d" % (word, score)

    print "------------------------------------------------------------"
             
    print "attempts: %d" % (attempts)
       
    if score < 1:
        return '.'
    else:
        return high_word



For each seven letter hand 13699 permutations are checked
in the first pass:

>>> import itertools
>>> perms = list(itertools.permutations('1234567', 7))
>>> len(perms)
5040
>>> perms = list(itertools.permutations('1234567', 6))
>>> len(perms)
5040
>>> perms = list(itertools.permutations('1234567', 5))
>>> len(perms)
2520
>>> perms = list(itertools.permutations('1234567', 4))
>>> len(perms)
840
>>> perms = list(itertools.permutations('1234567', 3))
>>> len(perms)
210
>>> perms = list(itertools.permutations('1234567', 2))
>>> len(perms)
42
>>> perms = list(itertools.permutations('1234567', 1))
>>> len(perms)
7
>>> 5040+5040+2520+840+210+42+7
13699

Output:


s u u f y j m
calling with:
        {'s': 1, 'u': 2, 'f': 1, 'y': 1, 'j': 1, 'm': 1}
local_hand:
        ['s', 'u', 'u', 'f', 'y', 'j', 'm']

word: fumy  score: 12
------------------------------------------------------------
attempts: 13699
Score: 184.62  Total Score: 184.62
Turn took 0.06 seconds, 1.75 seconds remaining

s u j
calling with:
        {'s': 1, 'u': 1, 'f': 0, 'y': 0, 'j': 1, 'm': 0}
local_hand:
        ['s', 'u', 'j']

word: jus  score: 10
------------------------------------------------------------
attempts: 15
Score: 400.00  Total Score: 584.61
Turn took 0.03 seconds, 1.73 seconds remaining

Final Score: 584.61


p s t z m o o
calling with:
        {'p': 1, 's': 1, 't': 1, 'z': 1, 'm': 1, 'o': 2}
local_hand:
        ['p', 's', 't', 'z', 'm', 'o', 'o']

word: pomos  score: 9
word: zooms  score: 16
------------------------------------------------------------
attempts: 13699
Score: 275.86  Total Score: 275.86
Turn took 0.06 seconds, 1.59 seconds remaining

p t
calling with:
        {'p': 1, 's': 0, 't': 1, 'z': 0, 'm': 0, 'o': 0}
local_hand:
        ['p', 't']

------------------------------------------------------------
attempts: 4
No legal combination possible.



s s u d g i t
calling with:
        {'s': 2, 'u': 1, 'd': 1, 'g': 1, 'i': 1, 't': 1}
local_hand:
        ['s', 's', 'u', 'd', 'g', 'i', 't']

word: disgust  score: 9
------------------------------------------------------------
attempts: 13699
Score: 1053.57  Total Score: 1053.57
Turn took 0.06 seconds, 1.36 seconds remaining

Final Score: 1053.57