Effizientester Kubifikator

19

Kubisch ist zu mühsam, um Code manuell . Ihre Herausforderung besteht darin, ASCII-Text in Cubically-Quellcode zu übersetzen.

Kubisch

Dies ist nur ein kurzer Überblick über Cubically. das Repository enthält eine ausführlichere Anleitung und Details.

Cubically ist ein Esolang, den ich vor einiger Zeit geschrieben habe und dessen Gebrauch schmerzhaft ist. Es enthält zwei Speicher, einen 3x3x3 Rubik's Cube und ein Register, das als "Notizblock" bezeichnet wird.

Erinnerung

Der interne Zauberwürfel wird folgendermaßen initialisiert:

   000
   000          top face
   000
111222333444    left, front, right, and back faces, respectively
111222333444
111222333444
   555
   555          down face
   555

Nach einer 90 ° -Drehung im Uhrzeigersinn auf der rechten Seite sieht der Speicherwürfel folgendermaßen aus:

   002
   002
   002
111225333044
111225333044
111225333044
   554
   554
   554

Befehle

Ein nicht ganzzahliges Zeichen legt den Standardbefehl fest. Für jede Ganzzahl, bevor der Standardbefehl erneut festgelegt wird, wird der Befehl mit dieser Ganzzahl ausgeführt. Zum Beispiel x524y312würde Befehl xmit 5, dann mit 2, dann mit 4, dann Befehl ymit 3, dann mit 1, dann mit 2 ausführen .

Die von den Befehlen verwendeten Ganzzahlen repräsentieren Flächenindizes. So funktionieren x0würde xauf dem UP (0 indiziert) Gesicht. x1würde durchführenx auf der linken (1-indizierten) Seite auftreten und so weiter.

Wenn Sie einen Befehl mit 6ausführen, wird dieser Befehl für den Notizblockwert ausgeführt. Das Ausführen eines Befehls mit einer Ganzzahl über 6 führt zu einem Fehler.

Hier sind einige Beispielbefehle:

  • R1 - Drehen Sie die RECHTE Seite im Uhrzeigersinn um 90 °, damit der interne Würfel wie im zweiten Beispiel oben aussieht
  • R11 - Das RECHTE Gesicht zweimal um 90 ° im Uhrzeigersinn drehen, identisch mit R2
  • +0 - Fügen Sie alle Werte des UP-Gesichts zum Notizblock hinzu
  • +000 - Fügen Sie alle Werte des UP-Gesichts dreimal zum Notizblock hinzu
  • @6 - Drucken Sie das nicht vorhandene 6. indizierte Gesicht (Gedächtnis) als Zeichen
  • %4 - Die Summe aller Werte auf der BACK-Seite als Ganzzahl ausgeben

Eine vollständige Liste der Befehle und der Syntax finden Sie im Repository .

Herausforderung

Sie nehmen ASCII-Text als Eingabe und drucken ein kubisches Programm als Ausgabe.

Beispiele (von hier und hier gestohlen ):

Input -> Output
Hello, World! -> +53@6+1F2L2+0@6L2F2U3R3F1L1+2@66L3F3R1U1B3+0@6:4U1R1+00@6-000@6*0-4+000@6-00@6+2-000000@6-5+4000@6-00@6/0+00@6:0+0/0+00@6
1$2$3$4$5$6$7$8$9$10$ -> B1+2/2%6@4+00/0%6@4+00/1%6@4+21/1%6@4+30/0%6@4+22/1%6@4+22/1%6@4+40/1%6@4+52/1%6@4+42/1%6@4

Regeln

  • Ihr Programm enthält möglicherweise kein Wörterbuch mit den Übersetzungen für die 100 Testfälle.
  • Ihr Programm muss in weniger als 180 Sekunden beendet sein (keine Brute-Force-Programme, die Wochen dauern).
  • Ihr Programm muss gültigen kubischen Code ausgeben, der in weniger als 180 Sekunden beendet ist.
  • Ihr Programm nimmt Eingaben über die Standardeingabe entgegen, es sei denn, Sie möchten sich mit dem Testtreiber anlegen.
  • Ihr Programm muss kubischen Code ausgeben, der beim Ausführen nur die Eingabe Ihres Programms erzeugt. ಠ_ಠ

Wertung

