Friday, December 30, 2005

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

20 comments:

Marius Gedminas said...

Wow.

How did you come up with the numbers?

André said...

All 3-string combinations can be represented by an index varying between:
0:3, 0:12, 0:10
where I use the Python slice notation. Thus, the shorter sequence for the modulus operation (i.e. that will give the fewer "wasted" indices) are
%3, %12 and %10. However, 3 is a dividor of 12 which means that, as we % from 1 to 255, there's going to be too much of an unwanted overlap (and not all relevant sequences will be generated). The next attempt has to be
%3, %14, %10
where the smallest prime numbers (2, 3, 5, 7) are used. Still, unless I am mistaken, to generate all 3-number combinations with these, you might need 3*14*10 = 420 consecutive integers. I wrote a little program (tried it with various combinations) and it was sheer luck that this generated all the required combinations with integers < 256!

Justin said...

Is there an typo in the post somewhere?
>>> s=' _ |_|_ _| |'
>>> s[0:][:3]
' _ '
>>> s[11:][:3]
'|'
>>> s[5:][:3]
'|_ '
>>>

To get '0' I have to use
0, 9, 3

also, with that string, how would you generate 1, which needs ' ' and ' |' ?

Joost said...

I tried to dig into your code to see how it works, but the output is not quite right.

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)
)
>>> print seven_seg("0123456789")
 _  |_ _  _  |_ _  _  _  _  _ 
||_|| || ||_  _| _||_||_ |_ 
|_ |_| _|| ||_|| ||_ |_||_ | |

(hope blogger will let me use &nbsp;)

The code string seems to be all right (the original post accidentally includes two single quotes in the second string).

That aside, congratulations with this ingenious little lambda function.

André said...

Sorry, I had left out some "pre" tags and spaces were wrongly indicated. It should be fixed now!

Runsun said...

Just tried to run the test.py a min ago, got:

'0' should result in:
_
| |
|_|

but your module produced:
_
| |
_|

Guess the blog is doing somthing weird?

Anonymous said...

Absolutely brilliant technique -- thanks for sharing! I knew there had to be a way to get rid of that extra space.

Just for fun, I tried to see if there was an ASCII-only solution using this technique, using different values of the two main strings and three integers.

I found 30 such combinations, none of which had fewer than 3 non-ASCII characters... oh well.

You could have used \xd5 instead of \x03 without changing the other string or the integers, as 0xd5 is also congruent to 0, 3, and 3 mod 3, 14, and 10, respectively.

Thanks again for posting your solution!

André said...

Sorry everyone about the problem with the spaces. I sent a copy of the working program to Simon Hengel (of PyContest fame!); hopefully he will agree to post it along with the other solutions.

Anonymous said...

Just for fun, here's a 119-character long variant of
your superb idea that's ASCII only. (Remove the line breaks to make it work!)

j=''.join;seven_seg=lambda z:j(j(' _ | |_ _|_|'
[ord('^r|=Zm.:v\r'[int(a)])%u*2:][:3]for a in z)
+"\n"for u in(3,7,8))

Christoph Zwerschke said...

Great work, André!

As already noted, there are some problems when you cut&paste the code from HTML because it has only single whitespace (copying from HTML source should work).

Mark's proposal is nice, but has an escaped CR (\r) as the last character in your string.

Here is a 118 character fully printable variant without the \r:

j=''.join;seven_seg=lambda x:j(j(' _ |_|_ _| |'[ord('^rm=3|4:s»'[int(c)])%d*2:][:3]for c in x)+"\n"for d in(3,8,7))

Note that there is only one non-ascii character in the code.

Also, as already mentioned, you can get rid of the 0x3-Byte like this:

j=''.join;seven_seg=lambda z:j(j(' _ | |_ _|_|'
[ord('^r|=Zm.:v\r'[int(a)])%u*2:][:3]for a in z)
+"\n"for u in(3,7,8))

Christoph Zwerschke said...

Sorry, I missed the point. Mark's solution was fully 7-bit though it was one char longer. It's questionable whether my shorter solution should be called "printable" because of the one 8-bit char (there is a difference between "visible" and "printable").

In the next contest, there should be subcategories for pure 7-bit ascii and no imports.

Matt Wilson said...

Wait -- what does

j=''.join;

accomplish?

André said...

Matt:

If you look closely, you will see that the solution reads:

lambda z:j(j( ...

Without j=''.join, this would have been

lambda z:''.join(''.join( ...

Even accounting for defining j, this assignment shortens the overall solution.

Mark Dickinson said...

Nice solution Christoph!

I was unhappy with the carriage return too, until I realised that while there is a CR in the string, there actually isn't any CR in the Python *source*; merely an r and a backslash next to each other. So every character c in the solution has ord(c) between 32 and 126, which I guess is what I meant when I said `fully printable' (though tabs and newlines should also be considered printable, I suppose).

Still, this isn't `my solution'; it's the result of my playing with André's solution. Before seeing this, my best solution was still running at around 180 chars!

Mark (having figured out how to post non-anonymously).

Anonymous said...

>>> print seven_seg("7337")
_ _ _ _
|_ _| _||_
|_||_ |_ |_|

>>>

Ummm, its very nice program, i tryed to do the python challenge too but couldnt get a workin test, however, urs prints out each digit 1 lower.. y?

André said...

Here's the result of an interactive session, with forbidden characters (by blogger) replaced...

Furthermore, pre-formatted html is not allowed here :-(

>>> j=''.join
>>> print '\xa5\x8f\xb1\xdb\xad\xbdi\x03K\x9f'
######### -> to be pasted in below
>>> seven_seg=lambda z:j(j('~_~~~|_|_~_|~|'
... [ord("#########"[int(a)])%u:][:3]for a in z)
... +"\n"for u in(3,14,10))
>>> print seven_seg('0123456789')
~_~~~~~_~~_~~~~~_~~_~~_~~_~~_~
|~|~~|~_|~_||_||_~|_~~~||_||_|
|_|~~||_~~_|~~|~_||_|~~||_|~_|

Anonymous said...

Hi André!

[OT]-question:

You write that it's been a while since you did any programming. I'm very interested in RUR-PLE, but it's been while since anything happened - how is 1.0 coming along?

/Håkan

André said...

Regarding RUR-PLE:

I just started again working on it last week. I've revised the first 20 lessons or so, making a few small, but important changes. I'm hoping to have version 1.0 done in about three months. This will include anywhere between 20 and 30 additional lessons as compared with 0.9. It will include dealing with classes and objects, both within rur-ple and for stand-alone programs.

After completing version 1.0, I am planning to continue expanding the lessons with an introduction to pygame.

Anonymous said...

That sounds great! I think the work so far has been fantastic! I'm looking forward to 1.0.

/Håkan

Rosie said...

These comments have been invaluable to me as is this whole site. I thank you for your comment.