Friday, December 25, 2009

The 17x17 challenge: setting up the grid

In the previous post, I talked about the 17x17 challenge, but did not provide any code.  Today, I will describe the code I use to represent a given grid.  Consider the following grid where A and b are used to represent two different colours:
AbAb
bAbA
bbAA
bAAA
This grid has two rectangles, one of which is emphasized below
....
.A.A
....
.A.A
Finding such a rectangle in a small grid is fairly easy to do.  A naive, but very inefficient way to do this is to have a function like the following:
def find_rect_candidates(row_1, row_2):
   points_in_common = [0, 0, ...] # one per colour
    for i, point in enumerate(row_1):
       if row_1[i] == row_2[i]:
          points_in_common[row_1[i]] += 1
   return points_in_common
where row_x[i] is set to a given colour, represented by an integer (0, 1, 2, ...). For an NxN grid, the first loop is of order N.  Note that this does not tell us (yet) if we have found a rectangle; we still have to loop over points_in_common and see if any entry is greater than 1.

A better way to do the comparison, which does not grow with N, is mentioned in this post and is based on the following observation:  for a given row, at a given point, a given colour is either present (True or 1) or not (False or 0). Thus, a given colour distribution on a single row can be represented as a string of 0s and 1s ... which can be thought of as the binary representation of an integer.  For example, the row containing the colour "A" in the pattern ".....A..A" can have this pattern represented by the number 9="1001".  Consider another row represented by the number 6="110". These two rows have no points in common (for this colour) and hence do not form a rectangle.  If we do a bitwise "and" for these two rows, i.e. 9&6 we will get zero.  This is achieved by a single operation instead of a series of comparisons.

What happens if two rows have a single point in common (for a given colour) so that no rectangle is present?  For example, consider 9="1001" and 15="1110".  If we do a bitwise "and" we have

answer = 9 & 15 = 8 = "1000"

Taking the bitwise "and" of answer and answer-1, we get

answer & (answer-1) = 8 & 7 = "1000" & "111" = 0.

If we have two points (1 bit) in common, it is easy to see that the bitwise comparison of answer & (answer-1) will not give zero.

Going back to the function above, we could rewrite it instead as follows:

def find_rect_candidates(row_1, row_2, colours):
   points_in_common = [0, 0, ...] # one per colour
      for c in colours:
         points_in_common[c] = row_1[c] & row_2[c]
   return points_in_common


where we still have to do the same (N-independent) processing of the return value as with the function above to determine if we do have rectangles.

Now, without further ado, here is the basic code that I use to represent a grid, together with two utility functions.

def rectangles_for_two_rows(row_1, row_2):
    '''returns 0 if two rows (given colour, encoded as a bit string)
        do not form a rectangle -
        otherwise returns the points in common encoded as a bit string'''
    intersect = row_1 & row_2
    if not intersect:   # no point in common
        return 0
    # perhaps there is only one point in common of the form 00010000...
    if not(intersect & (intersect-1)):
        return 0
    else:
        return intersect

def count_bits(x):
    '''counts the number of bits
    see http://stackoverflow.com/questions/407587/python-set-bits-count-popcount
    for reference and other alternative'''
    return bin(x).count('1')

class AbstractGrid(object):
    def __init__(self, nb_colours, max_rows, max_columns):
        self.nb_colours = nb_colours
        self.colours = list(range(nb_colours))
        self.max_rows = max_rows
        self.max_columns = max_columns
        self.powers_of_two = [2**i for i in range(max_columns)]
        self.grid = {}

    def initialise(self):
        '''initialise a grid according to some strategy'''
        raise NotImplemented

    def print_grid(self):
        '''prints a representation of the grid.
        Used for diagnostic only - no need to optimize further.'''
        for row in self.grid:
            row_rep = []
            for column in range(self.max_columns-1, -1, -1):
                for colour_ in self.colours:
                    if self.powers_of_two[column] & self.grid[row][colour_]:
                        row_rep.append(str(colour_))
            print("".join(row_rep))

    def identify_intersect_points(self):
        '''identifies the dots that contribute to forming rectangles'''
        # possibly could cut down the calculation time by only computing
        # for colours that have changed...
        nb_intersect = [0 for colour in self.colours]
        intersect_info = []
        for colour in self.colours:
            for row in self.grid:
                for other_row in range(row+1, self.max_rows):
                    intersect = rectangles_for_two_rows(
                                            self.grid[row][colour],
                                            self.grid[other_row][colour])
                    if intersect != 0:
                        nb_intersect[colour] += count_bits(intersect)
                        intersect_info.append([colour, row, other_row, intersect])
        return nb_intersect, intersect_info