Sie testen Ihr Programm mit 100 pseudozufälligen Zeichenfolgen von pseudozufälliger Länge. (Ein Bash-Skript wird mitgeliefert, das dies für Sie erledigt.) So werden Sie punkten:

  • Die Länge des Ausgabeprogramms sei o .
  • Die Länge der Eingabezeichenfolge sei l .
  • Sei eine Variable r das Ergebnis von o / l .
  • Finde den Durchschnitt aller r : (r 1 + r 2 + r ... + r 100 ) / 100 .

Testen Sie mit diesem Skript. Sie müssen es wie angewiesen ändern. Beachten Sie, dass das Programm nicht überprüft, ob die Ausgabe gültigen kubischen Code enthält. Wenn Sie das Skript nicht zum Laufen bringen können, kann ich Ihnen helfen. Ping mich in den kubischen Chatraum .

MD XF
quelle
1
Sandbox post
MD XF
Wäre " @6- die Summe des nicht vorhandenen sechsten indizierten Gesichts (Notizblock) als Zeichen drucken" genauer? Ist %4auch eine Summe? Sind +Befehle Summenfläche, die dann zu allen Werten addieren oder ...?
Jonathan Allan
@JonathanAllan @6/ %6druckt den Notizblockwert direkt als Zeichen / Ganzzahl. @x/ %x(wobei x für eine vorhandene Fläche steht) fügt alle Werte der xindizierten Fläche hinzu und gibt die Summe als Zeichen / Ganzzahl aus. +Fügt alle Werte auf dem angegebenen Gesicht zum Register hinzu.
MD XF
Ah, aus irgendeinem Grund dachte ich, dass der Notizblock auch 9 Werte hat.
Jonathan Allan

Antworten:

4

C ++ 11, Score : 6,37

#include <iostream>
#include <vector>
#include <array>
#include <limits>
#include <algorithm>

const int inf = std::numeric_limits<int>::max(),
maxDiff = 128, nFace = 6;
std::array<int, maxDiff+1> plusvalue, totalvalue, plustrace, totaltrace;
std::array<int, nFace> input;

void prtrace(int value) {
    while (value) {
        std::cout << plustrace[value];
        value -= input[plustrace[value]];
    }
}

void prexpr(int i) {
    char xorwt = 0;
    if (i < 0) {
        xorwt = '+' ^ '-';
        i = -i;
    }
    if (totalvalue[i] != 0 && totalvalue[i] != inf) {
        std::cout << (char)('+' xor xorwt);
        prtrace(totaltrace[i]);
        if (totaltrace[i] != i) {
            std::cout << (char)('-' xor xorwt);
            prtrace(totaltrace[i] - i);
        }
    }
}

int main() {
    std::cout << "RU";
    input = {6, 15, 27, 26, 19, 42};
    std::cin >> std::noskipws;

    std::fill(plusvalue.begin(), plusvalue.end(), inf);
    plusvalue[0] = 1; // '+'
    for (int i = 0; i < nFace; ++i) { // knapsack, each value repeated inf times
        int val = input[i];
        if (val == 0) continue;
        for (int p = 0; p <= maxDiff - val; ++p) {
            if (plusvalue[p] != inf && plusvalue[p + val] > plusvalue[p] + 1) {
                plusvalue[p + val] = plusvalue[p] + 1;
                plustrace[p + val] = i;
            }
        }
    }
    for (int p = 0; p <= maxDiff; ++p) totalvalue[p] = plusvalue[p], totaltrace[p] = p;
    totalvalue[0] = 0;
    for (int sub = 1; sub <= maxDiff; ++sub) {
        if (plusvalue[sub] == inf) continue;
        for (int p = 0; p <= maxDiff - sub; ++p) {
            if (plusvalue[p+sub] != inf && totalvalue[p] > plusvalue[p+sub] + plusvalue[sub]) { // include '+'s
                totalvalue[p] = plusvalue[p+sub] + plusvalue[sub];
                totaltrace[p] = p+sub;
            }
        }
    }

//    // Note: plustrace[x] = i<=nFace : plustrace[x-input[i]] + 1 = plustrace[x]
//    long long sum = 0;
//    for (int i = 0; i <= maxDiff; ++i) {
//        sum += totalvalue[i];
//        std::cout << i << '\t' << totalvalue[i] << '\t';
//        prexpr(i);
//        std::cout << '\n';
//    }
//
//    std::cout << "_______________________________\n\nAverage = " << sum / (maxDiff + 1.) << '\n';

// RU 3.98131

    char ch;
    int cur = 0;
    while (std::cin >> ch) {
        int diff = ch - cur;
        prexpr(diff);
        std::cout << "@6";
        cur += diff; // cur = ch
    }
}

