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.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ The question is? No idea about the sense of this "questions" \$\endgroup\$
    – Maulwurfn
    Commented Aug 11, 2012 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
    Commented Aug 11, 2012 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\$ Commented Aug 11, 2012 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\$ Commented Aug 11, 2012 at 13:20
  • 1
    \$\begingroup\$ By the way, I've improved my solution to use only 9 characters: ()+1cehrx. \$\endgroup\$ Commented Aug 11, 2012 at 19:29

1 Answer 1

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.

\$\endgroup\$
10
  • \$\begingroup\$ LOOOOOOOOOOOOOL +1 \$\endgroup\$
    – Ev_genus
    Commented Aug 14, 2012 at 9:34
  • \$\begingroup\$ Does Python permit literal chr(0) characters in strings? \$\endgroup\$ Commented Aug 14, 2012 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\$ Commented Aug 14, 2012 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\$ Commented Aug 15, 2012 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\$ Commented Aug 15, 2012 at 13:02