Fun with finite-state machines, graphviz and python

Hello,

I have come in need for a grammar parser in python (context-free). While there are plenty in python, many of them are very undocumented, some seem to have become orphaned projects and `yapps2` and `pyparsing` that I tried seem to be a bit limited for what I need them (or most probably I'm a noob). So, also in order to refresh my memory on grammars, I decided to make my own parser in python.

The first step was, as I saw it to go back to the roots, to finite-state machines. It happened that it is quite a bit of fun especially because it allows me to have a dip into `graphviz` and `pydot` for pretty plotting the state machines.

Here are some examples from "Elements of the Theory of Computation - H.Lewis, Ch. Papadimitriou, 2nd ed.


The first one is for the language L(M) = { w \in (a,b)* : w has an even number of b's}

And the second one decides the language L(M) = { w \in (a,b)* : w does not have three consecutive b's }

And here is the code: https://gist.github.com/mmxgn/5973875

Musical CSPs with Mingus and python-constraint

Hello,

I was looking for a nice python library for constraint programming. Unfortunately, the only one I could find was python-constraint which seemed quite nice and straightforward, but after using it for a while, I find it very limited.

So, as a first example, I tried solving the pretty classic musical CSP described at the Strasheela Examples page as the 'All Interval Series' which is taken from music serialism.

The problem states that we want to put a series of all different pitch classes on the chromatic scale, where each interval appears exactly once. We also take account for inversely equivalent intervals.

I used python-constraint in order to construct my CSP by using pure python syntax, and mingus to create a midi track and render it to .pdf, .png and .mid files.

Here's the code:
https://gist.github.com/mmxgn/5891884

Here's the output score with lilypond:

and the link to the midi file.

Calculating conditional pmf matrices in python (numpy)

Here is the thing that has tormented me for some time now.

I have a conjunctive probability table, with shape, for example (1,2,3,4,5,6) .

And I want to calculate the probability table, conditional to a value for some of the dimensions, for decision-making purposes. We define the values we want

The code I came up with at the moment is the following (the input is the dictionary "vdict" of the form {'variable_1': value_1, 'variable_2': value_2 ... } )

for i in vdict:

dim = self.invardict.index(i) # The index of the dimension that our Variable resides in

val = self.valdict[i][vdict[i]] # The value we want it to be

d = d.swapaxes(0, dim)

d = array([d[val]])

d = d.swapaxes(0, dim)

...

So, what I currently do is:

1. I translate the variables to the corresponding dimension in the cpt.

2. I swap the zero-th axis with the axis I found before.

3. I replace whole 0-axis with just the desired value.

I put the dimension back to its original axis.

Now, the problem is, in order to do step 2, I have (a.) to calculate a submatrix

and (b.) to put it in a list and translate it again to array so I'll have my new array.

Thing is, stuff in bold means that I create new objects, instead of using just the references to the old ones and this, if d is very large (which happens to me) and methods that use d are called many times (which, again, happens to me) the whole result is very slow.

So, has anyone come up with an idea that will subtitude this little piece of code and will run a lot faster? Maybe something that will allow me to calculate the conditionals in place.

Edit: I replaced the command in bold, with the code below:

d = conditionalize(d, dim, val)

where:

def conditionalize(arr, dim, val):

arr = arr.swapaxes(dim, 0)

shape = arr.shape[1:] # shape of the sub-array when we omit the desired

count = array(shape).prod() # count of elements omitted the desired dimension.

arr = arr.reshape(array(arr.shape).prod()) # flatten the array in-place.

arr = arr[val*count:(val+1)*count] # take the needed elements

arr = arr.reshape((1,)+shape) # the desired sub-array shape.

arr = arr. swapaxes(0, dim) # fix dimensions

return arr

Now, what before took 15 minutes to complete, now takes only about 6 seconds!