/*
RU 3.98131
*/

Probieren Sie es online! (Kubisch Code aus ASCII generieren) und (Kubisch Code ausführen)

Erläuterung:

  • Zuerst gibt das Programm "RU" aus, womit die Gesichtssumme von {0,9,18,27,36,45}bis gebildet wird {6, 15, 27, 26, 19, 42}. Was diese Gesichtssummenmenge nützlich macht, ist, dass der gcd 1 ist, so dass es nach Bézouts Identität eine Möglichkeit gibt, eine beliebige Zahl daus einer Summe (oder Differenz) dieser Zahlen zu konstruieren .
  • Wenn also das nächste Zeichen ist chund der aktuelle Notizblockwert ist n, d = ch - nkönnen wir Cubically-Befehle in der Form ausführen, +{digits from 0 to 5}-{digits from 0 to 5}dass der Notizblockwert wird ch. Dann einfach ausführen %6, um den Notizblockwert zu drucken.
  • Um den effizientesten Weg zu finden, um deine Summe / Differenz von Zahlen im Gesichtssummensatz auszudrücken , verwende ich den Knapsack-Algorithmus für alle Zahlen von 0 bis 128. Beispielsweise d=1wird das Programm 27 - 26 = 1so, wie es gedruckt wird +2-3, das heißt 27 - 26 = 1. Was sich beim Ausführen des Programms mit Eingabe zeigt abc, ist die Programmausgabe

    RU + 4333 @ 6 + 2-3 @ 6 + 2-3 @ 6

user202729
quelle
Woah, großartige Arbeit! Der Knapsack-Algorithmus ist genau das, wonach wir gesucht haben.
TehPers
Beachten Sie, dass Sie aufgrund von Sprachaktualisierungen eine bessere Punktzahl durch @implizites Aufrufen erzielen @6können - kann @in jedem Fall auf verkürzt werden.
MD XF
17

Lua, Score : 85,91 13,50 13,20 12,70 9,41 9,32 9,83 9,66 9,12 9,06 8,03 (Durchschnitt)

-- Get input
local inp = io.read("*a")

local out = ""
local faces = { [5] = 45, [4] = 36, [3] = 27, [2] = 18, [1] = 9 }
local lastChar = nil

-- Mode the program is in
-- 2 = not set (needs :), 1 = just set (needs +), 0 = normal
local mode = 1;
for i = 1, inp:len() do
  -- Character value at current position
  local c = string.byte(inp, i)

  if c == lastChar then
    -- Repeat character
    out = out .. "6"
  elseif c % 9 == 0 and c <= 45 then
    if #out == 0 then
      out = out .. "@"
    end
    out = out .. (c / 9)
  else
    local c2 = c

    -- Handle if difference from lastChar is divisible by 9
    if lastChar and (c - lastChar) % 9 == 0 then
      local difference = c - lastChar
      if difference > 0 then
        out = out .. "+"
      else
        out = out .. "-"
        difference = difference * -1
      end

      for index = 5, 1, -1 do
        local face = faces[index]
        while difference >= face do
          difference = difference - face
          out = out .. index
        end
      end
      c = 0
    end

    -- Handle anything not divisible by 9
    local extra = c % 9
    if extra > 0 then
      -- Try to optimize by dividing by 9, if possible
      if lastChar and math.floor(lastChar / 9) == extra then
        out = out .. "/1"
        mode = 1
        extra = 0
      else
        while extra > 0 do
          local n = extra > 5 and 5 or extra

          if mode == 2 then
            out = out .. ":"
            mode = 1
          elseif mode == 1 then
            out = out .. "+"
            mode = 0
          end
          out = out .. n
          extra = extra - n
        end
        out = out .. "/1"
        mode = 1
      end

      c = c - (c % 9)
    end

    -- Handle anything divisible by 9
    for index = 5, 1, -1 do
      local face = faces[index]
      while c >= face do
        if mode == 2 then
          out = out .. ":"
          mode = 1
        elseif mode == 1 then
          out = out .. "+"
          mode = 0
        end
        c = c - face
        out = out .. index
      end
    end

    out = out .. "@6"
    lastChar = c2
  end

  mode = 2
end
print(out)

Probieren Sie es online!

Okay, ich glaube nicht, dass ich das noch optimieren kann.

