Golfen Sie jeden ASCII-Charakter in 99

11

99 ist eine Programmiersprache, die ich Anfang dieser Woche für meine Herausforderung erfunden habe. Schreiben Sie einen Dolmetscher für 99 . (Erfunden, aber dank eines halben Dutzend von Ihnen nie implementiert werden .;)) Die vollständige Sprachspezifikation befindet sich in dieser Herausforderung, sodass ich mich nicht die Mühe mache, alles hier erneut zu veröffentlichen.

In 99 können Sie einzelne ASCII- Zeichen nach Standard drucken. Aufgrund der Einschränkungen der Sprache ist jedoch nicht immer klar, wie ein bestimmtes Zeichen so präzise wie möglich gedruckt werden soll.

Schreiben Sie für jedes der 128 ASCII-Zeichen ein 99- Programm, das keine Eingabe benötigt und dieses einzige Zeichen ausgibt. Sie können einige oder alle dieser Antworten von Hand codieren oder ein anderes Programm (in einer beliebigen Sprache) schreiben, um sie für Sie zu generieren.

Die Summe der Zeichen in jedem Ihrer 128 99 Programme ist Ihre Punktzahl. Die niedrigste Punktzahl gewinnt. Zeilenumbrüche zählen als ein Zeichen.

Denken Sie daran, dass in 99 nur Variablen mit gerader Größe wie 9999Ausgabe-ASCII-Zeichen (Variablen mit ungerader Größe Ganzzahlen ausgeben). Ihr Wert wird durch 9 geteilt und dann als Mod 128 verwendet, sodass die Werte nicht in einem bestimmten Bereich liegen müssen, um ASCII-Zeichen zugeordnet zu werden. Zum Beispiel entsprechen die internen Werte 297, 1449 und -855 alle dem Zeichen, !denn wenn sie durch 9 geteilt und mod 128 genommen werden, werden sie alle zu 33, was der Zeichencode für ist !.

Wenn Sie einen Interpreter für 99 benötigen , würde ich Macs Python-Antwort vorschlagen .

Ich weiß, ich sagte, meine nächste Herausforderung wäre interaktiver, aber ich arbeite immer noch an dem Zeug für diese.

Calvins Hobbys
quelle

Antworten:

7

Eine Aufgabe, 2075 (optimal)

Dies sollte der optimale Wert sein (es sei denn, ich habe einen großen Denkfehler oder meine Tests sind schlecht).

Vor allem. Es gibt nur 7 verschiedene Zahlen (Mod 128), die Sie in 99 ausdrücken können. Alle Werte von 7 oder mehr 9 ergeben dieselbe Zahl 71. (Weil 10 ^ 8 Mod 128 == 0, 10 ^ 9 Mod 128 == 0, ...)

Wenn einer der 4 Werte mit einer geraden Anzahl von Neunen ausgedrückt werden kann, ist die Ausgabe dieser Zahl eindeutig die optimale Lösung.

Ansonsten versuche ich, die Nummer mit einer Zuweisungsanweisung zu erreichen (99 zuweisen) und 99 zu drucken. Wie sich herausstellt, beträgt die maximale Programmgröße bei diesem Ansatz 22 Zeichen. Die Verwendung von Goto erfordert definitiv mehr. Die einzige Möglichkeit, dass eine Lösung mit einer Zuweisung geschlagen wird, ist eine Lösung mit zwei Zuweisungen. Ich habe dies getestet (hoffentlich ohne Fehler, der Code dafür ist ziemlich chaotisch) und keine Lösung für ein ASCII-Zeichen gefunden.

Daher sollte es ausreichen, nur die 4 direkten Zahlen und den Ansatz mit einer Zuweisung zu überprüfen, um die optimale Lösung zu finden. Das folgende Python-Programm (2 und 3 kompatibel) generiert alle Programme und fasst ihre Längen zusammen. Es verwendet einen einfachen IDA * -Ansatz.

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))

