period
Z ciągiem jest najkrótsza niezerowe przesunięcie tak, że ciąg pasuje do siebie, ignorując wszelkie części nawisu. Na przykład abcabcab
ma kropkę 3
. Zgodnie z konwencją mówimy, że jeśli nie ma takiego przesunięcia, łańcuch ma okres równy jego długości. Więc okres abcde
jest 5
i okres a
jest 1
.
Mówiąc bardziej formalnie, okres ciągu znaków S
jest minimalny, i > 0
więc S[1,n-i] == S[i+1,n]
(indeksowanie od 1
).
Dla danego ciągu S potęgi dwóch długości obliczymy okres wszystkich jego prefiksów potęgi dwóch długości. Rozważmy na przykład S = abcabcab
. Okresy, które obliczymy, to:
'a', 1
'ab', 2
'abca', 3
'abcabcab', 3
To znaczy po prostu wyprowadzimy tablicę okresów [1, 2, 3, 3]
.
Dla danej dodatniej mocy dwóch n
rozważ wszystkie możliwe ciągi binarne S
. Przypomnij sobie, że ciąg binarny jest po prostu ciągiem 1
s i 0
s, więc istnieją dokładnie 2^n
takie ciągi (czyli 2
do potęgi n
). Dla każdego z nich możemy obliczyć tę tablicę okresów.
Wyzwanie polega na napisaniu kodu, który pobiera
n
(potęga dwóch) danych wejściowych i oblicza, ile jest różnych takich tablic.
Odpowiedzi na n = 1, 2, 4, 8, 16, 32, 64, 128
to:
1, 2, 6, 32, 320, 6025, 216854, 15128807
Pełny zestaw różnych tablic okresowych dla n = 4
:
1, 1, 1
1, 1, 3
1, 1, 4
1, 2, 2
1, 2, 3
1, 2, 4
Wynik
Uruchomię Twój kod na moim komputerze z systemem Ubuntu przez 10 minut. Twój wynik jest największy, n
dla którego Twój kod kończy się w tym czasie. W przypadku remisu n
wygrywa odpowiedź, która zakończy wspólne największe najszybsze. W przypadku remisu w czasie 1 sekundy wygrywa pierwsza opublikowana odpowiedź.
Języki i biblioteki
Możesz użyć dowolnego dostępnego języka i bibliotek, które ci się podobają. Proszę podać pełne wyjaśnienie, w jaki sposób uruchomić / skompilować kod w systemie Linux, jeśli to w ogóle możliwe
Twój kod powinien w rzeczywistości obliczać odpowiedzi, a nie na przykład generować wstępnie obliczonych wartości.
Wiodące wpisy
- 2 minuty i 21 sekund dla n = 128 w języku C # autorstwa Petera Taylora
- 9 sekund dla n = 32 w Rust przez isaacg
n
, czy zaakceptowałbyś go? Nie jest dobrze określone, gdzie jest granica między kodowaniem na twardo a faktycznym przetwarzaniem.abcab
. Wszystkie oprócz ostatnich 3 liter sąabcab
. Te pasują i usunięcie mniejszej liczby liter nie pasuje.Odpowiedzi:
C #, n = 128 w około 2:40
Rozszerzenie do n = 256 wymagałoby przełączenia
BigInteger
na maski, co prawdopodobnie zabija wydajność zbyt mocno, aby n = 128 mógł przejść bez nowych pomysłów, nie mówiąc już o n = 256.Pod Linuksem kompiluj
mono-csc
i wykonuj za pomocąmono
.Podstawowe wyjaśnienie
Nie zamierzam dokonywać szczegółowej analizy, tylko przegląd pojęć.
Zasadniczo chętnie powtarzam w kolejności 2 50 elementów w programie kombinatorycznym typu brute-force. Aby dostać się do n = 128, konieczne jest zatem zastosowanie podejścia, które nie analizuje każdego ciągu bitów. Więc zamiast pracować naprzód od ciągów bitów do sekwencji kropek, pracuję wstecz: czy biorąc pod uwagę sekwencję kropek, czy istnieje ciąg bitów, który to realizuje? Dla n = 2 x jest łatwa górna granica 2 x (x + 1) / 2 sekwencji okresowych (w porównaniu do 2 2 x ciągów bitów).
Niektóre argumenty używają lematu okresowości łańcucha :
Wlog Zakładam, że wszystkie rozważane ciągi bitów zaczynają się od
0
.Biorąc pod uwagę sekwencję okresów, w której występuje okres prefiksu o długości 2 i ( zawsze), istnieją pewne łatwe obserwacje dotyczące możliwych wartości :
[p1 p2 ... pk]
pi
p0 = 1
pk+1
pk+1 ≥ pk
ponieważ okres ciągu znakówS
jest również okresem dowolnego prefiksuS
.pk+1 = pk
jest zawsze możliwym rozszerzeniem: wystarczy powtórzyć ten sam prymitywny ciąg dla dwóch razy większej liczby znaków.2k < pk+1 ≤ 2k+1
jest zawsze możliwym rozszerzeniem. Wystarczy to wykazać, ponieważ aperiodyczny ciąg długości można przedłużyć do aperiodycznego ciągu długości , dodając dowolną literę, która nie jest jego pierwszą literą.pk+1 = 2k+1
L
L+1
Weź łańcuch
Sx
o długości 2 k, którego okres jest, i rozważ łańcuch o długości 2 k + 1 . Wyraźnie ma na okres 2 k +1. Załóżmy, że jego okres jest krótszy.pk
SxyS
SxyS
q
Zatem przez okresowość lemat jest także okresem , a ponieważ największy dzielnik jest mniejszy lub równy swoim argumentom i jest najmniejszym okresem, musimy mieć odpowiedni współczynnik 2 k +1. Ponieważ jego iloraz nie może wynosić 2, mamy .
2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)
gcd(2k+1, q)
SxyS
q
q
q ≤ (2k+1)/3
Teraz, ponieważ jest to okres, który musi być okresem . Ale okres jest . Mamy dwa przypadki:
q ≤ 2k
SxyS
Sx
Sx
pk
gcd(pk, q) = pk
lub równo dzieli się na .pk
q
pk + q > 2k + gcd(pk, q)
aby lemat okresowości nie wymuszał krótszego okresu.Rozważ najpierw drugi przypadek. , co jest sprzeczne z definicją okresu . Dlatego jesteśmy zmuszeni dojść do wniosku, że jest to czynnik .
pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2q
pk
Sx
pk
q
Ale ponieważ
q
jest to okresSx
i jest to okres , prefiks długości jest tylko kopią prefiksu długości , więc widzimy, że jest to również okres .pk
Sx
q
q/pk
pk
pk
SxyS
Dlatego okres
SxyS
wynosi albo 2 k +1. Ale mamy dwie opcje ! Co najwyżej jeden wybór da okres , więc co najmniej jeden da okres 2 k +1. CO BYŁO DO OKAZANIA.pk
y
y
pk
Lemat okresowości pozwala nam odrzucić niektóre z pozostałych możliwych rozszerzeń.
Każde rozszerzenie, które nie przeszło testu szybkiego akceptowania lub szybkiego odrzucania, musi zostać przetestowane konstruktywnie.
Konstrukcja łańcucha bitów w sekwencji okresu jest zasadniczo problemem satysfakcji, ale ma wiele struktur. Istnieją proste ograniczenia równości implikowane przez każdy okres prefiksu, więc używam struktury danych zbioru unii do łączenia bitów w niezależne klastry. To wystarczyło, aby pokonać n = 64, ale dla n = 128 konieczne było pójście dalej. Używam dwóch użytecznych argumentów:
2k - pk
M
jest i prefiks długości ma kropkę, to prefiks długości musi kończyć się na . Jest to najsilniejsze właśnie w przypadkach, które w innym przypadku miałyby najbardziej niezależne klastry, co jest wygodne.01M-1
L > M
L
L
1M
M
jest, a prefiks długości ma kropkę z i kończy się w, to tak naprawdę musi on kończyć się na . Jest to najsilniejsze w przeciwnej skrajności, gdy sekwencja okresu zaczyna się od wielu.0M
L > M
L - d
d < M
0d
10d
Jeśli nie otrzymamy natychmiastowej sprzeczności, zmuszając klaster z pierwszym bitem (zakładanym jako zero) do jednego, wówczas brutalnie działamy (z pewnymi mikrooptymalizacjami) nad możliwymi wartościami dla niewymuszonych klastrów. Zauważ, że kolejność jest w malejącej liczby tych, bo jeśli
i
ty bit jest jeden, to okres ten nie może byći
i chcemy uniknąć okresów, które są krótsze niż te, które są już egzekwowane przez klastry. Zejście w dół zwiększa szanse na wcześniejsze znalezienie ważnego zadania.źródło
Rust, 32, 10s
11s29sna moim laptopieWywołaj to z bitowym rozmiarem jako argumentem wiersza poleceń.
Sprytne techniki: reprezentuj ciągi bitów bezpośrednio jako liczby, użyj bittwiddling, aby sprawdzić cykle. Przeszukuj tylko pierwszą połowę ciągów bitów, zaczynających się od 0, ponieważ tablica okresów ciągu bitów i jego odwrotności (0 zamienionych na 1s) są identyczne. Jeśli pojawiła się już każda możliwość uzyskania ostatecznej pozycji, nie szukam jej.
Bardziej sprytne rzeczy:
Aby deduplikować każdy blok (ciągi, w których pierwsza połowa bitów jest taka sama), używam bitvectora, który jest znacznie szybszy niż hashset, ponieważ końcowe długości cyklu nie wymagają haszowania.
Pomijam też pierwsze kroki sprawdzania cyklu, ponieważ wiem, że ostatni cykl nie może być krótszy niż cykl od drugiego do ostatniego.
Po wielu profilach mogę teraz stwierdzić, że prawie cały czas jest produktywnie wykorzystywany, więc myślę, że w tym przypadku konieczne będą ulepszenia algorytmów. Zmieniłem również na 32-bitowe liczby całkowite, aby zaoszczędzić trochę czasu.
Umieść
bit-vec = "0.4.4"
swój Cargo.tomlJeśli chcesz to uruchomić, sklonuj to: github.com/isaacg1/cycle, a następnie
Cargo build --release
skompiluj, a następnieCargo run --release 32
uruchom.źródło
time
daje mi 27 sekund użytkownika na moim laptopie.Rdza , 16
Wypróbuj online!
Kompilacja:
rustc -O <name>.rs
Ciąg jest implementowany jako wektor Bool.
next
Funkcja iterację kombinacji;find_period
Bierze kawałek Bool i zwraca okresu;compute_count_array
Nie praca dla każdego „mocą dwóch” podciąg każdej kombinacji Bools.Teoretycznie nie oczekuje się przepełnienia, dopóki nie
2^n
przekroczy maksymalnej wartości u64, tjn > 64
. Limit ten można przekroczyć kosztownym testem na s = [prawda, prawda, ... prawda].Zła wiadomość: zwraca 317 dla n = 16, ale nie wiem dlaczego. Nie wiem też, czy to zajmie dziesięć minut dla n = 32, ponieważ
Vec<bool>
nie jest zoptymalizowane dla tego rodzaju obliczeń.EDYTOWAĆ
Udało mi się usunąć limit 64 dla
n
. Teraz nien
zawiedzie się, dopóki nie będzie większa niż maksymalna liczba całkowita usize.Dowiedziałem się, dlaczego poprzedni kod zwrócił 317
n=32
. Liczyłem zestawy okresów, a nie tablice okresów. Były trzy tablice z tymi samymi elementami:Teraz działa. Nadal jest wolny, ale działa.
źródło
C - 16
Nie działa przy wartościach większych niż 16 cuz przepełnienia.
Nie mam pojęcia, jak szybko to działa, bo jestem na Chromebooku, który działa na repl.it.
Po prostu implementuje pytanie w trakcie czytania, przechodzi przez wszystkie ciągi bitów, oblicza tablice kropek i sprawdza, czy zostały już policzone.
Po prostu skompiluj go za pomocą gcc itp.
źródło
16
wtedy, gdy kod został zmieniony tak, że dwamalloc
s byłymalloc(...int*))
i...**
odpowiednio16
drukowaneAnswer: 320
zgodnie z oczekiwaniami, jednak32
drukowanaAnswer: 0
(i dość szybko).n = 8
ale po wydrukowaniu wyniku, co oznacza, że stos jest uszkodzony. Prawdopodobnie piszesz gdzieś poza przydzielonymi blokami pamięci.Haskell
Kompiluj z
ghc -O2
. Wypróbuj online!Działa w czasie krótszym niż 0,1 sekundy na moim 6-letnim laptopie dla
n=16
.n=32
zajmuje9992min, więc mam 9 lub 10 zniżki. Próbowałem buforować kropki w tabeli odnośników, więc nie muszę ich ponownie obliczać w kółko, ale na moim komputerze o pojemności 4 GB szybko kończy się pamięć.źródło
Python 2 (PyPy), 16
źródło
osboxes@osboxes:~/python$ python ascii_user.py 16 None
[C ++], 32, 4 minuty
źródło