One assignment, 2075 (optimal)
This should be the optimal value (unless I have a big error in reasoning or my testing sucks).
First of all. There are only 7 different numbers (mod 128) you can express in 99. All values of 7 or more 9 evaluate to the same number 71. (Because 10^8 mod 128 == 0, 10^9 mod 128 == 0, ...)
If one of the 4 values you can express with an even number of nines, than outputting this number is clearly the optimal solution.
Otherwise I try to reach the number with one assignment statement (assign to 99) and print 99. As it turns out the maximal program size with this approach is 22 char. Clearly using Goto takes definitely more than that. The only possibility that a one-assignment solution might be beaten is a solution with two assignments. I tested this (hopefully with no errors, the code for this is quite messy), and found no solution for any ASCII char.
Therefore only checking the 4 direct numbers and the one-assignment approach should be enough to find the optimal solution. The following Python (2 and 3 compatible) program generates all programs and sums up their lengths. It uses a simple IDA* approach.
from itertools import count
def nines_to_dec(nines):
return ((10**nines - 1) // 9) % 128
def shortest_representation(ascii_value):
# try simple output,
# max code length is 8, (8 nines == 10 nines == 12 nines == ...)
# if this works, than this is the shortest representation
for nines in range(2, 9, 2):
if nines_to_dec(nines) == ascii_value:
return "9" * nines
# otherwise try one assignment
for length in count(1):
result = assignment(ascii_value, length, [])
if result:
return "99 " + result + "\n99"
def assignment(value, left, nines_list):
if left == 0:
eval_numbers = [nines_to_dec(nines) for nines in nines_list]
if (sum(eval_numbers[::2]) - sum(eval_numbers[1::2])) % 128 == value:
return " ".join("9" * nines for nines in nines_list)
else:
return False
for nines in range(1, 8):
left2 = left - nines - 1 # -1 for space
if left2 >= 0:
result = assignment(value, left2, nines_list + [nines])
if result:
return result
return False
lengths = []
for i in range(128):
program =shortest_representation(i)
lengths.append(len(program))
print("ASCII-value: {}, ASCII-char: {}".format(i, chr(i)))
print(program)
print(sorted(lengths))
print(sum(lengths))
The output is of the following form:
....
ASCII-value: 65, ASCII-char: A
99 9 999999 9999999
99
ASCII-value: 66, ASCII-char: B
99 9 99 9999 99
99
ASCII-value: 67, ASCII-char: C
99 9 99 9 99 9999
99
....
You can find the complete output at: http://pastebin.com/bKXLAArq
The char with the shortest program (2 char) is vertical tab - 11
with a program length of 2, the chars with the longest programs (22 char) are bell - 7
and A - 65
.
The sum for all programs is 2075.
And by the way, I used the k/q interpreter from tmartin. I hat quite some troubles with the other ones (Python, Perl, CJam). Not sure if it was my fault.
It would help implementors of interpreters if you could describe what troubles you had. Great answer. – coredump – 2015-03-15T06:55:19.527