Cubificador más eficiente

19

Cubically es demasiado tedioso para escribir manualmente cualquier código. Su desafío es traducir el texto ASCII al código fuente Cubically.

Cúbicamente

Esto es solo un descuido rápido de Cubically; El repositorio tiene una guía y detalles más completos.

Cúbicamente es un esolang que escribí hace un tiempo, diseñado para ser doloroso de usar. Contiene dos piezas de memoria, un Cubo de Rubik 3x3x3 y un registro llamado "bloc de notas".

Memoria

El cubo interno de Rubik se inicializa así:

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

Después de realizar un giro de 90 ° en sentido horario en la cara derecha, el cubo de memoria se vería así:

   002
   002
   002
111225333044
111225333044
111225333044
   554
   554
   554

Comandos

Un carácter no entero establece el comando predeterminado. Para cada número entero antes de que el comando predeterminado se establezca una vez más, el comando se ejecuta con ese número entero. Por ejemplo, x524y312realizaría un comando xcon 5, luego con 2, luego con 4, luego realizaría un comando ycon 3, luego con 1, luego con 2.

Los enteros que usan los comandos representan índices faciales. Por x0lo tanto, se realizaría xen la cara UP (índice 0). x1funcionaría xen la IZQUIERDA (1 índice), y así sucesivamente.

La ejecución de cualquier comando con 6ejecutará ese comando en el valor del bloc de notas. La ejecución de cualquier comando con un número entero mayor de 6 dará como resultado un error.

Aquí hay algunos comandos de ejemplo:

  • R1 - gire la cara DERECHA 90 ° en sentido horario para que el cubo interno se vea como el segundo ejemplo anterior
  • R11 - gire la cara DERECHA 90 ° en sentido horario dos veces, idéntico a R2
  • +0 - agregue todos los valores de la cara ARRIBA al bloc de notas
  • +000 - Agregue todos los valores de la cara ARRIBA al bloc de notas tres veces
  • @6 - imprima la cara (memoria) sexta indexada inexistente como un carácter
  • %4 - imprime la suma de todos los valores en la cara POSTERIOR como un entero

Una lista completa de comandos y sintaxis está disponible en el repositorio .

Desafío

Tomará el texto ASCII como entrada e imprimirá un programa cúbico como salida.

Ejemplos (robados de aquí y de aquí ):

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

Reglas

  • Es posible que su programa no contenga un diccionario que contenga las traducciones para los 100 casos de prueba.
  • Su programa debe finalizar en menos de 180 segundos (no hay programas de fuerza bruta que demoren semanas).
  • Su programa debe generar un código cúbico válido que finalice en menos de 180 segundos.
  • Su programa tomará la entrada a través de la entrada estándar, a menos que desee meterse con el controlador de prueba.
  • Su programa debe generar código cúbico que no produce nada más que la entrada de su programa cuando se ejecuta. ಠ_ಠ

Puntuación

Probará su programa con 100 cadenas pseudoaleatorias de longitud pseudoaleatoria. (Se proporciona un script de bash que lo hará por usted). Así es como puntuará:

  • Deje que la longitud del programa de salida sea o .
  • Deje que la longitud de la cadena de entrada sea l .
  • Deje que una variable r sea ​​el resultado de o / l .
  • Encuentre el promedio de todos los r : (r 1 + r 2 + r ... + r 100 ) / 100 .

Prueba con este script. Tendrás que modificarlo según las instrucciones. Tenga en cuenta que el programa no verifica si la salida es válida Código cúbico. Si no puede hacer que el script funcione, puedo ayudarlo. Envíame un ping en la sala de chat Cubically .

MD XF
fuente
1
Sandbox post
MD XF
¿Sería " @6preciso imprimir la suma de la cara inexistente del sexto índice (bloc de notas) como un carácter"? ¿ %4También es una suma? ¿Los +comandos suman cara y luego los agregan a todos los valores o ...?
Jonathan Allan
@ JonathanAllan @6/ %6solo imprime directamente el valor del bloc de notas como un carácter / entero. @x/ %x(donde x es cualquier cara existente) agrega todos los valores en la xcara indexada e imprime la suma como un carácter / entero. +agrega todos los valores en la cara especificada al registro.
MD XF
Ah, por alguna razón, también pensaba que el bloc de notas tenía 9 valores.
Jonathan Allan

Respuestas:

4

C ++ 11, Puntuación : 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
*/

Pruébalo en línea! (generar código cúbico desde ASCII) y (ejecutar código cúbico)

Explicación:

  • Primero el programa imprime "RU", que hace que la cara sume de {0,9,18,27,36,45}a {6, 15, 27, 26, 19, 42}. Lo que hace que el conjunto de suma de caras sea útil es que el mcd es 1, por lo que, según la identidad de Bézout, existe una forma de construir cualquier número a dpartir de una suma (o diferencia) de esos números.
  • Por lo tanto, si el siguiente carácter es chy el valor actual del bloc de notas es n, entonces let d = ch - n, podemos ejecutar comandos Cubically en la forma +{digits from 0 to 5}-{digits from 0 to 5}tal que el valor del bloc de notas se convierta ch. Luego, simplemente ejecute %6para imprimir el valor del bloc de notas.
  • Para encontrar la forma más eficiente de expresar dcomo una suma / diferencia de números en el conjunto de suma de caras, utilizo el algoritmo Knapsack para todos los números del 0 al 128. Por ejemplo, para d=1, el programa obtiene 27 - 26 = 1, por lo que imprime +2-3, que es 27 - 26 = 1. Que se puede ver cuando se ejecuta el programa con entrada abc, la salida del programa

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

usuario202729
fuente
Woah, buen trabajo! El algoritmo de Mochila es lo que estábamos buscando, supongo.
TehPers
Tenga en cuenta que, debido a las actualizaciones de idioma, puede obtener una mejor puntuación a través de llamadas @implícitas, @6se puede acortar @en todos los casos.
MD XF
17

Lua, Puntaje : 85.91 13.50 13.20 12.70 9.41 9.32 9.83 9.66 9.12 9.06 8.03 (Promedio)

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

Pruébalo en línea!

Bien, no creo que pueda optimizar esto más.

Esta versión itera a través de cada carácter, agregando c% 9 (donde c es el valor decimal del carácter) haciendo :5+2/1, luego agrega las partes divisibles por 9 agregando el valor de esa cara. Por ejemplo: :2/1+551@para imprimir "e", donde :2/1agrega 2, +551agrega 99 (9 * (5 + 5 + 1) o 9 * 11) e @imprime la salida. La entrada se lee con io.read().

Las optimizaciones incluyen sumar / restar directamente después de imprimir si la diferencia entre caracteres es un múltiplo de 9, dividir el valor actual si es posible en lugar de establecer c% 9 desde cero y repetir caracteres imprimiendo el valor actual nuevamente en lugar de volver a calcularlo. Además, he implementado el método de Kamil de imprimir instantáneamente cualquier cara que ya contenga el valor objetivo, y la sugerencia de MD XF de no usar :al principio, sino simplemente comenzar con un +.

TehPers
fuente
1
Siempre puede comentar sobre sus propias preguntas y respuestas, pero aún no tiene los privilegios generales para comentar. No debería ser largo con respuestas como esta (o, más probablemente, solo esta respuesta una vez que algunas personas más la vean)
Kamil Drakari
2
@MDXF No soy tan agradable: P
Kamil Drakari
1
Puedes cambiar local inp = io.read()a local inp = io.read("*all"). Eso soluciona el problema.
MD XF
1
Otra posible optimización: dado que el bloc de notas comienza en 0, en realidad no necesita salida, por ejemplo :5+124, simplemente puede escribir +5124, lo que probablemente reducirá un poco la puntuación si lo ajusta correctamente.
MD XF
1
Es probable que obtenga una mejor puntuación si cambia su respuesta para admitir algunas de las actualizaciones cúbicas recientes, como los cambios de caras implícitos.
MD XF
16

Cúbicamente , Puntuación : 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 

Pruébalo en línea!

Resulta que todo lo que necesita son bucles condicionales, una cara igual a 1 y un comportamiento consistente de fin de entrada.

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

La suma / resta de la cara IZQUIERDA es hacer que el ciclo finalice cuando se lee EOF.

Kamil Drakari
fuente
2
Usted ha llegado a ser una broma. Esto es increíble.
MD XF
Oh, oye, ¡incluso tiene una mejor puntuación que mi respuesta original de C #!
Kamil Drakari
Tenga en cuenta que, debido a las actualizaciones de idioma, puede obtener una mejor puntuación a través de llamadas @implícitas, @6se puede acortar @en todos los casos.
MD XF
9

C # (.NET Core) , puntaje: 129.98 11.73 10.82 9.62 10.33 10.32 10.20

-1,2 puntos de la sugerencia de MD XF de usar en @6666...lugar de @6@6@6@6...para repetir caracteres y una secuencia de inicialización superior

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");
            }
}

Pruébalo en línea!

¡Mi versión más reciente en realidad manipula el cubo! ¡Hurra!

Primero Console.Write, hay una manipulación fija que MD XF resolvió que crea este cubo:

   242
   202
   242
000131555313
010121535343
000131555313
   424
   454
   424

La importancia de este cubo es que uno de sus lados tiene una suma de 1, lo que permite manipulaciones del Bloc de notas en una escala menor que múltiplos de nueve, y en particular simplifica el movimiento relativo en lugar de tener que comenzar desde cero cada carácter; En este algoritmo, tanto la suma como la resta se utilizan para tomar el camino más corto entre los caracteres.

La versión de MD XF de la inicialización hace que el lado 2 tenga una suma de 14, lo que ahorra muchos bytes de salida para distancias ASCII entre 14 y 20.

Ahora puede manejar entradas con nuevas líneas internas, Console.Read () obtiene caracteres individuales hasta el final del archivo; ver el enlace TIO que debe tener la entrada

Hello, 
World!

Afeitó un par de fracciones de un punto al generar inmediatamente un carácter si su valor ASCII ya existe en un lado.

Script de prueba cortesía de MDXF


Presentación previa aquí y explicación:

Esto es un poco aburrido, pero por lo que puedo decir, funciona. Es cierto que solo lo intenté, Hello, World!pero ejecuté la salida en el intérprete TIO Cubically y dio la salida "¡Hola, mundo!" Así que supuse que funciona.

En lugar de manipular realmente el cubo, el bloc de notas simplemente se incrementa por la suma de la 1 cara (9) repetidamente hasta que tenga el valor correcto para cada carácter, luego lo imprime.

Kamil Drakari
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Martin Ender
@MartinEnder ¿Podrías moverlos a la sala de chat existente ?
MD XF
@MDXF podría, pero no puedo decir si terminarían estando completamente fuera de lugar y contexto en esa sala de chat.
Martin Ender
@MartinEnder Los comentarios son más antiguos que la sala de chat, por lo que simplemente aparecerían en la transcripción, ¿correcto?
MD XF
Lo harían. Gracias, moveré los mensajes.
Martin Ender