The actual code I use has a few additional methods introduced for convenience.  If anyone can find a better method to identify intersection points between rows (from which rectangles can be formed), I would be very interested to hear about it.

The 17x17 challenge

In a recent blog post, William Gasarch issued a challenge: find a 17x17 four-colour grid for which there are no rectangles with 4 corners of the same colour.  If you can do this, Gasarch will give you $289.  For a more detailed explanation, you can either read Gasarch's post, or this post which contains a slightly friendlier explanation of the problem.

This problem, which is fairly easy to state, is extremely hard to solve as the number of possible grid configurations is 4289 which is a number much too large to solve by random searches or by naive methods.  As can be seen from the comments of the posts mentioned above, many people have devoted a lot of cpu cycles in an attempt to find a solution, but with no success.  Like others, I have tried to write programs to solve it ... but with no luck.  In a future post, I may write about the various strategies I have implemented in Python in an attempt to solve this problem.

Gasarch mentions that it is not known if a solution can be found for a 17x18 four-colour grid or even an 18x18 grid or a 17x19 one.  (Note that because of symmetry, an MxN solution can be rotated to give an NxM solution.)  While the number of configurations is large, the larger the grid is, I believe I have found a proof demonstrating that no solution can be found for a 17x18 grid.  This proof builds on the work of Elizabeth Kupin who has found the largest "colour class" i.e. the number of single-colour points on a 17x17 grid which is rectangle-free.  A generic solution found by Kupin is reproduced below:



Consider a 17x18 grid (17 rows and 18 columns).  Such a grid has 306 points.  Using the pigeonhole principle, one can easily show that, for any colouring, at least one colour must cover 77 points.  (Indeed, the most symmetric colouring would be 77, 77, 76, 76.)  Also, if a 17x18 rectangle-free solution exist, it must contain a 17x17 rectangle-free subset, which we take to be the above solution (other solutions for the 17x17 grid can be derived from this one using interchanges of rows and/or columns).

Let us attempt to add points in an additional column. First, we can try to add points in a row with 4 elements.  Without loss of generality, we can take this row to be the first one (row A).  Once we do this, we can not add any more points to row 3-17 without creating a rectangle.  The only row to which we can add a point is the second (row B) bringing the total number of points to 76 - one short of what we need.

Perhaps we can first remove a point from the 17x17 solution and then add a new column.  There are three cases we must consider: 1) that of a point belonging to a row with 5 points and a column with 5 points; 2) that of a point belonging to a row with 5 points and a column with 4 points; 3) that of a point belonging to a row with 4 points and a column with 5 points.

Case 1) Without loss of generality, let us move the point on row F in the first column to a new additional column, keeping the number of points at 74.  It is easy to show that the only rows to which we can then add an additional point without creating a rectangle are rows A, C, D, E. Once we add such a point (say on row A), we can no longer add a point on any of the remaining rows (C, D, E) without creating a rectangle.

Case 2) Without loss of generality, let us move the left-most point on row Q to a new column.  The only row to which we can then add a point in this new column is row A, bringing the total to 75.  We can't add another point without creating a rectangle.

Case 3) Again, without loss of generality, let us remove the top-left element (A) and move it to a new column added to the above solution.  We can add one more point, bringing the total to 75, to that new column (in row B) without creating a rectangle; any other addition of a point on that new column will result in a rectangle.


This concludes the sketch of the proof. 

UPDATE: Instead of adding a column, we can add a row (R) with 3 points located in the 9th, 12th and 17th column, bringing the total to 77 points and keeping the grid rectangle-free.  So the 17x18 case is still open... but I can't see how one could add a row with an extra 4 points to build a "single-colour" rectangle-free 17x19 grid.  (However, I won't venture again to say it is a proof until I have looked at all cases exhaustively.)

Note that construction of solutions for a 17x17 grid such as those found by Kupin, even for a single colours, can possibly be used to restrict the search space for the more general problem and help find a solution.  Unfortunately, no one has been able to do this (yet).

Sunday, November 15, 2009

Google Wave Fun

After a long time waiting, I finally got an Google Wave invitation this week - just as I was starting to look forward to a work slowdown so I could start programming again in the evenings.  The call of playing with a new toy was enough motivation to overcome inertia and spend a few hours, here and there in the evening, in order to create a new "gadget".  Google Wave Gadgets are actually fairly easy to create.  The only downside (from my point of view) is that they have to be written using javascript instead of Python.  Since this blog is called "Only Python", you may wonder how a post about a Google Wave Gadget could possibly belong here.  Believe me, it does.

A few years ago, in order to learn programming in Python, I created a "Karel the Robot" application in Python, to teach/learn Python, called rur-ple.  rur-ple was actually inspired by Guido van Robot (or GvR) which uses a Python like language.

I thought it would be a good idea to have something like rur-ple as a wave gadget.  Rather than re-inventing the wheel, I contacted Paul Carduner, who wrote gvr-online, and suggested that we could collaborate on a gadget - and he agreed.  The end goal is to have something like gvr-online as a gadget, but one which would recognize both the traditional GvR syntax OR the Python syntax used with rur-ple, as a choice for the end user.

The idea of having something like gvr-online as a wave gadget is the following: a teacher can embed such a gadget in a wave, with a predefined world, and assign it as a problem to either one, or more students - who could collaborate in that wave. All wave participants, including the teacher, can thus contribute and help each other.

Having had the idea, I wrote what was basically an empty shell of a gadget which Paul quickly connected to the existing code for gvr-online.  Some minor work remained for me to do to enable shared states and, apart from a minor UI bug, the prototype is now working.  What's left to do includes incorporation the Python syntax as an alternative to the traditional GvR syntax.

For those that might be interested in such a gadget, I suggest you first check gvr-online itself to get a better idea of what it does.  Then, if you have a Google Wave account, you can embed the gadget in a wave using this link.  Note that this is our "work in progress" link, that should not be expected to be a permanent one.

Sunday, September 13, 2009

Live preview of reStructuredText to HTML conversion in your browser

I've implemented a new plugin for Crunchy which may be of interest to some: a reStructuredText editor with live preview inside the browser window.  Each time a key is pressed in the editor (html textarea), an ajax request is sent to the Python backend with the entire content of the editor.  This is processed by docutils with the result sent back to the browser as a full html page displayed inside the browser as illustrated below.

I expected this to be slow (make that very slow) and for the first prototype I wrote, I only sent the ajax request when "enter" was pressed.  After playing with it for a while, I realized that there was no need for this.

If you type fast enough, the previewer does not keep up for each key press, but this does not hinder in any way the speed at which you can enter text in the editor.  By the way, the editor (html textarea) can be converted into a true embedded editor which can save and load files, etc. - otherwise, it would not be a very useful tool for working with reStructuredText documents.  When doing so, the live preview is turned off.  I've also included the possibility to save the html file produced so that one does not have to invoke docutils separately.  And this also incorporates the two custom directives (crunchy and getpythonsource) used by Crunchy and crst2s5.

This is included in the newest release (1.1.2) of Crunchy.

Wednesday, September 02, 2009

Upcoming Pycon and crst2s5

In a few months, many pythonistas will be converging to Atlanta to take part in the next Pycon.  I'm hoping to be able to attend it as I have been really inspired by the many people I met in two previous conferences.  While I most likely won't be presenting anything this time, I thought I would try to contribute to some presentations in an indirect way.

