117 Outdone by a reader!

Markus Schramm from Germany has left a comment on my post Journey to 117 showing how one could shave yet one more character from the 117 character solution to the PyContest challenge. So, 116 it is!

css, wxHtmlWindow and going back to RUR-PLE

About a month ago, my second computer (actually, my main computer as the kids had taken over the better one) died. I had saved the hard-drive and managed tonight to recover the data on it. I found the beginning of a "standard" tutorial (in French) that I had started to write so that my kids could learn Python. That was in August 2004. Shortly afterwards, I discovered Guido van Robot and got inspired to create RUR-PLE. I worked fairly steady on it for a year and then, somehow, haven't been able to find the time to work on it for the past few months.

While I have been quite please with RUR-PLE in general, I have found one thing less than satisfactory: RUR-PLE uses wxPython and wxHtmlWindow to display its tutorial. Unfortunately, wxHtmlWindow does not support style sheets, but only simple html tags. My French tutorial made use of all kinds of css tricks in an attempt to have a pleasant look. I had to gave that up and hard-code font information in the tutorial that has been included with RUR-PLE.

I have found the result with wxHtmlWindow and hard-coded fonts to be somewhat disappointing. So, today I decided that I had to try and implement some work-around so that at least I could use style-sheets to colorize the source code and headings. I have made some limited progress and I hope to have something working soon, so that I can 1. change the existing lessons so that they use some (limited) styles instead of hard-coded font information, and 2. go back to writing some more lessons and get to version 1.0!

Note: I know of the existence of wxMozilla, but haven't been able to get it to work last time I tried. RUR-PLE, which is geared towards beginners (or teachers!) already require three separate installs (Python, wxPython, and itself!). I find this is already a bit much. Besides, if I haven't been able to get wxMozilla to work on my computer, how could I expect a complete beginner to do it?...

Journey to 117

This blog entry is dedicated to Michael Spencer whose 120 character-long entry in the PyContest was submitted less than 90 minutes after the official beginning of submissions. Michael's entry gave a target to aim for which few people managed to reach. I strongly suspect that, in large part because of this, various hints have been posted on the web, enabling more people to slowly crawl towards ever-shorter solutions. I must admit that without the various hints I have read, I would never have been able to challenge Michael's solution.

After being asked a few questions here and elsewhere, I've decided that I should try and document the reasoning that eventually led me to my final solution to the PyContest. Of course, it is going to be more linear here (and with fewer dead-end explorations) than it was in real life. I definitely welcome comments from others' journeys.

First solution

After writing on paper the desired output for an input that included all digits, I quickly wrote down the following program to produce the desired output:

def seven_seg(i):
~~n=[[" _ ","   "," _ "," _ ","   "," _ "," _ "," _ "," _ "," _ "],
~~~~~["| |","  |"," _|"," _|","|_|","|_ ","|_ ","  |","|_|","|_|"],
~~~~~["|_|","  |","|_ "," _|","  |"," _|","|_|","  |","|_|"," _|" ]]
~~m=''
~~for j in 0,1,2:
~~~~for d in i:
~~~~~~~~m+=n[j][int(d)]
~~~~m+='\n'
~~return m
print seven_seg('0123456789')

In an attempt to preserve the visual appearance, I have replaced all the leading spaces by "~". In the future, whenever you see a "~", take it to be a space. After removing the print statement, the number of characters is 310, which is quite a ways from 117. One can reduce the number of characters by removing many unnecessary spaces but I will not do that until we are much closer to the "final" solution. Furthermore, I will keep the explicit for loops rather than using generators [with the ''.join() method] until the very end as I find the code easier to read that way. I will, however, move the [m=''] assignment within the function argument, thus removing a line (and at least two extra characters!) from the solution.

My next step was to look at the various "triplets" (three-character combinations) that appeared in "n". Quite a few are repeated. In fact, there are 7 unique triplets; they are:

"~~~", "~_~", "~_|", "|_~", "|_|", "~~|", "|~|"

With this ordering, and giving each triplet a number from 0 to 6, we have each input digit can be given by the following three number combination:
0=164, 1=055, 2=123, 3=133, 4=065, 5=132, 6=134, 7=155, 8=144, 9=142.