Diese Version durchläuft jedes Zeichen, addiert dabei c% 9 (wobei c der Dezimalwert des Zeichens ist) :5+2/1und addiert dann die durch 9 teilbaren Teile, indem der Wert dieser Fläche addiert wird. Beispiel: :2/1+551@Zum Drucken von "e" wird :2/12 +551hinzugefügt, 99 (9 * (5 + 5 + 1) oder 9 * 11) @hinzugefügt und die Ausgabe gedruckt. Eingabe wird mit gelesen io.read().

Zu den Optimierungen gehört das direkte Addieren / Subtrahieren nach dem Drucken, wenn der Unterschied zwischen den Zeichen ein Vielfaches von 9 ist, das Teilen des aktuellen Werts, sofern dies möglich ist, anstatt c% 9 von Grund auf neu festzulegen, und das Wiederholen der Zeichen, indem der aktuelle Wert erneut gedruckt und nicht neu berechnet wird. Zusätzlich habe ich die Methode von Kamil implementiert, mit der sofort jedes Gesicht gedruckt wird, das bereits den Zielwert enthält, sowie den Vorschlag von MD XF, nicht :am Anfang zu verwenden, sondern nur mit einem zu beginnen +.

TehPers
quelle
1
Sie können jederzeit Ihre eigenen Fragen und Antworten kommentieren, haben aber noch keine allgemeinen Kommentarberechtigungen. Mit Antworten wie diesen sollte es nicht lange
dauern
2
@ MDXF Ich bin nicht ganz so nett: P
Kamil Drakari
1
Sie können ändern , local inp = io.read()zu local inp = io.read("*all"). Das behebt das Problem.
MD XF
1
Eine weitere mögliche Optimierung: Da der Notizblock bei 0 beginnt, müssen Sie nicht wirklich etwas ausgeben, :5+124sondern können einfach nur schreiben +5124, wodurch sich die Punktzahl wahrscheinlich ein wenig verringert, wenn Sie sie richtig einstellen.
MD XF
1
Sie werden wahrscheinlich eine bessere Punktzahl erhalten, wenn Sie Ihre Antwort ändern, um einige der neuesten Cubically-Aktualisierungen zu unterstützen, z. B. implizite Gesichtszüge.
MD XF
16

Kubisch , Ergebnis : 86,98

U3D1R3L1F3B1U1D3~:7+1(-1@3(-1%1)6:1+3111@6%1-31111+004@6:1+11111%6:1+45@6:1-1%6~:7+1)6 

Probieren Sie es online!

Es hat sich herausgestellt, dass Sie lediglich bedingte Schleifen, eine Fläche von 1 und ein konsistentes Verhalten am Ende der Eingabe benötigen.

U3D1R3L1F3B1U1D3     set LEFT face sum to 1
~:7                  read input, set notepad to input
+1                   add 1 to notepad

(                    open loop that can always be jumped to
 -1                   subtract 1 from notepad
 @3                   print RIGHT face (ASCII 43 '+')

            ##   the following mechanism gets the output program's   ##
            ##   notepad to the current inputted ASCII value:        ##

 (                    open loop that can always be jumped to
  -1                   subtract 1 from notepad
  %1                   print '1'
 )6                   jump back to loop while notepad is nonzero

            ##   the following mechanism prints "/1@6:1"             ##

 :1+3111@6            set notepad to 47,    print (ASCII 47 '/')
 %1                   print LEFT face       print (integer '1')
 -31111+004@6         set notepad to 64,    print (ASCII 64 '@')
 :1+11111%6           set notepad to 6,     print (integer 6)
 :1+45@6              set notepad to 58,    print (ASCII 58 ':')
 :1-1%6               set notepad to 0,     print (integer 1)

 ~                    read input
 :7+1                 set notepad to input plus 1, so EOF changes to zero
)6                    loop if notepad is truthy

Das Addieren / Subtrahieren der LINKEN Fläche bewirkt, dass die Schleife endet, wenn EOF gelesen wird.

Kamil Drakari
quelle
2
Sie haben bekam zu scherzen. Das ist unglaublich.
MD XF
Oh hey, es hat sogar eine bessere Punktzahl als meine ursprüngliche C # -Antwort!
Kamil Drakari
Beachten Sie, dass Sie aufgrund von Sprachaktualisierungen eine bessere Punktzahl durch @implizites Aufrufen erzielen @6können - kann @in jedem Fall auf verkürzt werden.
MD XF
9

