Тема вызова грабителей здесь .

Задача копов: спроектировать язык программирования, который кажется непригодным для программирования, но допускает вычисления (или, по крайней мере, завершение задачи) по неочевидному механизму.

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

Это конкурс популярности. Цель полицейских - набрать как можно больше голосов, выжив 8 дней после публикации переводчика, не будучи взломанным. Для этого должны помочь следующие методы:

• Точное объяснение семантики вашего языка
• Написание читаемого кода

Следующая тактика настоятельно не рекомендуется:

• Использование шифрования, хэшей или других криптографических методов. Если вы видите язык, который использует шифрование RSA или отказывается выполнять программу, если ее хэш SHA-3 не равен 0x1936206392306, пожалуйста, не стесняйтесь понижать голос.

Задача грабителей: написать программу, которая находит третье по величине целое число на входе при запуске в интерпретаторе полицейских.

Это относительно просто. Для того, чтобы взломать ответ полицейского, вы должны создать программу, которая выполняет задачу при запуске в ее интерпретаторе. Когда вы взломаете ответ, опубликуйте комментарий с надписью «Взломан» на ссылку полицейского на ваш пост. Тот, кто взломает большинство копов, выигрывает у грабителей.

Правила ввода / вывода

• Интерпретаторы должны взять имя файла в командной строке для программы и использовать стандартный ввод и вывод при его запуске.
• Ввод будет дан в унарном формате и состоит только из символов 0и 1(48 и 49 в ASCII). Число N кодируется как N, 1s за которым следует a 0. Существует дополнительный 0до конца файла. Пример: для последовательности (3, 3, 1, 14) вход имеет вид 11101110101111111111111100.
• На входе гарантированно должно быть не менее 3 цифр. Все числа являются положительными целыми числами.
• Вывод будет оцениваться по количеству 1s, напечатанных до остановки программы. Другие персонажи игнорируются.

В следующих примерах первая строка - это ввод в десятичном формате; второй фактический ввод программы; третий пример вывода.

1, 1, 3
101011100
1

15, 18, 7, 2, 15, 12, 3, 1, 7, 17, 2, 13, 6, 8, 17, 7, 15, 11, 17, 2
111111111111111011111111111111111101111111011011111111111111101111111111110111010111111101111111111111111101101111111111111011111101111111101111111111111111101111111011111111111111101111111111101111111111111111101100
111111,ir23j11111111111u

247, 367, 863, 773, 808, 614, 2
<omitted>
<contains 773 1's>

Скучные правила для ответов полицейских:

• Чтобы предотвратить безопасность из-за неясности, интерпретатор должен быть написан на языке, входящем в топ-100 этого индекса TIOBE, и иметь свободно доступный компилятор / интерпретатор.
• Переводчик не должен толковать язык, который был опубликован до этого вызова.
• Переводчик должен вписываться в ваш пост и не размещаться снаружи.
• Переводчик должен быть детерминированным
• Переводчик должен быть переносимым и следовать стандарту своего языка; не используйте неопределенное поведение или ошибки
• Если программа решения слишком длинна, чтобы уместиться в ответе, вы должны опубликовать программу, которая ее генерирует.
• Программа решения должна состоять только из печатных ASCII и новых строк.
• Вы должны выполнить свою программу решения менее чем за 1 час на своем компьютере для каждого из приведенных выше примеров ввода.
• Программа должна работать для любых целых чисел меньше 10 ⁶ и любого числа целых чисел меньше 10 ⁶ (необязательно меньше часа) при условии, что общая длина ввода меньше 10 ⁹ .
• Чтобы стать безопасным, полицейский должен отредактировать программу решения в ответ после того, как прошло 8 дней.

счет

Полицейский, который становится безопасным с наибольшим количеством очков и положительным результатом, побеждает в этом вопросе.

Перевертыш (безопасный)

ShapeScript

ShapeScript - это естественный язык программирования. Переключатели форм (или Changelings , как они предпочитают называться) могут преобразовываться в набор инструкций, которые позволяют им обрабатывать данные.

ShapeScript - это стековый язык с относительно простым синтаксисом. Неудивительно, что большинство встроенных функций имеют дело с изменением формы струн. Это интерпретируется, символ за символом, следующим образом:

• 'и "начать строковый литерал.

  До тех пор, пока в исходном коде не будет найдена соответствующая кавычка, все символы между этими совпадающими кавычками собираются в строку, которая затем помещается в стек.

• 0чтобы 9подтолкнуть целые числа 0 до 9 в стеке. Обратите внимание, что 10толкает два целых числа.

• ! извлекает строку из стека и пытается оценить ее как ShapeScript.

• ? извлекает целое число из стека и помещает копию элемента стека по этому индексу.

  Индекс 0 соответствует самому верхнему элементу стека (LIFO), а индекс -1 - самому нижнему.

• _ извлекает итерацию из стека и увеличивает его длину.

• @ извлекает два элемента из стека и помещает их в обратном порядке.

• $извлекает две строки из стека и разбивает самую нижнюю в появлении самой верхней. Результирующий список отправляется взамен.

• &извлекает строку (самая верхнюю) и итерируемую из стека и присоединяет итеративную, используя строку в качестве разделителя. Результирующая строка отправляется взамен.

• Если ShapeScript используется на нашей планете, так как питоны подменышей ближайших родственников на Земле, все остальные символы Ĉ поп два пункта х и у (верхний) из стека, и попытаться оценить код Python x c y.

  Например, последовательность символов 23+будет оценена 2+3, в то время как последовательность символов "one"3*будет оценена 'one'*3, и последовательность символов 1''Aбудет оценена 1A''.

  В последнем случае, поскольку результат не является допустимым Python, Подменыш будет жаловаться на то, что его текущая форма не предназначена (синтаксическая ошибка), поскольку он не является допустимым ShapeScript.

Перед выполнением кода интерпретатор поместит весь ввод пользователя в виде строки в стек. После выполнения исходного кода интерпретатор напечатает все элементы в стеке. Если какая-либо часть между ними выходит из строя, Подменыш будет жаловаться, что его текущая форма неадекватна (ошибка во время выполнения).

Сдвиг формы

В своем естественном состоянии Changelings не принимают форму ShapeScript. Однако некоторые из них могут трансформироваться в один потенциальный исходный код (который не обязательно полезен или даже синтаксически действителен).

Все подходящие Changelings имеют следующую естественную форму:

• Все строки должны иметь одинаковое количество символов.

• Все строки должны состоять из печатных символов ASCII, за которыми следует один перевод строки.

• Количество строк должно соответствовать количеству печатаемых символов в строке.

Например, последовательность байтов ab\ncd\nявляется допустимой заменой.

В попытке перейти на ShapeScript, Перевертыш претерпевает следующее преобразование:

• Изначально нет исходного кода.

• Для каждой строки происходит следующее:

  • Аккумулятор Changeling установлен на ноль.

  • Для каждого символа c строки (включая завершающий перевод строки) кодовая точка c XORed с аккумулятором, деленным на 2, и символ Unicode, который соответствует результирующей кодовой точке, добавляется к исходному коду.

    После этого разница между кодовой точкой c и кодовой точкой пробела (32) добавляется к аккумулятору.

Если какая-либо часть из вышеперечисленного выходит из строя, Подменыш будет жаловаться, что его текущая форма неприятна.

После того, как все строки были обработаны, преобразование Changeling в (надеюсь, допустимый) ShapeScript завершено, и полученный код выполняется.

Решение (ShapeScript)

"0"@"0"$"0"2*&"0"@+0?_'@1?"0"$_8>"1"*+@1?"0"+$""&'*!#

На самом деле ShapeScript оказался вполне полезным; он может даже выполнять тестирование на простоту ( доказательство ) и, следовательно, удовлетворяет нашему определению языка программирования.

Я переиздал ShapeScript на GitHub с немного измененным синтаксисом и улучшенным I / O.

Код делает следующее:

"0"@    Push "0" (A) and swap it with the input string (S).
"0"$    Split S at 0's.
"0"2*   Push "00".
&       Join the split S, using "00" as separator.
"0"@+   Prepend "0" to S.
        The input has been transformed into
        "0<run of 1's>000<run of 1's>0...0<run of 1's>0000".
0?_     Push a copy and compute its length (L).
'       Push a string that, when evaluated, does the following:
  @1?     Swap A on top of S, and push a copy of S.
  "0"$    Split the copy of S at 0's.
  _8>     Get the length of the resulting array and compare it with 8.
          If this returns True, there are more than eight chunks, so there are
          more then seven 0's. With two 0's surrounding each run of 1's and
          three extra 0's at the end, this means that there still are three or
          more runs of 1's in the string.
  "1"*    Push "1" if '>' returned True and "" if it returned False.
  +       Append "1" or "" to A.
  @1?     Swap S on top of A, and push a copy of A.
  "0"+    Append "0" to the copy of A.
  $       Split S at occurrences of A+"0".
  ""&     Flatten the resulting array of strings.
'       This removes all occurrences of "010" in the first iteration, all
        occurrences of "0110" in the second, etc., until there are less than
        three runs of 1's left in S. At this point, A is no longer updated,
        and the code inside the string becomes a noop.
*!      Repeat the code string L times and evaluate.
#       Drop S, leaving only A on the stack.

Решение (Подменыш)