Note that the first digit of each triplet is either a 0 or a 1; this will be important later. Using these triplets leads to a second, shorter, solution:

def seven_seg(i, m=''):
~~n=["~~~","~_~","~_|","|_~","|_|","~~|","|~|"]
~~for j in '1011011111', '6622433544', '4632524542':
~~~~for d in i:
~~~~~~m+= n[int(j[int(d)])]
~~~~m+= '\n'
~~return m 

Note that the string '1011011111' represents the first digit of each triplet, and that the order in which they appear is '0123456789'.

By moving the inner for loop statement (5th line) at the end of the 4th line, using a single space for the first indentation and a tab character (expanded by Python to 8 spaces) for the second level of indentation and removing other non-required spaces, it is possible to reduce the length of the code to 171 characters -- still a long way from our final goal.

The next step is to eliminate "n" altogether; we can do this in two steps.
The first step is simply use it as is in the line

def seven_seg(i, m=''):
~~for j in '1011011111', '6622433544', '4632524542':
~~~~for d in i:
~~~~~~m+= ["~~~","~_~","~_|","|_~","|_|","~~|","|~|"][int(j[int(d)])]
~~~~m+= '\n'
~~return m 

The second step is to try to replace the list of strings by a single string and extract, when assigning, a 3-character substring. The shortest such string that we can construct is 14 character long. There are many such strings; here is one of many examples:

'~_~_|_~~~|~|_|'
~01234567890123 

Using this string, we see that the last 3-character substring, '|_|', starts at index 11. To encode the position of each beginning index, we would need at least 2 digits for some. A better way appears to lengthen the string a bit so that each required 3-character substring starts on an even index -- the last character of one substring being the first character of the next. Here is one such solution -- which, other than for some unnecessary spaces, is the exact first solution that I submitted at the exact opening of the contest at 14:00 UTC; for one minute it was in first place. :-)

def seven_seg(i, m=''):
~for s in '5455455555', '2600133611', '1630601610':
~~for k in i:
~~~~j=int(s[int(k)])*2;
~~~~m+='~_|_|~|_~~~_~~|'[j:j+3]
~~m+='\n'
~return m

Not having done any programming for a while, I didn't realise at the time that 'some_string'[j:j+3] could be written as 'some_string'[j][:3], thereby saving one assignment (to j) and some precious characters all around.

The next step is to try to shorten the three long numbers: '5455455555', '2600133611' and '160601610'. This can be done by encoding them in a base other than 10 and extracting the result when needed. A better way however is to re-arrange the number as a series of triplets and then encode the result. For example, the three long numbers just mentioned can be re-ordered as follows:

0=521, 1=466, 2=503, 3=500, 4=416, 5=530, 6=531, 7=566, 8=511, 9=510

This gives rather large integers (ex: 521) to try to encode in a base different from 10. A better choice would be to use the ordering

0=164, 1=055, 2=123, 3=133, 4=065, 5=132, 6=134, 7=155, 8=144, 9=142

that we had mentioned earlier, as it gives smaller integers. Now, Python's built-in function int() allows conversion to base 10 from other bases up to 36. Still, that would require a 2 character encoding from each triplet. A better choice is to take each triplet to be the decimal representation of an ascii character. As each triplet is a number less than 255, this is certainly possible (barring some unfortunate coincidence when a given triplet would correspond to a newline character.)

Actually, since none of the individual digits in the triplets is greater than 6, we can take them to be numbers in a base less than 10; from what I gather, most people chose 8 (as they try to do stuff with bit shifts and the like) and I chose 7 (for one of my submissions). Thus, a number like 164 is taken to mean

164 (in base 7)= 1*49 + 6*7 + 4 = 95 (in base 10). This will help further reduce the number of characters. Let's assume that everything is correct with these choices (i.e. still no newline character) and that the encoding of our triplets can be represented as

0=z, 1=o, 2=t, 3=T, 4=f, 5=F, 6=s, 7=S, 8=e, 9=n

where I have use the first letter of each number as a representation of its encoding.

As an aside, some useful comments about this (and other aspects of this problem) can be found on the following two blog entries (including comments):

Guyon Morée's blog



Roberto Alsina's blog

