Befunge to dwuwymiarowy ezoteryczny język programowania. Podstawową ideą jest to, że polecenia (jednoznakowe) są umieszczane na dwuwymiarowej siatce. Przepływ sterowania przechodzi przez siatkę, wykonując polecenia, które przechodzi, i zmienia kierunek, gdy uderza w strzałkę ( >^<v). Polecenia są oparte na stosie; zobacz tę listę . Zobacz także http://esolangs.org/wiki/Befunge .

Dostępna jest specyfikacja Befunge-98 .

Problem

Napisz program, który przekształci program Befunge w bardziej zwartą reprezentację. Na przykład drukowany jest następujący program 0:

>   0   v

>   @   .

^       <

W takim przypadku można go spakować bez zmiany zachowania programu, usuwając rzędy spacji

>0v
>@.
^ <

Bardziej zaawansowane transformacje mogą obracać lub odzwierciedlać sekwencje poleceń i eliminować niepotrzebne polecenia sterowania w celu skompresowania programu. Na przykład za pomocą tego programu:

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

możesz wsunąć koniec programu w otwór:

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

W pierwszym przykładzie najbardziej kompaktowym możliwym programem jest

>0.@

Możesz użyć dowolnej transformacji, o ile program wyjściowy daje taki sam wynik.

Programy wejściowe

Programy wejściowe są poprawnymi programami Befunge-98.

Możesz założyć, że program wejściowy jest deterministyczny. Oznacza to, że nie korzysta z polecenia odczytu stanu zewnętrznego: komendy wprowadzania danych przez użytkownika &i ~, tym randomizer ?i samo-modyfikując kod polecenia pi g.

Możesz założyć, że program wejściowy kończy się.

Punktacja

To nie jest gra w golfa z kodem, ale problem z napisaniem programu, który wykonuje grę w golfa.

Dane wejściowe to zestaw przypadków testowych (programy Befunge, które spełniają powyższe ograniczenia wprowadzania). Całkowity wynik jest sumą wyników dla przypadków testowych.

Ocena dla każdego przypadku testowego

Punktacja to obszar wypukłego kadłuba niepustych komórek w programie wyjściowym, gdzie każda komórka jest traktowana jako kwadrat, którego cztery rogi są punktami kratowymi w płaszczyźnie kartezjańskiej. Na przykład program

>   v
 @  <

otrzymuje wynik 9,5.

Jeśli twój program nie kończy się w rozsądnym czasie i pamięci na określonym wejściu, wynikiem jest wynik programu wejściowego. (Dzieje się tak, ponieważ można w prosty sposób dodać opakowanie ograniczające czas, które wyprowadza program wejściowy bez zmian, jeśli program nie zakończy się na czas.)

Jeśli program przypadku testowego ma inny wynik (lub się nie kończy) po przetworzeniu w programie, wynikiem jest wynik programu wejściowego plus kara 100 punktów.

Spędziłem długą podróż samolotem, kodując to. Napisałem pseudo kompilator befunge, który uruchamia program befunge, wyodrębnia podstawowe bloki i układa je w zwartą reprezentację.

Link do programu .

W programie 99 butelek:

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<
                    ,:
                    ^_ $$ @

Generuje następujące dane wyjściowe:

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#     <
    >$$@    

W rzeczywistości nie jest on znacznie bardziej kompaktowy niż źródło, ale prawdopodobnie będzie lepiej na większych / rzadszych programach.

Program jest ułożony z obszarem trasowania po lewej stronie i podstawową zawartością bloku po prawej stronie. Blok podstawowy jest zwykle układany w parzystej liczbie rzędów, więc wejście i wyjście sąsiaduje z obszarem trasy. Na końcu każdego bloku podstawowego gadżet #^_vi warianty rozmieszczone od prawej do lewej wykonują warunkową rozgałęzienie i przepływ do kolumn. Na początku każdego bloku podstawowego kolumny te są kierowane do wierszy docelowego bloku podstawowego.

Ponadto, jeśli dane wyjściowe są krótkie, po prostu jawnie generują dane wyjściowe, takie jak to:

"output">:#,_@

Nie zrobiłem nic, aby zoptymalizować same podstawowe bloki, tylko układ. Do zrobienia.

Więc gdzie są testy?

Sed, 5 znaków

Tak więc, nawet jeśli nie jest to codegolf, oto rozwiązanie, które będzie miało dość dobry stosunek długości kodu do wyniku, ale niekoniecznie dobry wynik.

/^$/d

Po prostu usuwa puste linie.