Kompaktowy program Befunge

17

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.

Ślimak mechaniczny
źródło
8
Co zapobiega uruchamianiu programu do końca i pisaniu programu Befunge, który drukuje to samo wyjście?
Keith Randall
5
Czy dozwolone jest „get” i „put”? Jeśli zezwolisz na „put” (kod samomodyfikujący), trudno będzie cokolwiek zrobić.
Keith Randall
2
Od czego zaczyna się egzekucja? Górny lewy róg? Jeśli tak, czy możesz wyjaśnić wyniki drugiego przykładu? .oznacza wyjściową liczbę całkowitą, ale jeśli zaczynasz od lewego górnego rogu, wówczas na stosie nie ma liczby całkowitej do wyprowadzenia.
elssar
1
@elssar tak, .wyświetla liczbę całkowitą. Ale także, gdy na stosie nie ma wystarczających parametrów, befunge udaje, że zamiast tego jest tam wystarczająca liczba zer. W ten sposób wyszedłby drugi przykład 000.
daniero
@KeithRandall: Pisanie nowego programu z tym samym wyjściem działa tylko w przypadku programów z krótkim wyjściem. gi pnie są dozwolone (przepraszam, zapomniałem o nich; edytowane).
Mechaniczny ślimak

Odpowiedzi:

12

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?

Keith Randall
źródło
1
link do kodu źródłowego wydaje się w tej chwili 500. Błędna konfiguracja serwera?
John Dvorak,
1
@JanDvorak: rzeczywiście. Naprawiony.
Keith Randall
1

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.

daniero
źródło
10
Twój kod jest nieprawidłowy! Nie można po prostu usunąć pustych linii. Nie mogę napisać kodu 2D w komentarzu. Rozważmy jednak przypadek, w którym kierunek jest w dół i rozpoczyna się ciąg znaków ( "). Każda pusta linia na drodze powinna być traktowana jako znak spacji. Jeśli wydrukujemy ten ciąg, wygenerowany kod nie będzie zawierał tych spacji!
saeedn
3
Spójrz na kod w ideone.com/BdcRcf Powinien zostać wydrukowany b a. Ale po skróceniu wydrukuje się ba.
saeedn