12
\$\begingroup\$

The proof of the set of characters is that there is a translator which takes any ascii python program as input and produces a limited character set version of the program. The limited character set program can be slower than the original program. It simply has to be possible to produce the same output as the valid python program.

For example, here is a translator that takes any ascii python program as input and writes out a version that doesn't use the character x:

import random
import string
with open('in.py') as infile:
    with open('out.py', 'w') as outfile:
        lines = infile.readlines()
        outfile.write("data = '")
        random_string = ''.join(random.choice(string.digits) for x in range(20))
        for line in lines:
            outfile.write(line.encode('string-escape').replace('x', random_string))
        outfile.write("'\n")
        outfile.write("exec data.replace('%s', chr(%s))" % (random_string, ord('x')))

note that this will fail if the program happens to have the random string in it already, but for the purposes of this question lets accept that 'any' can be slightly limited. We don't have to consider extremely low probabilities of failure due to random chance or a malicious input program.

Improve this question
\$\endgroup\$
9
  • 2
    \$\begingroup\$ The question is? No idea about the sense of this "questions" \$\endgroup\$ – Maulwurfn Aug 11 '12 at 11:44
  • \$\begingroup\$ good luck writing a useful program without sorted(set('import for while = in : if def [] return class () break .')) On the other hand, you can write en.wikipedia.org/wiki/Whitespace_(programming_language) programs with only three characters. \$\endgroup\$ – msw Aug 11 '12 at 12:04
  • 1
    \$\begingroup\$ @vishvanda: While this question has problems, it did inspire me to write such a translator, which removes all characters except for "()+,.1[]cehijnorx. My solution is here. \$\endgroup\$ – David Robinson Aug 11 '12 at 13:18
  • 2
    \$\begingroup\$ @msw: As you can see in my gist, it's actually possible to write any Python program with just the characters "()+,.1[]cehijnorx). \$\endgroup\$ – David Robinson Aug 11 '12 at 13:20
  • 1
    \$\begingroup\$ By the way, I've improved my solution to use only 9 characters: ()+1cehrx. \$\endgroup\$ – David Robinson Aug 11 '12 at 19:29
17
\$\begingroup\$

I've come up with a 9-character translator using exec (also posted at this GitHub gist):

def convert_txt(txt):
    """Convert the text of a Python program to minimal Python"""
    s = "+".join(["chr(%s)" % "+".join(["1"] * ord(c))
                            for c in txt])
    return 'exec(%s)' % s

The only characters it needs are ()+1cehrx.

Improve this answer
\$\endgroup\$
10
  • \$\begingroup\$ LOOOOOOOOOOOOOL +1 \$\endgroup\$ – Ev_genus Aug 14 '12 at 9:34
  • \$\begingroup\$ Does Python permit literal chr(0) characters in strings? \$\endgroup\$ – Peter Taylor Aug 14 '12 at 19:17
  • \$\begingroup\$ That's not how it's used here. This creates a program whose string is like exec(chr(1+1+1...)+chr(1+1...)). The new program thus uses only 9 characters, reconstructs the string, and uses exec \$\endgroup\$ – David Robinson Aug 14 '12 at 19:45
  • \$\begingroup\$ Precisely. So if I pass it a Python program which contains a literal chr(0) it will break. The most obvious place in which a literal chr(0) would be valid is inside a string. \$\endgroup\$ – Peter Taylor Aug 15 '12 at 9:00
  • \$\begingroup\$ Sorry, I misunderstood your original question. Anyway, I've been able to use it: for example, chr(100) + chr(0)+chr(65) yields 'd\x00A'. Am I missing something? \$\endgroup\$ – David Robinson Aug 15 '12 at 13:02