Wprowadzenie
W tym wyzwaniu macierz 2 × 2 jest indeksowana w następujący sposób:
0 1
2 3
Definiujemy rodzinę wzorów podobnych do fraktali F(L)
, gdzie L
znajduje się n
lista tych wskaźników i F(L)
ma ona rozmiar .2n-1 × 2n-1
- Jeśli
L == []
, toF(L)
jest wzór 1 × 1#
. Jeśli
L != []
, toF(L)
jest zbudowany w następujący sposób. NiechP
będzie wzorem uzyskanymL
po usunięciu pierwszego elementu. Weź cztery siatki wielkości wypełnione kropkami i zastąp siatkę indeksowaną wzorem . Następnie sklej siatki razem za pomocą jednej warstwy haszów między nimi. Oto schematy czterech przypadków:2n-1-1 × 2n-1-1
.
L[0]
P
#
L[0]==0 L[0]==1 L[0]==2 L[0]==3 #... ...# ...#... ...#... [P]#... ...#[P] ...#... ...#... #... ...# ...#... ...#... ####### ####### ####### ####### ...#... ...#... #... ...# ...#... ...#... [P]#... ...#[P] ...#... ...#... #... ...#
Przykład
Rozważ dane wejściowe L = [2,0]
. Zaczynamy od siatki 1 × 1 #
i przesuwamy L
od prawej. Najbardziej wysunięty na prawo element to 0
, więc bierzemy cztery kopie siatki 1 × 1 .
, zastępujemy pierwszą #
i sklejamy je haszami. Daje to siatkę 3 × 3
##.
###
.#.
Kolejnym elementem jest 2
, więc bierzemy cztery kopie siatki 3 × 3 .
s i zastępujemy trzecią powyższą siatką. Cztery siatki są
... ... ##. ...
... ... ### ...
... ... .#. ...
i sklejenie ich razem z #
wynikami s w siatce 7 × 7
...#...
...#...
...#...
#######
##.#...
####...
.#.#...
To jest nasz końcowy wynik.
Wejście
Twój wkład jest listą L
indeksów 0, 1, 2, 3
. Możesz wziąć to jako listę liczb całkowitych lub ciąg cyfr. Pamiętaj, że może być pusty i może zawierać duplikaty. Długość L
wynosi co najwyżej 5.
Wynik
Twój wynik to wzorzec F(L)
jako ciąg rozdzielany znakiem nowej linii.
Zasady i punktacja
Możesz napisać pełny program lub funkcję. wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.
Przypadki testowe
[]
#
[0]
##.
###
.#.
[3]
.#.
###
.##
[2,0]
...#...
...#...
...#...
#######
##.#...
####...
.#.#...
[1,1]
...#.##
...####
...#.#.
#######
...#...
...#...
...#...
[1,2,0]
.......#...#...
.......#...#...
.......#...#...
.......########
.......###.#...
.......#####...
.......#.#.#...
###############
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
[3,3,1]
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
###############
.......#...#...
.......#...#...
.......#...#...
.......########
.......#...#.##
.......#...####
.......#...#.#.
[0,1,2,3]
.......#...#...#...............
.......#...#...#...............
.......#...#...#...............
.......#########...............
.......#.#.#...#...............
.......#####...#...............
.......#.###...#...............
################...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
###############################
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
[0,0,1,2,3]
.......#...#...#...............#...............................
.......#...#...#...............#...............................
.......#...#...#...............#...............................
.......#########...............#...............................
.......#.#.#...#...............#...............................
.......#####...#...............#...............................
.......#.###...#...............#...............................
################...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
################################...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
###############################################################
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
#
?L !=[]
w tym przykładzie, ponieważ ma 1 lub więcej elementów. Czy to znaczy, że F (L) jest zawsze#
w pierwszej kolejności?L = [2,0]
odetniesz głowę i spojrzysz na wzórF([0])
, a następnie odetniesz głowę[0]
i spojrzysz na wzórF([])
, który jest siatką 1x1#
. Następnie użyj na nim odciętego indeksu0
, aby zbudować wzór 3x3, i użyj na nim odciętego indeksu2
, aby zbudować wzór 7x7. Aby odpowiedzieć na twoje pytanie: tak, zawsze zaczynasz od siatki 1x1, ponieważ jest to podstawowy przypadek rekurencji.Odpowiedzi:
CJam,
5947434140 bajtówDzięki Sp3000 za oszczędność 1 bajtu.
Sprawdź to tutaj.
Wyjaśnienie
Nieco przestarzałe. Naprawię później.
Wszystkie zmiany kolejności wymiarów list 4D powodują zawroty głowy ...
Ten kod implementuje specyfikację bardzo dosłownie, używając iteracyjnego algorytmu z sekcji przykładu zamiast jego rekurencyjnej definicji. Jedną z głównych sztuczek golfowych jest to, że używam spacji zamiast
#
podczas obliczeń i zastępuję je tylko#
na końcu, co upraszcza kod w jednym miejscu i pozwala mi używaćS
zamiast'#
lub"#"
w kilku.źródło
MATL ,
4241 bajtówWypróbuj online!
Wyjaśnienie
Działa to iteracyjnie przy użyciu produktu Kronecker w celu rozszerzenia tablicy w każdej iteracji. Tablica jest zbudowana z
0
i1
zamiast.
i#
, a na końcu są one zastępowane odpowiednimi znakami.Będzie tyle iteracji, co rozmiar wejściowy. Dane wejściowe są przetwarzane od prawej do lewej. Indeks iteracji zaczyna się od
1
.Korzystając z przykładu w wyzwaniu, z
[2,0]
danymi wejściowymi tablica jest inicjalizowana jakoOdpowiada to początkowej
1
(#
) rozszerzonej o jeden wiersz i jedną kolumnę, której cel zostanie wyjaśniony później. Wartości w tych kolumnach nie są ważne, ponieważ zostaną zastąpione; mogą to być również:Przy każdej iteracji istniejąca tablica jest mnożona przez Kroneckera przez tablicę 2 × 2 zero-jeden, która zawiera
1
w pozycji wskazanej przez bieżącą pozycję wejścia, a0
przy innych pozycjach. W przykładzie z iteracją i = 1, ponieważ pozycja wejściowa najbardziej na prawo to0
tablica zero-jedynkowaa produktem Kronecker tych dwóch tablic jest
Następnie wiersz i kolumna z indeksem
2^i
są wypełniane jednymi:Pierwsze trzy wiersze i kolumny stanowią wynik pierwszej iteracji. Tak jak poprzednio, istnieje dodatkowy wiersz i kolumna, które są przydatne do rozszerzenia tablicy w następnej iteracji.
Przy iteracji i = 2, ponieważ bieżąca wartość wejściowa zawiera
2
tablicę powyżej, pomnożono przez Kroneckeraco daje
Wypełnienie
2^i
-tego wiersza i kolumny jedynkami dajePonieważ jest to ostatnia iteracja, dodatkowy wiersz i kolumna są usuwane:
a zmiana postaci odbywa się w celu uzyskania końcowego wyniku:
Szczegółowy opis kodu wygląda następująco:
źródło
Haskell,
123122 bajtówPrzykład użycia:
Jak to działa:
źródło
JavaScript (ES6),
171152 bajtówPobiera wynik wywołania rekurencyjnego, a następnie zastępuje każdą linię samym sobą oraz skrót i ciąg kropek o tej samej długości, w razie potrzeby w odwrotnej kolejności, a następnie z tego wyniku częściowego tworzy ciąg kropek z wyjątkiem znaków nowej linii i środkowej kolumny skrótów, a także ciąg skrótów z otaczającymi znakami nowej linii, a następnie łączy te trzy ciągi razem w odpowiedniej kolejności.
źródło
Rubin,
143134 bajtówAnonimowa funkcja.
1 bajt zapisany przez przegrupowanie pierwszej linii. 6 bajtów zapisanych przez zmianę sposobu zwiększania wartości z z formuły do tabeli. 2 bajty zapisane przez wyeliminowanie zmiennej
w
.Niegolfowany w programie testowym
źródło
Rubinowy, 150 bajtów
Funkcja anonimowa. Używa wywołania rekurencyjnego, aby zbudować listę ciągów, jeden ciąg w wierszu, a następnie łączy je wszystkie razem na końcu.
źródło
Python 3.5, 1151 bajtów:
Niewiele golfa kodowego, ale no cóż. Postaram się przycinać to z czasem, gdy będę mógł.
Jest to dość naiwny sposób, ale jednak obecnie działa idealnie i, jak widać, nie używa zewnętrznych modułów / bibliotek. Dodatkowo, można go wziąć na drodze więcej niż 5 pozycji w podanej listy
s
bez utraty dokładności (czyli jeśli Twój sprzęt może obsłużyć). Spełnia wszystkie wymagania i nie mógłbym być bardziej zadowolony z tego, co dostałem. :)Może teraz akceptować nie tylko dowolną liczbę w zakresie
0=>3
jako dowolną z wartości, ale także dowolną liczbę , kropkę, dzięki&
operatorowi bitowemu! Możesz przeczytać więcej o nich tutaj . Teraz, na przykład,[4,4,1,2,3]
ponieważ lista wejściowa jest taka sama jak[0,0,1,2,3]
.Uwaga: Dane wejściowe należy podać w postaci listy
Nieoznakowany z wyjaśnieniem:
Szersze i znacznie bardziej atrakcyjne wizualnie wyjaśnienie:
Aby uzyskać szersze i znacznie bardziej atrakcyjne wizualnie wyjaśnienie, rozważ drugi raz przejście przez „główną” pętlę w powyższym kodzie, w którym znajduje się lista wejściowa
[0,2]
. W takim przypadku elementy na liście „głównej”l
to:i
i lista
y
zawierałaby tylko0
. Korzystając ze sposobu, w jaki Python indeksuje ostatni element siatkil[-1]
, możemy oznaczyć skrajnie lewe elementy siatki w następujący sposób:Jaki widzisz wzór? Każdy indeks po lewej stronie siatki jest wielokrotnością liczby 8, a ponieważ przy użyciu równania
2^(n-1)-1
uzyskuje się długość każdego segmentu kropek w siatce, możemy((2^(n-1)-1)*2)+2
znaleźć długość górnej krawędzi siatki jako całości (+2, aby uwzględnić środkowe#
s i\n
koniec). Możemy użyć tego równania, które wywołamy,i
aby znaleźć wartości indeksu każdego elementu po lewej stronie siatki o dowolnym rozmiarze, tworząc listę i dołączając do niej każdą liczbę całkowitą, którą nazwiemy_
w zakresie0=>length of grid l[-1]
, tak, że ten element jest wielokrotnościąi
, ORAZ również taki,_
który NIE jest równyi*(2^(n-1)-1)
, abyśmy mogli wykluczyć środkowy segment#
s oddzielając górną połowę od dolnej połówki. Ale chcemy WSZYSTKICH elementów kropkowych od lewej, a nie tylko elementów po lewej stronie. Cóż, jest to poprawka, a byłoby to po prostu dołączyć do listy listę zawierającą,i+h
gdzie h jest każdą liczbą całkowitą w zakresie za0=>2^(n-1)
każdym razem, gdy wartość z zakresu0=>length of grid l[-1]
jest dodawana do listy, aby za każdym razem pojawiała się tyle wartości dodanych do listy, ile długość jednej ćwiartki kropek. I to jest listaa
.Ale teraz, co powiesz na kropki po prawej stronie? Spójrzmy na indeksowanie w inny sposób:
Jak widać, wartości znajdujące się pośrodku to te, których potrzebujemy, ponieważ są one początkiem indeksu każdego segmentu kropek po prawej stronie siatki. Jaki jest tutaj wzór? Cóż, jeśli nie jest to wystarczająco oczywiste, teraz wszystkie środkowe wartości są wielokrotnościami
i/2
! Dzięki tym informacjom możemy teraz utworzyć kolejną listę,b
do któreji/2
dodawane są wielokrotności z zakresu,0=>length of grid l[-1]
tak że każda liczba całkowita z tego zakresu, który ponownie wywołamy_
, NIE jest równa(i/2)*(p*2)
wykluczeniu linii#
s oddzielającej górę i dolne połówki ORAZ takie, że _ NIE jest już na liście a, ponieważ tak naprawdę nie potrzebujemy 8,16,32 itd. na liścieb
. A teraz znowu nie chcemy tylko tych konkretnych indeksów. Chcemy WSZYSTKICH znaków kropek po prawej stronie siatki. Cóż, tak jak zrobiliśmy to na liściea
, tutaj możemy również dodać do listb
listy,_+h
gdzieh
jest liczba całkowita z zakresu0=>2^(n-1)
.Teraz mamy obie listy
a
ib
zapakowane i gotowe do pracy. Jak moglibyśmy je teraz połączyć? To gdzie wymieniaW
,T
,G
, iC
przyjść. Będą one posiadać indeksy do każdej ćwiartce określonej ilości punktów w siatcel[-1]
. Na przykład, zarezerwujmy listęW
jako listę dla wszystkich indeksów równych kwadrancie 1 (indeks 0) siatki. Na tej liście dodalibyśmy wtedy pierwsze2^(n-1)
listy z listya
, ponieważ listaa
zawiera wszystkie indeksy kropek w lewej połowie siatki, a następnie dzieli je wszystkie, abyW
teraz zawierały(2^(n-1))*(2^(n-1))
elementy. Zrobilibyśmy to samo dla listyT
, ale z tą różnicą,T
że zawierałaby elementy z listyb
, ponieważT
jest zarezerwowany dla kwadrantu 2 (indeks 1). ListaG
byłaby taka sama jak listaW
, z tym że zawierałaby resztę elementów z listya
, a listaC
jest taka sama jak listaT
, z tym że zawiera teraz resztę elementów z listyb
. I to wszystko! Mamy obecnie wartości indeksu dla każdej ćwiartki zawierającej kropki w siatce, wszystkie podzielone na cztery listy odpowiadające każdej ćwiartce. Teraz możemy użyć tych 4 list (W, T, G, C), aby powiedzieć programowi, które znaki powinien zastąpić w siatcel[-1]
przy każdym znaku z siatkil[0]
, co jest pierwszym elementem listyl
. Ponieważ wartość jest0
tutaj, zastąpiłaby wszystkie kropki w pierwszej ćwiartce (indeks 0)l[0]
listą wykorzystującą siatkęW
.Dlatego wreszcie mamy następujące:
Uff! Długi proces, prawda? Działa to jednak doskonale i znów nie mogę być szczęśliwszy. :)
źródło