Wprowadzenie
Jest poborca podatkowy, który ma pewne problemy z zarządzaniem podatkami swojego królestwa: zapisy historyczne spłonęły w wielkim pożarze.
Chce dowiedzieć się, ile może istnieć przeszłości, jeśli chodzi o to, skąd odziedziczyły obecne pieniądze. Na szczęście jego królestwo jest bardzo proste.
Królestwo można modelować za pomocą macierzy boolowskiej 2D, w której l
reprezentuje ktoś, kto odziedziczył pieniądze, i O
reprezentuje kogoś, kto tego nie zrobił. Na przykład:
l O l l
O O O l
l O l O
O O O l
(Zawsze będzie to prostokąt)
W następnym pokoleniu królestwo jest mniejsze (wilki są silne!).
Następna generacja wyglądałaby tak, nałożona na poprzednią generację ( x
jest symbolem zastępczym dla potomka w następnej generacji)
l O l l
x x x
O O O l
x x x
l O l O
x x x
O O O l
Potomek będzie patrzeć na przodków, które są bezpośrednio wokół nich (So lewym górnym rogu x
będzie zobaczyć { l
, O
, O
, O
}, zwany aligné prostokątne sąsiedztwo )
Jeśli tylko jeden przodek odziedziczył pieniądze, potomek odziedziczy je od nich. Jeśli więcej niż jeden przodek odziedziczy pieniądze, będą się kłócić, a potomek nie odziedziczy pieniędzy. Jeśli nikt nie odziedziczył pieniędzy, potomek nie odziedziczy żadnych pieniędzy.
(Więcej niż jeden potomek może odziedziczyć po jednym przodku)
Tak więc następna generacja wyglądałaby następująco:
l l O
l l O
l l O
Wyzwanie
Wejście
Obecny stan generacji, jako tablica tablic o dowolnych dwóch odrębnych wartościach, przy czym tablice wewnętrzne mają tę samą długość.
Na przykład w powyższym przykładzie może to być:
[
[True, True, False],
[True, True, False],
[True, True, False]
]
Wynik
Liczba całkowita reprezentująca liczbę unikalnych poprzednich generacji, przy czym wejście nowej generacji jest wejściem.
Możesz założyć, że odpowiedź będzie zawsze mniejsza niż 2 ^ 30 - 1. (lub 1073741823).
Poprzednia generacja nazywa się „preimage”, a tym wyzwaniem byłoby policzyć preimage .
Punktacja
To jest najszybszy kod wyzwanie, więc każde zgłoszenie zostanie przetestowane na moim komputerze, a zgłoszenie, które zajmie najmniej czasu, będzie zwycięzcą.
Przykład wejścia i wyjścia
(Gdzie 1
jest potomek, który odziedziczył pieniądze i 0
jest potomkiem, który nie odziedziczył pieniędzy)
Wejście:
[[1, 0, 1],
[0, 1, 0],
[1, 0, 1]]
Wynik:
4
Wejście:
[[1, 0, 1, 0, 0, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0],
[1, 1, 1, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 1, 1, 1]]
Wynik:
254
Wejście:
[[1, 1, 0, 1, 0, 1, 0, 1, 1, 0],
[1, 1, 0, 0, 0, 0, 1, 1, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 1, 1, 0, 0]]
Wynik:
11567
źródło
Odpowiedzi:
C ++ przy użyciu biblioteki BuDDy
Wydawało się, że to dobra wymówka do gry z binarnymi diagramami decyzyjnymi . Królestwo przekształca się w wielką formułę logiczną, w której musimy policzyć liczbę sposobów, w jakie można go spełnić. Można to (czasem) zrobić bardziej efektywnie, niż się wydaje.
Królestwo należy podać jako stałą programu jako płaską tablicę i wyraźnie podane wymiary. (Ładne wejście pozostało jako wykonanie dla czytelnika :-)
Oto zawstydzająco prosty kod:
Aby skompilować z debianem 8 (jessie), zainstaluj
libbdd-dev
i wykonajg++ -std=c++11 -o hist hist.cpp -lbdd
. (Optymalizacja opcji nie robi prawie żadnej różnicy, ponieważ prawdziwa praca jest wykonywana w bibliotece).Wielkie przykłady mogą prowadzić do komunikatów na temat wyrzucania elementów bezużytecznych. Można je stłumić, ale wolę je widzieć.
bdd_satcount
zwraca adouble
, ale jest to wystarczająco dobre dla oczekiwanego zakresu wyników. Ta sama technika liczenia jest możliwa przy dokładnych (dużych) liczbach całkowitych.Kod jest zoptymalizowany dla
ROWS<COLS
. Jeśli masz dużo więcej wierszy niż kolumn, dobrym pomysłem może być transpozycja macierzy.źródło
Python 2.7
To tylko naiwna pierwsza próba. Nie jest to szczególnie szybkie, ale jest poprawne.
Pierwszą obserwacją jest to, że każda komórka jest zależna od dokładnie czterech komórek w poprzedniej generacji. Możemy przedstawić te cztery komórki jako liczbę 4-bitową (0–15). Zgodnie z regułami, jeśli dokładnie jedna sąsiednia komórka w poprzedniej generacji jest
1
, to dana komórka w bieżącej generacji będzie1
, w przeciwnym razie będzie0
. Ci odpowiadają potęgi dwójki, a mianowicie[1, 2, 4, 8]
. Gdy czterech przodków jest reprezentowanych jako liczba 4-bitowa, każda inna liczba spowoduje0
w bieżącej generacji. Dzięki tym informacjom, po zobaczeniu komórki w bieżącym pokoleniu, możemy zawęzić możliwości sąsiedztwa w poprzednim pokoleniu odpowiednio do jednej z czterech lub jednej z dwunastu możliwości.Wybrałem reprezentowanie okolicy w następujący sposób:
gdzie 0 jest najmniej znaczącym bitem i tak dalej.
Drugą obserwacją jest to, że w przypadku dwóch sąsiednich komórek w bieżącym pokoleniu dwie dzielnice poprzedniej generacji pokrywają się:
lub:
W przypadku poziomym
2
lewe sąsiedztwo zachodzi3
na prawe sąsiedztwo i podobnie z0
lewym i1
prawym. W przypadku pionowym1
górne sąsiedztwo pokrywa się3
z dolnym sąsiedztwem i podobnie z0
górnym i2
dolnym.To nakładanie się oznacza, że możemy zawęzić możliwości dla jeszcze nie wybranych dzielnic w oparciu o to, co już wybraliśmy. Kod działa w sposób od lewej do prawej, od góry do dołu, w rekurencyjnym poszukiwaniu głębokości w poszukiwaniu możliwych obrazów. Poniższy diagram wskazuje, które poprzednie sąsiedztwa musimy wziąć pod uwagę, patrząc na możliwe sąsiedztwa bieżącej komórki:
Oto kod:
Aby uruchomić:
źródło
O(<something>^n)
tak myślę.)