Самый эффективный кубификатор

19

Кубически слишком утомительно, чтобы вручную писать какой-либо код. Ваша задача - перевести текст ASCII в кубический исходный код.

кубично-

Это просто быстрое сокращение кубов; хранилище имеет более полное руководство и детали.

Кубически это esolang, который я написал некоторое время назад, разработанный, чтобы быть болезненным в использовании. Он содержит два куска памяти, кубик Рубика 3х3х3 и регистр, называемый «блокнотом».

Память

Внутренний кубик Рубика инициализируется так:

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

После поворота правого лица на 90 ° по часовой стрелке куб памяти будет выглядеть так:

   002
   002
   002
111225333044
111225333044
111225333044
   554
   554
   554

команды

Нецелочисленный символ устанавливает команду по умолчанию. Для каждого целого числа перед тем, как команда по умолчанию будет установлена ​​снова, команда выполняется с этим целым числом. Например, x524y312будет выполнять команду xс 5, затем с 2, затем с 4, затем выполнять команду yс 3, затем с 1, затем с 2.

Целые числа, которые используют команды, представляют индексы лица. Так x0что будет выполнять xна лице UP (0-indexed). x1будет работать xна левом (1-индексированном) лице и так далее.

Выполнение любой команды с помощью 6выполнит эту команду со значением блокнота. Выполнение любой команды с любым целым числом более 6 приведет к ошибке.

Вот несколько примеров команд:

  • R1 - поверните правую грань по часовой стрелке на 90 °, чтобы внутренний куб выглядел как во втором примере выше
  • R11 - поверните ПРАВУЮ грань по часовой стрелке на 90 ° дважды, идентично R2
  • +0 - добавить все значения лица UP в блокнот
  • +000 - добавить все значения лицевой стороны UP в блокнот три раза
  • @6 - напечатать несуществующее 6-ое индексируемое лицо (память) как символ
  • %4 - вывести сумму всех значений на грани BACK в виде целого числа

Полный список команд и синтаксиса доступен в хранилище .

Вызов

Вы возьмете текст ASCII в качестве входных данных и напечатаете кубическую программу в качестве выходных данных.

Примеры (украденные здесь и здесь ):

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

правила

  • Ваша программа может не содержать словаря, содержащего переводы для 100 тестовых случаев.
  • Ваша программа должна завершиться менее чем за 180 секунд (никаких переборов, которые занимают недели).
  • Ваша программа должна вывести действительный кубический код, который заканчивается менее чем за 180 секунд.
  • Ваша программа будет принимать ввод через стандартный ввод, если вы не хотите связываться с тестовым драйвером.
  • Ваша программа должна выводить кубический код, который при запуске выдает только ввод вашей программы. ಠ_ಠ

счет

Вы протестируете свою программу с 100 псевдослучайными строками псевдослучайной длины. (Предоставляется сценарий bash, который сделает это за вас.) Вот как вы забьете:

  • Пусть длина выходной программы будет o .
  • Пусть длина входной строки будет l .
  • Пусть переменная r будет результатом o / l .
  • Найти среднее значение всех r : (r 1 + r 2 + r ... + r 100 ) / 100 .

Протестируйте с помощью этого скрипта. Вам придется изменить его в соответствии с инструкциями. Обратите внимание, что программа не проверяет, является ли на выходе правильный кубический код. Если вы не можете заставить скрипт работать, я могу помочь. Пинг меня в кубическом чате .

MD XF
источник
Будет ли " @6- печатать сумму несуществующего 6-го индексируемого лица (блокнота) в виде символа" точнее? Это %4тоже сумма? Являются ли +команды sum face, затем добавить это ко всем значениям или ...?
Джонатан Аллан
@JonathanAllan @6/ %6просто печатает значение блокнота как символ / целое число. @x/ %x(где x - любое существующее лицо) добавляет все значения на x-индексированном лице и печатает сумму в виде символа / целого числа. +добавляет все значения указанного лица в регистр.
MD XF
Ах, я почему-то думал, что блокнот тоже имеет 9 значений.
Джонатан Аллан

Ответы:

4

С ++ 11, оценка : 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
*/

Попробуйте онлайн! (генерировать кубический код из ASCII) и (запускать кубический код)

Объяснение:

  • Сначала программа печатает «RU», что делает сумму лица от {0,9,18,27,36,45}до {6, 15, 27, 26, 19, 42}. Что делает этот набор суммы граней полезным, так это то, что gcd равен 1, поэтому, благодаря идентичности Безу, существует способ построить любое число dиз суммы (или разности) этих чисел.
  • Следовательно, если следующий символ равен chтекущему значению блокнота n, то, допустим d = ch - n, мы можем выполнять кубические команды в форме, +{digits from 0 to 5}-{digits from 0 to 5}такой, что значение блокнота становится равным ch. Затем просто выполните, %6чтобы напечатать значение блокнота.
  • Чтобы найти наиболее эффективный способ выражения dв виде суммы / разности чисел в наборе сумм граней, я использую алгоритм рюкзака для всех чисел от 0 до 128. Например d=1, программа получает 27 - 26 = 1, поэтому печатает +2-3, что есть 27 - 26 = 1. Что видно при запуске программы с вводом abc, выводом программы

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

