Befunge - это двумерный эзотерический язык программирования. Основная идея заключается в том, что (односимвольные) команды размещаются на двумерной сетке. Поток управления проходит по сетке, выполняя команды, через которые он проходит, и изменяя направление, когда ударяет стрелку ( >^<v). Команды основаны на стеке; увидеть этот список . Смотрите также http://esolangs.org/wiki/Befunge .

Спецификация для Befunge-98 доступна.

проблема

Напишите программу, которая преобразует программу Befunge в более компактное представление. Например, следующая программа печатает 0:

>   0   v

>   @   .

^       <

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

>0v
>@.
^ <

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

>12345v
      6
v....7<
.
.
.
@

вы можете заправить конец программы в отверстие:

>12345v
>...@ 6
^....7<

Для первого примера самая компактная из возможных программ

>0.@

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

Входные программы

Программы ввода являются действительными программами Befunge-98.

Вы можете предположить, что входная программа является детерминированной. То есть он не использует команды, которые читают внешнее состояние: команды пользовательского ввода &и ~, рандомизатор ?и команды самоизменяющегося кода pи g.

Вы можете предположить, что входная программа завершается.

счет

Это не кодовый гольф, а проблема в написании программы, которая выполняет кодовый гольф.

Входные данные представляют собой набор тестовых случаев (программы Befunge, которые удовлетворяют ограничениям ввода, указанным выше). Общий балл - это сумма баллов за тестовые случаи.

Оценка для каждого теста

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

>   v
 @  <

получает оценку 9,5.

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

Если программа тестового примера имеет другой результат (или не может завершиться) после обработки вашей программой, результатом является оценка входной программы плюс штраф в 100 баллов.

Я провел долгую поездку на самолете, кодируя это. Я написал псевдо-компилятор befunge, который запускает программу befunge, извлекает базовые блоки и размещает их в компактном представлении.

Ссылка на программу .

При запуске на этой программе 99 бутылок:

92+9*                           :. v  <
>v"bottles of beer on the wall"+910<
,:
^_ $                             :.v
            >v"bottles of beer"+910<
            ,:
            ^_ $                     v
>v"Take one down, pass it around"+910<
,:
^_ $                           1-v
                                 :
        >v"bottles of beer"+910.:_          v
        ,:
        ^_ $                          ^
                    >v" no more beer..."+910<
                    ,:
                    ^_ $$ @

Он генерирует следующий вывод:

92+9*:.019+"llaw eht no "v
v  _v# :"bottles of beer"<
>    ,:    v
^  _v#     <
    >$:.019+"reeb f"v
 v _  v#:"bottles o"<
 >     ,:  v
 ^ _  v#   <
      >$019+"dnuo"v
     v"pass it ar"<
     >" ,nwod eno"v
 v _    v#:"Take "<
 >       ,:v
 ^ _    v# <
        >$1-:v
 v _      v# <
 >         :.019+"reeb "v
  v_  v#   :"bottles of"<
  >        ,v
  ^_  v#   :<
      >    $019+"llaw"v
           v" on the "<
           >"reeb fo "v
^  _^#      :"bottles"<
          >019+"...r"v
v  _v#:" no more bee"<
>    ,:    v
^  _v#     <
    >$$@    

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

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

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

"output">:#,_@

Я ничего не сделал для оптимизации самих базовых блоков, только макет. Сделать.

Так где же тесты?

Sed, 5 символов

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

/^$/d

Это просто удаляет пустые строки.