The corresponding program, still written with the explicit for-loops, can be written schematically as follows:

def seven_seg(i, m=''):
~for a in 49, 7, 0:
~~for k in i:
~~~~m+='~_|_|~|_~~~_~~|'[ord("z0tTfFsSen"[int(k)])/a%7*2:][:3]
~~m+='\n'
~return m

Let's examine what the innermost loop does. We convert each character in the input string into a digit, extract the corresponding ascii-encoded triplet, decode it into an actual number, divide by the appropriate power of our base and take the modulo in that base, thus extracting the relevant digit in the triplet; the result is multiplied by 2 to find the relevant index in our string of "~|_". So you can see the advantage of using a base less than 10 as it takes fewer characters to write.

To make the solution as short as possible, we rewrite it as a lambda and use join() and generators instead of explicit for loops. This also eliminates the use of an extra variable ("m"). The result can be written as:

j=''.join
seven_seg=lambda i:j(
j('~_|_|~|_~~~_~~|'[ord("z0tTfFsSen"[int(k)])/a%7*2:][:3]for k in i) 
+'\n' for a in(49,7,0))

When all the extra spaces are removed, this gives a 121-character long solution. I'll refer you to the already mentioned blogs for a 120 character long solution!

To get to 117 characters, we need a slightly different approach.

We need to go back to some assumptions we made earlier. Do we really need to have even-numbered indexes? If not, we could use a shorter "~|_" type string which included all relevant 3-character substrings, thereby possibly saving one character. Let us look at such a possible string and the various indices. I will take the string of my posted 117 character long solution '~_~~~|_|_~_|~|', and extract the location of the indices of the relevant substrings:
"~~~":2, "~_~":0, "~_|":9, "|_~":7, "|_|":5, "~~|":3, "|~|":11.
With these 3-character substrings, our triplets are:

0=0-11-5, 1=233, 2=097, 3=099, 4=253, 5=079, 6=075, 7=033, 8=055, 9=059

For each triplet, instead of encoding it in a given base, we will look at a number which, when taking the modulo with three different bases, will give us back the relevant digit. By this, I mean something like the following:

165%3 = 0
165%14 = 11
165%10 = 5

i.e., the triplet for "0" could be represented by the integer 165 when taking the modulo with 3, 14 and 10 respectively - as I have done in the 117 solution. Using brute force, which is what one does when one is too tired, one can loop over the integers less than 255 and find out if all the relevant triplets can be found. Or, you notice that 11*5*3 = 165 [11%14=11, 5%10=5, 3%3=0], and you proceed from there. With this information (and the comments on the previous blog entry), you should now have all the relevant information to understand how this solution was obtained.

On that final note, I wish you a very Happy New Year!

pyContest challenge: 117 character-long solution

It has been quite a while since I did any programming; the absence of posts on this blog (nothing since the end of July) is a reflection of this. Still, with a welcome break during the Xmas holidays, I got spurred back into action with the http://www.pycontest.net/ pyContest challenge. It has been fun.

On to serious business. A 117 byte solution to the challenge is given by:

j=''.join;seven_seg=lambda z:j(j(' _   |_|_ _| |'
[ord("'\xa5\x8f\xb1\xdb\xad\xbdi\x03K\x9f'"[int(a)])%u:][:3]for a in z)
+"\n"for u in(3,14,10))

where I have written the encoded string in a way that blogger would not complain about and added some line breaks as blogger breaks it up at inappropriate places. Last night, I couldn't figure out how to generate the string with the \x03 character included. (Today, after the challenge was over, I simply did print chr(3) in a Python interpreter and cut and paste the appropriate character in the string.) My attempts at generating the encoded string and printing to a file with the \x03 character included always resulted in an empty file.

So, what I did was to subtract one from each character before writing to the file ... and then change "ord" to "-~ord" to shift back the values to the right ones ... but thereby adding two extra characters. As this was already a solution shorter than those posted, I decided it was time to give up and try to get some much needed sleep.

Note that the string ' _ |_|_ _| |' is shorter than the "usual one" where the 3-character strings start on an even index.

Here's how to generate the encoded string (with 33 replacing 3; replace with cut-and-paste after):

