Type based API's and Duck Typing Shocker!!

The Voidspace tech blog has href="http://www.voidspace.org.uk/python/articles/duck_typing.shtml">an
article in which the author, Michael Ford, blames duck-typing
for a problem in trying to find the type of an argument.



After a very good explanation of how duck typing in Python
 comes about Michael starts his section on the problem by
stating the principal of duck typing as:

"The
principle of duck typing says that you shouldn't care what type of
object you have - just whether or not you can do the required action
with your object."

All well and good but then later on Michael states:

"If we
want our code to treat different types of object differently then
the approach in example two fails. This isn't contrived - this is
exactly the situation we found ourselves in with ConfigObj."

So, type is important in his case. Fine. style="font-weight: bold;">But why lay the blame at duck
typings door ?



His example interface relies on knowing what constitutes a "listy"
object, or a "stringy" object, etc, in Python 2.x, which he notes is a
pain, but I think the cause of the problem w.r.t. duck typing is
choosing an API that relies on an ill-defined idea of what constitutes
close enough to a dict/list/string or whatever, then not having the
language provide an easy solution.



Abstract
base classes are an attempt to help out in such cases that is
new in Python 2.6 and 3.0, but if you want to link functionality with
type then you can't expect to get duck typing too.

Where Duck Typing Does Not fit.

If a function has an expensive or non-reversible operation that depends
on an  attribute of an argument, then it may be wise to check
all arguments for compatibility up-front; but even then, whats wrong
with reading the code?  Defensive programming can creep up on
you...

Killer Script

Following on from my href="http://paddy3118.blogspot.com/2009/03/batch-process-runner-in-bash-shell.html"
target="_blank">Batch process runner script, I got
thinking that a nice capability would be to have a maximum runtime
limit for the jobs.



My first thought was to create an href="http://unixhelp.ed.ac.uk/CGI/man-cgi?at" target="_blank">at
command set to execute the reuired time after the start of each job,
one for each job, that would kill the job.

Nah.

Discussions with a friend lead to consideration of using href="http://docs.sun.com/app/docs/doc/816-5165/ulimit-1?l=en&a=view&q=ulimit"
target="_blank">ulimit in the script to limit the
run time, but unfortunately on the Unix box I was testing on, ulimit
could only limit the maximum CPU time, not run time. If the job was
stuck in a non-busy wait then it would not be auto-killed.



I decided to try creating a script to run a time eating processing task
that created a background kill task so the script would be self
killing.

The script

Line 1:    The KILLAFTER environment
variable will kill the script after 3 seconds

Line 5:    Store the process ID for the
'bash -c'  script for killing later

Line 8:    This is the slleping background
sub-process that wakes after KILLAFTER seconds and kills the script.

Line 9:    But if the normal script commands
finish, store the sub-process PID so it can be cleanly killed itself.

Line 12:  Some dummy command that counts up every second.

Line 13:   And save its exit status so it can be
restored after removing the background kill process.

Line 16:   Terminate the background kill process so
we are not left waiting.

Line 18:   Exit with the saved exit status.

Line 19:   Prints the exit status of the whole 'bash
-c' script



Lines 20-24 show the output of the first run. Notice how although the
for loop in line 12 is set to count to 5, the count gets killed after
printing 3, i.e. the three seconds of $KILLAFTER.