"1+-.......................
""B1.......................
"" 2)+7....................
"" 2)=<....................
""( $86=...................
""B8=......................
""247......................
""]`b......................
""B1.......................
""%D1=.....................
""%500=....................
""%&74?....................
""%&#.2....................
""%[bdG....................
""%D1=.....................
""%<5?.....................
""%:6>.....................
""%&65?....................
""%&-%7>...................
""%D1=.....................
""%500=....................
""%&74?....................
""%&,)5>...................
""%&%,79...................
"" )$?/=...................
""),-9=....................
""# !......................

Как и во всех программах Changeling, этот код имеет завершающий перевод строки.

ShapeScript выдаст ошибку сразу по любому символу, который не понимает, но мы можем выдвинуть произвольные строки как заполнители и вытолкнуть их позже. Это позволяет нам помещать только небольшое количество кода в каждую строку (в начале, где аккумулятор мал), после чего следует открывать ". Если мы начинаем следующую строку с "#, мы закрываем и выталкиваем строку, не влияя на реальный код.

Кроме того, нам предстоит преодолеть три незначительных препятствия:

• Длинная строка в коде ShapeScript представляет собой один токен, и мы не сможем поместить его в строку.

  Мы поместим эту строку в чанки ( '@', '1?'и т. Д.), Которые мы объединим позже.

• Кодовая точка _довольно высока, и продвижение '_'будет проблематичным.

  Тем не менее, мы сможем нажать '_@'без усилий, а затем еще один, '@'чтобы отменить обмен.

Код ShapeScript, который сгенерирует наша перестановка, выглядит так : ¹ :

"0""
"#@"
"#"0"$"
"#"0"2"
"#*&"0""
"#@+"
"#0?"
"#_@"
"#@"
"#'@'"
"#'1?'"
"#'"0'"
"#'"$'"
"#'_@'"
"#'@'"
"#'8'"
"#'>'"
"#'"1'"
"#'"*+'"
"#'@'"
"#'1?'"
"#'"0'"
"#'"+$'"
"#'""&'"
"#"+"77"
"#+*!*"
"#!#"

Я нашел код Перестановки, запустив вышеуказанный код ShapeScript через этот конвертер . ²

Переводчик (Python 3)

#!/usr/bin/env python3

import fileinput

def error(code):
  print("This shape is " + ["unpleasant", "unpurposed", "inadequate"][code - 1] + ".")
  exit(code)

def interpret(code):
  global stack
  stringing = 0
  for char in code:
    quote = (char == "'") + 2 * (char == '"')
    if quote or stringing:
      if not stringing:
        string = ""
        stringing = quote
      elif stringing == quote:
        stack.append(string)
        stringing = 0
      else:
        string += char
    elif char in "0123456789":
      stack.append(int(char))
    else:
      x = stack.pop()
      if char == '!':
        interpret(x)
      else:
        if char == '?':
          y = stack[~x]
        elif char == "_":
          y = len(x)
        else:
          y = stack.pop()
          if char == '@':
            stack.append(x)
          elif char == '$':
            y = y.split(x)
          elif char == '&':
            y = x.join(map(str, y))
          else:
            try:
              y = eval(repr(y) + char + repr(x))
            except SyntaxError:
              error(2)
        stack.append(y)

source = ""
lengths = []

for line in fileinput.input():
  if not line or sorted(line)[:2][-1] < " " or max(line) > "~":
    error(1)
  lengths.append(len(line))
  accumulator = 0
  for char in line:
    value = ord(char)
    try:
      source += chr(value ^ (accumulator >> 1))
    except:
      error(1)
    accumulator += value - 32

lengths.append(len(lengths) + 1)

if min(lengths) != max(lengths):
  error(1)

stack = ""

for line in fileinput.input("-"):
  stack += line

stack = [stack]

try:
  interpret(source)
except:
  error(3)

print("".join(map(str, stack)))

¹ _{Каждая строка дополняется случайным мусором до количества строк, а переводы строки фактически отсутствуют.}
² _{Числа внизу указывают самую низкую и самую высокую кодовые точки в коде перестановки, которые должны находиться в диапазоне от 32 до 126.}

Shuffle (написанный на C ++), Cracked! Мартин

Править Мартин взломал его. Чтобы увидеть его решение, нажмите на ссылку. Мое решение также было добавлено.

Редактировать Исправлена print-dкоманда, чтобы иметь возможность обрабатывать как регистры и стеки. Поскольку это команда отладки, которая не разрешена в решении, это не должно повлиять на кого-либо, использующего предыдущую версию интерпретатора.

Я все еще новичок в этом, поэтому, если что-то не так с моим ответом или моим переводчиком, пожалуйста, дайте мне знать. Пожалуйста, попросите разъяснений, если что-то не понятно.

Я не думаю, что это будет слишком сложно, но, надеюсь, это вызовет какие-то проблемы. Что делает shuffle довольно непригодным для использования, так это то, что оно будет печататься только тогда, когда все будет на своем месте

-> Основа:

Есть 24 стека, мы их называем stack1, ... stack24. Эти стеки живут в списке. В начале любой программы эти стеки имеют нулевой толчок, и они начинаются на своем месте, то есть укладывают i в i - ую позицию в списке (обратите внимание, что мы будем индексировать, начиная с 1, в отличие от C ++). В ходе программы порядок стеков в списке будет меняться. Это важно по причинам, которые будут объяснены при обсуждении команд.

Для использования доступно 5 регистров. Они названы Alberto, Gertrude, Hans, Leopold, ShabbySam. Каждый из них устанавливается в ноль в начале программы.

Итак, в начале любой программы существует 24 стека, каждый из которых имеет свой номер, соответствующий его индексу в списке стеков. Каждый стек имеет ровно один ноль сверху. Каждый из пяти регистров обнуляется.

-> Команды и Синтаксис :

В Shuffle доступно 13 команд (+1 команда отладки). Они следующие

• cinpushэта команда не принимает аргументов. Он ожидает ввода в командной строке способом, описанным в вопросе (другой ввод приведет к неопределенным / неопределенным результатам). Затем он разбивает входную строку на целые числа, например 101011100-> 1,1,3. Для каждого полученного ввода выполняется следующее: (1) переставляет список стеков на основе значения. Пусть целое значение в вопросе можно назвать . Если а меньше 10, он делает перестановку и . Если a составляет от 9 до 30 (не включительно), он выполняет перестановку d . В противном случае это делает перестановку r . (2) Затем она толкаетна стек, который является первым в списке. Обратите внимание, что я не имею в виду stack1(хотя это может быть случай, который stack1является первым в списке). Перестановки определены ниже. Поскольку cinpushэто единственный способ получить пользовательский ввод , он должен появиться в любом решении.

• mov value registerКоманда movв основном присваивается переменная. Он назначает valueна register. valueможет принимать несколько форм: это может быть (1) целое число, например 47 (2) имя другого регистра, например Hans (3) индекс стека, за которым следует 's', например 4s. Обратите внимание, что это индекс в списке, а не номер стека. Таким образом, число не должно превышать 24.

  Некоторые movпримеры:

  mov 4s Hans 
  mov Hans ShabbySam
  mov 9999 Gertrude
  

• movfs index registerЭто означает «движение из стека». Это похоже на movкоманду. Он существует для того, чтобы вы могли получить доступ к стеку, проиндексированному регистром. Например, если раньше вы установили Ганса равным 4 ( mov 4 Hans), то вы можете использовать его, movfs Hans Gertrudeчтобы установить Гертруду равной вершине стека 4. Этот тип поведения недоступен просто при использовании mov.

• inc register увеличивает значение регистра на 1.
• dec register уменьшает значение регистра на 1.
• compg value value registerЭто означает «сравнить больше». Он устанавливает регистр равным наибольшему из двух значений. valueможет быть целым числом, регистром или индексом стека, за которым следует 's', как указано выше.
• compl value value register «сравнить меньше», как указано выше, за исключением того, что принимает меньшее значение.
• gte value1 value2 registerПроверяет, value1 >= value2помещает ли тогда логическое значение (как 1 или 0) в register.
• POP!! indexвыскакивает из верхней части стека, проиндексированного indexв списке стека.
• jmp labelбезоговорочно переходит на метку label. Это хорошее время, чтобы поговорить о лейблах. Метка - это слово, за которым следует «:». Интерпретатор выполняет предварительный анализ меток, поэтому вы можете переходить как к меткам, так и назад.
• jz value labelпереходит к labelесли valueноль.

• jnz value labelпереходит к labelесли valueненулевой.

  Примеры меток и прыжков:

  this_is_my_label:
       jmp this_is_my_label
  
  mov 10 Hans
  jnz Hans infinite_loop
  
  infinite_loop:
       jmp infinite_loop
  

• "shuffle" permutationВот команда перемешивания. Это позволяет вам переставлять список стеков. Есть три действительные перестановок , которые могут быть использованы в качестве аргументов, l, f, и b.

• print registerЭто проверяет, все ли стеки находятся в своих начальных позициях, то есть стек i имеет индекс i в списке стеков. Если это так, он печатает значение registerв унарном виде. В противном случае выдает неприятную ошибку. Как видите, для вывода чего-либо все стеки должны быть в правильных местах.
• done!это говорит программе выйти без ошибок. Если программа заканчивается без done!, она выведет на консоль число сверху каждого стека, за которым следует номер стека. Порядок печати стеков соответствует порядку их появления в списке стеков. Если стек пуст, он будет опущен. Это поведение для целей отладки и не может быть использовано в решении.
• print-d valueэто печатает значение заданного стека, регистра или целого числа (чтобы получить доступ к стеку i , передайте в isкачестве аргумента, как описано выше). Это инструмент отладки, а не часть языка, поэтому он не разрешен в решении.

-> Вот код интерпретатора

Весь разбор происходит в основной функции. Здесь вы найдете разбор для конкретных команд.

#include<fstream>
#include<iostream>
#include<string>
#include<stack>
#include<cmath>

using namespace std;

class superStack: public stack<long> {
    private:
        int m_place;
    public:
        static int s_index;


        superStack() {
            m_place = s_index;
            s_index++;
        }

        int place() {
            return m_place;
        }
};
int superStack::s_index=1;

superStack  stack1,stack2,stack3,stack4,stack5,stack6,stack7,stack8,stack9,stack10,stack11, \
            stack12,stack13,stack14,stack15,stack16,stack17,stack18,stack19,stack20,stack21,stack22,stack23,stack24;


superStack* stackptrs[]=    { \
                        &stack1,&stack2,&stack3,&stack4,&stack5,&stack6,&stack7,&stack8,&stack9,&stack10,&stack11, \
                        &stack12,&stack13,&stack14,&stack15,&stack16,&stack17,&stack18,&stack19,&stack20,&stack21,&stack22,&stack23,&stack24 \
                        };


long Gertrude=0;
long Hans=0;
long Alberto=0;
long ShabbySam=0;
long Leopold=0;


void SWAP( int i, int j) {    // 0 < i,j < 25

    i--;
    j--;


    superStack* tempptr = stackptrs[i];
    stackptrs[i]=stackptrs[j];
    stackptrs[j] = tempptr;



}

void u() {
    int list[3][4] = {
                        {1,9,6,13},
                        {2,10,5,14},
                        {17,19,20,18},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void d() {
    int list[3][4] = {
                        {3,11,8,15},
                        {4,12,7,16},
                        {22,24,23,21},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void r() {
    int list[3][4] = {
                        {2,17,8,24},
                        {4,18,6,23},
                        {9,10,12,11},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void l() {
    int list[3][4] = {
                        {1,19,7,22},
                        {3,20,5,21},
                        {14,13,15,16},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void f() {
    int list[3][4] = {
                        {20,9,24,16},
                        {18,11,22,14},
                        {1,2,4,3},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}
void b() {
    int list[3][4] = {
                        {19,10,23,15},
                        {17,12,21,13},
                        {5,6,8,7},
                    };

    for(int i=0;i<3;i++) {
        for(int j=1;j<4;j++) {
            SWAP( list[i][0], list[i][j] );         
        }
    }
}

void splitpush(string input) {
    long value=0;

    for(long i=0;i<input.size();i++) {

        if(input[i]=='1'){
            value++;
        }
        else if(input[i]=='0' && value!=0 ) {
            if(value<10) {
                u();
            }
            else if (value<30) {
                d();

            }
            else {
                r();
            }
            (*stackptrs[0]).push(value);
            value=0;

        }
        else {
            break;
        }

    }

}

long strToInt(string str) { // IF STRING HAS NON DIGITS, YOU WILL GET GARBAGE, BUT NO ERROR
    long j=str.size()-1;
    long value = 0;
    for(long i=0;i<str.size();i++) {
        long x = str[i]-48;

        value+=x*floor( pow(10,j) );
        j--;
    }
    return value;
}

bool isEmpty(superStack stk) {
    if( stk.size()>0){return false; }
    else {return true;}

}    

long getValue(string str) {
    if(str=="ShabbySam") {
        return ShabbySam;
    }
    else if(str=="Hans") {
        return Hans;
    }
    else if(str=="Gertrude") {
        return Gertrude;
    }
    else if(str=="Alberto") {
        return Alberto;
    }   
    else if(str=="Leopold") {
        return Leopold;
    }
    else if(str[ str.size()-1 ]=='s'){
        str.pop_back();

        long index = strToInt(str)-1;

        if( !isEmpty( (*stackptrs[index]) ) ) {
            return (*stackptrs[index]).top();
        }
        else {
            cerr<<"Bad Expression or Empty Stack";


        }   
    }
    else {
        return strToInt(str);
    }

}

void printUnary(long i) {
    while(i>0) {
        cout<<1;
        i--;
    }
}

int main(int argc, char**argv) {

    if(argc<2){std::cerr<<"No input file given"; return 1;}
    ifstream inf(argv[1]);
    if(!inf){std::cerr<<"File open failed";return 1;}

    for(int i=0;i<24;i++) { 
        (*stackptrs[i]).push(0);         // Pre push a zero on every stack
    }

    string labels[20];
    unsigned labelPoints[20];
    int index=0;



    string str;
    while(inf) { //  parse for labels
        inf>>str;
        //cout<<inf.tellg()<<" ";
        if(inf) {
            if(str[str.size()-1]==':') {
                str.pop_back();
                bool alreadyExists = false;
                for(int i=0; i<index;i++){
                    if(labels[i] == str ) { alreadyExists=true;}
                }
                if(!alreadyExists) {
                    labels[index]=str;
                    labelPoints[index]= inf.tellg();
                    index++;
                }
            }

        }

    }
    inf.clear();
    inf.seekg(0,inf.beg);

    while(inf) { // parse for other commands 
        inf>>str;

        if(inf) {


            if(str=="cinpush") {
                string input;
                cin>>input;
                splitpush(input);
            }

            else if(str=="mov") {
                inf>>str;
                long value = getValue(str);

                inf>>str;
                if(str=="Gertrude"){Gertrude=value;}
                else if(str=="Hans"){Hans=value;}
                else if(str=="ShabbySam"){ShabbySam=value;}
                else if(str=="Alberto"){Alberto=value;}
                else if(str=="Leopold"){Leopold=value;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="movfs") {
                inf>>str;
                long index = getValue(str);
                if(!isEmpty( *stackptrs[index-1] )) {
                    inf>>str;
                    long value = (*stackptrs[index-1]).top();
                    if(str=="Gertrude"){Gertrude=value;}
                    else if(str=="Hans"){Hans=value;}
                    else if(str=="ShabbySam"){ShabbySam=value;}
                    else if(str=="Alberto"){Alberto=value;}
                    else if(str=="Leopold"){Leopold=value;}
                    else {cerr<<"Bad register name.";}
                }
                else {
                    cerr<<"Empty Stack";
                }



            }

            else if(str=="inc") {
                inf>>str;
                if(str=="Gertrude"){Gertrude++;}
                else if(str=="Hans"){Hans++;}
                else if(str=="ShabbySam"){ShabbySam++;}
                else if(str=="Alberto"){Alberto++;}
                else if(str=="Leopold"){Leopold++;}
                else {cerr<<"Bad register name. ";}
            }
            else if(str=="dec") {
                inf>>str;
                if(str=="Gertrude"){Gertrude--;}
                else if(str=="Hans"){Hans--;}
                else if(str=="ShabbySam"){ShabbySam--;}
                else if(str=="Alberto"){Alberto--;}
                else if(str=="Leopold"){Leopold--;}
                else {cerr<<"Bad register name. ";}
            }


            else if(str=="compg") {
                inf>>str;
                long value1 = getValue(str);
                inf>>str;
                long value2 = getValue(str);
                inf>>str;
                long larger;
                if(value1>value2){larger = value1;}
                else {larger = value2;}

                if(str=="Gertrude"){Gertrude=larger;}
                else if(str=="Hans"){Hans=larger;}
                else if(str=="ShabbySam"){ShabbySam=larger;}
                else if(str=="Alberto"){Alberto=larger;}
                else if(str=="Leopold"){Leopold=larger;}
                else {cerr<<"Bad register name. ";}

            }
            else if(str=="compl") {
                inf>>str;
                long value1 = getValue(str);
                inf>>str;
                long value2 = getValue(str);
                inf>>str;
                long larger; //LARGER IS REALLY SMALLER HERE
                if(value1>value2){larger = value2;}
                else {larger = value1;}

                if(str=="Gertrude"){Gertrude=larger;}
                else if(str=="Hans"){Hans=larger;}
                else if(str=="ShabbySam"){ShabbySam=larger;}
                else if(str=="Alberto"){Alberto=larger;}
                else if(str=="Leopold"){Leopold=larger;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="gte") {
                inf>>str;
                long value1= getValue(str);
                inf>>str;
                long value2= getValue(str);
                inf>>str;
                bool torf = value1 >= value2;

                if(str=="Gertrude"){Gertrude=torf;}
                else if(str=="Hans"){Hans=torf;}
                else if(str=="ShabbySam"){ShabbySam=torf;}
                else if(str=="Alberto"){Alberto=torf;}
                else if(str=="Leopold"){Leopold=torf;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="lte") {
                inf>>str;
                long value1= getValue(str);
                inf>>str;
                long value2= getValue(str);
                inf>>str;
                bool torf = value1 <= value2;

                if(str=="Gertrude"){Gertrude=torf;}
                else if(str=="Hans"){Hans=torf;}
                else if(str=="ShabbySam"){ShabbySam=torf;}
                else if(str=="Alberto"){Alberto=torf;}
                else if(str=="Leopold"){Leopold=torf;}
                else {cerr<<"Bad register name. ";}

            }

            else if(str=="POP!!") {
                inf>>str;
                long index = getValue(str);
                index--; //because we (C++ and this interpreter) index differently
                if(!isEmpty( *stackptrs[index] )) {
                    (*stackptrs[index]).pop();
                }
                else {cerr<<"Can't POP!! from empty stack";}

            }

            else if(str=="push"){cerr<<" You can't. ";}

            /*
            else if(str[str.size()-1]==':') {
                str.pop_back();
                bool alreadyExists = false;
                for(int i=0; i<index;i++){
                    if(labels[i] == str ) { alreadyExists=true;}
                }
                if(!alreadyExists) {
                    labels[index]=str;
                    labelPoints[index]= inf.tellg();
                    index++;
                }
            }*/

            else if(str=="jmp") {
                inf>>str;
                for(int i=0;i<index;i++) {
                    if( labels[i]==str) {
                        inf.seekg( labelPoints[i], ios::beg);
                    }
                }
            }
            else if(str=="jz") {
                inf>>str;
                long value = getValue(str);

                if(value==0) {
                    inf>>str;
                    for(int i=0;i<index;i++) {
                        if( labels[i]==str) {
                            inf.seekg( labelPoints[i], ios::beg);
                        }
                    }
                }
            }

            else if(str=="jnz") {
                inf>>str;
                long value = getValue(str);

                if(value!=0) {
                    inf>>str;
                    for(int i=0;i<index;i++) {
                        if( labels[i]==str) {
                            inf.seekg( labelPoints[i], ios::beg);
                        }
                    }
                }
            }

            else if(str== "\"shuffle\"") {
                inf>>str;
                if(str=="l"){ l(); }
                else if(str=="f"){ f(); }
                else if(str=="b"){ b(); }
                else {cerr<<"Bad shuffle parameter";}

            }

            else if(str=="print") {

                for(int i=0;i<24;i++) {

                    if( (i+1) != (*stackptrs[i]).place() ) {
                        cerr<< "Sorry, your stacks are in the wrong place! You can't print unless you put them back! Exiting. ";
                        return 1;
                    }

                }
                inf>>str;
                if(str=="Gertrude"){printUnary(Gertrude);}
                else if(str=="Hans"){printUnary(Hans);}
                else if(str=="ShabbySam"){printUnary(ShabbySam);}
                else if(str=="Alberto"){printUnary(Alberto);}
                else if(str=="Leopold"){printUnary(Leopold);}
                else {cerr<<"Bad register name. ";}


            }

            else if(str=="done!") {return 0;}

            else if(str=="print-d" ){
                inf>>str;
                long value = getValue(str);
                cout<<str;
              }
        }

    }







    /*for(int i=1;i<25;i++) {
        (*(stackptrs[i-1])).push(i);
    }

    u();d();r();l();f();b();
    */

    cout<<"\n";
    for(int i=1;i<25;i++) {
        if( (*(stackptrs[i-1])).size()>0 ) {
            cout<<(*(stackptrs[i-1])).top()<<" "<<(*(stackptrs[i-1])).place()<<"\n";
            (*(stackptrs[i-1])).pop();
        }
    }
    /*
    for (int i=0;i<index;i++) {
        cout<<labels[i]<<": "<<labelPoints[i]<<"\n";
    }*/

    return 1;
}

-> Перестановки Перестановки переставляют элементы списка стека следующим образом:

Где это означает, что

(Они также появляются в коде интерпретатора. Если есть расхождение, интерпретатор корректен.)

-> Простой пример

Эти две простые программы печатают числа от 24 до 1 (в унарном формате) без пробелов.

mov 24 Hans
start:
    print Hans
    dec Hans
    jnz Hans start
done!

или же

mov 24 Hans start: print Hans dec Hans jnz Hans start done!

Это одна и та же программа.

Объяснение и решение:

У Мартина также есть хорошее объяснение в его ответе .

Как выяснил Мартин, этот язык был вдохновлен карманным кубом (он же 2х2 кубика Рубика). 24 стека похожи на 24 отдельных квадрата на кубе. Перестановки являются основными допустимыми движениями: вверх, вниз, вправо, влево, вперед, назад.

Основная проблема здесь в том, что когда значения сдвигаются, используются только три хода: вверх, вниз и вправо. Тем не менее, у вас нет доступа к этим ходам при «перетасовке» стеков. У вас есть только три других хода.

Как оказалось, оба набора из трех ходов фактически охватывают всю группу (т.е. являются генераторами), поэтому проблема разрешима. Это означает, что вы можете решить любой кубик Рубика 2x2, используя только 3 хода.

Все, что осталось сделать, - это выяснить, как отменить движения вверх, вниз и вправо, используя остальные три. Для этого я использовал систему компьютерной алгебры под названием GAP .

После отмены перестановок найти третье по величине число довольно тривиально.

cinpush
main:
    mov 1s ShabbySam
    POP!! 1
    jmp compare
    continue:
        gte 0 ShabbySam Leopold
        jnz Leopold end
        gte ShabbySam 9 Leopold
        jz Leopold uinverse
        gte ShabbySam 29 Leopold
        jz Leopold dinverse
        jnz Leopold rinverse
compare:
    gte ShabbySam Alberto Leopold
    jz Leopold skip
    mov Gertrude Hans
    mov Alberto Gertrude
    mov ShabbySam Alberto
    jmp continue
    skip:
        gte ShabbySam Gertrude Leopold
        jz Leopold skip_2
        mov Gertrude Hans
        mov ShabbySam Gertrude
        jmp continue
    skip_2:
        gte ShabbySam Hans Leopold
        jz Leopold continue
        mov ShabbySam Hans
        jmp continue
uinverse: 
    "shuffle" f
    "shuffle" f
    "shuffle" f
    "shuffle" l
    "shuffle" b
    "shuffle" l
    "shuffle" b
    "shuffle" b
    "shuffle" b
    "shuffle" l
    "shuffle" l
    "shuffle" l
    "shuffle" b
    "shuffle" b
    "shuffle" b
    "shuffle" l
    "shuffle" l
    "shuffle" l
    "shuffle" f
    jmp main
dinverse:
    "shuffle" f
    "shuffle" b
    "shuffle" l
    "shuffle" b
    "shuffle" b
    "shuffle" b
    "shuffle" f
    "shuffle" f
    "shuffle" f
    jmp main
rinverse: 
    "shuffle" b "shuffle" l "shuffle" f "shuffle" l "shuffle" b
    "shuffle" f "shuffle" f "shuffle" f "shuffle" b
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" b "shuffle" b "shuffle" b
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" f "shuffle" l "shuffle" f
    "shuffle" l "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l 
    "shuffle" f "shuffle" l "shuffle" l 
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" l "shuffle" l "shuffle" l "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    "shuffle" f "shuffle" f "shuffle" f
    "shuffle" l "shuffle" f "shuffle" l "shuffle" f "shuffle" l "shuffle" f
    "shuffle" l "shuffle" l "shuffle" l
    jmp main
end:
    print Hans
    done!

Брайан и Чак , взломанные картонной коробкой

Некоторое время я был заинтригован идеей языка программирования, в котором две программы взаимодействуют друг с другом (вероятно, вдохновленный ROCB ). Этот вызов был хорошим стимулом, чтобы наконец-то заняться этой концепцией, стараясь сохранить язык как можно более минимальным. Цели проекта заключались в том, чтобы сделать язык Тьюринга полным, в то время как каждая его часть по отдельности не является полной по Тьюрингу. Кроме того, даже оба вместе не должны быть Turing-завершенными без использования манипулирования исходным кодом. Я думаю, что мне это удалось, но я еще не доказал ничего из этого формально. Так что без лишних слов я представляю вам ...

Главные герои

Брайан и Чак - две подобные Brainfuck программы. Только один из них выполняется в любой момент времени, начиная с Брайана. Загвоздка в том, что лента памяти Брайана также является исходным кодом Чака. И лента памяти Чака также является исходным кодом Брайана. Кроме того, головка ленты Брайана также является указателем Чака, и наоборот. Ленты являются полубесконечными (то есть бесконечными справа) и могут содержать целые числа произвольной точности со знаком, инициализированные нулем (если в исходном коде не указано иное).

Поскольку исходный код также является лентой памяти, команды технически определяются целочисленными значениями, но они соответствуют разумным символам. Существуют следующие команды:

• ,( 44): Считывание байта из STDIN в текущую ячейку памяти. Только Брайан может сделать это. Эта команда не предназначена для Чака.
• .( 46): Записать текущую ячейку памяти по модулю 256 в качестве байта в STDOUT. Только Чак может сделать это. Эта команда не предназначена для Брайана.
• +( 43): Увеличить текущую ячейку памяти.
• -( 45): Уменьшить текущую ячейку памяти.
• ?( 63): Если текущая ячейка памяти равна нулю, это не работает. В противном случае передать управление другой программе. Головка ленты на программе, которая использует ?, останется на ?. Ленточная головка другой программы перед выполнением первой команды переместится на одну ячейку вправо (поэтому ячейка, используемая в качестве теста, сама не выполняется).
• <( 60): Переместите головку ленты на одну ячейку влево. Это не работает, если головка ленты уже находится на левом конце ленты.
• >( 62): Переместите головку ленты на одну ячейку вправо.
• {( 123): Повторно перемещайте головку ленты влево, пока либо текущая ячейка не станет равной нулю, либо не будет достигнут левый конец ленты.
• }( 125): Повторно перемещайте головку ленты вправо, пока текущая ячейка не станет равной нулю.

Программа завершается, когда указатель инструкций активной программы достигает точки, где больше нет инструкций справа от нее.

Исходный код

Исходный файл обрабатывается следующим образом:

• Если файл содержит строку ```, файл будет разбит на две части вокруг первого появления этой строки. Все начальные и конечные пробелы удаляются, и первая часть используется в качестве исходного кода для Брайана, а вторая часть для Чака.
• Если файл не содержит эту строку, первая строка файла будет использоваться в качестве источника для Брайана, а вторая часть для Чака (кроме новой строки с разделителями, пробелы не будут удалены).
• Все вхождения _в обеих программах заменяются пустыми байтами.
• Две ленты памяти инициализируются кодами символов, соответствующими полученной строке.