C # (.NET Core) , Score: 129,98 11,73 10,82 9,62 10,33 10,32 10,20

-1,2 Punkte nach dem Vorschlag von MD XF @6666... anstelle von@6@6@6@6... wiederholten Zeichens eine überlegene Initialisierungssequenz zu verwenden

static void Main()
{
	List<byte> input = new List<byte>();
            int inChar = Console.Read();
            while (inChar != -1)
            {
                input.Add((byte)inChar);
                inChar = Console.Read();
            }


            Console.Write("U3D1R3L1F3B1U1D3");
            byte[] sides = new byte[] { 20, 1, 14, 43, 24, 33 };

            byte currentChar = 0;

   	    if(currentChar == input[0] || sides.Contains(input[0])) Console.Write("@");

            foreach (byte character in input)
            {
		if (currentChar == character)
		{
			Console.Write("6");
			continue;
		}
		
		if (sides.Contains(character))
		{
			Console.Write(Array.IndexOf(sides, character));
			continue;
		}
                if (currentChar < character)
                {
                    Console.Write("+");
                    while (currentChar < character)
                    {
                        byte nextAdd = sides.Where(s => s + currentChar <= character).Max();
                        currentChar = (byte)(currentChar + nextAdd);
                        Console.Write(Array.IndexOf(sides, nextAdd));
                    }
                }

                if (currentChar > character)
                {
                    Console.Write("-");
                    while (currentChar > character)
                    {
                        byte nextSub = sides.Where(v => currentChar - v >= character).Max();
                        currentChar = (byte)(currentChar - nextSub);
                        Console.Write(Array.IndexOf(sides, nextSub));
                    }
                }

                Console.Write("@6");
            }
}

Probieren Sie es online!

Meine neueste Version manipuliert tatsächlich den Würfel! Yay!

Als erstes Console.Writegibt es eine feste Manipulation, die MD XF ausgearbeitet hat und die diesen Würfel erzeugt:

   242
   202
   242
000131555313
010121535343
000131555313
   424
   454
   424

Die Bedeutung dieses Würfels besteht darin, dass eine seiner Seiten eine Summe von 1 hat, was Manipulationen des Notizblocks in einem kleineren Maßstab als ein Vielfaches von neun erlaubt, und insbesondere die Relativbewegung vereinfacht, anstatt dass jedes Zeichen bei Null beginnen muss; In diesem Algorithmus werden sowohl Addition als auch Subtraktion verwendet, um den kürzesten Weg zwischen Zeichen zu nehmen.

Die Version der Initialisierung von MD XF bewirkt, dass Seite 2 eine Summe von 14 aufweist, wodurch viele Bytes an Ausgabe für ASCII-Abstände zwischen 14 und 20 gespart werden.

Jetzt können Eingaben mit internen Zeilenumbrüchen verarbeitet werden. Console.Read () erhält einzelne Zeichen bis zum Ende der Datei. Siehe den TIO-Link, der den Eingang haben soll

Hello, 
World!

Rasiert ein paar Bruchteile eines Punktes, indem sofort ein Zeichen ausgegeben wird, wenn sein ASCII-Wert zufällig bereits auf einer Seite vorhanden ist.

Test Script mit freundlicher Genehmigung von MDXF


Vorherige Einreichung hier und Erläuterung:

Das ist ein bisschen langweilig, aber soweit ich das beurteilen kann, funktioniert es. Zugegeben, ich habe es nur versuchtHello, World! aber ich habe die Ausgabe im TIO Cubically Interpreter ausgeführt und es wurde "Hello, World!" also nahm ich an, dass es funktioniert.

Anstatt den Würfel tatsächlich zu manipulieren, wird der Notizblock einfach wiederholt um die Summe der 1 Fläche (9) erhöht, bis er den richtigen Wert für jedes Zeichen hat, und dann gedruckt.

Kamil Drakari
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Martin Ender
@MartinEnder Könnten Sie sie stattdessen in den vorhandenen Chatroom verschieben ?
MD XF
@MDXF Ich könnte, aber ich kann nicht sagen, ob sie in diesem Chatroom völlig fehl am Platz und im Kontext wären.
Martin Ender
@MartinEnder Die Kommentare sind älter als der Chatroom, also erscheinen sie einfach weit zurück im Protokoll. Richtig?
MD XF
Sie würden. Danke, ich verschiebe die Nachrichten.
Martin Ender