Category Archives: Python

SAT-based KenKen Solver

Python, , ,

Inspired by the SAT-based Sudoku solver by Tjark Weber and the corresponding Python implementation, I coded up a quick SAT-based KenKen solver.

The ideas in the KenKen solver are pretty similar to the Sudoku solver. In particular, we reuse the framework of using a boolean variable to represent
each possible digit in each cell and all of the clauses which correspond to the following rules:

  • At least one digit must be present in a cell
  • Two or more digits may not be present in a cell
  • The same digit may not appear more than once in any row
  • The same digit may not appear more than once in any column

To satisfy the mathematical expressions, we generate all list of all possible ways each “cage” can be filled. This is most naturally expressed in disjunctive normal form:

(cell1 has value v1 AND cell2 has value v2 AND ...)
OR (cell1 is value w1 AND cell2 has value w2 AND ...)
OR ...

This can be easily and efficiently transformed into a equisatisfiable conjunctive normal form by adding a few auxiliary variables.

The SAT-based solver is reasonably fast. For example, on my laptop it can solve a 6-by-6 KenKen problem in about 23 ms. On a big a 9-by-9 problem it takes about 328 ms which is a factor of 5 or so slower than the NekNek solver (which takes about 65 ms).

A data descriptor for __doc__

Python, , ,

In Python, suppose you want to implement a class which has a dynamically generated docstring. The easiest way to do this would be to use the @property decorator for the __doc__ attribute. (You also need your class to be a “new-style” class, i.e., inherit from object). For example:

class A(object):
    """Docstring for class."""
    def __init__(self, x):
        self.x = x
    @property
    def __doc__(self):
        return "My value of x is %s." % self.x

This gives the desired result:

>>> a = A(10)
>>> print(a.__doc__)
My value of x is 10.

But hides the docstring for the class A:

>>> A.__doc__
<property at 0x2083db8>

Read on to see how we can fix this. Continue reading A data descriptor for __doc__ →

Instance Methods & Cython Functions

Python,

One of the great features of Python is the ability to define methods outside of classes. For example, we can define a function which increments the attribute x and add it to a Point class:

def incx(self):
    self.x += 1

class Point(object):
    def __init__(self, x): self.x = x
    incx = incx

We can then create a point at the origin and increment x:

In [2]: p = Point(0)

In [3]: p.incx()

In [4]: print p.x
1

The same code which defines Point continues to work if we move incx to another file, say demo.py, and import it using from demo import incx.

But if we were to put incx in demo.pyx and compile it (using python setup.py build_ext --inplace), we get a strange error when running our simple test:

$ python bad.py
Traceback (most recent call last):
  File "bad.py", line 10, in <module>
    p.incx()
TypeError: incx() takes exactly one argument (0 given)

Read on to learn about instance methods and see how I fixed this.
Continue reading Instance Methods & Cython Functions →

True division in IPython

Python,

As Python transitions from version 2 to version 3, the meaning of the division operator on integers is changing:

Python 2.x Python 3.x 
$ python2.7
Python 2.7.2+ (...)
...
>>> 1/2
0
 
$ python3.2
Python 3.2.2 (...)
...
>>> 1/2
0.5

In this post, we’ll discuss how to configure the behavior of the division operator in Python 2.7 and IPython to behave like the Python 3.x counterpart.

Continue reading True division in IPython →

IPython Qt Console and printf

IPython

The recent 0.11 release of IPython includes a Qt-based console which offers an improved experience compared to running IPython in a terminal. In particular, the console feels like a terminal but offers multi-line editing, syntax highlighting, graphical tooltips, and inline plot figures.

But when I tried to run an existing script in the new IPython Qt Console, the usual overly verbose set of diagnostic messages did not appear! The symtoms were:

  • Regular print statements in Python worked fine.
  • printf statements in C-code wrapped with Boost.Python did not appear.

Read on to see a solution. Continue reading IPython Qt Console and printf →

Debugging MPI + Python

Python, , , , , ,

Python is increasingly becoming a popular language for controlling large numerical simulations due to its scripting abilities and easy bindings with C, C++, and Fortran as provided by ctypes, Boost.Python, SWIG, etc. In addition, there are some nice convenience wrappers for MPI, including mpi4py.

However debugging MPI scripts can be challenging. Here are some useful ways to run your programs for debugging.

  • Open an xterm window for each MPI process, with the script running in iPython.

    $ mpirun -np 4 xterm -e "ipython script.py"
  • Open an xterm window for each MPI process, with gdb attached to each python process. The -x flag tells gdb to run the commands given in the specified file. This is often a good place to add additional breakpoints.

    $ echo "run script.py" > gdb.in
$ mpirun -np 4 xterm -e "gdb -x gdb.in python"
  • Open each MPI process within screen, then open a gnome-terminal with one tab for each screen.

    $ mpirun -np 4 screen -L -m -D -S mpi 
    ipython script.py &
$ gnome-terminal --tab -e "screen -RR -p mpi" 
                 --tab -e "screen -RR -p mpi" 
                 --tab -e "screen -RR -p mpi" 
                 --tab -e "screen -RR -p mpi"

    If your program dies unexpectedly, it is probably because LD_LIBRARY_PATH is stripped by glibc since screen is a setgid/setuid program. You can work around this my modifying the mpirun call as

    $ mpirun -np 4 screen -L -m -D -S mpi 
    env LD_LIBRARY_PATH=$LD_LIBRARY_PATH ipython script.py

Simple Timer using Python’s With Statement

Python, ,

Python’s with statement, available since Python 2.5, does not seem to be widely used despite being very useful.

Here we describe how to use the with statement to create a simple timer with the syntax:

>>> with TicToc():
...     some_slow_operations
...
Elapsed time is 2.000073 seconds.

Readers familiar with MATLAB will recognize the similarity to the familiar timing mechanism:

> tic ; some_slow_operations; toc
Elapsed time is 10.020349 seconds.

Continue reading Simple Timer using Python’s With Statement →

Calling Python from C++

Boost.Python, Python, ,

In a previous post we already covered calling a C function from one Boost.Python module in another module.

What if instead we want to call a Python function directly from C? We’ll stick with the same Bird / Quacker metaphor as in the previous post, but we’ll now implement our duck class in PyDuck.py:

"""
PyDuck.py
"""

def quack():
    print "Python Quack"

Now how can we call Python from C++? It turns out that Boost.Python defines operator() for the object class, so calling Python is relatively easy.  But things become more difficult if we want to maintain a default implementation in C.

Continue reading Calling Python from C++ →

Python Capsules

Boost.Python, Python, ,

Python Capsules are useful for passing C pointers between different Python modules.  In particular, one can encapsulate a C function pointer in one module and unpack and call it in another module.

To begin, suppose we have two Boost.Python modules:

  1. Bird, which has methods setQuack() and callQuack().
  2. CppDuck, which has a method getQuack().

Our goal will be to get a function pointer with CppDuck.getQuack(), set it in another module in Bird.setQuack(), and finally call it with Bird.callQuack().

Continue reading Python Capsules →