В качестве примера приведен следующий исходный файл

  abc
```
0_1
23

Дали бы следующие начальные ленты:

Brian: [97 98 99 0 0 0 0 ...]
Chuck: [48 0 49 10 50 51 0 0 0 0 ...]

Переводчик

Переводчик написан на Ruby. Он принимает два флага командной строки, которые не должны использоваться никаким решением (так как они не являются частью фактической спецификации языка):

• -dС этим флагом Брайан и Чак понимают еще две команды. !напечатает строковое представление обеих лент памяти, активная программа будет указана первой (a ^пометит текущие головки ленты). @также сделает это, но затем немедленно прекратит работу программы. Поскольку я ленив, ни одна из этих команд не работает, если они являются последней командой в программе, поэтому, если вы хотите использовать их там, повторите их или напишите неактивные после них.
• -D: Это подробный режим отладки. Он выведет ту же отладочную информацию, что и !после каждого тика. @также работает в этом режиме.

Вот код:

# coding: utf-8

class Instance
    attr_accessor :tape, :code, :ip

    OPERATORS = {
        '+'.ord  => :inc,
        '-'.ord  => :dec,
        '>'.ord  => :right,
        '<'.ord  => :left,
        '}'.ord  => :scan_right,
        '{'.ord  => :scan_left,
        '?'.ord  => :toggle,
        ','.ord  => :input,
        '.'.ord  => :output,
        '!'.ord  => :debug,
        '@'.ord  => :debug_terminate
    }

    OPERATORS.default = :nop

    def initialize(src)
        @code = src.chars.map(&:ord)
        @code = [0] if code.empty?

        @ip = 0
    end

    def tick
        result = :continue
        case OPERATORS[@code[@ip]]
        when :inc
            @tape.set(@tape.get + 1)
        when :dec
            @tape.set(@tape.get - 1)
        when :right
            @tape.move_right
        when :left
            @tape.move_left
        when :scan_right
            @tape.move_right while @tape.get != 0
        when :scan_left
            @tape.move_left while @tape.ip > 0 && @tape.get != 0
        when :toggle
            if @tape.get != 0
                @tape.move_right
                result = :toggle
            end
        when :input
            input
        when :output
            output
        when :debug
            result = :debug
        when :debug_terminate
            result = :debug_terminate
        end

        return :terminate if result != :toggle && @ip == @code.size - 1

        move_right if result != :toggle

        return result
    end

    def move_right
        @ip += 1
        if @ip >= @code.size
            @code << 0
        end
    end

    def move_right
        @ip += 1
        if @ip >= @code.size
            @code << 0
        end
    end

    def move_left
        @ip -= 1 if @ip > 0
    end

    def get
        @code[@ip]
    end

    def set value
        @code[@ip] = value
    end

    def input() end
    def output() end

    def to_s
        str = self.class.name + ": \n"
        ip = @ip
        @code.map{|i|(i%256).chr}.join.lines.map do |l|
            str << l.chomp << $/
            str << ' '*ip << "^\n" if 0 <= ip && ip < l.size
            ip -= l.size
        end
        str
    end
end

class Brian < Instance
    def input
        byte = STDIN.read(1)
        @tape.set(byte ? byte.ord : -1)
    end
end

class Chuck < Instance
    def output
        $> << (@tape.get % 256).chr
    end
end

class BrianChuck

    class ProgramError < Exception; end

    def self.run(src, debug_level=0)
        new(src, debug_level).run
    end

    def initialize(src, debug_level=false)
        @debug_level = debug_level

        src.gsub!('_',"\0")

        if src[/```/]
            brian, chuck = src.split('```', 2).map(&:strip)
        else
            brian, chuck = src.lines.map(&:chomp)
        end

        chuck ||= ""

        brian = Brian.new(brian)
        chuck = Chuck.new(chuck)

        brian.tape = chuck
        chuck.tape = brian

        @instances = [brian, chuck]
    end

    def run
        (puts @instances; puts) if @debug_level > 1

        loop do
            result = current.tick

            toggle if result == :toggle

            (puts @instances; puts) if @debug_level > 1 || @debug_level > 0 && (result == :debug || result == :debug_terminate)

            break if result == :terminate || @debug_level > 0 && result == :debug_terminate
        end
    end

    private

    def current
        @instances[0]
    end

    def toggle
        @instances.reverse!
    end
end

case ARGV[0]
when "-d"
    debug_level = 1
when "-D"
    debug_level = 2
else
    debug_level = 0
end

if debug_level > 0
    ARGV.shift
end

BrianChuck.run(ARGF.read, debug_level)

Вот мое (написанное от руки) решение проблемы:

