Adding Locking Wheels to a Cast Iron Grinder Stand

Harbor Freight used to sell the same grinder stand as the Grizzly H7763 where the base is a hollow casting, complicating wheel mounting. Most stud mounted wheels only have a bit over an inch in stud length and more than two inches plus an enormous fender washer would be needed to mount on this base.

I made aluminum adapters to go from the 1/2"-20 wheel studs on the 4 in. Hard Rubber Heavy Duty Swivel Casters with Brake Harbor Freight Item #90999 to a 3/8"-16 tapped hole. The adapters are about two inches long and easily clear the the hollow casting. The mount is very solid but the assembly is top heavy and a bit tippy but still works well with the wheels locked.

Click on any picture for a slideshow.

Number 5 is Alive

A metal bodied wood plane that looks like a complete rust bucket can almost always be restored to be a good looking user. Other than heavy chips or rust pitting ahead of the mouth other wear and damage doesn't usually matter.

This Stanley Number 5 jack plane has good finish on the knob and tote so it was retained. Good wax was just rubbed in with 0000 steel wool. If the knob and tote are really chewed up they can be stripped, sanded, oiled and waxed and will look terrific. The knob is quickly sanded on a lathe or drill press. The tote is all handwork. Strips of sandpaper used shoe shine fashion while the tote is in a vise are helpful.

I use wire wheels in the drill press to remove rust and then Scotchbrite pads to give the
steel a uniform scratch pattern. Brass parts are polished on a buffing wheel and with Simichrome metal polish. Steel screw heads can be buffed to a chrome-like luster with the buffing wheel.

I used naval jelly on the rusty parts of the japanning and then wiped on some oil.

I reassemble all the parts with a drop of oil on all threads.

Click on the first picture for a slideshow:

 All parts before and after cleaning:

The final result still has lots of patina, just no rust. The sides of the plane could have been lapped until they were bright as well.

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

Linear Interpolation Calculator

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

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_())

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]

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.

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.

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.

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.

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

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}

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.

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

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

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