Mainly Tech projects on Python and Electronic Design Automation.

Tuesday, March 30, 2010

Why Python?

Choose for yourself. Have a look at the examples on the Rosetta Code site. You might like to follow the links to a few pages that I did the task descriptions for as they tend to be meatier tasks, but the examples in different languages should allow you to compare how different languages are used to solve the same problems.

Unfortunately it cannot eliminate the issue of the competence of the individual programmers, but it might provide some useful info.

Have fun :-)

Tuesday, March 16, 2010

Expressions to Truth-Tables

I had a need for the data in the truth tables for a standard cell library, rather like that shown here if you look at say page 35 you will see that for for every Cell it gives the cell name; the cell function as a boolean expression, and the truth-table for the cell.

My cell library was an Infineon one and I had the pdf version of the databook. A quick squirt through pdftotext scrambled the truth table, but did preserve the boolean expression of each cells' function, and the cell name.

I wrote a Python script that used a multi-line regexp to extract each cells info including the boolean equation.

The equation from the Infineon databook uses +,*, and ! for boolean or, and and not operators, but also used lots of parentheses so that operator precedence did not affect the value of the infix expression. I realised that I could substitute for the Python bitwise operators, and form a python expression that could then be evaluated with appropriate values for any input names to create a truth table.

I have left out the parsing and present a function to create a truth-table from a boolean expression:

from itertools import product

def truthtable(expressionstring):
comp = compile(expressionstring.strip(), '-', 'eval')
inputs = sorted(comp.co_names)
table = {}
for values in product( *([(0,1)] * len(inputs)) ):
valuedict = dict(zip(inputs, values))
answer = eval(comp, valuedict)
table[values] = answer
return expressionstring.strip(), inputs, table

def pptable(ex, inputs, table):
print("\nTRUTH-TABLE FOR EXPRESSION: %r\n" % ex)
print(' ' + ' '.join('%2s' % inp for inp in inputs) + ': OUTPUT')
fmt = ' %i' * len(inputs) + ': %i'
for inp, ans in sorted(table.items()):
print(fmt % tuple(list(inp) + [ans]))

ex, inputs, table = truthtable('(A & (~C)) | D')
pptable(ex, inputs, table)


Going through function truthtable:
  • compile() gives access to all the names in the compiled expression via attribute .co_names - this is all the names used in the expression.
  • product() allows you to quickly generate the 1/0 value combinations for the input names.
  • valuedict assigns a value to each name used in the expression.
  • eval evaluates the expression with the given values on each name
The output of the program is:

TRUTH-TABLE FOR EXPRESSION: '(A & (~C)) | D'

A C D: OUTPUT
0 0 0: 0
0 0 1: 1
0 1 0: 0
0 1 1: 1
1 0 0: 1
1 0 1: 1
1 1 0: 0
1 1 1: 1


- No separate parser required!

Thursday, March 04, 2010

NPR 2002 Puzzle

A puzzle I copied from here via reddit:
1 2 3 4 5 6 7 8 9 = 2002
Put any combination of plus, times, and spaces between the digits on the left to make the identify true.
The answer was easy and was quick to compute.

I realised that you could evaluate all expressions where the numbers 1 through nine are separated by the permutations of either a null string, '', '+' or '*'

The answer came from the following:

>>> from itertools import product
>>> eqn = '%s'.join(list('123456789')) + '==2002'
>>> eqn
'1%s2%s3%s4%s5%s6%s7%s8%s9==2002'
>>> for ops in product(*[['', '+', '*']]*8):
if eval(eqn % ops):
print(eqn % ops)


1*23+45*6*7+89==2002
1*2+34*56+7+89==2002
>>>

So, there are two solutions.

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive