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 p
i 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.
źródło
.
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..
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ład000
.g
ip
nie są dozwolone (przepraszam, zapomniałem o nich; edytowane).Odpowiedzi:
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:
Generuje następujące dane wyjściowe:
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
#^_v
i 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:
Nie zrobiłem nic, aby zoptymalizować same podstawowe bloki, tylko układ. Do zrobienia.
Więc gdzie są testy?
źródło
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.
Po prostu usuwa puste linie.
źródło
"
). 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!b a
. Ale po skróceniu wydrukuje sięba
.