11
\$\begingroup\$

99 is a programming language I invented earlier this week for my challenge Write an interpreter for 99. (Invented but never needed to implement thanks to half a dozen of you. ;) ) The full language spec is in that challenge so I'm not bothering to repost it all here.

In 99 you can print individual ASCII characters to stdout, but due to the constraints of the language, it is not always clear how to print a particular character as concisely as possible.

For each of the 128 ASCII characters, write a 99 program that takes no input and outputs that sole character. You may code any or all of these answers by hand, or you can write another program (in any language you like) to generate them for you.

The sum of the characters in each of your 128 99 programs is your score. The lowest score wins. Newlines count as one character.

Remember, in 99, only even sized variables like 9999 output ASCII characters (odd sized variables output integers). Their value is divided by 9 and then taken mod 128, so values do not need to be in a certain range to map to ASCII characters. For example, the internal values 297, 1449, and -855 all correspond to the character ! because when they are divided by 9 and taken mod 128, they all become 33, which is the character code for !.

If you need an interpreter for 99, I'd suggest Mac's Python answer.

I know I said my next challenge would be more interactive but I'm still working on the stuff for that one.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It would help implementors of interpreters if you could describe what troubles you had. Great answer. \$\endgroup\$ – coredump Mar 15 '15 at 6:55
3
\$\begingroup\$

A Variety of Techniques, 42109

For the numbers, instead of calculating the large ASCII character, I just calculated the number's value. You only said to be able to output the character, so this should still work.

EDIT: Switched the numbers to use the ASCII characters, so disregard that. I left the original number code in the Java code but commented out in case anyone wanted to use it.

Some of these I did by hand, most I just wrote a program to type out.

These are made up of 1-4 lines each, so they're fairly friendly to just copy and paste into a program. It should be noted that they don't work in succession due to my generated code not preserving variable states.

The most common technique used here was the same as orlp's approach:

Keep subtracting 9 from 99, then output.

My version differs by using some custom cases and composing a lot of the math onto just one line. Custom cases are just where the character can be represented with just a bunch of 9's and no math or my generation code could be shortened.

Programs

I've put the output on Pastebin for those of you who don't feel like running the program:

http://pastebin.com/Cs6WZUfb

Java Code I used:

public class AsciiGen99 {

  public static void main(String[] args) {
    long totalsize = 0;
    for (int i = 0; i < 128; i++) {
      System.out.println("\n The program for ASCII code " + i + " is as follows:\n");
      String yea = find(i);
      if (yea != null) {
        System.out.println(yea);
        totalsize += yea.length();
      } else {
        String v = "99 9 9\n9 99 9";
        if (i != 0) {
          v += "\n99";
          for (int j = 0; j < i; j++) {
            v += " 99 9";
          }
        }

        v += "\n99";

        System.out.println(v);
        totalsize += v.length();
      }
    }
    System.out.println(totalsize);
  }

  public static String find(int i) {
    switch (i) {
      case '\0':
        return "99 9 9\n99";
      case '\1':
        return "99 9\n99";
    }
//    if (48 <= i && i <= 57) {
//      switch (i) {
//        case '0':
//          return "9 9 9\n9";
//        case '1':
//          return "9";
//        case '2':
//          return "999 9 9\n9 999 9\n999 999 9 999 9\n999";
//        case '3':
//          return "999 9 9\n9 999 9\n999 999 9 999 9 999 9\n999";
//        case '4':
//          return "999 9 9\n9 999 9\n999 999 9 999 9 999 9 999 9\n999";
//        case '5':
//          return "999 9 9\n9 999 9\n999 999 9 999 9 999 9 999 9 999 9\n999";
//        case '6':
//          return "99 9 9\n9 99 9\n999 99 9 99 9 99 9 99 9 99 9 99 9\n999";
//        case '7':
//          return "99 9 9\n9 99 9\n999 99 9 99 9 99 9 99 9 99 9 99 9 99 9\n999";
//        case '8':
//          return "99 9 9\n9 99 9\n999 99 9 99 9 99 9 99 9 99 9 99 9 99 9 99 9\n999";
//        case '9'://ironic
//          return "99 9 9\n9 99 9\n999 99 9 99 9 99 9 99 9 99 9 99 9 99 9 99 9 99 9\n999";
//      }
//    }
    int x, a;
    for (x = 0; x < 100000; x++) {
      a = i + 128 * x;
      String s = "" + a*9;
      if (containsOnly9(s) && (s.length() & 1) == 0) {
        return ("" + (a * 9));
      }
    }

    return null;
  }
  public static boolean containsOnly9(String s) {
    for (char c : s.toCharArray()) {
      if (c != '9' && c != ' ' && c != '\n' && c != '\r' && c != '\t') {
        return false;
      }
    }
    return true;
  }
}
\$\endgroup\$
  • \$\begingroup\$ You do have to actually output the character, not just the number. So all the programs with 999 at the end need to be fixed. \$\endgroup\$ – Calvin's Hobbies Mar 14 '15 at 20:31
  • \$\begingroup\$ Ah, alrighty then, I'll fix that in a moment. \$\endgroup\$ – bloo Mar 14 '15 at 20:33
  • \$\begingroup\$ Should be fixed now unless I missed something. I left the original code in but commented out in case someone wanted to use the numbers like that. Pastebin was also edited. \$\endgroup\$ – bloo Mar 14 '15 at 20:45
  • \$\begingroup\$ Great. Though for some I think you could have just added 99 999\n99 (to reassign 999 to 99 so it will print as a character). \$\endgroup\$ – Calvin's Hobbies Mar 14 '15 at 20:51
1
\$\begingroup\$

Repeated subtraction, 65280

A trivial solution to compare against. Keep subtracting 9 from 99, then output. Example for ASCII character 10:

99 99 9
99

There are 128 programs. The first program is two characters long (99), each one after that is 8 characters (99 99 9\n) longer than the previous one.

Python program generating programs seperated by empty lines, and computing score:

score = 0
for n in range(128):
    program = "99 99 9\n" * n + "99"
    score += len(program)
    print(program + "\n")

print(score)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.