A while ago, Ned Batchelder wrote about presentation tools - more specifically about how he found all of them lacking.  In the comments section, many people made various suggestions - including one suggestion by Steve Holden which read as follows:

Crunchy? http://code.google.com/p/crunchy/

HTML plus live Python - what could be better?
While I, of course, approve of any positive support of Crunchy, I had to admit to myself (and mention in a subsequent comment) that Crunchy was really not up to the task - at least not yet.

In his post, Ned addresses some of the weaknesses of the tools he looked at.  In particular, he mentioned S5 about which he wrote:

S5 (A Simple Standards-Based Slide Show System) is all HTML, CSS, and Javascript, runs in the browser, and was created by Eric Meyer, a very nice pedigree. Remarkably, the thing I like least about it is that when I display the slides in a full-screen Firefox, they look horrible. The text is either too small or too large, and the line-spacing too tight, while the slide title overlaps the text in the wrong way, exposing some of the structure of the divs.
I would have hoped that a CSS-based slideshow by the king of CSS would be a shining example of how information could be cleanly authored and then sparklingly displayed. S5 seems to miss this mark, especially since there don't seem to be many themes available for it, another surprise given how CSS should have made it accessible to lots of designers. Also, although (or perhaps because) the format is native to the web, it's not possible to get the slides as illustrations.
Still, S5 is used for quite a few presentations by pythonistas thank to rst2s5, the docutils script that transform reStructuredText files into S5 presentations.  If I can summarize, rst2s5 strengths are as follow:

  • uses reStructuredText as source - easier to write than html
  • produce html files - thus easy to post and share -see link above.
  • use well known S5 slides (version 1.1 designed by Eric Meyer) to switch between "full paper"/slides.  It is possible to include extra notes in the "full paper".
Some of the weaknesses are the following:
  • From rst2s5's own documentation, it is impossible to have:
     - speaker's notes on the laptop screen
     - slides on the projector
     - two views stay in sync
     - presentation controlled from either display
  • like most (all?) slide-based presentation, content on one slide is limited to a given number of lines ... which makes it ackward to show long-ish code samples.
  • as Ned Batchelder alludes to, the automatic scaling done by S5 often yields unsatisfactory results in terms of line spacing, etc.
  • Finally, no interactive Python code in presentation ;-)

rst2s5 is based on S5 version 1.1.  A new version (1.2 alpha) is available which addresses some of the shortcomings of version 1.1 with the addition of speaker's notes which are in a separate window (e.g. on the laptop screen) while the slides themselves are in a different window (which can be on the projector) with the two synchronized.

I have decided to hack at the source (I don't like javascript...) and adapt S5 1.2 in ways which address some of Ned Batchelder's criticisms about the line spacing, etc, by disabling the automatic font scaling.  I incorporated it in a new program called crst2s5 which can be thought of as a Crunchy-extension to rst2s5.  crst2s5 on its own can produce standalone presentations (like rst2s5).  I consider it to be an improvement to rst2s5 ... time will tell if others share my opinion.

However, where crst2s5 can yield really interesting results is when you view the html output with Crunchy.  For now (version 1.1), when you do so, the automatic synchronization of speaker notes and slides is disabled - this will be addressed hopefully in the near future.   You can either try it by downloading the code or have a look at this sneak preview which I put together in one quick take as an experiment:



Get the Flash Player to see this movie.


Original location: 'Crunchy'
at ShowMeDo from the Python category.

Now, if only I had better graphical skills to design good looking slides...

Sunday, August 23, 2009

New plugin for Crunchy ... and bug fixes

Crunchy has a new plugin: getsource. What it does is enable a tutorial writer to embed a "link" to a python module inside an html file, or a class within that module, or a function or method, and have the source code being extracted by the inspect module and inserted within the html page.

Crunchy being Crunchy, it can also embed an interpreter or an editor right below the code source so that a user can interact with it.

And since not everyone likes to write documentation using straight html, a custom docutils directive is supported so that it works from reStructuredText files too.

The docutils directive looks as follows:

..getsource:: relative/path/to/module[.function] [linenumber] [editor or interpreter]

with a similar syntax for html files.

This plugin (which still has some minor bugs) is included in release 1.0.1 of Crunchy, which contains other minor bug fixes (as compared with release 1.0).

Crunchy 1.0 released!!

Crunchy 1.0 has finally been released. :-)

