W 2014 roku demoscener Jakub „Ilmenit” Dębski wydał demo 250-bajtowej (1) grafiki proceduralnej dla Atari XL o nazwie Mona . Rysuje następujący obrazek (2) :
Twoim zadaniem jest wygenerowanie dokładnie tego samego obrazu w wybranym języku.
(1) Podział: 136 bajtów danych + 114 bajtów kodu.
(2) Oryginalne zdjęcie to 128x96. Powyższa wersja została powiększona do 256 x 192. Kilka pikseli różni się od oryginału, ale jest to oczekiwany wynik z pseudokodem opisanym w tym wyzwaniu.
W jaki sposób?
To jest golf golfowy . Chociaż masz uprawnienia do korzystania z dowolnej metody, najlepsze wyniki najprawdopodobniej zostaną osiągnięte przy użyciu oryginalnego algorytmu, który opisano poniżej.
Uwaga : ten akapit nie jest specyfikacją, ale raczej ogólnym opisem. Szczegółowe informacje na temat algorytmu znajdują się w pseudokodzie i implementacji referencyjnej.
Obraz składa się z 64 pseudolosowych pociągnięć pędzla ( patrz ten film ), cyklicznie następujących kolorów (w formacie szesnastkowym RRGGBB):
COLOR = [ 0xFFE289, 0xE99E45, 0xA55A00, 0x000000 ]
Tło jest początkowo wypełnione czwartym kolorem (czarnym). Każde uderzenie jest krótsze niż poprzednie.
Generator pseudolosowy wykorzystuje rejestr przesunięcia liniowego (LFSR) na 32-bitowej liczbie całkowitej początkowo ustawionej na 0x7EC80000
i XOR'ed 0x04C11DB7
.
Każde uderzenie jest inicjowane 16-bitową wartością, która zastępuje najniższe bajty zarodka:
BRUSH = [
0x030A, 0x37BE, 0x2F9B, 0x072B, 0x0E3C, 0xF59B, 0x8A91, 0x1B0B,
0x0EBD, 0x9378, 0xB83E, 0xB05A, 0x70B5, 0x0280, 0xD0B1, 0x9CD2,
0x2093, 0x209C, 0x3D11, 0x26D6, 0xDF19, 0x97F5, 0x90A3, 0xA347,
0x8AF7, 0x0859, 0x29AD, 0xA32C, 0x7DFC, 0x0D7D, 0xD57A, 0x3051,
0xD431, 0x542B, 0xB242, 0xB114, 0x8A96, 0x2914, 0xB0F1, 0x532C,
0x0413, 0x0A09, 0x3EBB, 0xE916, 0x1877, 0xB8E2, 0xAC72, 0x80C7,
0x5240, 0x8D3C, 0x3EAF, 0xAD63, 0x1E14, 0xB23D, 0x238F, 0xC07B,
0xAF9D, 0x312E, 0x96CE, 0x25A7, 0x9E37, 0x2C44, 0x2BB9, 0x2139
];
Wartości te są również używane do ustawienia nowej pozycji pędzla na początku obrysu (bx, by) : bx jest podawany przez najmniej znaczący bajt, a przez przez najbardziej znaczący bajt.
Kierunek skoku jest podany przez bity # 1 i # 7 nasion. (Zobacz instrukcję SWITCH w pseudokodzie).
Pseudo kod
Poniżej jest algorytm w pseudo-kodzie, zakładając 0 indeksowane tablice, tam gdzie AND
, OR
i XOR
średnie operacje bitowe.
seed = 0x7EC80000
dir = 0x00
FOR part = 0 TO 63
word = BRUSH[part]
seed = (seed AND 0xFFFF0000) OR word
bx = word AND 0xFF
by = (word >> 8) AND 0xFF
FOR len = 0 TO (64 - part) * 32 - 1
carry = seed AND 0x80000000
seed = (seed << 1) AND 0xFFFFFFFF
IF carry
seed = seed XOR 0x04C11DB7
dir = seed AND 0xFF
ENDIF
SWITCH dir AND 0x82
CASE 0x00:
by = (by + 1) AND 0x7F
ENDCASE
CASE 0x02:
bx = (bx + 1) AND 0x7F
ENDCASE
CASE 0x80:
by = (by - 1) AND 0x7F
ENDCASE
CASE 0x82:
bx = (bx - 1) AND 0x7F
ENDCASE
ENDSWITCH
drawPixel(bx, by, COLOR[part AND 3])
ENDFOR
ENDFOR
Realizacja referencyjna
Poniżej znajduje się niezawierająca odniesienia implementacja w JavaScript.
Tutaj możesz także zobaczyć animowaną wersję .
Wyjaśnienie i zasady
- Dane wyjściowe muszą zostać przycięte do 128 x 96, mimo że algorytm rysuje poza tym obszarem.
- Jeśli Twój język / platforma nie jest w stanie wydrukować dokładnych kolorów opisanych powyżej, musisz użyć kolorów, które są jak najbardziej zbliżone.
- Jeśli zdecydujesz się zastosować alternatywną metodę, nadal musisz wygenerować dokładnie ten sam wynik.
- Na wszelki wypadek: przesłanie oryginalnego kodu asemblera 6502 lub jakiejkolwiek nieznacznie zmodyfikowanej wersji jest niedozwolone.
- Czy potrafisz pokonać 250 bajtów? Miłego rysowania!
Odpowiedzi:
x86 opcode,
227224223 bajtówObraz:
źródło
0122 6681F7B71DC104 xor edi, 00001DB7
błąd znaleziony w W32Dasm8086 Zestaw - NASM (MBR) -
248245 bajtówźródło
xor dx,dx
i zmieniszmov bp,0xa000; mov es,bp
napush 0xa000; pop es
.PUSH imm
Excel VBA 32-bit,
1011720 bajtówWersja 49; Wynik Δ = 291 bajtów
Grał w golfa
Pełna
Sub
procedura, która nie pobiera danych wejściowych i wysyła Mona Lisę doActiveSheet
obiektu w zakresie[A1:DX96]
.Było dużo czarnej magii zaangażowany w golfa to w dół do jej aktualnego stanu, - nuty, niektóre sztuczki zaangażowane są prep sztuka pikseli , bit przesunięcia kolorów niejawna konwersja typu , a
kompresji bajtów jakobase64
kompresjaString
.Uwaga: To rozwiązanie zostało ograniczone do wersji 32-bitowej wersji programu Excel VBA jak
^
jestLongLong
dosłowna typu w wersji 64-bitowejUwaga: Drugi: ciąg znaków w linii 3 nie jest komentarzem, ponieważ
”
nie jest równoważny z"
Wydajność
Gif pokazujący wyjście do
ActiveSheet
momentuM
wywołania w bezpośrednim oknie VBE. Zauważ, że z powodu ograniczeń rozmiaru pliku tenrysunekgif ma mniej ramek niż faktycznie wyprodukowano.Bez golfa
Pełna nieprofesjonalna
sub
procedura, która nie pobiera danych wejściowych i wytwarza mona lisa przy użyciu metody opisanej powyżej naActiveSheet
obiekcieźródło
HTML + CSS + JavaScript (ES6), 499 bajtów
678...478475473465459455451447449 bajtówNigdzie nie jest blisko 250 bajtów, ale na pewno zadowoli mnie mniej niż 500 bajtów! Ogromne podziękowania dla @Arnauld i @Firefly za pomoc w grze w golfa tego potwora.
Aby uzyskać większą skalę, zamień CSS na:
Historia z komentarzami!
Świetnie się bawiłem, grając w kod referencyjny Arnaulda, a niektóre możesz znaleźć tutaj. Cieszyć się!
Pokaż fragment kodu
źródło
Befunge,
11311052 bajtówIstnieje wiele problemów, które sprawiają, że jest to trudny problem w Befunge:
Befunge ma tylko 2000 bajtów pamięci do pracy (wraz z kodem źródłowym), więc nie ma możliwości, abyśmy mogli wyrenderować cały obraz w pamięci przed wysłaniem go. Sposób obejścia tego problemu polega na wielokrotnym uruchamianiu algorytmu 96 razy, raz dla każdej linii. Każdy przebieg przechowuje tylko piksele potrzebne w bieżącej linii, które są następnie wyprowadzane na końcu przebiegu. To pozwala nam poradzić sobie z buforem pikseli o wielkości zaledwie 128 bajtów.
Befunge nie ma żadnych operacji. Wiele
AND
operacji można po prostu emulować za pomocą operatora modulo (np.a AND 0x7F
Można je zastąpića % 0x80
). JednakXOR
wymaga dość skomplikowane manipulacje bitów, co mamy do czynienia z jednym bajcie na raz, przy użyciu zestawu niestandardowych wzorów Hardcoded obsłużyć cztery bajty, których potrzebujemy. Na przykład do obliczeniaa XOR 0xC1
używamy wzoru:a + 0xC1 - (a/64%4*64 + a%2)*2
Interfejs TIO nie jest ograniczeniem percepcji jako takiej, ale nie jest w stanie obsługiwać rozszerzonych znaków ASCII w źródle, co byłoby najłatwiejszym sposobem przechowywania tabel pędzla i kolorów. Pracuję nad tym, generując te tabele jako listę liczb na stosie, a następnie mam małą pętlę inicjującą, która kopiuje wartości ze stosu do pamięci. Znaczną część mojego czasu spędziłem na grze w golfa przy tym stole, który zajmuje pierwsze pięć i pół linijki kodu.
Niestety, pomimo wszystkich moich starań, aby kod był zgodny z TIO i wybrałem format pliku, który można wyodrębnić z TIO ( PPM ), jest on zbyt wolny, aby wypełnić go w 60-sekundowym limicie czasu (prawdopodobnie algorytm jest uruchamiany 96 razy nie pomaga). Ale ponieważ generuje obraz linia po linii, powinieneś uzyskać wystarczającą ilość danych wyjściowych, aby odzyskać prawie połowę obrazu.
Wypróbuj online!
Jeśli nie masz lokalnej przeglądarki plików PPM, możesz łatwo przekonwertować ją na inny format za pomocą jednego z wielu konwerterów online. Jednym z przykładów jest Convertio .
źródło
Python 3,
544536523519518 bajtówJest to kolejna nieudolna wersja implementacji referencyjnej CCB60 w języku Python. Początkowo użyłem dużej liczby szesnastkowej do przedstawienia pędzla algorytmu, ale później zdałem sobie sprawę, że moje nieuzasadnione założenie, że reprezentacja ciągu Unicode nie zadziała w Pythonie, było fałszywe.
Początkowo myślałem, że moja liczba bajtów jest znacznie niższa, ale jak zauważyłem tylko ASCII , nie pamiętam, aby liczyć znaki Unicode jako więcej niż jeden bajt.
Wyjście (128 x 96)
Identyczny z wyjściem CCB60.
źródło
Java 7,
681677675626612610 bajtówWysyła następujący obraz w rozdzielczości 128x96:
Wiem, że nie ma nawet 250 bajtów, ale hej, to java
-2 bajty dzięki Zacharýowi
źródło
#Language, <s>Old Scores</s> Score Bytes
i 2 można dokonać kod nieco bardziej czytelne, dodając w fladze językowej formie<!-- language-all: lang-java -->
przed twój blok kodu0x04C11DB7
=>0x4C11DB7
i0x7f
=>127
. Nie zwariuj, gdy nie jest to potrzebne.C #,
960850 bajtówProsta kopia pseudo kodu z dodanym golfem. Wciąż jest wiele rzeczy do gry w golfa, ale chciałem opublikować swoją odpowiedź, aby piłka się potoczyła.
Wersja pełna / sformatowana:
źródło
var m = new Bitmap(128,96)
AE IU WAUGH WYPython 2.7;
880876 bajtów łącznie (łącznie z danymi)-4 bajty do 876 dzięki ZacharyT. (Mój interpreter pytona nie podobał się jego sugestii, by upuścić spacje między latami 80. i jeszcze innymi).
Sugestia Taylora Scotta, aby umieścić pędzel w bazie 10, jest doskonała, ale notjagan (w komentarzu) posunął swoją sugestię o krok dalej, używając rozszerzonego formatu liczb całkowitych Pythona w zapisie szesnastkowym. odpowiedź notjagana znajduje się w Pythonie 3 i jest to taka poprawa w stosunku do tego, co zrobiłem, że zasługuje na uznanie. Mam nadzieję, że opublikuje to jako osobną odpowiedź.
Wyjście do okna Tkinter. Bez skalowania obraz jest bardzo mały, ale skalowanie dodaje około kilkunastu bajtów.
Niewiele się tu dzieje poza tłumaczeniem na Python i podstawową grą w golfa. Czasami manipulacje bitowe są krótsze, czasem matematyka całkowita. Nie mogłem znaleźć sposobu na spakowanie większej ilości logiki do list lub tablic. Podstawowy algorytm jest już dość gęsty.
źródło
<!-- language-all: lang-py -->
80
„aelse
”. I czy0x00
to to samo0
, prawda?import
i*
.Tcl / Tk, 805
808815816819826839840843Wciąż przegrany, alemusiałem to zrobić! być może mogę później zagrać w golfa!Teraz nie przegrany!
Tcl / Tk, 1370
Bardzo nieokreślona transliteracja pseudokodu przed rozpoczęciem szału golfowego!
update
Linia sprawia, że możliwe, aby zobaczyć rysunek robione stopniowo!źródło
Python 3 + matplotlib, 541
To zapisuje obraz jako plik png „i”. Aby wyświetlić obraz, możesz zastąpić imsave imshow i show na 545 bajtów.
źródło
SmileBASIC,
454447444 bajtówCiąg „x” zawierał nieprawidłowe znaki Unicode, więc nie mogę go tutaj opublikować. Oto kody znaków w postaci dziesiętnej (tylko tablica BRUSH w odwrotnej kolejności):
8505, 11193, 11332, 40503, 9639, 38606, 12590, 44957, 49275, 9103, 45629, 7700, 44387, 16047, 36156, 21056, 32967, 44146, 47330, 6263, 59670, 16059, 2569, 1043, 21292, 45297, 10516, 35478, 45332, 45634, 21547, 54321, 12369, 54650, 3453, 32252, 41772, 10669, 2137, 35575, 41799, 37027, 38901, 57113, 9942, 15633, 8348, 8339, 40146, 53425, 640, 28853, 45146, 47166, 37752, 3773, 6923, 35473, 62875, 3644, 1835, 12187, 14270, 778
źródło
"xx...xx"
ciągu?: r4, 764 bajtów
źródło do uruchomienia w : r4 github
Używam sztuczki do wykonania ruchu bez warunków, przekształcam bit 8 na znak i przesuwam z bitem 2. wersja z nazwami stosu:
źródło
Yabasic,
790779 bajtówPodstawowa odpowiedź, że nie bierze wejścia i wyjścia w nowym oknie graficznym.
Wydajność
Poniżej skaluje się współczynnik 8
źródło