Lines 27 onwards show a second run where KILLAFTER is set to more time
than is used by the for loop. Notice how the script prints the full
count up to 5, and has a return status of zero.

 1 bash-paddy:  style="font-weight: bold;">env  style="font-weight: bold;" color="#008080">KILLAFTER style="font-weight: bold;">= style="font-weight: bold;" color="#ff00ff">3 style="font-weight: bold;"> bash  style="font-weight: bold;" color="#6a5acd">-c style="font-weight: bold;"> '
 color="#804040"> 2 # New bash script shell environment
 color="#804040"> 3 
 color="#804040"> 4 # Its PID
 color="#804040"> 5 export  color="#008080">thisshellpid color="#804040">= color="#a020f0">$$
 color="#804040"> 6 
 color="#804040"> 7 # Sleeping killer will blast this script after given time
 color="#804040"> 8 (sleep  color="#a020f0">$KILLAFTER  color="#804040">;  color="#804040">kill  color="#ff00ff">-9 $thisshellpid color="#804040">) color="#804040">&
 color="#804040"> 9 killerpid= color="#a020f0">$!
 color="#804040">10 
 color="#804040">11 # Any time consuming command
 color="#804040">12 for y  color="#804040">in  color="#ff00ff">1 2  color="#ff00ff">3 4  color="#ff00ff">5;  color="#804040">do sleep  color="#ff00ff">1;  color="#804040">echo color="#ff00ff"> $y color="#804040">;  color="#804040">done
 color="#804040">13 trueexitstatus= color="#a020f0">$?
 color="#804040">14 
 color="#804040">15 # If time consuming command worked OK then...
 color="#804040">16 kill  color="#ff00ff">-9 $killerpid
 color="#804040">17 
 color="#804040">18 exit  color="#a020f0">$trueexitstatus
 color="#804040">19  style="font-weight: bold;">'  style="font-weight: bold;" color="#804040">; style="font-weight: bold;">  style="font-weight: bold;" color="#804040">echo style="font-weight: bold;" color="#ff00ff"> Returned status:  style="font-weight: bold;" color="#a020f0">$?
 color="#804040">20 1
 color="#804040">21 2
 color="#804040">22 3
 color="#804040">23 Killed
 color="#804040">24 Returned status:  color="#ff00ff">137
 color="#804040">25 bash-paddy:
 color="#804040">26 bash-paddy:
 color="#804040">27 bash-paddy:  style="font-weight: bold;">env  style="font-weight: bold;" color="#008080">KILLAFTER style="font-weight: bold;">= style="font-weight: bold;" color="#ff00ff">10 style="font-weight: bold;"> bash  style="font-weight: bold;" color="#6a5acd">-c style="font-weight: bold;"> '
 color="#804040">28 # New bash script shell environment
 color="#804040">29 
 color="#804040">30 # Its PID
 color="#804040">31 export  color="#008080">thisshellpid color="#804040">= color="#a020f0">$$
 color="#804040">32 
 color="#804040">33 # Sleeping killer will blast this script after given time
 color="#804040">34 (sleep  color="#a020f0">$KILLAFTER  color="#804040">;  color="#804040">kill  color="#ff00ff">-9 $thisshellpid color="#804040">) color="#804040">&
 color="#804040">35 killerpid= color="#a020f0">$!
 color="#804040">36 
 color="#804040">37 # Any time consuming command
 color="#804040">38 for y  color="#804040">in  color="#ff00ff">1 2  color="#ff00ff">3 4  color="#ff00ff">5;  color="#804040">do sleep  color="#ff00ff">1;  color="#804040">echo color="#ff00ff"> $y color="#804040">;  color="#804040">done
 color="#804040">39 trueexitstatus= color="#a020f0">$?
 color="#804040">40 
 color="#804040">41 # If time consuming command worked OK then...
 color="#804040">42 kill  color="#ff00ff">-9 $killerpid
 color="#804040">43 
 color="#804040">44 exit  color="#a020f0">$trueexitstatus
 color="#804040">45  style="font-weight: bold;">'  style="font-weight: bold;" color="#804040">; style="font-weight: bold;">  style="font-weight: bold;" color="#804040">echo style="font-weight: bold;" color="#ff00ff"> Returned status:  style="font-weight: bold;" color="#a020f0">$?
 color="#804040">46 1
 color="#804040">47 2
 color="#804040">48 3
 color="#804040">49 4
 color="#804040">50 5
 color="#804040">51 Returned status:  color="#ff00ff">0
 color="#804040">52 bash-paddy:
 color="#804040">53 

XKCD Simpler Knapsack Solution

 After reading the feedback on my href="http://paddy3118.blogspot.com/2009/06/xkcd-knapsack-solution.html"
target="_blank">earlier solution to the XKCD knapsack problem,
I decided to re-write it without itertools.product and with integer
maths.



I came up with a solution that used explicit while loops that worked,
and used much less traversals through nested loops, but I then boiled
that down to a recursive solution which retains the ability to easily
modify the number of dishes , whilst restricting the number of times
through the loops to the bare minimum.



In the previous solution I worked out the maximum number of each dish
that cost less than or equal to the amount and looped from zero to that
many times. In the solution below the while loops cut off looping on
any particular dish when adding another would put the cost over the
maximum.



And now the code:

items = ( ('MIXED FRUIT',   2.15),
          (' color="#ff00ff">FRENCH FRIES',  2.75),
          (' color="#ff00ff">SIDE SALAD',    3.35),
          (' color="#ff00ff">HOT WINGS',     3.55),
          (' color="#ff00ff">MOZZ STICKS',   4.20),
          (' color="#ff00ff">SAMPLER PLATE', 5.80),
          (' color="#ff00ff">BARBEQUE',      6.55) )

exactcost = 15.05

dishes, prices = zip(*items)
 color="#0000ff"># All calcs in integer cents.
prices = [int(price*100)  color="#804040">for price  color="#804040">in prices]
ecost = int(exactcost*100)

 color="#0000ff"># counts of each dish
dishcounts = [0]*len(prices)
 color="#0000ff">possibleorders = []
cost = 0
maxnesting = len(dishcounts)

 color="#804040">def  color="#008080">enumeratedish(nest, cost, possibleorders):
     color="#804040">global dishcounts, prices, ecost, maxnesting
     color="#804040">while cost <= ecost:
         color="#804040">if nest+1 < maxnesting:
            enumeratedish(nest+1, cost, possibleorders)
         color="#804040">elif cost == ecost:
            possibleorders.append(dishcounts[:])
             color="#804040">break
        dishcounts[nest] += 1
        cost += prices[nest]
         color="#0000ff">#print (dishcounts)
    cost -= prices[nest] * dishcounts[nest]
    dishcounts[nest] = 0

enumeratedish(0, 0, possibleorders)
 color="#804040">print(' color="#6a5acd">\nALL POSSIBLE CHOICES OF MENU ITEMS THAT COST %.2f, ONE PER LINE' % exactcost)
 color="#804040">for order  color="#804040">in possibleorders:
    order = zip(dishes, order)
     color="#804040">print( ' color="#ff00ff">  ',
           ' color="#ff00ff">, '.join(' color="#ff00ff">%s: %i' % dishcount  color="#804040">for dishcount  color="#804040">in order  color="#804040">if dishcount[1]))

feel free to compare the two solutions. 

XKCD Knapsack Solution

A brute force solution to the following comic from href="http://xkcd.com/287/">XKCD:



title="General solutions get you a 50% tip."
src="http://imgs.xkcd.com/comics/np_complete.png">





Assuming the one sandwich represents the end of the menu, I used an
exhaustive search algorithm. Things to note are the use of zip(*table)
to transpose the items and itertools.product instead of nested for
loops.

'''
from:  href="http://xkcd.com/287/">http://xkcd.com/287/
'''

 color="#a020f0">from itertools  color="#a020f0">import product

items = ( (' color="#ff00ff">MIXED FRUIT',   2.15),
          (' color="#ff00ff">FRENCH FRIES',  2.75),
          (' color="#ff00ff">SIDE SALAD',    3.35),
          (' color="#ff00ff">HOT WINGS',     3.55),
          (' color="#ff00ff">MOZZ STICKS',   4.20),
          (' color="#ff00ff">SAMPLER PLATE', 5.80),
          (' color="#ff00ff">BARBEQUE',      6.55) )

exactcost = 15.05

dishes, prices = zip(*items)
rangeofdishes = [tuple(range(1+int( (exactcost+0.005)/price )))  color="#804040">for price  color="#804040">in prices]

possibleorders = [tuple(zip(dishes, numbers))
                   color="#804040">for numbers  color="#804040">in product(*rangeofdishes)
                   color="#804040">if int(exactcost*100)
                       == int(100* sum(num*price
                                        color="#804040">for num,price  color="#804040">in zip(numbers, prices)))
                  ]
 color="#804040">print(' color="#6a5acd">\nALL POSSIBLE CHOICES OF MENU ITEMS THAT COST %.2f, ONE PER LINE' % exactcost)
 color="#804040">for order  color="#804040">in possibleorders:
     color="#804040">print( ' color="#ff00ff">  ',
           ' color="#ff00ff">, '.join(' color="#ff00ff">%s: %i' % dishcount  color="#804040">for dishcount  color="#804040">in order  color="#804040">if dishcount[1]))

The answers I get are:

style="font-family: monospace;">ALL POSSIBLE CHOICES OF MENU
ITEMS THAT COST 15.05, ONE PER LINE style="font-family: monospace;">
  
MIXED FRUIT: 1, HOT WINGS: 2, SAMPLER PLATE: 1 style="font-family: monospace;">
  
MIXED FRUIT: 2, MOZZ STICKS: 1, BARBEQUE: 1

  
MIXED FRUIT: 7

(I'd go with the hot wings).