Die Ausgabe hat die folgende 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
....

Die vollständige Ausgabe finden Sie unter: http://pastebin.com/bKXLAArq

Das Zeichen mit dem kürzesten Programm (2 vertical tab - 11Zeichen ) hat eine Programmlänge von 2, die Zeichen mit den längsten Programmen (22 Zeichen) sind bell - 7und A - 65.

Die Summe für alle Programme beträgt 2075.

Übrigens habe ich den k / q-Interpreter von tmartin verwendet . Ich habe einige Probleme mit den anderen (Python, Perl, CJam). Ich bin mir nicht sicher, ob es meine Schuld war.

Jakube
quelle
Es würde Implementierern von Dolmetschern helfen, wenn Sie beschreiben könnten, welche Probleme Sie hatten. Gute Antwort.
Coredump
3

Eine Vielzahl von Techniken, 42109

Anstatt das große ASCII-Zeichen zu berechnen, habe ich für die Zahlen nur den Wert der Zahl berechnet. Sie haben nur gesagt, dass Sie das Zeichen ausgeben können, daher sollte dies weiterhin funktionieren.

BEARBEITEN: Die Zahlen wurden geändert, um die ASCII-Zeichen zu verwenden. Ignorieren Sie dies. Ich habe den ursprünglichen Nummerncode im Java-Code belassen, aber für den Fall, dass jemand ihn verwenden möchte, auskommentiert.

Einige davon habe ich von Hand gemacht, die meisten habe ich gerade geschrieben, um sie abzutippen.

Diese bestehen jeweils aus 1-4 Zeilen, so dass sie recht einfach zu kopieren und in ein Programm einzufügen sind. Es sollte beachtet werden, dass sie nicht nacheinander funktionieren, da mein generierter Code keine variablen Zustände beibehält.

Die hier am häufigsten verwendete Technik war die gleiche wie der Ansatz von orlp:

Subtrahieren Sie weiterhin 9 von 99 und geben Sie dann aus.

Meine Version unterscheidet sich durch die Verwendung einiger benutzerdefinierter Fälle und das Zusammenstellen eines Großteils der Mathematik in nur einer Zeile. Benutzerdefinierte Fälle sind nur Fälle, in denen das Zeichen mit nur ein paar Neunen dargestellt werden kann und keine Mathematik oder mein Generierungscode verkürzt werden kann.

Programme

Ich habe die Ausgabe auf Pastebin für diejenigen unter Ihnen eingestellt, die keine Lust haben, das Programm auszuführen:

http://pastebin.com/Cs6WZUfb

Java Code, den ich verwendet habe:

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;
  }
}
bloo
quelle
Sie müssen tatsächlich das Zeichen ausgeben, nicht nur die Zahl. Also müssen alle Programme mit 999am Ende repariert werden.
Calvins Hobbys
Ah, in Ordnung, ich werde das gleich beheben.
Bloo
Sollte jetzt behoben werden, es sei denn, ich habe etwas verpasst. Ich habe den Originalcode beibehalten, aber kommentiert, falls jemand die Zahlen so verwenden wollte. Pastebin wurde ebenfalls bearbeitet.
Bloo
Groß. Für einige denke ich, dass Sie gerade hinzugefügt haben könnten 99 999\n99(um es neu zuzuweisen 999, 99damit es als Zeichen gedruckt wird).
Calvins Hobbys
1

Wiederholte Subtraktion, 65280

Eine triviale Lösung zum Vergleich. Subtrahieren Sie weiterhin 9 von 99 und geben Sie dann aus. Beispiel für ASCII-Zeichen 10:

99 99 9
99

Es gibt 128 Programme. Das erste Programm ist zwei Zeichen lang (99), jedes danach 8 Zeichen (99 99 9 \ n) länger als das vorherige.

Python-Programm, das durch Leerzeilen getrennte Programme generiert und Punktzahl berechnet:

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

print(score)
orlp
quelle