Powszechnie wiadomo, że osoba na siatce pod wpływem alkoholu ma równe szanse pójścia we wszystkich dostępnych kierunkach. Jednak to rozsądne stwierdzenie nie dotyczy królestwa bardzo małych pijaków, których zachowanie jest tak, jakby podejmowali oni każdą dostępną ścieżkę naraz, a możliwe ścieżki, które podążają, mogą kolidować ze sobą. Twoim zadaniem jest wyświetlenie możliwych pozycji takiego kwantowego pijaka po wykonaniu n
kroków.
Specyfikacja
Wspomniany pijak zajmuje kwadratową siatkę i może być uważany za 3-stanowy automat komórkowy wykorzystujący sąsiedztwo von Neumanna (w kształcie plus), które przestrzega tych prostych zasad:
Empty
idzie do,Awake
jeśli przylega do dokładnie jednegoAwake
, a w przeciwnym razie idzie doEmpty
Awake
idzie doSleeping
Sleeping
idzie doSleeping
Początkowy stan planszy to pojedynczy Awake
otoczony nieskończonym polem Empty
s.
Wyzwanie
Biorąc pod uwagę nieujemną liczbę całkowitą n
, po n
kroku utwórz reprezentację ASCII pijaka . Każdy stan powinien być reprezentowany przez inny charakter, a rozwiązania powinny określać, który znak oznacza, który stan. Jeśli używasz spacji do Empty
, nie musisz dołączać ich na końcu linii.
To jest golf golfowy , więc wygrywa najkrótsza odpowiedź. Obowiązują standardowe luki , dozwolone są początkowe i końcowe spacje, dozwolone są dane wyjściowe z tablicy znaków / tablicy znaków 2d itp.
Przykłady
Te przykłady używają dla
Empty
, @
dla Awake
i #
dla Sleeping
.
n=0
@
n = 1
@
@#@
@
n = 2
@
#
@###@
#
@
n = 3
@
@#@
@ # @
@#####@
@ # @
@#@
@
n=6
@
#
@###@
@#@
@ ### @
#@# # #@#
@###########@
#@# # #@#
@ ### @
@#@
@###@
#
@
n=10
@
#
@###@
@#@
###
# # #
#######
# ### #
@ ## ### ## @
#@# ### # ### #@#
@###################@
#@# ### # ### #@#
@ ## ### ## @
# ### #
#######
# # #
###
@#@
@###@
#
@
Ciekawa uwaga
Analizując sekwencję liczby zajętych komórek w OEIS, odkryłem, że pijak kwantowy jest izomorficzny w stosunku do znacznie lepiej zbadanej sekwencji wykałaczek . Jeśli potrafisz włączyć tę wiedzę do lepszego golfa, będę pod wrażeniem.
źródło
n=10
jest poprawna? Wypróbowałem kilka podejść i wszystkie otrzymały tę samą (niewłaściwą) odpowiedź, więc chcę się tylko upewnić. Trochę to wygląda, ale nie wiem.Odpowiedzi:
Wolfram Language (Mathematica) ,
9291 bajtówIdealne wyzwanie do korzystania z wbudowanego Mathematica
CellularAutomaton
!Wypróbuj online!
Pusty = 0, Przebudź = 1, Spanie = 2
Animacja pierwszych 256 iteracji (biały = pusty, szary = przebudzony, czarny = spanie):
Wyjaśnienie
Uruchom
CellularAutomaton
ze specyfikacjami ...Zastosuj 3-kolorową regułę totalistyczną 7049487784884 z sąsiedztwem von Neumanna ...
Na planszy z pojedynczym 1 na środku, z tłem 0 ...
Powtórz
<input>
czasy ({j#}
ocenia na{{{#}}}
). Macierz automatycznie się rozwija, jeśli komórka poza ramką nie jest taka sama jak tłoTa reguła pochodzi od liczby podstawowej 3
220221220221220221220221220
, co oznacza „zmień wszystko1
lub2
na2
i zmień0
na1
i tylko wtedy, gdy1
wokół niej jest nieparzysta liczba s”.Wydrukuj tablicę.
Pół-dowód „nieparzystych
1
” jest równoważny z „dokładnie jednym1
”:Rozważ tę siatkę pikseli 5x5. Biały to komórka
0
lub2
(nie obudzone piksele), a szary to1
komórka.Jeśli
1
komórka została wygenerowana wokół trzech0
komórek, siatka musi wyglądać następująco: ma trzy1
s ułożone w kształcie litery U (lub wersji obróconej) w następujący sposób:Ze względu na samopodobieństwo tego automatu komórkowego, każdy wzór pojawiający się w automacie komórkowym musi pojawić się na przekątnej (przez indukcję). Jednak ten wzór nie jest ukośnie symetryczny. tzn. nie może wystąpić na przekątnej i nie może pojawić się nigdzie w automacie komórkowym.
Przebudzenie / spanie są równoważne
Zauważ, że
0
komórka nie może być otoczona dokładnie jedną lub trzema2
komórkami i komórkami spoczynkowymi0
, ponieważ oznaczałoby to, że kilka kroków wcześniej komórka miała sąsiada z jedną lub trzema1
komórkami - i musiała zmienić się w1
już (sprzeczność). W związku z tym, że jest w porządku, aby ignorować różnicy między1
i2
a stan "zmienić wszystko1
, aby1
i0
do1
wtedy i tylko wtedy, gdy ma nieparzystą liczbę niezerowych sąsiadów.Powstały automat komórkowy jest rzeczywiście identyczny z oryginałem, jedyną różnicą jest to, że nie ma rozróżnienia między „przebudzonymi” i „uśpionymi” pijakami. Ten wzór jest opisany w OEIS A169707 .
Wypróbuj online!
Bezpośrednie porównanie pierwszych 16 iteracji:
Dodanie dwóch kolejnych iteracji daje wynik zgodny ze specyfikacją wyzwania (94 bajty):
Wypróbuj online!
źródło
Python 2 , 192 bajty
Wypróbuj online!
-17 bajtów dzięki Mr. Xcoder
-9 bajtów przy użyciu formatu wyjściowego Jonathana
-11 bajtów dzięki Lynn
-3 bajtów dzięki ovs
źródło
exec
zapisuje 9 bajtów i…for k in 0,1,2,3for…
zapisuje jeszcze jeden: Linkn=[C+k for k in-1j,1j,-1,1for C in c]
oszczędza jeszcze jeden bajt!X+Y*1jin
jest to coś, co tak naprawdę nie wydawało mi się możliwe: PC,
360354343319Nowe
#define
linie po nieliniach są tutaj tylko do prezentacji, więc nie są liczone. Dołączyłem funkcję otoki, więc jest to -6 (313), jeśli funkcja nie jest liczona i zakładasz, żen
pochodzi ona z innego miejsca.q(10)
wyjścia:Używanie
do pustych,
"
do spania i!
do przebudzenia.Działa to tak:
A(i,b,e)
to „∀i∈ [b, e).”,B(b,e)
to „∀r∈ [b, e) .∀c∈ [b, e).”Zauważ, że po n pokoleniach plansza ma 2 n + 1 kwadrat.
Ze względu na symetrię planszy, musi to tylko symulować prawą dolną ćwiartkę, więc przydzielamy macierz kwadratową n + 1 z 1 rzędem i kolumną wypełnienia dla późniejszego wyszukiwania sąsiada (więc n + 2).
Przydział za pomocą
calloc
pozwala nam jednocześnie pomnożyć szerokość przez wysokość i wyczyścić planszę0
(pusta).Podczas wyszukiwania komórki według jej współrzędnych (
C
iD
) używa bezwzględnej wartości wiersza i kolumny (W
) do automatycznego odzwierciedlenia współrzędnych.Tablica jest przechowywana jako tablica par liczb całkowitych reprezentujących obecne i poprzednie generacje. Liczby, o których mowa, są
char
, abyśmy mogli uniknąćsizeof
.Generacja najczęściej sprawdzana (test sąsiada) to generacja poprzednia, więc jest umieszczona w indeksie 0 w parze, aby można było uzyskać do niej dostęp
*
.Przy każdej generacji (
g
) bieżąca generacja jest kopiowana z poprzedniej generacji za pomocąB
pętli, a następnie nowa generacja jest generowana ze starej.Każda komórka jest reprezentowana za pomocą
0
pustych,1
przebudzonych i2
do spania. Zliczanie sąsiadów było pierwotnie obliczeniem liczby bitów ustawionych w niskich 4 bitach komórki, gdy 4 sąsiadów przesunięto i OR skasowano razem jako flagi (N
), używając16
do spania. Ale z obserwacją, że nieparzysta liczba sąsiadów odpowiada dokładnie 1 sąsiadowi, możemy zapisać kilka postaci, używając tylko maski z 1.Na końcu plansza jest drukowana w całości przez iterację w prawym dolnym kwadrancie przy użyciu tej samej sztuczki współrzędnych wartości bezwzględnej, bez dopełniania, aby nie drukować zewnętrznego dopełniania na planszy. Z tego powodu
B
pętla zawiera otwierający nawias klamrowy, ponieważ mamy dodatkową instrukcję nowego wiersza w zewnętrznej pętli.Kody ASCII dogodnie mapują 0 + 32 (puste) na spację, 2 + 32 (spanie) na
"
i 1 + 32 (przebudzenie) na!
.Podsumowując, myślę, że jest to zaskakująco czytelny golf ze względu na ładną strukturę problemu.
źródło
putchar(10)
zeputs("")
&~
Nie jest to NAND, miałem na myśli, że czasami myśleć!(a &~ b)
w kategoriacha NAND (NOT b)
, choć w tym przypadku logiczny!
nie jest taka sama jak bitowe~
ponieważ jesteśmy powołując się na0
lub1
wyniku!
.MATL , 39 bajtów
Wyświetla się
Empty
jako(spacja)
Awake
tak jak#
Sleeping
jak!
.Wypróbuj online! Możesz także obserwować, jak wzorzec rośnie w sztuce ASCII lub graficznie (zmodyfikowany kod).
Wyjaśnienie
Kod wykorzystuje liczb zespolonych
0
,1
,j
aby reprezentować trzy stany: pusta, budzenie, spanie odpowiednio.źródło
Befunge,
384304 bajtyWypróbuj online!
Problemem przy próbie zaimplementowania tego rodzaju funkcji w Befunge jest ograniczony rozmiar pamięci (2000 bajtów zarówno dla danych, jak i kodu). Musiałem więc użyć algorytmu, który oblicza poprawny znak dla dowolnej współrzędnej bez odniesienia do poprzednich obliczeń. Osiąga to poprzez rekurencyjne spoglądanie w przeszłość na wszystkie możliwe ścieżki, którymi pijak mógł podążać, aby osiągnąć ten punkt.
Niestety nie jest to szczególnie wydajne rozwiązanie. Działa, ale jest niesamowicie wolny i staje się wykładniczo wolniejszy wraz ze wzrostem wartości n . Więc chociaż może potencjalnie działać dla dowolnego n do około 127 (7-bitowy limit komórek pamięci Befunge), w praktyce nieuchronnie stracisz zainteresowanie czekaniem na wynik. W TIO osiągnie 60 sekundowy limit czasu na czymkolwiek większym niż około 6 (co najwyżej). Kompilator poradzi sobie znacznie lepiej, ale nawet wtedy prawdopodobnie nie chciałbyś iść dużo wyżej niż 10.
Mimo to pomyślałem, że warto go przesłać, ponieważ jest to całkiem niezła demonstracja rekurencyjnej „funkcji” w Befunge.
źródło
Python 2 , 214 bajtów
Wypróbuj online!
Wyjaśnienie
Zastosowania
0
dlaempty
,1
dlasleeping
i2
dlaawake
. Drukuje dwuwymiarową listę znaków (ciągi o jednej długości).Definiuje funkcję, która przyjmuje nieujemną liczbę całkowitą
n
. Sukcesywnie przesuwa automat komórkowy do osiągnięcia pożądanego stanu. Na koniec stosowana jest konwersja między wewnętrznymi wartościami całkowitymi a rzeczywistymi znakami.źródło
Lua ,
251242239238 bajtów-8 bajtów poprzez uproszczenie inicjalizatora tablicy kosztem dodatkowych wiodących białych znaków.
-1 bajt, zmieniając
c=i==2+...and print(s)
nac=i~=2+...or print(s)
.-3 bajty, budując najpierw kompletny ciąg i drukując raz na końcu.
-1 bajt dzięki Jonathan Frech przepisując
or(g(...)==1 and
jakoor(1==g(...)and
.Wypróbuj online!
Empty = Space
Awake =
1
Sleeping =
0
Pobiera dane z wiersza poleceń i drukuje na standardowe wyjście.
Reprezentując stany jak
false
/nil
,1
i0
wewnętrznie, wykrywanie „pusty” nie potrzeba żadnego kodu i „dokładnie jeden przebudzony” Kontrola może odbywać się tylko z dodatkiem.źródło
or(g(...)==1 and
może byćor(1==g(...)and
.APL (Dyalog) , 38 bajtów
Wypróbuj online!
-4 dzięki Adámowi .
-8 dzięki ngn .
źródło
Galaretka ,
3929 bajtówWypróbuj online!
Używa
0
,1
a2
do pustego czuwania i spania. Stopka w linku konwertuje to na,
@
i#
.ṬŒḄ
zamiastḤḶ=¹
.-
zamiast1N
. Również czyni¤
niepotrzebnym.S
zamiast+/
.Ḃ+Ḃ+
zamiast%3=1+=1Ḥ$+
. Teraz używa2
do spania zamiast3
.Wyjaśnienie nadchodzi ...
źródło
APL (Dyalog Classic) , 38 bajtów
Wypróbuj online!
oparty na rozwiązaniu Erika the Outgolfer
⍪1
to matryca 1x1 zawierająca 1⎕
ewaluowane dane wejściowe( )⍣⎕
zastosuj to wiele razy(⌽0,⍉)⍣4
surround 0s, czyli 4 razy do: transpose (⍉
), dodaj 0 po lewej stronie (0,
), odwróć w poziomie (⌽
)g←3+/0,,∘0
nazywamy to funkcją sumującą potrójne poziomeg
⍉∘g∘⍉
funkcja sumująca potrójne pionowe -g
podlegająca transpozycji2 | ⍉∘g∘⍉ + g←3+/0,,∘0
suma dwóch sum modulo 2⌈
tym większy między tym a ...2∘∧
LCM 2 i oryginalnej matrycy - zamienia 1s w 2s, zachowując 0s i 2sźródło
Perl 5 , 192 + 1 (
-n
) = 193 bajtówWypróbuj online!
Używa 0 dla pustych, 1 dla obudzonych i 2 dla uśpienia.
źródło
Rubin ,
164153 bajtyWypróbuj online!
Używa „” dla pustego, „@” dla wybudzania i „#” dla uśpienia (jak w przykładzie). Przypuszczam, że mógłbym zaoszczędzić 6 bajtów, używając liczb, ale wygląda to lepiej.
źródło
Pip ,
6961 bajtów60 bajtów kodu, +1 dla
-l
flagi.Przyjmuje
n
jako argument wiersza polecenia. Używa0
pustego,1
przebudzonego i2
do spania. (Aby uzyskać ładniejszy ASCII-art jak w przykładach Wyzwaniem jest, wymień końcowyy
z" @#"@y
).Wypróbuj online!
Wyjaśnienie
Ustawiać:
Główna pętla:
gdzie treść funkcji to:
Po zakończeniu pętli po prostu drukujemy automatycznie
y
.-l
Flaga oznacza, że lista jest zagnieżdżona drukowane przez złączenie zawartość każdego rzędu i oddzielenia rzędów ze znakami nowej linii.źródło
Java (OpenJDK 8) , 220 bajtów
Wypróbuj online!
Uwaga: zwrócona tablica zawiera ramkę lub
'\0'
znaki. Ponieważ samolot ma być nieskończony, używana jest tylko granica.Mapowanie postaci:
(spacja)
=
0
Oszczędza
źródło
@
kontroli, a ty znalazłeś klucz! Miły.char
-Cast był całkowity nadzór ze mną.Python,
199192 bajtówTen kod działa zarówno w Pythonie 2, jak i Pythonie 3, ale używa popularnej biblioteki Numpy innej firmy do obsługi tablicy.
print(f(6))
wyjściaJeśli chcesz ładniejszego drukowania, możesz to nazwać w ten sposób:
który drukuje przy użyciu tych samych znaków, jakie podano w pytaniu.
źródło
[e]ach state should be represented by a different character
(interpretujęcharacter
jako rzeczywisty znak ASCII, a nie liczbę całkowitą).