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!