Crunchy 1.0 is compatible with Python 2.4, 2.5, 2.6 ... and 3.1. It is also compatible with Jython 2.5 modulo some bugs when trying to work with examples containing unicode strings.

Crunchy, for those that are not familiar with it, is a one-of-a-kind application. It is an application designed to transforms otherwise static html Python tutorials into interactive session viewed within a browser. Currently Crunchy has only been fully tested with Firefox. Crunchy should work with all operating systems - it has been tested fairly extensively on Linux, Windows and Mac OS.

In more details, here's what Crunchy does:

1. It loads an existing html file (or reStructuredText file) containing some Python code; this file can reside locally, or anywhere on the web.
2. It removes any existing javascript code & embedded interactive elements (applets, flash apps, etc.).
3. It further transforms the file by inserting some extra elements, including some custom javascript code.
4. It sends the transformed file to your browser of choice (read: Firefox).
5. It establishes a communication between the browser and the Crunchy back end and wait for user interaction.

Crunchy can embed Python interpreters and code editors (and more!) within an html page, enabling a user to enter (or edit) some Python code inside a browser window, send it to the Crunchy back end for execution, and observe the result back in the browser window.

In a sense, Crunchy is a Python programming environment embedded within a browser. However, it does not require a custom format for interactivity: for html files, as long as the Python code is included in a pre-formatted element (<pre>), Crunchy will recognize it, style it, and include the appropriate interactive element.

Crunchy comes with a fairly complete tutorial and supporting documentation. It is highly configurable.

Release 1.0 is NOT the end of the road for Crunchy. Future plans include support for interactivity with languages other than Python.

Thursday, April 16, 2009

Python textbooks wanted

Python textbooks wanted(1). Actually, what I'm mostly interested in are links to textbooks and other resources that would be useful to educators either teaching Python as a programming language or other courses where Python feature prominently. The reason behind this request is that I volunteered to be responsible to take care of the edu-sig page on the Python site. Through no one's fault in particular, the old page (2) had gone stale and only one textbook was listed. We're now up to six and I am sure I have not included them all. By ensuring that up to date and complete information is available on that page, we can facilitate the adoption of Python as a language taught in High Schools, Colleges and Universities.

So, if you know of any useful information that should be added to the edu-sig page, please let me know.

(1) Actually, this is not exactly correct ... but if you want to send me some for reviews, I won't say no. ;-)

(2) The page linked here will eventually disappear...

Friday, April 10, 2009

Learning paths at ShowMeDo

ShowMeDo is a great site to learn about Python (and a few other subjects) by watching screncasts. One of my favourite videos is Learn Django: Create a Wiki in 20 minutes, which taught me the basic concepts so that I was later able to adapt and play around with Google App Engine. Many authors on ShowMeDo have multiple screencasts (I made a few on RUR-PLE and Crunchy a while ago), some of which (not mine) are very professional looking. Such series of videos give the viewpoint of a given author, introducing some concepts in a logical sequence.

The newest addition to the ShowMeDo site is called Learning Paths. The idea of Learning Paths is to improve upon the existing series by including videos from multiple authors into a coherent sequence. While this concept is very much in its infancy, it promises to become a great addition to what is already a fantastic site.

In case anyone were wondering: I have no financial interest whatsover in ShowMeDo; I am just a satisfied user who considers this site a very good resource, well worth exploring. If only I had more time...

Thursday, January 08, 2009

Testing code highlighting

Update:

In order to have the styling work, I had to include by hand the styling information (keyword and string) from this style sheet - and adapt as desired.

- - - - - - -
This is a test of Python code highlighting on Blogger following these instructions.
print "Hello World!"

# And this is a comment
End of test.