user202729
источник
Вау, отличная работа! Думаю, мы искали алгоритм ранца.
TehPers
Обратите внимание, что благодаря обновлениям языка, вы можете получить лучший результат, если @неявно звоните - @6его можно сократить @во всех случаях.
MD XF
17

Lua, оценка : 85,91 13,50 13,20 12,70 9,41 9,32 9,83 9,66 9,12 9,06 8,03 (в среднем)

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

Попробуйте онлайн!

Ладно, я не думаю, что смогу больше это оптимизировать.

Эта версия перебирает каждый символ, добавляя c% 9 (где c - десятичное значение символа) :5+2/1, затем добавляет части, кратные 9, добавляя значение этого лица. Например: :2/1+551@вывести «e», где :2/1добавляет 2, +551добавляет 99 (9 * (5 + 5 + 1) или 9 * 11) и @печатает вывод. Ввод читается с io.read().

Оптимизация включает в себя непосредственное добавление / вычитание после печати, если разница между символами кратна 9, деление текущего значения, если это возможно, вместо установки c% 9 с нуля, и повторение символов путем повторной печати текущего значения вместо его пересчета. Кроме того, я реализовал метод Камиля для мгновенной печати любого лица, которое уже содержит целевое значение, и предложение MD XF не использовать :в начале, а вместо этого просто начать с +.

TehPers
источник
1
Вы всегда можете комментировать свои собственные вопросы и ответы, но вы еще не дошли до общих прав комментирования. Не должно быть долго с ответами, подобными этому (или, более вероятно, только этим ответом, когда его увидят еще несколько человек)
Камил Дракари
2
@MDXF Я не так хорош: P
Камил Дракари
1
Вы можете изменить local inp = io.read()на local inp = io.read("*all"). Это решает проблему.
MD XF
1
Другая возможная оптимизация - поскольку блокнот начинается с 0, вам на самом деле не нужно выводить, например :5+124, вместо этого вы можете просто написать +5124, что, вероятно, немного снизит счет, если вы правильно его настроите.
MD XF
1
Скорее всего, вы получите более высокий балл, если измените свой ответ, чтобы поддержать некоторые из последних кубических обновлений, таких как неявные повороты лица.
MD XF
16

Кубически , оценка : 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 

Попробуйте онлайн!

Оказывается, все, что вам нужно, это условные циклы, грань, равная 1, и согласованное поведение конца ввода.

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

Сложение / вычитание грани ЛЕВЫЙ должно завершить цикл при чтении EOF.

Камил Дракари
источник
2
Вы получили быть шутишь. Это невероятно.
MD XF
О, эй, это даже лучше, чем мой оригинальный ответ на C #!
Камил Дракари
Обратите внимание, что благодаря обновлениям языка, вы можете получить лучший результат, если @неявно звоните - @6его можно сократить @во всех случаях.
MD XF
9

C # (.NET Core) , оценка: 129,98 11,73 10,82 9,62 10,33 10,32 10,20

-1,2 балла от предложения MD XF использовать @6666...вместо @6@6@6@6...повторяющегося символа и превосходную последовательность инициализации

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

Попробуйте онлайн!

Моя новейшая версия на самом деле делает некоторые манипуляции с кубом! Ура!

Сначала Console.Writeбыло разработано исправление MD XF, которое создает этот куб:

   242
   202
   242
000131555313
010121535343
000131555313
   424
   454
   424

Значение этого куба состоит в том, что одна из его сторон имеет сумму 1, что позволяет манипулировать Блокнотом в меньшем масштабе, чем кратное девяти, и, в частности, он упрощает относительное перемещение, вместо того, чтобы начинать с нуля каждый символ; в этом алгоритме как сложение, так и вычитание используются для выбора кратчайшего пути между символами.

Версия инициализации MD XF приводит к тому, что сторона 2 имеет сумму 14, что экономит много байтов вывода для ASCII-расстояний между 14 и 20.

Теперь можно обрабатывать ввод с внутренними символами новой строки, Console.Read () получает отдельные символы до конца файла; см. ссылку TIO, которая должна иметь вход

Hello, 
World!

Побрили пару долей точки, сразу же выведя символ, если его ASCII-значение уже существует на стороне.

Скрипт теста любезно предоставлен MDXF


Предыдущее представление здесь и объяснение:

Это довольно скучно, но, насколько я могу судить, это работает. По общему признанию я только попробовалHello, World! но я управлял выводом в интерпретаторе TIO Cubically, и это выводило "Привет, Мир!" поэтому я предположил, что это работает.

Вместо того, чтобы вообще манипулировать кубом, блокнот просто несколько раз увеличивается на сумму 1 грани (9) до тех пор, пока он не получит правильное значение для каждого символа, а затем напечатает его.

Камил Дракари
источник
Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .
Мартин Эндер
@MartinEnder Не могли бы вы переместить их в существующий чат ?
MD XF
@MDXF Я мог, но не могу сказать, в конечном итоге они оказались совершенно не к месту и контексту в этом чате.
Мартин Эндер
@MartinEnder Комментарии старше чата, так что они просто появятся в стенограмме, верно?
MD XF
Они бы. Спасибо, я перенесу сообщения.
Мартин Эндер