>}>}>
brace left: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
brace left: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>} Append a bunch of 1s as a dummy list element:
+>+>+>+>+>+>+>+>+>+
Append two 1s and some code to the list; the first is a marker for later; the latter will be the integer
1: >+
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1: >+
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow right: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
_
{<<<<<<<<<{<{    Move back to the start
Read a character and subtract 48 to get actual 0 or 1
,------------------------------------------------
?   If 1 switch to Chuck otherwise continue
>}>}>>>>>>>>>}<<<<<<- Subtract 1 from the result to account for initial 1
?   If integer was positive switch to Chuck
@todo: process end
_
This code is run when reading 1:
}>}>>>>>>>>>}<<<<<<+ Move to the end of Chuck; skip one null cell; move to the end of the list
{<<<<<<<<<{<?   Move back to the code that resets this loop.
_
This code is run after finalising an integer:
change the code after the integer first
<<--<--<--}
Append two 1s and some code to the list; the first is a marker for later; the latter will be the integer
1: +
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1: >+
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow right: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
brace right: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
{<<<<<<<+<<{<{    Move back to the start; incrementing the list length
Read a character and subtract 48 to get actual 0 or 1
,------------------------------------------------
?   If 1 switch to Chuck otherwise continue
>}>}>>>>>>>>>}
Leave the resetting code, but remove the rest of the last list element:
<<<--<--<--
1: <-
question mk: <---------------------------------------------------------------
arrow left: <------------------------------------------------------------
brace right: <-----------------------------------------------------------------------------------------------------------------------------
1: <-
<{< Move back to the cell we reserved for the counter
<<<<<<-- decrement list size by two so we don't process the two largest elements
_

<{<<<<<<{<{<{<{<{>}>}>>>>>>> This is the beginning of the loop which decrements all list elements by 1
+ Add 1 to the running total
>>- Set marker of dummy list element to zero
_ Beginning of loop that is run for each list element
<{<<<<<<{<{<{<{<{>}>}>}>}+ set last marker back to 1
>>>>>>>>>> move to next marker
? Skip the next bit if we're not at the end of the list
<? Move back to the beginning of the loop
@ we should never get here
_
This is run when we're not at the end of the list
<<<- Set marker to 0 to remember current position
>>>>- Move to the current value and decrement it
? Move back to loop beginning if value is not zero yet
- Make element negative so it's skipped in the future
{<{<{>- Move to remaining list length and decrement it
? If it's nonzero switch to Chuck
>>>>>>>>->->->->->->->->->- Remove the dummy list to make some space for new code:
>}+ Fill in the marker in the list
{<<<<<<<<< Add some loop resetting code after the result:
brace left: +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
arrow left: >++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
question mk: >+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
_
This loop adds a print command to Chuck's code while decrementing the result
>>>>>>>>}>>>>>}>>>>>} Move to the very end of Chuck's code and leave some space to seek the 1
print: ++++++++++++++++++++++++++++++++++++++++++++++
{<<<<<{<<<<<{<<<<<<<{<
- decrement the result
? if nonzero run loop again
At this point we just need to make Chuck seek for the 1 at the end of this code print it often enough
>>}>>>>>>>}>>>>>}
arrow right: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
<?1 Switch to Chuck which moves Brian's tape head onto the 1 and then prints it N times


```

_   Dummy cell to hold input
This code is run when reading a 1:
{<{<{<{ ensure we're at the start
}>}<? Skip 0 handling code and switch to Brian
_ This code is run after a 1 has been processed:
{<{<?

Этот код работает как есть, потому что все аннотации используют no-ops и пропускаются {и }.

Основная идея:

1. Добавьте новый нулевой элемент в список (в конце ленты Чака) и увеличьте длину списка на 1.
2. Пока мы читаем 1s, увеличиваем этот элемент.

3. Когда мы читаем 0, сделайте некоторую очистку. Если полученное целое число было больше нуля, вернитесь к 1.

   Теперь у нас есть список входных чисел в конце ленты Чака, и мы знаем длину списка.

4. Вычтите 2 из длины списка (чтобы следующие шаги игнорировали два самых больших элемента), вызовите это N.

5. В то время как N > 0увеличиваем промежуточную сумму, а затем уменьшаем все элементы списка. Всякий раз, когда элемент списка достигает нуля, уменьшается N.

   В конце этого промежуточная сумма будет содержать третье по величине число на входе M.

6. Написать Mкопии .до конца ленты Чака.

7. На Чаке, ищите 1на ленте Брайана, а затем выполните те, что были сгенерированы .в конце.

Закончив это, я понял, что могу кое-что упростить в некоторых местах. Например, вместо того, чтобы отслеживать этот счетчик и записывать их .на ленту Чака, я мог просто напечатать 1сразу, каждый раз, прежде чем уменьшать все элементы списка. Однако вносить изменения в этот код довольно сложно, поскольку он распространяет другие изменения повсеместно, поэтому я не стал вносить изменения.

Интересным моментом является то, как отслеживать список и как его перебирать. Вы не можете просто хранить числа вплотную на ленте Чака, потому что тогда, если вы хотите проверить условие для одного из элементов списка, вы рискуете выполнить оставшуюся часть списка, которая может содержать действительный код. Вы также не знаете, как долго будет длиться список, поэтому вы не можете просто зарезервировать место перед кодом Чака.

Следующая проблема заключается в том, что нам нужно оставить список для уменьшения, Nпока мы его обрабатываем, и нам нужно вернуться в то же место, где мы были раньше. Но {и }просто пропустил бы весь список.

Поэтому нам нужно динамически написать код на Чака. Фактически каждый элемент списка iимеет вид:

[1 <Code A> i <Code B>]

1это маркер, который мы можем установить на ноль, чтобы указать, где мы остановились при обработке списка. Его цель - поймать {или }который просто передаст код и i. Мы также используем это значение, чтобы проверить, находимся ли мы в конце списка во время обработки, поэтому, пока мы не находимся, это будет, 1и условное ?переключит управление на Чака. Code Aиспользуется, чтобы справиться с этой ситуацией и соответственно переместить IP-адрес Брайана.

Теперь, когда мы уменьшаем, iнам нужно проверить, iравен ли уже ноль. Пока это не так, ?снова переключим управление, поэтому Code Bесть, чтобы справиться с этим.

HPR, написанный на Python 3 ( взломан TheNumberOne )

HPR (имя ничего не значит) - это язык для обработки списков целых чисел. Он разработан, чтобы быть минималистичным , чрезвычайно ограниченным и свободным от «искусственных» ограничений . Программирование в HPR является болезненным не потому, что вам нужно решить головоломку, чтобы не дать переводчику кричать на вас, а потому, что трудно заставить программу сделать что-нибудь полезное. Я не знаю, способен ли HPR на что-либо существенно более интересное, чем вычисление третьего по величине элемента списка.

Спецификация языка

Программа HPR выполняется в среде , которая представляет собой неупорядоченный набор неотрицательных целых чисел и списков неотрицательных целых чисел, не содержащих дубликатов. Первоначально среда содержит только входной список (интерпретатор анализирует его для вас). Существует три команды и два оператора «потока управления», которые изменяют среду:

• *удаляет первый элемент каждого непустого списка в среде и помещает его в среду. Пустые списки не затрагиваются. Например, он трансформируется

  {4,1,[0,2],[1,3],[]} -> {4,1,0,[2],[3],[]}
  

• -уменьшает все числа в окружении, а затем удаляет отрицательные элементы. Например, он трансформируется

  {4,2,0,[0,2],[4,4,4]} -> {3,1,[0,2],[4,4,4]}
  

• $вращает каждый список в среде на один шаг влево. Например, он трансформируется

  {4,1,[0,2],[3,4,1]} -> {4,1,[2,0],[4,1,3]}
  

• !(A)(B)Где Aи где Bнаходятся программы, это в основном whileцикл. Он выполняет «действие» Aдо тех пор, пока «тест» Bне приведет к пустой среде. Это может привести к бесконечному циклу.
• #(A)(B)где Aи где Bпрограммы, применяются Aи Bк текущей среде и принимает симметричную разницу результатов.

Команды выполняются слева направо. В конце размер среды печатается одинарным.

Переводчик

Этот интерпретатор имеет команду отладки ?, которая печатает среду без ее изменения. Оно не должно появляться ни в каком решении задачи. Любые символы, кроме *-$!#()?, просто игнорируются, поэтому вы можете писать комментарии прямо в код. Наконец, интерпретатор распознает идиому !(A)(#(A)())как «выполнить Aдо тех пор, пока результат больше не изменится» и оптимизирует ее для дополнительной скорости (мне нужно было, чтобы мое решение закончилось менее чем за час в последнем тестовом примере).

import sys

def parse(prog):
    "Parse a prefix of a string into an AST. Return it and the remaining input."
    ret = []
    while prog:
        if prog[0] in "#!":
            sub1, prog1 = parse(prog[2:])
            sub2, prog2 = parse(prog1[1:])
            ret += [prog[0],sub1,sub2]
            prog = prog2
        elif prog[0] == ')':
            prog = prog[1:]
            break
        else:
            ret += [prog[0]]
            prog = prog[1:]
    return ret, prog

def intp(ast, L_env, N_env):
    "Interpret the AST on an environment, return the resulting environment."
    ptr = 0
    while ptr < len(ast):
        cmd = ast[ptr]
        if cmd == '*':
            N_env = N_env | set(L[0] for L in L_env if L)
            L_env = set(L[1:] for L in L_env)
            ptr += 1
        elif cmd == '-':
            N_env = set(N-1 for N in N_env if N>0)
            ptr += 1
        elif cmd == '$':
            L_env = set(L[1:]+L[:1] for L in L_env)
            ptr += 1
        elif cmd == '!':
            # Speed optimization
            cond = ast[ptr+2]
            if cond == ['#', ast[ptr+1], []]:
                L_next, N_next = intp(ast[ptr+1], L_env, N_env)
                while L_next != L_env or N_next != N_env:
                    L_env, N_env = L_next, N_next
                    L_next, N_next = intp(ast[ptr+1], L_env, N_env)
            else:
                while True:
                    L_test, N_test = intp(cond, L_env, N_env)
                    if not L_test and not N_test:
                        break
                    L_env, N_env = intp(ast[ptr+1], L_env, N_env)
            ptr += 3
        elif cmd == '#':
            L_env1, N_env1 = intp(ast[ptr+1], L_env, N_env)
            L_env2, N_env2 = intp(ast[ptr+2], L_env, N_env)
            L_env = L_env1 ^ L_env2
            N_env = N_env1 ^ N_env2
            ptr += 3
        elif cmd == '?':
            print(L_env | N_env)
            ptr += 1
        else:
            ptr += 1
    return L_env, N_env

def main(p, L):
    "Run the program on the input, return the output."
    # Parse the input list
    L = ''.join(c for c in L if c in "01")
    while "00" in L:
        L = L.replace("00","0")
    L = [-2] + [i for i in range(len(L)-1) if L[i:i+2] == "10"]
    L = tuple(b-a-1 for (a,b) in zip(L, L[1:]))
    # Parse the program
    ast = parse(p)[0]
    L_env, N_env = intp(ast, set([L]), set())
    return '1'*(len(L_env) + len(N_env))

if __name__ == "__main__":
    filename = sys.argv[1]
    f = open(filename, 'r')
    prog = f.read()
    f.close()
    L = input()
    print(main(prog, L))

Мое решение

Мое эталонное решение имеет длину 484 байта, что довольно мало по сравнению с 3271-байтовой программой TheNumberOne. Это наиболее вероятно из-за сложной и удивительной макросистемы TheNumberOne, разработанной для программирования в HPR. Основная идея в обеих наших программах похожа:

1. Узнайте, как создать максимальный элемент списка.
2. Чтобы удалить элемент максимума, вращайте список до тех пор, пока первый элемент не станет равным максимуму, а затем вытолкните его.
3. Удалите максимум дважды, затем напечатайте новый элемент максимума.

Однако, насколько я могу судить, точные детали реализации совсем другие. Вот мое решение:

!($)(!(-)(#(-)())#(!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))(*)#(!(-)(#(-)()))())*!(-)(#(-)())!($)(!(-)(#(-)())#(!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())#(-)(#(!(-)(#(-)()))()))(*)#(!(-)(#(-)()))())*!(-)(#(-)())!(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))(#(-#(!(*)(#(*)())#(!(-)(#(-)()))())(!(-)(#(-)())))())-#(!(-)(#(-)()))()

А вот прокомментированная Python-программа, которая его производит (здесь нет ничего сложного, только базовые манипуляции со строками, чтобы избавиться от всех повторений):

# No numbers in the environment
no_nums = "#(-)()"
# No non-empty lists in the environment
no_lists = "#(*)()"
# Remove all numbers from the environment
del_nums = "!(-)(" + no_nums + ")"
# Remove all lists from the environment
del_lists = "#(" + del_nums + ")()"
# Splat the list to the environment:
#  pop the list until it's empty and delete the empty list,
#  then take symmetric difference with all numbers removed
splat = "#(!(*)(" + no_lists + ")" + del_lists + ")(" + del_nums + ")"
# Put into the environment all numbers up to list maximum:
#  decrement and splat until a fixed point is reached.
#  Without the speed optimization, this is very slow if the list elements are large.
splat_upto = "!(-" + splat + ")(#(-" + splat + ")())"
# Copy maximum element to environment:
#  take all elements up to maximum,
#  then take symmetric difference of decrement and list deletion
copy_max = splat_upto + "#(-)(" + del_lists + ")"
# Delete maximum element from list:
#  rotate until first element is maximal, then pop and delete it
del_max = "!($)(" + del_nums + "#(" + copy_max + ")(*)" + del_lists + ")*" + del_nums
# Full program:
#  remove the maximum twice, then produce all numbers up to maximum,
#  then decrement and remove lists. The environment will contain exactly
#  the integers from 0 to third largest - 1, and their number is printed.
main = del_max + del_max + splat_upto + "-" + del_lists
print(main)

TKDYNS (чтобы убить дракона, тебе нужен меч) - взломан Мартином Бюттнером

РЕДАКТИРОВАТЬ: я добавил свое решение и объяснение ниже основного поста.

Фон

На этом языке вы управляете доблестным воином, которому поручено убить ужасного дракона. Дракон живет в подземном лабиринте, полном опасностей и опасностей, и до сих пор никто не смог его спланировать и выжить. Это означает, что вы должны пройти свой путь к дракону в кромешной тьме, имея только интуицию и храбрость, чтобы направлять вас.

...

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

Еще немного деталей

Логово дракона принимает форму сетки 10х10. Между некоторыми соседними точками в сетке есть узкий проход; между другими существует глубокая пропасть и верная смерть. Пример макета для сетки 4x4 может быть следующим:

 0---1   2---3
     |   |   |
 4---5---6   7
 |           |
 8   9--10  11
     |       |
12--13--14--15

Вы знаете, что всегда есть способ добраться из одной точки в любую другую, но не более того, что вам было открыто.

Чтобы успешно победить дракона, вам сначала нужно собрать несколько предметов, которые вы сможете объединить вместе, чтобы создать волшебный клинок, убивающий дракона. Удобно, что все части этого оружия были разбросаны по логову дракона. Вы просто должны собрать их.

Суть в том, что каждая часть оружия была заминирована. Каждый раз, когда кто-то собирается, расположение дорожек меняется. Ранее безопасные пути могли теперь привести к верной смерти, и наоборот.

команды

Есть только 5 действительных команд.

• < - Сделай шаг влево

• > - Сделай шаг вправо

• ^ - Сделай шаг вверх

• v - Сделай шаг вниз

• c- Соберите все предметы, которые случайно оказались в вашем текущем положении. Если там были предметы, расположение логова меняется. С позициями, пронумерованными в строках, как указано выше, измените свою позицию по модулю 10. В интерпретаторе жестко запрограммировано 10 макетов, и макет изменится на соответствующий. Например, если вы находитесь в положении 13, то макет меняется наlayouts[3]

Макеты в том виде, в котором они отображаются в интерпретаторе, были закодированы в целые числа следующим образом:

• Пустой макет кодируется в ноль.

• Для каждого ребра в макете, пусть xбудет меньше из двух позиций, которые он соединяет.

  • Если шаг горизонтальный, добавьте 2^(2*x)кодировку (это power-of, а не XOR)

  • Если шаг вертикальный, добавьте 2^(2*x + 1)кодировку.

Поток выполнения

Интерпретатор запускается с именем исходного файла в качестве аргумента командной строки.

Когда интерпретатор запущен, он попросит пользователя предоставить квест. Этот вход должен быть в форме, описанной в вопросе, и определяет места в логове компонентов оружия. В частности, каждое входное целое число берется по модулю 100 и помещается в соответствующее место в логове.

Каждая исходная программа состоит из нескольких строк, каждая строка состоит из некоторой последовательности из 5 вышеуказанных допустимых символов. Эти линии представляют ваших миньонов. Вы, воин, следите за последовательностью действий, которые, как известно, безопасны. Изначально вы ничего не знаете о логове, поэтому эта последовательность пуста. Взяв каждого миньона по очереди, выполняется следующее, начиная с позиции 0:

• Миньону поручено выполнить все известные для безопасности действия, за которыми следуют действия в его собственной строке кода.

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

  • Если вместо этого миньон выживает, то вы все равно его испарите - в конце концов, это всего лишь миньон. Как и раньше, это запускает сброс логова в его начальное состояние, но на этот раз вы добавляете действия из строки кода миньона в последовательность действий, о которых известно, что вы должны быть в безопасности.

Как только все миньоны истощены, вы, воин, выполняете все действия, которые, как известно, безопасны, снова начиная с позиции 0. Возможны два результата:

• Вы собираете все части оружия - в этом случае вы успешно убиваете дракона, и выдается захватывающее сообщение о победе. Это победное сообщение будет содержать, среди других символов, nте, где nнаходится третье наибольшее число, указанное в качестве ввода.

• Вам не удалось собрать некоторые части оружия - в этом случае дракон живет, и вы потерпели неудачу в своем квесте.

Код интерпретатора (Python 2)

import collections
import copy
import sys

size = 10
layouts = [108705550239329248440770931020110627243913363144548922111951,108386637020100924277694952798729434993885646706222210602969,133885860318189115027934177821170081234850573770998325845482,102397795295522647918061101991513921833376565032742993744791,131948019244359669407266662537098175265242405785636894694611,127512068876349726396523358265982765442984953916545984706958,106817519055019354200334114020150263381328246524221867629943,33472343358375525802921815863230485208221126168622186265959,133909781123963725874096031069972704024813281938330035579187,132244654022332695610020359820518831299843076834682749020986]

class Interpreter(object):

    def __init__(self, source_file):
        self.source_filename = source_file
        self.layout = layouts[0]
        self.position = 0
        self.ingredients = []
        self.quest_items = {}
        self.attempts = collections.deque()

        self.safe_position = 0
        self.safe_ingredients = []
        self.safe_quest_items = {}
        self.safe_layout = layouts[0]

    def get_input(self):
        s = raw_input("Which quest would you like to embark on today?")
        ind = s.find('00')
        s = s[:ind]
        items = map(len, s.split('0'))
        for item in items:
            if item not in self.safe_quest_items:
                self.safe_quest_items[item] = 1
            else:
                self.safe_quest_items[item] += 1

    def parse_attempts(self):
        with open(self.source_filename, 'r') as source:
            for line in source:
                self.attempts.append(line.strip())

    def enc(self, x, y):
        x, y = min(x, y), max(x, y)
        if x < 0:
            return 0
        if y == x + 1:
            return 1 << (2*x)
        elif y == x + size:
            return 1 << (2*x + 1)
        else:
            return 0

    def exec_command(self, char):
        if char == '<':
            if self.enc(self.position, self.position-1) & self.layout:
                self.position -= 1
            else:
                return False
        elif char == '>':
            if self.enc(self.position, self.position+1) & self.layout:
                self.position += 1
            else:
                return False
        elif char == '^':
            if self.enc(self.position, self.position-size) & self.layout:
                self.position -= size
            else:
                return False
        elif char == 'v':
            if self.enc(self.position, self.position+size) & self.layout:
                self.position += size
            else:
                return False
        elif char == 'c':
            for item in xrange(self.position, 10**6, size*size):
                if item in self.quest_items:
                    self.ingredients += ([item] * self.quest_items.pop(item))
                    self.ingredients.sort()
                    self.layout = layouts[self.position % 10]
        else:
            raise ValueError

        return True

    def run_minion(self):
        minion = self.attempts.popleft()
        self.position = self.safe_position
        self.ingredients = copy.copy(self.safe_ingredients)
        self.quest_items = copy.copy(self.safe_quest_items)
        self.layout = self.safe_layout
        dead = False

        for cmd in minion:
            if not self.exec_command(cmd):
                dead = True

        if not dead:
            self.safe_position = self.position
            self.safe_ingredients = copy.copy(self.ingredients)
            self.safe_quest_items = copy.copy(self.quest_items)
            self.safe_layout = self.layout

    def process_minions(self):
        while self.attempts:
            self.run_minion()

    def final_run(self):
        if len(self.safe_quest_items) == 0:
            print "You killed the dragon" + "!!1" * self.safe_ingredients[-3]
        else:
            print "The dragon lives on. Better luck next time..."

    def interpret(self):
        self.get_input()
        self.parse_attempts()
        self.process_minions()
        self.final_run()

if __name__ == "__main__":
    if len(sys.argv) != 2:
        print "Wrong number of arguments"
    else:
        test = Interpreter(sys.argv[1])
        test.interpret()

Удачи, доблестный воин.

Мое решение и объяснение

Вот скрипт Python, который генерирует исходный код для решения проблемы. Для интереса, окончательный исходный код Мартина примерно в 5 раз меньше, чем код, созданный моим сценарием. С другой стороны, мой скрипт для генерации кода примерно в 15 раз меньше, чем программа Мартина Мартина ...

size = 10
layouts = [108705550239329248440770931020110627243913363144548922111951,108386637020100924277694952798729434993885646706222210602969,133885860318189115027934177821170081234850573770998325845482,102397795295522647918061101991513921833376565032742993744791,131948019244359669407266662537098175265242405785636894694611,127512068876349726396523358265982765442984953916545984706958,106817519055019354200334114020150263381328246524221867629943,33472343358375525802921815863230485208221126168622186265959,133909781123963725874096031069972704024813281938330035579187,132244654022332695610020359820518831299843076834682749020986]

def enc(edge):
    x,y = min(edge), max(edge)
    if x < 0:
        return 0
    if y == x + 1:
        return 1 << (2*x)
    elif y == x + size:
        return 1 << (2*x + 1)

def path(x, y, tree):
    stack = [(x,'')]
    while stack[-1][0] != y:
        vertex, path = stack.pop()
        if (enc((vertex, vertex+1))&tree) and ((not path) or path[-1] != '<'):
            stack.append((vertex+1, path+'>'))
        if (enc((vertex, vertex-1))&tree) and ((not path) or path[-1] != '>'):
            stack.append((vertex-1, path+'<'))
        if (enc((vertex, vertex+size))&tree) and ((not path) or path[-1] != '^'):
            stack.append((vertex+size, path+'v'))
        if (enc((vertex, vertex-size))&tree) and ((not path) or path[-1] != 'v'):
            stack.append((vertex-size, path+'^'))
    return stack[-1][1]

def reverse(path):
    rev = ''
    for i in xrange(len(path)-1, -1 ,-1):
        if path[i] == '<':
            rev += '>'
        if path[i] == '>':
            rev += '<'
        if path[i] == 'v':
            rev += '^'
        if path[i] == '^':
            rev += 'v'
    return rev

def assert_at(x, tree):
    path_ul = path(x, 0, tree)
    path_dr = path(x, size*size - 1, tree)
    return path_ul + reverse(path_ul) + path_dr + reverse(path_dr)

def safe_path(x, y, tree):
    return assert_at(x, tree) + path(x, y, tree)

with open('source.txt', 'w') as f:
    for x in xrange(size*size - 1):
        for tree in layouts:
            f.write(safe_path(x, x+1, tree) + 'c\n')

Базовая структура

Это генерирует 990 строк исходного кода, которые объединяются в группы по 10. Первые 10 строк содержат инструкции, которые пытаются переместить миньона из позиции 0в позицию 1, а затем собрать элемент - по одному набору для каждого возможного макета. Следующие 10 строк содержат инструкции, которые пытаются переместить миньона из позиции 1в позицию 2, а затем собрать предмет. И так далее ... Эти пути рассчитываются с помощью pathфункции в скрипте - он просто выполняет поиск в глубину.

Если мы сможем обеспечить, чтобы в каждой группе из 10 преуспел ровно один миньон, то мы решим проблему.

Вопрос с подходом

Не всегда может быть так, что точно один миньон из группы из 10 преуспевает - например, миньон, предназначенный для перехода из позиции 0в позицию, 1может случайно преуспеть в перемещении из позиции 1в позицию 2(из-за сходства в раскладках), и что просчет будет распространяться через, потенциально вызывая сбой.

Как это исправить

Исправление, которое я использовал, было следующим:

Для каждого миньона, который пытается добраться из положения nв n+1, сначала заставьте его ходить из положения nв положение 0(верхний левый угол) и обратно, затем из положения nв положение 99(нижний правый угол) и обратно. Эти инструкции можно безопасно выполнять только с позиции n- любая другая стартовая позиция и миньон отойдет от края.

Эти дополнительные инструкции, таким образом, предотвращают случайное попадание миньонов туда, куда они не предназначены, и это гарантирует, что ровно один миньон из каждой группы из 10 успешен. Обратите внимание, что это не обязательно тот миньон, которого вы ожидаете - возможно, миньон, который полагает, что он находится в макете 0, преуспевает, даже когда мы действительно в макете 7 - но в любом случае, тот факт, что мы имеем Теперь измененная позиция означает, что все остальные миньоны в группе обязательно умрут. Эти дополнительные шаги вычисляются assert_atфункцией, и safe_pathфункция возвращает путь, который является объединением этих дополнительных шагов с обычным путем.

Firetype, взломанный Мартином Бюттнером

Действительно странное сочетание BF и CJam. И кто знает, что еще! Уверен, это будет легко, но все равно было весело. К вашему сведению, это название относится к Огню Вермиллиона из Final Fantasy Type-0 .

ПРИМЕЧАНИЕ : Пожалуйста, простите меня за любые неясности в этом описании. Я не лучший писатель ...: O

Мартин взломал это очень быстро! Это была моя оригинальная программа для решения проблемы:

_
,
^
~
+
|
|
-
%
+
_
+
=











`
~
+
|
%

_
=

\
@
-
-
!
<
>
>
>

_
+
.
<
-
`
~
~
+
|
|
-
#
%

Синтаксис

Скрипт Firetype - это в основном список строк. Первый символ каждой строки - команда для запуска. Пустые строки - это в основном NOP.

Семантика

У вас есть массив целых чисел и указатель (например, BF). Вы можете перемещать влево и вправо или «вставлять» элементы в массив.

Нажимать

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

команды

_

Вставьте ноль в массив.

+

Увеличить элемент на текущий указатель.

-

Уменьшить элемент в текущем указателе.

*

Удвойте элемент по текущему указателю.

/

Половина элемента на текущий указатель.

%

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

=

Возьмите элемент по текущему указателю и перейдите к этой строке + 1. Например, если текущий элемент есть 0, он перейдет к строке 1. Это также перемещает указатель влево.

,

Считайте символ из стандартного ввода и введите его значение ASCII.

^

Возьмите элемент в текущем указателе, интерпретируйте его как значение ASCII для символа и преобразуйте его в целое число. Например, если текущее значение 49 (значение ASCII 1), элемент в текущем указателе будет установлен в целое число 1.

.

Запишите текущий номер на экран.

!

Возьмите элемент с текущего указателя и повторите следующую строку столько раз. Также перемещает указатель влево.

<

Переместите указатель влево. Если вы уже в начале, выдается ошибка.

>

Переместите указатель вправо. Если вы уже в конце, выдается ошибка.

~

Если текущий элемент ненулевой, замените его на 0; в противном случае замените его на 1.

|

Квадрат текущего элемента.

@

Установите текущий элемент в длину массива.

`

Дублируйте текущий элемент.

\

Сортировка элементов в и перед указателем.

#

Отрицание текущего элемента.

Переводчик

Также доступно на Github .

#!/usr/bin/env python

# The FireType interpreter.
# Runs under Python 2 and 3.
import sys

class Array(object):
    def __init__(self):
        self.array = []
        self.ptr = 0

    def push_zero(self):
        if self.ptr == len(self.array):
            self.array.append(0)
        else:
            self.array[self.ptr] = 0
        self.ptr += 1

    def left(self):
        self.ptr -= 1
        assert self.ptr >= 0 and self.array, 'pointer underflow (at %d)' % i

    def right(self):
        self.ptr += 1
        assert self.ptr <= len(self.array), 'pointer overflow (at %d)' % i

    def sort(self):
        lhs = self.array[:self.ptr-1]
        rhs = self.array[self.ptr-1:]
        lhs.sort()
        lhs.reverse()
        self.array = lhs + rhs

    def __call__(self, *args):
        args = list(args)
        assert self.array, 'out-of-bounds (at %d)' % i
        if not args:
            return self.array[self.ptr-1]
        self.array[self.ptr-1] = args.pop()
        assert not args

    def __len__(self):
        return len(self.array)

    def __str__(self):
        return 'Array(array=%s, ptr=%s)' % (self.array, self.ptr)

    def __repr__(self):
        return 'Array(array=%r, ptr=%r)' % (self.array, self.ptr)

def execute(lines):
    global i, array
    i = 0
    array = Array()
    rep = 0
    while i < len(lines):
        line = lines[i]
        if not line:
            i += 1
            continue
        line = line[0]
        if line == '_':
            array.push_zero()
        elif line == '+':
            array(array() + 1)
        elif line == '-':
            array(array() - 1)
        elif line == '*':
            array(array() * 2)
        elif line == '/':
            array(int(array() / 2))
        elif line == '%':
            i += array()
            array.left()
        elif line == '=':
            i = array()-1
            array.left()
        elif line == ',':
            array.push_zero()
            array(ord(sys.stdin.read(1)))
        elif line == '.':
            sys.stdout.write(str(array()))
        elif line == '!':
            rep = array()
            array.left()
            i += 1
        elif line == '<':
            array.left()
        elif line == '>':
            array.right()
        elif line == '^':
            array(int(chr(array())))
        elif line == '~':
            array(int(not array()))
        elif line == '|':
            array(array() ** 2)
        elif line == '@':
            array(len(array))
        elif line == '`':
            top = array()
            array.push_zero()
            array(top)
        elif line == '\\':
            array.sort()
        elif line == '#':
            array(-array())

        if rep:
            rep -= 1
        else:
            i += 1

def main(args):
    try:
        _, path = args
    except ValueError:
        sys.exit('usage: %s <file to run, - for stdin>')

    if path == '-':
        data = sys.stdin.read()
    else:
        with open(path) as f:
            data = f.read()

    try:
        execute(data.split('\n'))
    except:
        print('ERROR!')
        print('Array was %r' % array)
        print('Re-raising error...')
        raise

if __name__ == '__main__':
    main(sys.argv)

Точность !! (безопасный)

Это баак ...

... и, надеюсь, определенно более надежным.

Я уже прочитал Акк! спекуляция Как Акк !! разные?

В акк !! переменные цикла выходят из области видимости при выходе из цикла. Вы можете использовать их только внутри цикла. Снаружи вы получите ошибку «имя не определено». За исключением этого изменения, языки идентичны.

Заявления

Команды анализируются построчно. Существует три типа команд:

1. Count <var> while <cond>

Считается <var>от 0 до тех пор, пока он не <cond>равен нулю, что эквивалентно C ++ for(int <var>=0; <cond>; <var>++). Счетчик цикла может быть любой строчной буквой. Условием может быть любое выражение, необязательно включающее переменную цикла. Цикл останавливается, когда значение условия становится равным 0.

Для петель требуются фигурные скобки в стиле K & R (в частности, вариант Страуструпа ):

Count i while i-5 {
 ...
}

Как упоминалось выше, переменные цикла доступны только внутри их циклов ; попытка ссылаться на них впоследствии приводит к ошибке.

2. Write <charcode>

Выводит один символ с заданным значением ASCII / Unicode в стандартный вывод. Код может быть любым выражением.

3. выражение

Любое выражение, стоящее само по себе, оценивается и присваивается аккумулятору (который доступен как _). Таким образом, например, 3является оператором, который устанавливает аккумулятор в 3; _ + 1увеличивает аккумулятор; и _ * Nчитает символ и умножает аккумулятор на его код.

Примечание: аккумулятор является единственной переменной, которая может быть напрямую назначена; переменные цикла и Nмогут быть использованы в расчетах, но не изменены.

Аккумулятор изначально равен 0.

Выражения

Выражение может включать в себя целочисленные литералы, переменные цикла ( a-z) _для аккумулятора и специальное значение N, которое читает символ и вычисляет его кодовый символ каждый раз, когда он используется. Примечание: это означает, что вы можете получить только один выстрел, чтобы прочитать каждого персонажа; в следующий раз вы Nбудете читать следующий.

Операторы:

• +, дополнение
• -вычитание; одинарное отрицание
• *, умножение
• /целочисленное деление
• %по модулю
• ^возведение в степень

Круглые скобки могут использоваться для обеспечения приоритета операций. Любой другой символ в выражении является синтаксической ошибкой.

Пробелы и комментарии

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

# начинается однострочный комментарий.

Ввод, вывод

Точность !! ожидает одну строку символов в качестве ввода. Каждый входной символ может быть извлечен в последовательности, и его кодовый символ обработан, используя N. Попытка прочитать последний символ строки приводит к ошибке. Символ можно вывести, передав его код в Writeоператор.

переводчик

Переводчик (написанный на Python 3) переводит Acc !! код в Python и execс ним.

import re, sys

def main():
    if len(sys.argv) != 2:
        print("Please supply a filename on the command line.", file=sys.stderr)
        return
    codeFile = sys.argv[1]
    with open(codeFile) as f:
        code = f.readlines()
    code = translate(code)
    exec(code, {"inputStream": (ord(char) for char in input())})

def translate(accCode):
    indent = 0
    loopVars = []
    pyCode = ["_ = 0"]
    for lineNum, line in enumerate(accCode):
        if "#" in line:
            # Strip comments
            line = line[:line.index("#")]
        line = line.strip()
        if not line:
            continue
        lineNum += 1
        if line == "}":
            if indent:
                loopVar = loopVars.pop()
                pyCode.append(" "*indent + loopVar + " += 1")
                indent -= 1
                pyCode.append(" "*indent + "del " + loopVar)
            else:
                raise SyntaxError("Line %d: unmatched }" % lineNum)
        else:
            m = re.fullmatch(r"Count ([a-z]) while (.+) \{", line)
            if m:
                expression = validateExpression(m.group(2))
                if expression:
                    loopVar = m.group(1)
                    pyCode.append(" "*indent + loopVar + " = 0")
                    pyCode.append(" "*indent + "while " + expression + ":")
                    indent += 1
                    loopVars.append(loopVar)
                else:
                    raise SyntaxError("Line %d: invalid expression " % lineNum
                                      + m.group(2))
            else:
                m = re.fullmatch(r"Write (.+)", line)
                if m:
                    expression = validateExpression(m.group(1))
                    if expression:
                        pyCode.append(" "*indent
                                      + "print(chr(%s), end='')" % expression)
                    else:
                        raise SyntaxError("Line %d: invalid expression "
                                          % lineNum
                                          + m.group(1))
                else:
                    expression = validateExpression(line)
                    if expression:
                        pyCode.append(" "*indent + "_ = " + expression)
                    else:
                        raise SyntaxError("Line %d: invalid statement "
                                          % lineNum
                                          + line)
    return "\n".join(pyCode)

def validateExpression(expr):
    "Translates expr to Python expression or returns None if invalid."
    expr = expr.strip()
    if re.search(r"[^ 0-9a-z_N()*/%^+-]", expr):
        # Expression contains invalid characters
        return None
    elif re.search(r"[a-zN_]\w+", expr):
        # Expression contains multiple letters or underscores in a row
        return None
    else:
        # Not going to check validity of all identifiers or nesting of parens--
        # let the Python code throw an error if problems arise there
        # Replace short operators with their Python versions
        expr = expr.replace("^", "**")
        expr = expr.replace("/", "//")
        # Replace N with a call to get the next input character
        expr = expr.replace("N", "inputStream.send(None)")
        return expr

if __name__ == "__main__":
    main()

Решение

Крушение оригинального Acc! переменные цикла, которые продолжали быть доступными вне их циклов. Это позволило сохранить копии аккумулятора, что сделало решение слишком простым.

Здесь, без этого контура отверстия (извините), у нас есть только аккумулятор для хранения вещей. Однако для решения задачи нам нужно хранить четыре произвольно больших значения. ¹ Решение: чередовать их биты и сохранять полученный номер комбинации в аккумуляторе. Например, значение аккумулятора 6437 будет хранить следующие данные (используя бит младшего разряда в качестве однобитового флага):

1100100100101  Binary representation of accumulator
321032103210F  Key

The flag is 1 and the four numbers are
Number 0: 010 = 2
Number 1: 001 = 1
Number 2: 100 = 4
Number 3: 110 = 6

Мы можем получить доступ к любому биту любого числа, разделив аккумулятор на соответствующую мощность 2, mod 2. Это также позволяет устанавливать или переключать отдельные биты.

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

Самая сложная часть (и причина, по которой у меня были глобальные переменные цикла в первом воплощении) - это сравнение двух чисел, чтобы узнать, нужно ли их поменять местами. Чтобы сравнить два бита, мы можем превратить таблицу истинности в математическое выражение; мой прорыв для Acc! находил алгоритм сравнения, который переходил от младших к старшим битам, так как без глобальных переменных невозможно перебрать биты числа слева направо. Бит младшего разряда накопителя хранит флаг, который сигнализирует, следует ли поменять местами два числа, которые в настоящее время рассматриваются.

Я подозреваю, что Acc !! завершена по Тьюрингу, но я не уверен, что хочу доказать это.

Вот мое решение с комментариями:

# Read and process numbers until the double 0

Count y while N-48 {
    # Read unary number and store it (as binary) in number 0
    # The above loop header consumed the first 1, so we need to add 1 to number 0

    _ + 2

    # Increment number 0 for each 1 in input until next 0

    Count z while N-48 {
        # In this context, the flag indicates a need to carry; set it to 1
        _ - _%2 + 1

        # While carry flag is set, increment the next bit in line
        Count i while _%2 {
            # Set carry flag to 1 if i'th bit is 1, 0 if it's 0
            # Set i'th bit to 1 if it was 0, 0 if it was 1
            _ - _%2 + _/2^(i*4+1)%2 + (-1)^(_/2^(i*4+1)%2)*2^(i*4+1)
        }
    }

    # Bubble number 0 upwards

    Count n while n-3 {
        # The flag (rightmost bit of accumulator) needs to become 1 if we want to swap
        # numbers (n) and (n+1) and 0 if we don't
        # Iterate over bit-groups of accumulator, RTL
        Count i while _/2^(i*4+1) {
            # Adjust the flag as follows:
            # _/2^(i*4+n+1)%4 is the current bit of number (n+1) followed by the current
            # bit of number (n), a value between 0 and 3
            # - If this quantity is 1 (01), number (n) is bigger so far; set flag to 1
            # - If this quantity is 2 (10), number (n+1) is bigger so far; set flag to 0
            # - If this quantity is 0 (00) or 3 (11), the two bits are the same; keep
            #   current value of flag
            _ + (_/2^(i*4+n+1)%4%3 + 1)/2*(_/2^(i*4+n+1)%4%3%2 - _%2)
        }

        # Now swap the two if the flag is 1
        Count i while (_%2)*(_/2^(i*4+1)) {
            # _/2^(i*4+n+1)%2 is the current bit of number (n)
            # _/2^(i*4+n+2)%2 is the current bit of number (n+1)
            _ - (_/2^(i*4+n+1)%2)*2^(i*4+n+1) - (_/2^(i*4+n+2)%2)*2^(i*4+n+2) + (_/2^(i*4+n+2)%2)*2^(i*4+n+1) + (_/2^(i*4+n+1)%2)*2^(i*4+n+2)
        }
    }

    # Discard number 0, setting it to all zeros for the next iteration
    Count i while _/2^(i*4+1) {
        _ - _/2^(i*4+1)%2*2^(i*4+1)
    }
}

# Once the loop is over, all input has been read and the result is in number 1
# Divide by 2 to get rid of flag bit

_ / 2

# Zero out numbers 2 and 3

Count i while _/2^(i*4) {
    _ - _/2^(i*4+2)%2*2^(i*4+2)
}

Count i while _/2^(i*4) {
    _ - _/2^(i*4+3)%2*2^(i*4+3)
}

# Move bits of number 1 down to their final locations

Count i while _/2^i {
    _ - _/2^(i*4+1)%2*2^(i*4+1) + _/2^(i*4+1)%2*2^i
}

# _ now contains the correct answer in decimal; to output in unary:

Count z while z-_ {
    Write 49
}

_{¹ Согласно спецификации вопроса, поддерживаются только значения до 1 миллиона. Я рад, что никто не воспользовался этим для более простого решения - хотя я не совсем уверен, как вы будете делать сравнения.}

Picofuck (безопасно)

Picofuck похож на Smallfuck . Он работает на бинарной ленте, которая не связана справа, связана слева. У него есть следующие команды:

• > переместить указатель вправо

• <переместите указатель влево. Если указатель падает с ленты, программа завершается.

• * перевернуть бит по указателю

• (если бит в указателе есть 0, перейти к следующему)

• )ничего не делать - круглые скобки в Picofuck - это ifблоки, а не whileциклы.

• .написать в stdout бит по указателю как ascii 0или 1.

• ,читать из стандартного ввода до тех пор, пока мы не встретим 0или или 1, и сохранить это в бит по указателю.

Код Picofuck переносится - после достижения конца программы она продолжается с начала.

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

переводчик

Написано на Python 2.7

использование: python picofuck.py <source_file>

import sys

def interpret(code):
    # Ensure parentheses match and are not nested.
    in_if_block = False
    for c in code:
        if c == '(':
            if in_if_block:
                print "NESTED IFS DETECTED!!!!!"
                return
            in_if_block = True
        elif c == ')':
            if not in_if_block:
                print "Unmatched parenthesis"
                return
            in_if_block = False
    if in_if_block:
        print "Unmatched parenthesis"
        return


    code_ptr = 0
    array = [0]
    ptr = 0

    while 1:
        command = code[code_ptr]
        if command == '<':
            if ptr == 0:
                break
            ptr -= 1
        elif command == '>':
            ptr += 1
            if ptr == len(array):
                array.append(0)
        elif command == '*':
            array[ptr] = 1-array[ptr]
        elif command == '(':
            if array[ptr] == 0:
                while code[code_ptr] != ')':
                    code_ptr = (code_ptr + 1) % len(code)
        elif command == ',':
            while True:
                c = sys.stdin.read(1)
                if c in ['0','1']:
                    array[ptr] = int(c)
                    break
        elif command == '.':
            sys.stdout.write(str(array[ptr]))
        code_ptr = (code_ptr+1)%len(code)

if __name__ == "__main__":
    with open(sys.argv[1]) as source_file:
        code = source_file.read()
    interpret(code)

Решение

Следующая программа на Python 2.7 выводит мое решение, которое можно найти здесь

Я могу отредактировать этот пост позже с более подробным объяснением того, как это работает, но оказывается, что Picofuck завершен по Тьюрингу.

states = {
    "SETUP":(
        "*>",
        "GET_NUMBER",
        "GET_NUMBER"
    ),

    "GET_NUMBER":(
        ",",
        "CHANGE_A",
        "PREPARE_PRINT_C"
    ),

    "GET_DIGIT":(
        ",",
        "CHANGE_A",
        "GOT_DIGIT"
    ),

    "GOT_DIGIT":(
        ">>>>",
        "GO_BACK",
        "GO_BACK"
    ),

    "CHANGE_A":(
        ">",
        "CHANGE_B",
        "SET_A"
    ),

    "SET_A":(
        "*>>>>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "CHANGE_B":(
        ">",
        "CHANGE_C",
        "SET_B"
    ),

    "SET_B":(
        "*>>>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "CHANGE_C":(
        ">",
        "CONTINUE_GET_NUMBER",
        "SET_C"
    ),

    "SET_C":(
        "*>>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "CONTINUE_GET_NUMBER":(
        ">>",
        "GET_DIGIT",
        "GET_DIGIT"
    ),

    "GO_BACK":(
        "<<<<<",
        "FINISH_GO_BACK",
        "GO_BACK"
    ),

    "FINISH_GO_BACK":(
        ">",
        "GET_NUMBER",
        "GET_NUMBER"
    ),

    "PREPARE_PRINT_C":(
        ">>>",
        "PRINT_C",
        "PRINT_C"
    ),

    "PRINT_C":(
        ".>>>>>",
        "PRINT_C",
        "TERMINATE"
    ),

    "TERMINATE":(
        "<",
        "TERMINATE",
        "TERMINATE"
    ),
}

def states_to_nanofuck(states,start_state):
    state_list = list(states)
    state_list.remove(start_state)
    state_list.insert(0,start_state)

    states_by_index = []
    for i,state in enumerate(state_list):
        commands, next1, next0 = states[state]
        states_by_index.append((commands,state_list.index(next1),state_list.index(next0)))


    # setup first state
    fragments = ['*(*>>>>>*<<<<<)>>>>>']

    # reset states that don't match
    for index in range(len(states_by_index)):
        for bool in range(2):
            # at state_0_0
            state_dist = index*3 + bool
            # move state to curstate
            fragments.append('>'*state_dist)
            fragments.append('(*')
            fragments.append(  '<'*state_dist)
            fragments.append(  '<<*>>')
            fragments.append(  '>'*state_dist)
            fragments.append(')')
            fragments.append('<'*state_dist)

            # go to arr
            fragments.append('<<<')

            if bool == 0:
                #flip arr
                fragments.append('*')

            # compute match = arr & curstate
            fragments.append('(>)(>*<)<(<)>')

            if bool == 0:
                #flip arr
                fragments.append('*')

            # reset curstate
            fragments.append('>(*)')

            # move match to matchstate, go back to state_0_0
            matchstate_dist = index*3 + 2
            fragments.append('>(*>')
            fragments.append(  '>'*matchstate_dist)
            fragments.append(  '*')
            fragments.append(  '<'*matchstate_dist)
            fragments.append('<)>')

    #fragments.append('|')

    # do the commands of the matching state
    for index,state in enumerate(states_by_index):
        for bool in range(2):
            # at state_0_0
            matchstate_dist = index*3 + 2
            # move matchstate to curstate
            fragments.append('>'*matchstate_dist)
            fragments.append('(*')
            fragments.append(  '<'*matchstate_dist)
            fragments.append(  '<<*>>')
            fragments.append(  '>'*matchstate_dist)
            fragments.append(')')
            fragments.append('<'*matchstate_dist)

            # if curstate, reset curstate
            fragments.append('<<(*')

            # go to arr
            fragments.append('<')

            # do commands
            commands,next1,next0 = state
            for c in commands:
                if c in '<>':
                    fragments.append(c*(3*len(states_by_index)+5))
                else:
                    fragments.append(c)

            # go to state_0_0
            fragments.append('>>>')

            # set next states
            for dist in [next0*3, next1*3+1]:
                fragments.append('>'*dist)
                fragments.append('*')
                fragments.append('<'*dist)

            # go to curstate
            fragments.append('<<')

            # end if
            fragments.append(')')

            # go to state_0_0
            fragments.append('>>')


    # go back to setup and set it
    fragments.append('<<<<<*')

    code = ''.join(fragments)

    return code



print states_to_nanofuck(states, "SETUP")

PQRS - безопасно! / Решение предоставлено

основы

Все подразумеваемые инструкции имеют четыре операнда адреса памяти:

P₀ Q₀ R₀ S₀
P₁ Q₁ R₁ S₁
...
Pᵥ₋₁ Qᵥ₋₁ Rᵥ₋₁ Sᵥ₋₁

Где vразмер памяти в квартетах.

Pᵢ, Qᵢ, Rᵢ, SᵢПодписываются целые числа в родном размере вашей машины (например , 16, 32 или 64 бит) , которые мы будем называть слова.

Для каждого квартета iподразумеваемая операция с []обозначением косвенности:

if (([Pᵢ] ← [Qᵢ] − [Rᵢ]) ≤ 0) go to Sᵢ else go to Pᵢ₊₁

Обратите внимание, что Subleq является подмножеством PQRS .

Subleq был доказан завершенным, поэтому PQRS также должен быть полным!

Структура программы

PQRS определяет начальный заголовок следующим образом:

H₀ H₁ H₂ H₃ H₄ H₅ H₆ H₇

H₀ H₁ H₂ H₃всегда первая инструкция P₀ Q₀ R₀ S₀. H₀в H₃должны быть определены во время загрузки.

PQRS имеет элементарный ввод / вывод, но достаточный для вызова.

H₄ H₅: при запуске программы она читает максимум H₅символов ASCII из стандартного ввода и сохраняет как слова при индексировании и H₄далее. H₄и H₅должны быть определены во время загрузки. После прочтения H₅будет установлено количество прочитанных символов (и сохраненных слов).

H₆ H₇: при завершении программы, начиная с индекса H₆, она выводит все байты, содержащие H₇слова, на стандартный вывод в виде символов ASCII. H₆и H₇должны быть определены до окончания программы. Нулевые байты '\0'в выводе будут пропущены.

прекращение

Прекращение достигается путем установления Sᵢграниц i < 0или i ≥ v.

Ухищрения

Квартеты Pᵢ Qᵢ Rᵢ Sᵢне обязательно должны быть выровненными или последовательными, ветвление разрешено с интервалами в квартал.

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

Код может быть самоизменяющимся!

переводчик

Переводчик написан на C:

#include <stdlib.h>
#include <stdio.h>

// The "architecture"
enum {P, Q, R, S, START_OF_INPUT, LENGTH_OF_INPUT, START_OF_OUTPUT, LENGTH_OF_OUTPUT};
const int NEXT = S + 1;

// Recommend optimized!
#define OPTIMIZED

#ifdef PER_SPECS
// This may not work on all OSes and architectures - just too much memory needed!
const int K = 1002000200;
#else // OPTIMIZED
// This provides enough space to run the test cases with challenge-optimized.pqrs
const int K = 5200;
#endif

int main(int argc, char *argv[])
{
    int i, *M;
    char *p;
    FILE *program;

    // Allocate enough memory
    M = calloc(K, sizeof(int));

    // Load the program
    for (i = 0, program = fopen(argv[1], "r"); i < K && !feof(program); i++)
        if (!fscanf(program, "%d", M + i))
            break;
    fclose(program);

    // Read in the input
    for (i = 0; i < M[LENGTH_OF_INPUT] && !feof(stdin); i++)
    {
        int c = fgetc(stdin);
        if (c != EOF)
            M[M[START_OF_INPUT] + i] = c;
        else
            break;
    }
    M[LENGTH_OF_INPUT] = i;

    // Execute until terminated
    for (i = 0; i >= 0 && i < K; )
        i = (M[M[P + i]] = M[M[Q + i]] - M[M[R + i]]) <= 0? M[S + i]: i + NEXT;

    // Write the output
    for (i = 0, p = (char *)(M + M[START_OF_OUTPUT]); i < M[LENGTH_OF_OUTPUT] * sizeof(int); i++)
        // Ignore '\0'
        if (p[i])
            fputc(p[i], stdout);

    // Done
    free(M);

    return 0;
}

Чтобы использовать, сохраните вышеупомянутое как pqrs.c, затем скомпилируйте:

gcc -o pqrs pqrs.c

Пример программы

Эхосигнал вводит до 40 символов, перед которым стоит 'PQRS-'.

8 8 8 -1 14 40 9 45 0 80 81 82 83 45

Для запуска сохраните вышеуказанное как echo.pqrs, затем:

$ ./prqs echo.pqrs
greetings[enter]
[ctrl-D]
PQRS-greetings

Запуск тестовых случаев:

$ ./pqrs challenge-optimized.pqrs < test-1.txt
1

$ ./pqrs challenge-optimized.pqrs < test-2.txt
11111111111111111

$ ./pqrs challenge-optimized.pqrs < test-3.txt
[lots of ones!]

$ ./pqrs challenge-optimized.pqrs < test-3.txt | wc
0       1     773

Все тесты выполняются очень быстро, например, <500 мс.

Соревнование

PQRS можно считать стабильным, поэтому задача начинается 2015-10-31 13:00 и заканчивается 2015-11-08 13:00, время в UTC.

Удачи!

Решение

Этот язык очень похож на тот, который используется в "Baby" - первой в мире электронной цифровой машине с хранимыми программами. На этой странице находится программа, которая находит самый высокий коэффициент целого числа менее чем в 32 словах (CRT!) Памяти!

Я обнаружил, что написание решения для соответствия спецификациям несовместимо с операционной системой и машиной, которую я использовал (производная Linux Ubuntu на чуть более старом оборудовании). Просто требовалось больше памяти, чем доступно, и дамп памяти. В ОС с расширенным управлением виртуальной памятью или машинах с объемом памяти не менее 8 ГБ вы, вероятно, можете запустить решение в соответствии со спецификациями. Я предоставил оба решения.

Очень трудно напрямую кодировать в PQRS , сродни написанию машинного языка, возможно, даже микрокода. Вместо этого легче написать на языке ассемблера, чем «скомпилировать» его. Ниже приведен аннотированный язык ассемблера для решения, оптимизированного для выполнения тестовых случаев:

; ANNOTATED PQRS ASSEMBLER CODE
; MINIMAL SIZED BUFFERS TO RUN THE TEST CASES

;OFFSET   LABEL       P-OP        Q-OP        R-OP        S-OP
0                     TEMP        ZERO        ZERO        L1

; INPUT AND OUTPUT LOCATIONS AND SIZES
4                     INPUT       4000        
6         L0:         OUTPUT      1000        

; GET CURRENT INPUT
8         L1:         TEMP        INPUT       ASCII_ZERO  L2
12                    SUM         SUM         INC         IGNORE
16                    L1+1        L1+1        INC         IGNORE
20                    TEMP        ZERO        ZERO        L1

; CHECK IF END OF NUMBERS
24        L2:         NUMBERS     SUM         ZERO        L3

; ADVANCE TO NEXT NUMBER
28                    L2          L2          INC         IGNORE

; ADVANCE COUNT
32                    COUNT       COUNT       INC         IGNORE
36                    L1+1        L1+1        INC         IGNORE

; CLEAR SUM AND GO BACK
40                    SUM         ZERO        ZERO        L1

; SORT NUMBERS                
44        L3:         P           NUMBERS     ZERO        LA
48        L4:         Q           NUMBERS+1   ZERO        L9

; COMPARE                
52                    TEMP        Q           P           L8

; SWAP IF OUT OF ORDER
56                    L5+1        L3+1        ZERO        IGNORE
60                    L6          L3+1        ZERO        IGNORE
64                    L6+1        L4+1        ZERO        IGNORE
68                    L7          L4+1        ZERO        IGNORE
72        L5:         TEMP        P           ZERO        IGNORE
76        L6:         P           Q           ZERO        IGNORE
80        L7:         Q           TEMP        ZERO        IGNORE

; INCREMENT INNER INDEX
84        L8:         L4+1        L4+1        INC         IGNORE
88                    TEMP        ZERO        ZERO        L3

; INCREMENT OUTER INDEX AND RESET INNER INDEX
92        L9:         L3+1        L3+1        INC         IGNORE
96                    L4+1        L3+1        INC         IGNORE
100                   TEMP        ZERO        ZERO        L3

; OUTPUT THIRD LARGEST NUMBER
104                   L0+1        NUMBERS+2   ZERO        IGNORE
108       LA:         TEMP        NUMBERS+2   ZERO        EXIT
112       LB:         OUTPUT      ASCII_ONE   ZERO        IGNORE
116                   LB          LB          INC         IGNORE
120                   NUMBERS+2   NUMBERS+2   DEC         EXIT
124                   TEMP        ZERO        ZERO        LA

; SAFETY LOOP – JUST IN CASE IGNORE DOESN'T WORK AS PLANNED!
128       IGNORE:     TEMP        ZERO        ZERO        IGNORE

; CONSTANTS
132       ZERO:        0
133       INC:        -1
134       DEC:         1
135       ASCII_ZERO: 48
136       ASCII_ONE:  49

; VARIABLES
137       TEMP:       [1]
138       SUM:        [1]
139       COUNT:      [1]
140       P:          [1]
141       Q:          [1]

; WORKING SPACE
142       NUMBERS:    [10]

; I/O SPACE
152       INPUT:      [4000]
4152      OUTPUT:     [1000]
5152

То, что он делает, - это анализирует входные данные, конвертирует унарное в двоичное, затем сортирует пузырьки по числам со значениями в порядке убывания, а затем, наконец, выводит третье по величине значение, преобразовывая двоичное число обратно в унарное.

Обратите внимание, что INC(приращение) является отрицательным, а (приращение DEC) является положительным! Где он использует L#или L#+1как P-или Q-OPs, происходит то, что он обновляет указатели: увеличение, уменьшение, замена и т. Д. Ассемблер был вручную скомпилирован в PQRS путем замены меток смещениями. Ниже приведено оптимизированное решение PQRS :

137 132 132 8
152 4000
4152 1000
137 152 135 24
138 138 133 128
9 9 133 128
137 132 132 8
142 138 132 44
24 24 133 128
139 139 133 128
9 9 133 128
138 132 132 8
140 142 132 108
141 143 132 92
137 141 140 84
73 45 132 128
76 45 132 128
77 49 132 128
80 49 132 128
137 140 132 128
140 141 132 128
141 137 132 128
49 49 133 128
137 132 132 44
45 45 133 128
49 45 133 128
137 132 132 44
7 144 132 128
137 144 132 -1
4152 136 132 128
112 112 133 128
144 144 134 -1
137 132 132 108
137 132 132 128
0
-1
1
48
49

Приведенный выше код можно сохранить как challenge-optimized.pqrsдля запуска тестовых случаев.

Для полноты, вот источник per specs:

; ANNOTATED PQRS ASSEMBLER CODE
; FULL SIZED BUFFERS TO RUN ACCORDING TO SPECS

;OFFSET   LABEL       P-OP        Q-OP        R-OP        S-OP
0                     TEMP        ZERO        ZERO        L1

; INPUT AND OUTPUT LOCATIONS AND SIZES
4                     INPUT       10^9        
6         L0:         OUTPUT      10^6        

; GET CURRENT INPUT
8         L1:         TEMP        INPUT       ASCII_ZERO  L2
12                    SUM         SUM         INC         IGNORE
16                    L1+1        L1+1        INC         IGNORE
20                    TEMP        ZERO        ZERO        L1

; CHECK IF END OF NUMBERS
24        L2:         NUMBERS     SUM         ZERO        L3

; ADVANCE TO NEXT NUMBER
28                    L2          L2          INC         IGNORE

; ADVANCE COUNT
32                    COUNT       COUNT       INC         IGNORE
36                    L1+1        L1+1        INC         IGNORE

; CLEAR SUM AND GO BACK
40                    SUM         ZERO        ZERO        L1

; SORT NUMBERS                
44        L3:         P           NUMBERS     ZERO        LA
48        L4:         Q           NUMBERS+1   ZERO        L9

; COMPARE                
52                    TEMP        Q           P           L8

; SWAP IF OUT OF ORDER
56                    L5+1        L3+1        ZERO        IGNORE
60                    L6          L3+1        ZERO        IGNORE
64                    L6+1        L4+1        ZERO        IGNORE
68                    L7          L4+1        ZERO        IGNORE
72        L5:         TEMP        P           ZERO        IGNORE
76        L6:         P           Q           ZERO        IGNORE
80        L7:         Q           TEMP        ZERO        IGNORE

; INCREMENT INNER INDEX
84        L8:         L4+1        L4+1        INC         IGNORE
88                    TEMP        ZERO        ZERO        L3

; INCREMENT OUTER INDEX AND RESET INNER INDEX
92        L9:         L3+1        L3+1        INC         IGNORE
96                    L4+1        L3+1        INC         IGNORE
100                   TEMP        ZERO        ZERO        L3

; OUTPUT THIRD LARGEST NUMBER
104                   L0+1        NUMBERS+2   ZERO        IGNORE
108       LA:         TEMP        NUMBERS+2   ZERO        EXIT
112       LB:         OUTPUT      ASCII_ONE   ZERO        IGNORE
116                   LB          LB          INC         IGNORE
120                   NUMBERS+2   NUMBERS+2   DEC         EXIT
124                   TEMP        ZERO        ZERO        LA

; SAFETY LOOP – JUST IN CASE IGNORE DOESN'T WORK AS PLANNED!
128       IGNORE:     TEMP        ZERO        ZERO        IGNORE

; CONSTANTS
132       ZERO:        0
133       INC:        -1
134       DEC:         1
135       ASCII_ZERO: 48
136       ASCII_ONE:  49

; VARIABLES
137       TEMP:       [1]
138       SUM:        [1]
139       COUNT:      [1]
140       P:          [1]
141       Q:          [1]

; WORKING SPACE
142       NUMBERS:    [10^6]

; I/O SPACE
1000142   INPUT:      [10^9]
1001000142 OUTPUT:    [10^6]
1002000142

И решение:

137 132 132 8
1000142 1000000000
1001000142 1000000
137 1000142 135 24
138 138 133 128
9 9 133 128
137 132 132 8
142 138 132 44
24 24 133 128
139 139 133 128
9 9 133 128
138 132 132 8
140 142 132 108
141 143 132 92
137 141 140 84
73 45 132 128
76 45 132 128
77 49 132 128
80 49 132 128
137 140 132 128
140 141 132 128
141 137 132 128
49 49 133 128
137 132 132 44
45 45 133 128
49 45 133 128
137 132 132 44
7 144 132 128
137 144 132 -1
1001000142 136 132 128
112 112 133 128
144 144 134 -1
137 132 132 108
137 132 132 128
0
-1
1
48
49

Для запуска выше, вы должны закомментировать #define OPTIMIZEDи добавить #define PER_SPECSв pqrs.cи перекомпилировать.

Это был большой вызов - очень понравилась умственная тренировка! Вернул меня к моим старым 6502 дням ассемблера ...

Если бы я реализовал PQRS как «настоящий» язык программирования, я бы, вероятно, добавил бы дополнительные режимы для прямого и дважды косвенного доступа в дополнение к косвенному доступу, а также относительное положение и абсолютное положение, как с опциями косвенного доступа для ветвления!

Цинк, треснул! @Zgarb

Также доступно на GitHub .

Вам нужен Dart 1.12 и Pub. Просто запустите, pub getчтобы загрузить единственную зависимость - библиотеку синтаксического анализа.

Надеюсь, что этот длится дольше 30 минут! : O

Язык

Цинк ориентирован на переопределение операторов. Вы можете легко переопределить все операторы на языке!

Структура типичной программы Zinc выглядит следующим образом:

let
<operator overrides>
in <expression>

Есть только два типа данных: целые числа и множества. Не существует такого понятия, как литерал набора, и пустые наборы запрещены.

Выражения

Ниже приведены допустимые выражения в Zinc:

литералы

Zinc поддерживает все обычные целочисленные литералы, такие как 1и -2.

переменные

Цинк имеет переменные (как и большинство языков). Чтобы ссылаться на них, просто используйте имя. Снова, как и большинство языков!

Тем не менее, есть специальная переменная, Sкоторая ведет себя как Pyth Q. Когда вы впервые используете его, он будет читать строку из стандартного ввода и интерпретировать его как набор чисел. Например, строка ввода 1234231превратится в набор {1, 2, 3, 4, 3, 2, 1}.

ВАЖНАЯ ЗАМЕТКА!!! В некоторых случаях литерал в конце переопределения оператора анализируется неправильно, поэтому его необходимо заключить в скобки.

Бинарные операции

Поддерживаются следующие двоичные операции:

• Сложение с помощью +: 1+1.
• Вычитание с помощью -: 1-1.
• Умножение с помощью *: 2*2.
• Отдел по /: 4/2.
• Равенство с =: 3=3.

Кроме того, также поддерживается следующая унарная операция:

• Длина с #: #x.

Приоритет всегда правильно-ассоциативный. Вы можете использовать скобки, чтобы переопределить это.

Только равенство и длина работают на множествах. Когда вы попытаетесь получить длину целого числа, вы получите количество цифр в его строковом представлении.

Установить понимание

Чтобы манипулировать множествами, Цинк установил понимание. Они выглядят так:

{<variable>:<set><clause>}

Предложение является либо предложением когда, либо предложением сортировки.

А когда предложение выглядит так ^<expression>. Выражение после каретки должно приводить к целому числу. Использование предложения when будет принимать только элементы в наборе, для которых expressionненулевое значение. Внутри выражения переменная _будет установлена ​​на текущий индекс в наборе. Это примерно эквивалентно этому Python:

[<variable> for _, <variable> in enumerate(<set>) when <expression> != 0]

Предложение сортировки , которое выглядит $<expression>, сортирует набор по убыванию по значению <expression>. Он равен этому Python:

sorted(<set>, key=lambda <variable>: <expression>)[::-1]

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

• Возьмем только те элементы множества, sкоторые равны 5:

  {x:s^x=5}
  

• Сортируйте набор sпо значению, если его элементы возведены в квадрат:

  {x:s$x*x}
  

Переопределение

Переопределения операторов позволяют переопределять операторов. Они выглядят так:

<operator>=<operator>

или же:

<variable><operator><variable>=<expression>

В первом случае вы можете определить оператор, равный другому оператору. Например, я могу определить, +чтобы фактически вычесть через:

+=-

Когда вы сделаете это, вы можете переопределить оператор, чтобы стать магическим оператором . Есть два магических оператора:

• joinпринимает набор и целое число и объединяет содержимое набора. Например, соединение {1, 2, 3}с 4приведет к целому числу 14243.

• cutтакже принимает набор и целое число и будет разделять набор при каждом появлении целого числа. Использование cuton {1, 3, 9, 4, 3, 2}и 3создаст {{1}, {9, 4}, {2}}... НО все одноэлементные наборы сглаживаются, так что результат на самом деле будет {1, {9, 4}, 2}.

Вот пример, который переопределяет +оператор, чтобы означать join:

+=join

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

x+y=1+:x+:y

А что +:? Вы можете добавить двоеточие :к оператору, чтобы всегда использовать встроенную версию. В этом примере используется встроенная функция +via +:для сложения чисел, затем добавляется 1 (помните, что все ассоциативно справа).

Переопределение оператора длины выглядит примерно так:

#x=<expression>

Обратите внимание, что почти все встроенные операции (кроме равенства) будут использовать этот оператор длины для определения длины набора. Если вы определили это как:

#x=1

каждая часть Zinc, которая работает на наборах, за исключением того, =что будет работать только на первом элементе набора, который ей был дан.

Несколько переопределений

Вы можете переопределить несколько операторов, разделяя их запятыми:

let
+=-,
*=/
in 1+2*3

печать

Вы не можете напрямую печатать что-либо в Цинке. Результат выражения следующий inбудет напечатан. Значения набора будут объединены с разделителем. Например, возьмите это:

let
...
in expr

Если exprустановлено {1, 3, {2, 4}}, 1324будет напечатано на экране после завершения программы.

Собираем все вместе

Вот простая программа Zinc, которая, кажется, добавляет, 2+2но приводит к результату 5:

let
x+y=1+:x+:y
in 1+2

Переводчик

Это идет в bin/zinc.dart:

import 'package:parsers/parsers.dart';
import 'dart:io';

// An error.
class Error implements Exception {
  String cause;
  Error(this.cause);
  String toString() => 'error in Zinc script: $cause';
}


// AST.
class Node {
  Obj interpret(ZincInterpreter interp) => null;
}

// Identifier.
class Id extends Node {
  final String id;
  Id(this.id);
  String toString() => 'Id($id)';
  Obj interpret(ZincInterpreter interp) => interp.getv(id);
}

// Integer literal.
class IntLiteral extends Node {
  final int value;
  IntLiteral(this.value);
  String toString() => 'IntLiteral($value)';
  Obj interpret(ZincInterpreter interp) => new IntObj(value);
}

// Any kind of operator.
class Anyop extends Node {
  void set(ZincInterpreter interp, OpFuncType func) {}
}

// Operator.
class Op extends Anyop {
  final String op;
  final bool orig;
  Op(this.op, [this.orig = false]);
  String toString() => 'Op($op, $orig)';
  OpFuncType get(ZincInterpreter interp) =>
    this.orig ? interp.op0[op] : interp.op1[op];
  void set(ZincInterpreter interp, OpFuncType func) { interp.op1[op] = func; }
}

// Unary operator (len).
class Lenop extends Anyop {
  final bool orig;
  Lenop([this.orig = false]);
  String toString() => 'Lenop($orig)';
  OpFuncType get(ZincInterpreter interp) =>
    this.orig ? interp.op0['#'] : interp.op1['#'];
  void set(ZincInterpreter interp, OpFuncType func) { interp.op1['#'] = func; }
}

// Magic operator.
class Magicop extends Anyop {
  final String op;
  Magicop(this.op);
  String toString() => 'Magicop($op)';
  Obj interpret_with(ZincInterpreter interp, Obj x, Obj y) {
    if (op == 'cut') {
      if (y is! IntObj) { throw new Error('cannot cut int with non-int'); }
      if (x is IntObj) {
        return new SetObj(x.value.toString().split(y.value.toString()).map(
          int.parse));
      } else {
        assert(x is SetObj);
        List<List<Obj>> res = [[]];
        for (Obj obj in x.vals(interp)) {
          if (obj == y) { res.add([]); }
          else { res.last.add(obj); }
        }
        return new SetObj(new List.from(res.map((l) =>
          l.length == 1 ? l[0] : new SetObj(l))));
      }
    } else if (op == 'join') {
      if (x is! SetObj) { throw new Error('can only join set'); }
      if (y is! IntObj) { throw new Error('can only join set with int'); }
      String res = '';
      for (Obj obj in x.vals(interp)) {
        if (obj is! IntObj) { throw new Error('joining set must contain ints'); }
        res += obj.value.toString();
      }
      return new IntObj(int.parse(res));
    }
  }
}

// Unary operator (len) expression.
class Len extends Node {
  final Lenop op;
  final Node value;
  Len(this.op, this.value);
  String toString() => 'Len($op, $value)';
  Obj interpret(ZincInterpreter interp) =>
    op.get(interp)(interp, value.interpret(interp), null);
}

// Binary operator expression.
class Binop extends Node {
  final Node lhs, rhs;
  final Op op;
  Binop(this.lhs, this.op, this.rhs);
  String toString() => 'Binop($lhs, $op, $rhs)';
  Obj interpret(ZincInterpreter interp) =>
    op.get(interp)(interp, lhs.interpret(interp), rhs.interpret(interp));
}

// Clause.
enum ClauseKind { Where, Sort }
class Clause extends Node {
  final ClauseKind kind;
  final Node expr;
  Clause(this.kind, this.expr);
  String toString() => 'Clause($kind, $expr)';
  Obj interpret_with(ZincInterpreter interp, SetObj set, Id id) {
    List<Obj> res = [];
    List<Obj> values = set.vals(interp);
    switch (kind) {
    case ClauseKind.Where:
      for (int i=0; i<values.length; i++) {
        Obj obj = values[i];
        interp.push_scope();
        interp.setv(id.id, obj);
        interp.setv('_', new IntObj(i));
        Obj x = expr.interpret(interp);
        interp.pop_scope();
        if (x is IntObj) {
          if (x.value != 0) { res.add(obj); }
        } else { throw new Error('where clause condition must be an integer'); }
      }
      break;
    case ClauseKind.Sort:
      res = values;
      res.sort((x, y) {
        interp.push_scope();
        interp.setv(id.id, x);
        Obj x_by = expr.interpret(interp);
        interp.setv(id.id, y);
        Obj y_by = expr.interpret(interp);
        interp.pop_scope();
        if (x_by is IntObj && y_by is IntObj) {
          return x_by.value.compareTo(y_by.value);
        } else { throw new Error('sort clause result must be an integer'); }
      });
      break;
    }
    return new SetObj(new List.from(res.reversed));
  }
}

// Set comprehension.
class SetComp extends Node {
  final Id id;
  final Node set;
  final Clause clause;
  SetComp(this.id, this.set, this.clause);
  String toString() => 'SetComp($id, $set, $clause)';
  Obj interpret(ZincInterpreter interp) {
    Obj setobj = set.interpret(interp);
    if (setobj is SetObj) {
      return clause.interpret_with(interp, setobj, id);
    } else { throw new Error('set comprehension rhs must be set type'); }
  }
}

// Operator rewrite.
class OpRewrite extends Node {
  final Anyop op;
  final Node value;
  final Id lid, rid; // Can be null!
  OpRewrite(this.op, this.value, [this.lid, this.rid]);
  String toString() => 'OpRewrite($lid, $op, $rid, $value)';
  Obj interpret(ZincInterpreter interp) {
    if (lid != null) {
      // Not bare.
      op.set(interp, (interp,x,y) {
        interp.push_scope();
        interp.setv(lid.id, x);
        if (rid == null) { assert(y == null); }
        else { interp.setv(rid.id, y); }
        Obj res = value.interpret(interp);
        interp.pop_scope();
        return res;
      });
    } else {
      // Bare.
      if (value is Magicop) {
        op.set(interp, (interp,x,y) => value.interpret_with(interp, x, y));
      } else {
        op.set(interp, (interp,x,y) => (value as Anyop).get(interp)(x, y));
      }
    }
    return null;
  }
}

class Program extends Node {
  final List<OpRewrite> rws;
  final Node expr;
  Program(this.rws, this.expr);
  String toString() => 'Program($rws, $expr)';
  Obj interpret(ZincInterpreter interp) {
    rws.forEach((n) => n.interpret(interp));
    return expr.interpret(interp);
  }
}


// Runtime objects.
typedef Obj OpFuncType(ZincInterpreter interp, Obj x, Obj y);

class Obj {}

class IntObj extends Obj {
  final int value;
  IntObj(this.value);
  String toString() => 'IntObj($value)';
  bool operator==(Obj rhs) => rhs is IntObj && value == rhs.value;
  String dump() => value.toString();
}

class SetObj extends Obj {
  final List<Obj> values;
  SetObj(this.values) {
    if (values.length == 0) { throw new Error('set cannot be empty'); }
  }
  String toString() => 'SetObj($values)';
  bool operator==(Obj rhs) => rhs is SetObj && values == rhs.values;
  String dump() => values.map((x) => x.dump()).reduce((x,y) => x+y);
  List<Obj> vals(ZincInterpreter interp) {
    Obj lenobj = interp.op1['#'](interp, this, null);
    int len;
    if (lenobj is! IntObj) { throw new Error('# operator must return an int'); }
    len = lenobj.value;
    if (len < 0) { throw new Error('result of # operator must be positive'); }
    return new List<Obj>.from(values.getRange(0, len));
  }
}


// Parser.
class ZincParser extends LanguageParsers {
  ZincParser(): super(reservedNames: ['let', 'in', 'join', 'cut']);
  get start => prog().between(spaces, eof);
  get comma => char(',') < spaces;
  get lp => symbol('(');
  get rp => symbol(')');
  get lb => symbol('{');
  get rb => symbol('}');
  get colon => symbol(':');
  get plus => symbol('+');
  get minus => symbol('-');
  get star => symbol('*');
  get slash => symbol('/');
  get eq => symbol('=');
  get len => symbol('#');
  get in_ => char(':');
  get where => char('^');
  get sort => char('\$');

  prog() => reserved['let'] + oprw().sepBy(comma) + reserved['in'] + expr() ^
            (_1,o,_2,x) => new Program(o,x);
  oprw() => oprw1() | oprw2() | oprw3();
  oprw1() => (basicop() | lenop()) + eq + (magicop() | op()) ^
             (o,_,r) => new OpRewrite(o,r);
  oprw2() => (id() + op() + id()).list + eq + expr() ^
             (l,_,x) => new OpRewrite(l[1], x, l[0], l[2]);
  oprw3() => lenop() + id() + eq + expr() ^ (o,a,_,x) => new OpRewrite(o, x, a);
  magicop() => (reserved['join'] | reserved['cut']) ^ (s) => new Magicop(s);
  basicop() => (plus | minus | star | slash | eq) ^ (op) => new Op(op);
  op() => (basicop() + colon ^ (op,_) => new Op(op.op, true)) | basicop();
  lenop() => (len + colon ^ (_1,_2) => new Lenop(true)) |
             len ^ (_) => new Lenop();
  expr() => setcomp() | unop() | binop() | prim();
  setcomp() => lb + id() + in_ + rec(expr) + clause() + rb ^
               (_1,i,_2,x,c,_3) => new SetComp(i,x,c);
  clausekind() => (where ^ (_) => ClauseKind.Where) |
                  (sort  ^ (_) => ClauseKind.Sort);
  clause() => clausekind() + rec(expr) ^ (k,x) => new Clause(k,x);
  unop() => lenop() + rec(expr) ^ (o,x) => new Len(o,x);
  binop() => prim() + op() + rec(expr) ^ (l,o,r) => new Binop(l,o,r);
  prim() => id() | intlit() | parens(rec(expr));
  id() => identifier ^ (i) => new Id(i);
  intlit() => intLiteral ^ (i) => new IntLiteral(i);
}


// Interpreter.
class ZincInterpreter {
  Map<String, OpFuncType> op0, op1;
  List<Map<String, Obj>> scopes;
  ZincInterpreter() {
    var beInt = (v) {
      if (v is IntObj) { return v.value; }
      else { throw new Error('argument to binary operator must be integer'); }
    };
    op0 = {
      '+': (_,x,y) => new IntObj(beInt(x)+beInt(y)),
      '-': (_,x,y) => new IntObj(beInt(x)-beInt(y)),
      '*': (_,x,y) => new IntObj(beInt(x)*beInt(y)),
      '/': (_,x,y) => new IntObj(beInt(x)/beInt(y)),
      '=': (_,x,y) => new IntObj(x == y ? 1 : 0),
      '#': (i,x,_2) =>
        new IntObj(x is IntObj ? x.value.toString().length : x.values.length)
    };
    op1 = new Map<String, OpFuncType>.from(op0);
    scopes = [{}];
  }

  void push_scope() { scopes.add({}); }
  void pop_scope() { scopes.removeLast(); }
  void setv(String name, Obj value) { scopes[scopes.length-1][name] = value; }
  Obj getv(String name) {
    for (var scope in scopes.reversed) {
      if (scope[name] != null) { return scope[name]; }
    }
    if (name == 'S') {
      var input = stdin.readLineSync() ?? '';
      var list = new List.from(input.codeUnits.map((c) =>
        new IntObj(int.parse(new String.fromCharCodes([c])))));
      setv('S', new SetObj(list));
      return getv('S');
    } else throw new Error('undefined variable $name');
  }
}


void main(List<String> args) {
  if (args.length != 1) {
    print('usage: ${Platform.script.toFilePath()} <file to run>');
    return;
  }
  var file = new File(args[0]);
  if (!file.existsSync()) {
    print('cannot open ${args[0]}');
    return;
  }
  Program root = new ZincParser().start.parse(file.readAsStringSync());
  ZincInterpreter interp = new ZincInterpreter();
  var res = root.interpret(interp);
  print(res.dump());
}

И это идет в pubspec.yaml:

name: zinc
dependencies:
  parsers: any

Предполагаемое решение

let
#x=((x=S)*(-2))+#:x,
/=cut
in {y:{x:S/0$#:x}^_=2}

Суп Компас ( треснутый картонной коробкой )

Переводчик: C ++

Compass Soup - это своего рода машина Тьюринга с бесконечной двумерной лентой. Основная проблема заключается в том, что память команд и память данных находятся в одном и том же пространстве, а выходные данные программы представляют собой все содержимое этого пространства.

Как это устроено

Программа представляет собой двухмерный блок текста. Пространство программы начинается со всего исходного кода, помещенного с первым символом в (0,0). Остальное пространство программы бесконечно и инициализируется нулевыми символами (ASCII 0).

Есть два указателя, которые могут перемещаться по программному пространству:

• Указатель выполнения имеет местоположение и направление (север, юг, восток или запад). Каждый тик, инструкция под указателем выполнения выполняется, затем указатель выполнения перемещается в своем текущем направлении. Указатель выполнения начинает двигаться на восток (положительное число x), в месте расположения !символа или в (0,0), если этого не существует.
• Указатель данных имеет только местоположение. Он перемещается с инструкциями x, X, y, и Y. Он начинается с местоположения @символа или с (0,0), если его не существует.

вход

Содержимое стандартного ввода выводится в пространство программы, начиная с местоположения >символа или с (0,0), если его не существует.

Выход

Программа завершается, когда указатель выполнения безвозвратно выходит за пределы. Выходными данными является все содержимое пространства программы в то время. Он отправляется в stdout и 'result.txt'.

инструкции

• n - перенаправляет указатель выполнения на север (отрицательный у)
• e - перенаправляет указатель выполнения на восток (положительный х)
• s - перенаправляет указатель выполнения на юг (положительный y)
• w - перенаправляет указатель выполнения на запад (отрицательный х)
• y - перемещает указатель данных на север (отрицательный у)
• X - перемещает указатель данных на восток (положительный х)
• Y - перемещает указатель данных на юг (положительный y)
• x - перемещает указатель данных на запад (отрицательный х)
• p- записывает следующий символ, встреченный указателем выполнения, в указатель данных. Этот персонаж не выполняется как инструкция.
• j- проверяет следующий символ, обнаруженный указателем выполнения, против символа под указателем данных. Этот персонаж не выполняется как инструкция. Если они совпадают, указатель выполнения перепрыгивает через следующий символ.
• c - записывает нулевой символ в указатель данных.
• * - точка останова - просто заставляет переводчика сломаться.

Все остальные символы игнорируются указателем выполнения.

переводчик

Интерпретатор принимает исходный файл в качестве аргумента и вводит в stdin. У него есть пошаговый отладчик, который вы можете вызвать с помощью инструкции точки останова в коде ( *). В случае прерывания указатель выполнения отображается как ASCII 178 (более темный заштрихованный блок), а указатель данных отображается как ASCII 177 (более светлый заштрихованный блок).

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>

// Compass Soup programming language interpreter
// created by Brian MacIntosh (BMacZero)
// for https://codegolf.stackexchange.com/questions/61804/create-a-programming-language-that-only-appears-to-be-unusable
//
// 31 October 2015

struct Point
{
    int x, y;
    Point(int ix, int iy) { x = ix; y = iy; };
    bool operator==(const Point &other) const
    {
        return other.x == x && other.y == y;
    }
    bool operator!=(const Point &other) const
    {
        return other.x != x || other.y != y;
    }
};

struct Bounds
{
    int xMin, xMax, yMin, yMax;
    Bounds(int xmin, int ymin, int xmax, int ymax)
    {
        xMin = xmin; yMin = ymin; xMax = xmax; yMax = ymax;
    }
    bool contains(Point pt)
    {
        return pt.x >= xMin && pt.x <= xMax && pt.y >= yMin && pt.y <= yMax;
    }
    int getWidth() { return xMax - xMin + 1; }
    int getHeight() { return yMax - yMin + 1; }
    bool operator==(const Bounds &other) const
    {
        return other.xMin == xMin && other.xMax == xMax && other.yMin == yMin && other.yMax == yMax;
    }
    bool operator!=(const Bounds &other) const
    {
        return other.xMin != xMin || other.xMax != xMax || other.yMin != yMin || other.yMax != yMax;
    }
};

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

Bounds hull(Point a, Bounds b)
{
    return Bounds(min(a.x, b.xMin), min(a.y, b.yMin), max(a.x, b.xMax), max(a.y, b.yMax));
}

Bounds hull(Bounds a, Bounds b)
{
    return Bounds(min(a.xMin, b.xMin), min(a.yMin, b.yMin), max(a.xMax, b.xMax), max(a.yMax, b.yMax));
}

Bounds programBounds(0,0,0,0);
char** programSpace;

Point execPtr(0,0);
Point execPtrDir(1,0);
Point dataPtr(0,0);
Point stdInPos(0,0);

bool breakpointHit = false;
char breakOn = 0;

/// reads the character from the specified position
char read(Point pt)
{
    if (programBounds.contains(pt))
        return programSpace[pt.x - programBounds.xMin][pt.y - programBounds.yMin];
    else
        return 0;
}

/// read the character at the data pointer
char readData()
{
    return read(dataPtr);
}

/// read the character at the execution pointer
char readProgram()
{
    return read(execPtr);
}

/// gets the bounds of the actual content of the program space
Bounds getTightBounds(bool debug)
{
    Bounds tight(0,0,0,0);
    for (int x = programBounds.xMin; x <= programBounds.xMax; x++)
    {
        for (int y = programBounds.yMin; y <= programBounds.yMax; y++)
        {
            if (read(Point(x, y)) != 0)
            {
                tight = hull(Point(x, y), tight);
            }
        }
    }
    if (debug)
    {
        tight = hull(dataPtr, tight);
        tight = hull(execPtr, tight);
    }
    return tight;
}

/// ensure that the program space encompasses the specified rectangle
void fitProgramSpace(Bounds bounds)
{
    Bounds newBounds = hull(bounds, programBounds);

    if (newBounds == programBounds) return;

    // allocate new space
    char** newSpace = new char*[newBounds.getWidth()];

    // copy content
    for (int x = 0; x < newBounds.getWidth(); x++)
    {
        newSpace[x] = new char[newBounds.getHeight()];
        for (int y = 0; y < newBounds.getHeight(); y++)
        {
            Point newWorldPos(x + newBounds.xMin, y + newBounds.yMin);
            newSpace[x][y] = read(newWorldPos);
        }
    }

    // destroy old space
    for (int x = 0; x < programBounds.getWidth(); x++)
    {
        delete[] programSpace[x];
    }
    delete[] programSpace;

    programSpace = newSpace;
    programBounds = newBounds;
}

/// outputs the current program space to a file
void outputToStream(std::ostream &stream, bool debug)
{
    Bounds tight = getTightBounds(debug);
    for (int y = tight.yMin; y <= tight.yMax; y++)
    {
        for (int x = tight.xMin; x <= tight.xMax; x++)
        {
            char at = read(Point(x, y));
            if (debug && x == execPtr.x && y == execPtr.y)
                stream << (char)178;
            else if (debug && x == dataPtr.x && y == dataPtr.y)
                stream << (char)177;
            else if (at == 0)
                stream << ' ';
            else
                stream << at;
        }
        stream << std::endl;
    }
}

/// writes a character at the specified position
void write(Point pt, char ch)
{
    fitProgramSpace(hull(pt, programBounds));
    programSpace[pt.x - programBounds.xMin][pt.y - programBounds.yMin] = ch;
}

/// writes a character at the data pointer
void write(char ch)
{
    write(dataPtr, ch);
}

/// writes a line of text horizontally, starting at the specified position
void writeLine(Point loc, std::string str, bool isSource)
{
    fitProgramSpace(Bounds(loc.x, loc.y, loc.x + str.size(), loc.y));
    for (unsigned int x = 0; x < str.size(); x++)
    {
        programSpace[x + loc.x][loc.y] = str[x];

        // record locations of things
        if (isSource)
        {
            switch (str[x])
            {
            case '>':
                stdInPos = Point(loc.x + x, loc.y);
                break;
            case '!':
                execPtr = Point(loc.x + x, loc.y);
                break;
            case '@':
                dataPtr = Point(loc.x + x, loc.y);
                break;
            }
        }
    }
}

void advanceExecPtr()
{
    execPtr.x += execPtrDir.x;
    execPtr.y += execPtrDir.y;
}

void breakpoint()
{
    breakpointHit = true;
    outputToStream(std::cout, true);
    std::cout << "[Return]: step | [Space+Return]: continue | [<char>+Return]: continue to <char>" << std::endl;
    while (true)
    {
        std::string input;
        std::getline(std::cin, input);
        if (input.size() == 0)
        {
            break;
        }
        else if (input.size() == 1)
        {
            if (input[0] == ' ')
            {
                breakpointHit = false;
                break;
            }
            else
            {
                breakOn = input[0];
                breakpointHit = false;
                break;
            }
        }
    }
}

int main(int argc, char** argv)
{
    if (argc != 2)
    {
        printf("Usage: CompassSoup <source-file>");
        return 1;
    }

    // open source file
    std::ifstream sourceIn(argv[1]);

    if (!sourceIn.is_open())
    {
        printf("Error reading source file.");
        return 1;
    }

    programSpace = new char*[1];
    programSpace[0] = new char[1];
    programSpace[0][0] = 0;

    // read starting configuration
    std::string line;
    int currentLine = 0;
    while (std::getline(sourceIn, line))
    {
        writeLine(Point(0, currentLine), line, true);
        currentLine++;
    }

    sourceIn.close();

    // take stdin
    std::string input;
    std::cout << ">";
    std::cin >> input;
    std::cin.ignore();
    writeLine(stdInPos, input, false);

    // execute
    while (programBounds.contains(execPtr))
    {
        if (execPtrDir.x == 0 && execPtrDir.y == 0)
        {
            printf("Implementation error: execPtr is stuck.");
            break;
        }

        advanceExecPtr();

        char command = readProgram();

        // breakpoint control code
        if (breakpointHit || (breakOn != 0 && command == breakOn))
        {
            breakOn = 0;
            breakpoint();
        }

        switch (command)
        {
        case 'n':
            execPtrDir = Point(0,-1);
            break;
        case 'e':
            execPtrDir = Point(1,0);
            break;
        case 's':
            execPtrDir = Point(0,1);
            break;
        case 'w':
            execPtrDir = Point(-1,0);
            break;
        case 'x':
            dataPtr.x--;
            break;
        case 'X':
            dataPtr.x++;
            break;
        case 'y':
            dataPtr.y--;
            break;
        case 'Y':
            dataPtr.y++;
            break;
        case 'p':
            advanceExecPtr();
            write(readProgram());
            break;
        case 'j':
            advanceExecPtr();
            if (readData() == readProgram())
            {
                advanceExecPtr();
            }
            break;
        case 'c':
            write(0);
            break;
        case '*':
            breakpoint();
            break;
        }
    }

    std::ofstream outputFile("result.txt");
    outputToStream(outputFile, false);
    outputToStream(std::cout, false);
    outputFile.close();
}