Witam, przed chwilą przyszła mi do głowy taka rzecz, być może się powtórzę, ale mam nadzieję, że nie (nie wiem nawet jak to nazwać).
Jest taka gra (FEZ), są w niej sekrety, do których rozwiązania potrzebne jest wciśnięcie odpowiednich klawiszy na padzie, gotowych kombinacji można szukać oczywiście w grze ale niektóre zagadki wymagają jednak tzw. bruteforce'a.
Załóżmy, że wiem gdzie wcisnąć te kombinacje, oraz ilu wciśnięć potrzeba (powiedzmy \(\displaystyle{ 6}\)), możliwych klawiszy do wciśnięcia jest \(\displaystyle{ 7}\). A więc wychodzi \(\displaystyle{ 7^6}\) możliwości, całkiem sporo.
Chciałbym wiedzieć czy da się ustalić taki ciąg cyfr, który zawierałby każdą możliwą liczbę \(\displaystyle{ 6}\)-cyfrową o cyfrach od \(\displaystyle{ 1}\) do \(\displaystyle{ 7}\) w swoim podciągu w taki sposób aby miał on minimalną długość.
Dzięki temu można podejść do problemu w sposób optymalny, unikając powtarzania wszystkiego od nowa, tylko korzystania z poprzednich prób jako części nowej kombinacji.
Można od razu podać rozwiązanie dla \(\displaystyle{ n}\) wciśnięć i \(\displaystyle{ m}\) przycisków, jeśli w ogóle istnieje rozwiązanie tego problemu, mam nadzieję, że nie zahaczyłem o jakiś problem milenijny
Pozdrawiam
Najkrótszy ciąg cyfr - zagadko/problem
-
- Użytkownik
- Posty: 33
- Rejestracja: 6 paź 2009, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Bolesławiec
- Podziękował: 9 razy
- Pomógł: 2 razy
Najkrótszy ciąg cyfr - zagadko/problem
Ostatnio zmieniony 21 lip 2013, o 08:44 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Brak LaTeXa. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm . Temat umieszczony w złym dziale.
Powód: Brak LaTeXa. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm . Temat umieszczony w złym dziale.
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Najkrótszy ciąg cyfr - zagadko/problem
Oczywiście taki ciąg da się zrobić. Żeby wykonać wszystkie kombinacje należy wykonać \(\displaystyle{ n \cdot m^{n}}\) przyciśnięć (jest \(\displaystyle{ m ^{n}}\) wszystkich możliwości a każda możliwość wymaga \(\displaystyle{ n}\) przyciśnięć.
Jeżeli będziemy wykonywali wciśnięcia po kolei (czyli tak że drugie wciśnięcie w kombinacji jest początkiem następnej kombinacji) to cała procedura wymaga co najmniej \(\displaystyle{ m ^{n}+n-1}\) wciśnięć. I to jest najmniejsza liczba wciśnięć. Jest to osiągnięte gdy kolejne kombinacje się nie powtarzają.
Jeżeli będziemy wykonywali wciśnięcia po kolei (czyli tak że drugie wciśnięcie w kombinacji jest początkiem następnej kombinacji) to cała procedura wymaga co najmniej \(\displaystyle{ m ^{n}+n-1}\) wciśnięć. I to jest najmniejsza liczba wciśnięć. Jest to osiągnięte gdy kolejne kombinacje się nie powtarzają.
-
- Użytkownik
- Posty: 33
- Rejestracja: 6 paź 2009, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Bolesławiec
- Podziękował: 9 razy
- Pomógł: 2 razy
Najkrótszy ciąg cyfr - zagadko/problem
Zgadza się, doszedłem do tych samych wniosków w międzyczasie i wynika z tego np, że jeśli przyjęlibyśmy, że mamy \(\displaystyle{ 7}\) przycisków i \(\displaystyle{ 7}\) przyciskową kombinację oraz że naciśnięcie każdego wymaga \(\displaystyle{ 1}\) sekundy czasu rzeczywistego, to:
Bruteforcem: \(\displaystyle{ 7^7 \cdot 7 \Rightarrow 5764801 [s] = 66,7}\) dnia (tak naprawdę krócej, bo "niechcąco" pewne kombinacje zostaną wciśnięte wcześniej)
Najkrótszym ciągiem: \(\displaystyle{ 7^7 + 7 - 1 \Rightarrow 823549 [s] = 9,5}\) dnia!
Problemem natomiast jest, jaki dokładnie ten ciąg jest (jedna z możliwości).
Przez ten czas doszedłem do kilku własnych odkryć/wniosków:
Oczywiście w tych wszystkich wywodach kombinacja to dla mnie wariacja z powtórzeniami
Przyjmijmy, że mamy ustaloną liczbę przycisków \(\displaystyle{ p}\) oraz ustaloną długość kombinacji \(\displaystyle{ d}\).
Możemy stworzyć pewien graf skierowany, którego wierzchołkami są kolejne możliwe kombinacje długości \(\displaystyle{ d}\) zawierające cyfry od \(\displaystyle{ 0}\) do \(\displaystyle{ p-1}\).
Porządek możemy ustalić w następujący prosty sposób:
Na przykład dla \(\displaystyle{ p = 3}\) i \(\displaystyle{ d = 2}\) wierzchołek o numerze \(\displaystyle{ 3}\) (indeksujemy od \(\displaystyle{ 0}\) do \(\displaystyle{ p^d - 1}\)) odpowiada kombinacji: \(\displaystyle{ 10}\), czyli czwartej możliwej kombinacji.
2. Zbiór krawędzi ustalamy w następujący sposób:
\(\displaystyle{ |V(G)| = p^d}\)
\(\displaystyle{ |E(G)| = p^{d+1}}\) (bądź \(\displaystyle{ p^{d+1} - p}\) pomijając pętle)
Z każdego (zaliczając pętle) wychodzi \(\displaystyle{ p}\) krawędzi oraz wchodzi \(\displaystyle{ p}\) krawędzi, każdy wierzchołek jest więc stopnia \(\displaystyle{ 2p}\).
W tej relacji wierzchołków natomiast jest taki myk, że po zdekodowaniu dwóch wierzchołków, które są ze sobą połączone łukiem (w grafie występują także krawędzie, ale mniejsza) możemy zauważyć pewną rzecz:
np. w podanym wyżej przykładzie z wierzchołka \(\displaystyle{ 0}\) wychodzą \(\displaystyle{ 3(2)}\) łuki: do \(\displaystyle{ 0,1,2}\). To co można zauważyć to to, że gdybyśmy usunęli pierwszy bit \(\displaystyle{ 0}\) i doczepili ostatni bit jednego z tych wierzchołków, to otrzymamy właśnie te wierzchołki po zakodowaniu!
np.
Gdy znajdziemy taki cykl bądź ścieżkę (bardzo prawdopodobne, że jak już, to są same cykle), reszta jest już bardzo prosta wystarczy z tej sekwencji wierzchołków wydobyć gotową sekwencję wciśnięć, która będzie najkrótszą możliwą.
Zobrazuję to na przykładzie, w którym mamy problem 2 przycisków oraz 3 wciśnięć:
Znalazłem \(\displaystyle{ 2}\) unikatowe cykle Hamiltona z każdego można wydobyć \(\displaystyle{ 8}\) różnych sekwencji, czyli w sumie mamy \(\displaystyle{ 16}\) możliwych sekwencji wciśnięć dla tego problemu, poniżej ilustracje:
Warto zwrócić uwagę na niezmienność dwóch podsekwencji: 4,0,1 oraz 3,7,6. Jeśli wystartujemy z 0 to na pewno skończymy na 4.
Tak więc zamiast wciskać: \(\displaystyle{ 000001010011100\textcolor{gray}{101110111}}\) (tak naprawdę wszystko się zrobi przed szarymi wciśnięciami), czyli wszystkie możliwości po kolei, możemy zastosować minimalną sekwencję odkodowując jeden z cykli Hamiltona w następujący sposób:
W ten sposób dostajemy, najkrótszą, najbardziej upakowaną w kombinacje sekwencję dla tego konkretnego problemu (oczywiście istnieje jeszcze 15 innych odmian, ale potrzebujemy do szczęścia tylko jednej).
Wszystko pięknie ale jest mały problem... Najlepiej zobrazuje to ten obrazek:
Bynajmniej, jest to tylko graf marnego problemu \(\displaystyle{ 3}\) przycisków i długości \(\displaystyle{ 5}\).
Złożoność problemu rośnie wykładniczo, jest on ściśle NP-zupełny, oznacza to niezłe kłopoty i może przekreślić szanse na znalezienie chociaż jednego cyklu Hamiltona w problemie \(\displaystyle{ 7^7}\)
Musiałem trochę poczekać, aż wygeneruje się sam graf problemu \(\displaystyle{ 3^5}\), nie chcę nawet myśleć o szukaniu cyklu!
I w tym miejscu się zatrzymałem i nie wiem jak dalej ruszyć, program z którego korzystam (Sage) ma wbudowaną funkcję is_hamiltonian, dla wszystkich możliwych do sprawdzenia grafów jakie udało mi się wygenerować zwracała True, więc można się spodziewać, że wszystkie skonstruowane grafy są Hamiltonowskie a to byłby pierwszy sukces, że jest czego szukać.
Niestety są 2 problemy.
Dla grafów skierowanych funkcja nie może zwrócić sekwencji wierzchołków, mimo znalezienia cyklu, ale to mniejszy problem.
Drugim problemem jest złożoność, od 20~30 wierzchołków zaczynają się problemy czasowe, powyższy graf \(\displaystyle{ f(3,5)}\) (tak go chyba nazwę, graf fezowski ) ma wierzchołków 243! a graf \(\displaystyle{ f(7,7)}\)... 823543!!!
Nie ma więc najmniejszej szansy na znalezienie cykli drogą algorytmiczną. Pocieszający może być fakt, że przy tak wielkich liczbach graf jest śmiesznie rzadki (nowa definicja ) w porównaniu do kwadratu wierzchołków.
Jedyną nadzieją pozostaje szybkie odczytanie sekwencji opierając się na własnościach tego grafu, znalezieniu jakichś zależności jak np. te które podałem wyżej. Patrząc na wielkość grafu można się spodziewać, że ostatecznych cykli może być mnóstwo, tylko jak je znaleźć?
Być może ktoś spotkał się z podobnym problemem, podobnym bądź tak samo zdefiniowanym grafem, do którego są już jakiegoś typu gotowce, wzory?
Byłbym wdzięczny za wszelką pomoc, bądź własne przemyślenia na ten temat
Pozdrawiam
Bruteforcem: \(\displaystyle{ 7^7 \cdot 7 \Rightarrow 5764801 [s] = 66,7}\) dnia (tak naprawdę krócej, bo "niechcąco" pewne kombinacje zostaną wciśnięte wcześniej)
Najkrótszym ciągiem: \(\displaystyle{ 7^7 + 7 - 1 \Rightarrow 823549 [s] = 9,5}\) dnia!
Problemem natomiast jest, jaki dokładnie ten ciąg jest (jedna z możliwości).
Przez ten czas doszedłem do kilku własnych odkryć/wniosków:
Oczywiście w tych wszystkich wywodach kombinacja to dla mnie wariacja z powtórzeniami
Przyjmijmy, że mamy ustaloną liczbę przycisków \(\displaystyle{ p}\) oraz ustaloną długość kombinacji \(\displaystyle{ d}\).
Możemy stworzyć pewien graf skierowany, którego wierzchołkami są kolejne możliwe kombinacje długości \(\displaystyle{ d}\) zawierające cyfry od \(\displaystyle{ 0}\) do \(\displaystyle{ p-1}\).
Porządek możemy ustalić w następujący prosty sposób:
\(\displaystyle{ V(G) = [0..p^d-1]}\)
1. Numer wierzchołka odpowiada jego reprezentacji w systemie o podstawie p.Na przykład dla \(\displaystyle{ p = 3}\) i \(\displaystyle{ d = 2}\) wierzchołek o numerze \(\displaystyle{ 3}\) (indeksujemy od \(\displaystyle{ 0}\) do \(\displaystyle{ p^d - 1}\)) odpowiada kombinacji: \(\displaystyle{ 10}\), czyli czwartej możliwej kombinacji.
\(\displaystyle{ 3_{10}}\) = \(\displaystyle{ 10_3}\)
Czyli myk polega na tym, że za każdym indeksem danego wierzchołka kryje się sekwencja wciśnięć, wystarczy ją "zdekodować".2. Zbiór krawędzi ustalamy w następujący sposób:
\(\displaystyle{ (v_i,v_j) in E(G) Leftrightarrow j in [(icdot pmod{p^d} ; i cdot pmod{p^d} + p) extcolor{gray}{ wedge i
eq j}}\)
(Ostatnia koniunkcja nie jest potrzebna, bo bez niej relacje są również poprawne dla tego problemu, tyle, że wystąpią w nim wtedy pętle co będzie się trochę kłóciło z dalszymi założeniami)eq j}}\)
\(\displaystyle{ |V(G)| = p^d}\)
\(\displaystyle{ |E(G)| = p^{d+1}}\) (bądź \(\displaystyle{ p^{d+1} - p}\) pomijając pętle)
Z każdego (zaliczając pętle) wychodzi \(\displaystyle{ p}\) krawędzi oraz wchodzi \(\displaystyle{ p}\) krawędzi, każdy wierzchołek jest więc stopnia \(\displaystyle{ 2p}\).
W tej relacji wierzchołków natomiast jest taki myk, że po zdekodowaniu dwóch wierzchołków, które są ze sobą połączone łukiem (w grafie występują także krawędzie, ale mniejsza) możemy zauważyć pewną rzecz:
np. w podanym wyżej przykładzie z wierzchołka \(\displaystyle{ 0}\) wychodzą \(\displaystyle{ 3(2)}\) łuki: do \(\displaystyle{ 0,1,2}\). To co można zauważyć to to, że gdybyśmy usunęli pierwszy bit \(\displaystyle{ 0}\) i doczepili ostatni bit jednego z tych wierzchołków, to otrzymamy właśnie te wierzchołki po zakodowaniu!
np.
\(\displaystyle{ 0_{10} = 00_3 \Rightarrow 0 \Rightarrow 02_3 = 2_{10}}\)
Czyli za pomocą sekwencji \(\displaystyle{ 002}\) możemy zminimalizować wpisywanie kombinacji \(\displaystyle{ 00}\) i \(\displaystyle{ 02}\) do jedynie \(\displaystyle{ 3}\)-cyfrowej sekwencji. Całe sedno problemu sprowadza się więc do jednej rzeczy - znalezienia cyklu/ścieżki Hamiltona.
Gdy znajdziemy taki cykl bądź ścieżkę (bardzo prawdopodobne, że jak już, to są same cykle), reszta jest już bardzo prosta wystarczy z tej sekwencji wierzchołków wydobyć gotową sekwencję wciśnięć, która będzie najkrótszą możliwą.
Zobrazuję to na przykładzie, w którym mamy problem 2 przycisków oraz 3 wciśnięć:
Poszukiwania zacząłem od wyboru wierzchołka 0 jako startowego (czy ma to wpływ na znajdywalność? nie wiem/wątpię).
Znalazłem \(\displaystyle{ 2}\) unikatowe cykle Hamiltona z każdego można wydobyć \(\displaystyle{ 8}\) różnych sekwencji, czyli w sumie mamy \(\displaystyle{ 16}\) możliwych sekwencji wciśnięć dla tego problemu, poniżej ilustracje:
Wyglądają jak jeden obrócony, odbity cykl.
Warto zwrócić uwagę na niezmienność dwóch podsekwencji: 4,0,1 oraz 3,7,6. Jeśli wystartujemy z 0 to na pewno skończymy na 4.
Tak więc zamiast wciskać: \(\displaystyle{ 000001010011100\textcolor{gray}{101110111}}\) (tak naprawdę wszystko się zrobi przed szarymi wciśnięciami), czyli wszystkie możliwości po kolei, możemy zastosować minimalną sekwencję odkodowując jeden z cykli Hamiltona w następujący sposób:
\(\displaystyle{ 0,1,2,5,3,7,6,4 \Rightarrow \textcolor{red}{000}, 00\textcolor{red}{1},01\textcolor{red}{0},10\textcolor{red}{1},01\textcolor{red}{1},11\textcolor{red}{1},11\textcolor{red}{0},10\textcolor{red}{0} \Rightarrow \textcolor{red}{0001011100}}\)
Wystarczy że skopiujemy pierwszą kombinację oraz ostatnie bity całej reszty i gotowe!W ten sposób dostajemy, najkrótszą, najbardziej upakowaną w kombinacje sekwencję dla tego konkretnego problemu (oczywiście istnieje jeszcze 15 innych odmian, ale potrzebujemy do szczęścia tylko jednej).
Wszystko pięknie ale jest mały problem... Najlepiej zobrazuje to ten obrazek:
A cóż to jest? Czyżby to był graf dla problemu \(\displaystyle{ 7}\) przycisków oraz długości równej \(\displaystyle{ 7}\)?
Bynajmniej, jest to tylko graf marnego problemu \(\displaystyle{ 3}\) przycisków i długości \(\displaystyle{ 5}\).
Złożoność problemu rośnie wykładniczo, jest on ściśle NP-zupełny, oznacza to niezłe kłopoty i może przekreślić szanse na znalezienie chociaż jednego cyklu Hamiltona w problemie \(\displaystyle{ 7^7}\)
Musiałem trochę poczekać, aż wygeneruje się sam graf problemu \(\displaystyle{ 3^5}\), nie chcę nawet myśleć o szukaniu cyklu!
I w tym miejscu się zatrzymałem i nie wiem jak dalej ruszyć, program z którego korzystam (Sage) ma wbudowaną funkcję is_hamiltonian, dla wszystkich możliwych do sprawdzenia grafów jakie udało mi się wygenerować zwracała True, więc można się spodziewać, że wszystkie skonstruowane grafy są Hamiltonowskie a to byłby pierwszy sukces, że jest czego szukać.
Niestety są 2 problemy.
Dla grafów skierowanych funkcja nie może zwrócić sekwencji wierzchołków, mimo znalezienia cyklu, ale to mniejszy problem.
Drugim problemem jest złożoność, od 20~30 wierzchołków zaczynają się problemy czasowe, powyższy graf \(\displaystyle{ f(3,5)}\) (tak go chyba nazwę, graf fezowski ) ma wierzchołków 243! a graf \(\displaystyle{ f(7,7)}\)... 823543!!!
Nie ma więc najmniejszej szansy na znalezienie cykli drogą algorytmiczną. Pocieszający może być fakt, że przy tak wielkich liczbach graf jest śmiesznie rzadki (nowa definicja ) w porównaniu do kwadratu wierzchołków.
Jedyną nadzieją pozostaje szybkie odczytanie sekwencji opierając się na własnościach tego grafu, znalezieniu jakichś zależności jak np. te które podałem wyżej. Patrząc na wielkość grafu można się spodziewać, że ostatecznych cykli może być mnóstwo, tylko jak je znaleźć?
Być może ktoś spotkał się z podobnym problemem, podobnym bądź tak samo zdefiniowanym grafem, do którego są już jakiegoś typu gotowce, wzory?
Byłbym wdzięczny za wszelką pomoc, bądź własne przemyślenia na ten temat
Pozdrawiam
-
- Użytkownik
- Posty: 33
- Rejestracja: 6 paź 2009, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Bolesławiec
- Podziękował: 9 razy
- Pomógł: 2 razy
Najkrótszy ciąg cyfr - zagadko/problem
Problem rozwiązany, okazało się, że problem jest bardzo znany, tylko nie wiedziałem jak go znaleźć
Napisałem w Javie program, który dla danego \(\displaystyle{ p}\) i \(\displaystyle{ d}\) generował wszystkie możliwości (zaczynając od 0) i zliczał ich ilość. W ten sposób dla \(\displaystyle{ p = 2}\) wyskoczyły po kolei: \(\displaystyle{ 1,1,2,16,2048}\)
Wklepałem tę sekwencję do OEISa i wyskoczył jedyny, jednoznaczny ciąg:
Okazuje się, że mój szukany ciąg jest Cyklem de Bruijna dla \(\displaystyle{ k=7,n=7}\). (Nie przywłaszczę sobie odkrycia )
Wśród jego zastosowań znajduje się właśnie między innymi Bruteforce PINów które odczytuje się na podstawie ostatnich n wciśnięć. (Nie ma przycisku ENTER)
Dla zainteresowanych tematem (Sam dopiero zaczynam się w to wgłębiać ):
Pozostaje jedynie problem znalezienia maszyny która do policzy, lub znaleźć gotowe rozwiązanie dla 7,7 bo u mnie krzyczy, że brak pamięci a na stronie jest limit
Dziękuję i Pozdrawiam
Napisałem w Javie program, który dla danego \(\displaystyle{ p}\) i \(\displaystyle{ d}\) generował wszystkie możliwości (zaczynając od 0) i zliczał ich ilość. W ten sposób dla \(\displaystyle{ p = 2}\) wyskoczyły po kolei: \(\displaystyle{ 1,1,2,16,2048}\)
Wklepałem tę sekwencję do OEISa i wyskoczył jedyny, jednoznaczny ciąg:
Kod: Zaznacz cały
http://oeis.org/search?q=1%2C1%2C2%2C16%2C2048
Wśród jego zastosowań znajduje się właśnie między innymi Bruteforce PINów które odczytuje się na podstawie ostatnich n wciśnięć. (Nie ma przycisku ENTER)
Dla zainteresowanych tematem (Sam dopiero zaczynam się w to wgłębiać ):
Kod: Zaznacz cały
http://pl.wikipedia.org/wiki/Cykl_de_Bruijna
http://en.wikipedia.org/wiki/De_Bruijn_sequence
http://chessprogramming.wikispaces.com/De+Bruijn+sequence
Generator: http://www.hakank.org/comb/debruijn_k_10_n_4.html
Dziękuję i Pozdrawiam