dec_list=(165,143,177,219,173,189,105,33,75,159)
encoded = ''.join(chr(i) for i in dec_list)

These decimal numbers encode the following
>>> 165%3
0
>>> 165%14
11
>>> 165%10
5

Thus the number '0' is represented by (0, 11, 5) which are the beginning indices of 3-character strings in ' _ |_|_ _| |'. Thus,
'0' = (' _ ', '| |', '|_|').

I was going to wait until the official announcement to post this but thinking of how curious I was earlier on to eventually find out what I thought would be the winning solution (120 character), I decided it was time to do it.

Note For a more detailed explanation, see the next entry at Journey to 117

Poor man's i18n

Internationalization (i18n) of a [Python] program appears to be daunting task. After looking on the web, I haven't been able to find a simple tutorial explaining the steps to be taken; the closest that I have found is the wxPython one, on the wxPython wiki. The procedure described appears to be rather involved, even if one only deals with translations of text (and not localization of dates, currencies, etc.), which is what I will focus on.

The first step is the replacement of all strings of the form:
"This needs to be translated"
by the following call (interpreted to be a C macro in Gnu's gettext)
_("This needs to be translated")
which is very simple.

The standard way then requires the use of gettextand results in the creation of ".pot" files (Portable Object Templates) to be copied and translated in ".po" (Portable Object) files by a human translator; these are then converted into ".mo" (Machine Object) files by a compiler. Yet, a few more steps, mostly dealing with directory structures and setting up locales, are needed before one can conclude the process.

I present here a simpler way to proceed which, at a later time, can easily be converted to the standard gettext method as it basically uses the same "_()" notation required by gettext. This was inspired by a comp.lang.python post by Martin v. Löwis to a question I asked almost a year ago.

Consider the following simple (English) program [Note: "." are used to indicate indentation as Blogger appears to eat up leading spaces]

def name():
....print "My name is Andre"

if __name__ == '__main__':
....name()

The French translation of this program would be

# -*- coding: latin-1 -*-
def name():
....print u"Je m'appelle André"

if __name__ == '__main__':
....name()

Without further ado, here's the internationalized version using a poor man's i18n method and demonstrating how one can easily switch between languages:

from translate import _, select

def name():
....print _("My name is Andre")

if __name__ == '__main__':
....name()
....select('fr')
....name()
....select('en')
....name()

The key here is the creation of the simple translate.py module:

__language = 'en'  # leading double underscore to avoid namespace collisions

def select(lang):
....global  __language
....__language = lang
....if lang == 'fr':
........global fr
........import fr
def _(message):
....if  __language == 'en':
........return message
....elif  __language == 'fr':
........return fr.translation[message]

together with the language-specific fr.py module containing a single dictionary whose keys are the original English strings.:

# -*- coding: latin-1 -*-

translation = {
"My name is Andre" : u"Je m'appelle André"
}

That's it! Try it out!

In conclusion, if you want to make your programs translation friendly, all you have to do is:

1. replace all "strings" by _("strings")
2. include the statement "from translate import _, select" at the beginning of your program.
3. create a file named "translate.py" containing the following:

def select(lang):
....pass

def _(message):
....return message

and leave the rest to the international users/programmers; you will have done them a huge favour!

N = N + 1

When first learning about programming, most people get confused by expressions like
N = N + 1
The origin of the confusion is easy to understand. Expressions like
N = N + 1 often occurs in a computer program dealing with mathematical concepts. And, in mathematics, the expression
N = N + 1
is just plain wrong. Ergo the confusion. To get around the confusion, some programming language introduce a different symbol for "variable assignment". Something like ":=" , or "<--" can be used for that purpose. Python uses the equality symbol for variable assignments. As a result, beginners are often presented with the baffling N = N + 1 before they have understood enough about the language to grasp quickly what is meant by that expression. I suggest that examples based on a "human language context" as opposed to a traditional "mathematical context" could be more useful to teach the meaning of variable assignment.

1. A little story

John, Pierre and Antonio are three good friends that share a house. John is originally from England, Pierre from France and Antonio from Spain.

One day, John was speaking in English to Pierre. During that conversation, John said the word "once", referring to an event that occurred a single time. Pierre translated this concept in his mind as "une_fois".

>>> once = 1
>>> une_fois = once

>>> print 'once = ', once, '     une_fois = ', une_fois
once =  1      une_fois =  1

Later that day, John was speaking in Spanish to Antonio. He mentioned his favourite number: "once" (11), made up of the same letters as the English word "once".

>>> once = 11

However, the conversation that John is having with Antonio has not changed the meaning of "une_fois" for Pierre.

>>> print 'once = ', once, '     une_fois = ', une_fois
once =  11      une_fois =  1

The various words in human languages are associated with concepts or objects that are independent of the words used to represent them. So, "une_fois" is associated with the number 1, through its association with the word "once". However, "once" is just a word, not an object. So, when "once" takes on a different value later, the concept represented by "une_fois" is unchanged.

2. The meaning of = in Python

In Python the symbol "=" associates a synonym on its left hand side to a concept on its right hand side.

synonym = concept/object

Words that are chosen as synonyms, are chosen in a context dependent way. In our later story above, names are chosen based on the "human language context". The same combination of letters can mean two different things in different languages, or even in the same language. I remember a little test a friend of mine did in grad school, showing parts of a newspaper headline to fellow classmates (all science geeks) and asking them to quickly read it aloud. The word "unionized" appeared in the headline. Now, think "labour" and "chemistry" and you will think of two different way of pronouncing this word.

Now, in the typical programming situation, "N+1" represents a mathematical concept. We can give it a (temporary) synonym of our own chosing, depending on the context...

3. Another short story

John makes a groceries shopping list, with two items: "bananas" and "pears". He then tapes it on the fridge door.

>>> groceries = ["bananas", "pears"]
>>> epicerie = groceries
>>> print groceries
['bananas', 'pears']
>>> print epicerie
['bananas', 'pears']

Later that day, Pierre walks by and notices the list too (une liste d'épicerie) which he associates with the word epicerie. Still later that day, John adds "apples" to the list on the fridge door. He notices that Antonio had already bought pears and remembers that they also need oranges. He thus scratches the item "pears" and replace it by "oranges".

>>> groceries.append("apples")
>>> print groceries
['bananas', 'pears', 'apples']

>>> groceries[1]="oranges"
>>> print groceries
['bananas', 'oranges', 'apples']

>>> print epicerie
['bananas', 'oranges', 'apples']

The list has changed throughout the day, but it remains taped to the fridge. When they think about the grocery list, both John and Pierre are referring to the same object in their own language. When that object changes, it changes for both of them in the same way.

4. Yet another short story

John makes a groceries shopping list, with two items: "bananas" and "pears". He then tapes it on the fridge door. Later that day, Pierre walks by and notices the list and decides to make his own copy.

>>> groceries = ["bananas", "pears"]
>>> epicerie = list(groceries)

Still later that day, John adds "apples" to the list on the fridge door. He notices that Antonio had already bought pears and remembers that they also need oranges. He thus scratches the item "pears" and replace it by "oranges".

>>> groceries.append("apples")
>>> groceries[1] = "oranges"
>>> print groceries
['bananas', 'oranges', 'apples']

Pierre's list, however, is unchanged.

>>> print epicerie
['bananas', 'pears']

Let's just hope that Pierre won't go out and buy pears!

5. Conclusion?

Your comments are going to provide a much better conclusion than I could write at this point!

News about rur-ple

Things now seem to happen all at once on the rur-ple front.

A. Judkis at the Academy of Allied Health and Science, in Neptune NJ, had decided to inflict RUR-PLE on his 10th graders. The response has been so far very positive from the students from what I hear.

Someone contacted me offering to translate RUR-PLE in Spanish. Hopefully this can be done before version 1.0 is released.

A number of bugs were introduced accidently in version 0.8.5 - mostly due to the language selection ability (English/French) that was added. These bugs never manifested themselves on my computer, but they seem to affect everyone else! I suspect it's because I have a French version of Windows. These bugs should now be fixed in version 0.8.6a.

I have a neat (I think) Tower of Hanoi solution worked out and included (undocumented) in version 0.8.6a. This version also includes a solution to the 8 queen puzzle (also undocumented).

Unfortunately, I will be on the road for 3 weeks in June, and will not have time to do significant work on RUR-PLE for a while.