Zainspirowany The Great API Easter Egg Hunt!
streszczenie
Twoim zadaniem jest poszukiwanie z góry określonej liczby całkowitej w „przestrzeni Collatz” (wyjaśnione później) przy użyciu jak najmniejszej liczby kroków.
Wprowadzenie
Wyzwanie to opiera się na słynnej hipotezie Collatz, o której, przynajmniej mam nadzieję, wszyscy tu słyszeli. Oto podsumowanie zaczerpnięte z Print the Super Collatz numbers .
Collatz Sequence (zwany również problem 3x + 1) jest tam, gdzie zaczynają się każdej liczby całkowitej dodatniej, w tym przykładzie użyjemy 10, i zastosować zestaw kroków do niego:
if n is even: Divide it by 2 if n is odd: Multiply it by 3 and add 1 repeat until n = 1
Odległość Collatz C(m,n)
między dwiema liczbami m
i n
, na potrzeby tego wyzwania, jest odległością między dwiema liczbami na wykresie Collatz (Podziękowania dla @tsh za poinformowanie mnie o tej koncepcji), która jest zdefiniowana następująco: (za pomocą 21
i 13
jako przykłady ):
Zapisz sekwencję Collatz dla m
(w tym przypadku 21
):
21, 64, 32, 16, 8, 4, 2, 1
Zapisz sekwencję Collatz dla n
(w tym przypadku 13
):
13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Teraz policz, ile liczb pojawia się tylko w jednej sekwencji. Jest to zdefiniowane jako odległość Collatz między m
i n
. W tym przypadku 8
, a mianowicie
21, 64, 32, 13, 40, 20, 10, 5
Mamy więc odległość Collatz między 21
i 13
jak C(21,13)=8
.
C(m,n)
mają następujące miłe właściwości:
C(m,n)=C(n,m)
C(m,n)=0 iff. m=n
Mam nadzieję, że definicja C(m,n)
jest teraz jasna. Zacznijmy polować na jajka w przestrzeni Collatz!
Na początku gry kontroler decyduje o położeniu jajka wielkanocnego, które wyraża się w jego jednowymiarowej współrzędnej: Liczba całkowita w przedziale [p,q]
(innymi słowy liczba całkowita między p
i q
, włącznie z obydwoma końcami).
Pozycja jajka pozostaje stała podczas gry. Będziemy oznaczać tę współrzędną jako r
.
Możesz teraz początkowo zgadnąć 0 , a to zostanie zarejestrowane przez kontroler. To twoja 0 runda. Jeśli masz tyle szczęścia, że udało Ci się to zrobić na pierwszym miejscu (tj. 0 = r), gra się kończy, a twój wynik to 0
(Im niższy wynik, tym lepiej). W przeciwnym razie wchodzisz do pierwszej rundy i zgadujesz 1 , to trwa do momentu, aż wszystko będzie dobrze, tj. N = r, a twój wynik będzie n
.
Dla każdej rundy po 0 kontroler podaje jedną z następujących informacji zwrotnych, dzięki czemu można lepiej zgadywać na podstawie podanych informacji. Załóżmy, że aktualnie jesteś w n
trzeciej rundzie, więc zgadujesz, że to n
- "Znalazłeś to!" jeśli a n = r, w takim przypadku gra się kończy i zdobywasz punkty
n
. - „Jesteś bliżej :)” jeśli C (a n , r) <C (a n-1 , r)
- „Krążysz wokół jajka”, jeśli C (a n , r) = C (a n-1 , r)
- „Jesteś dalej :(” jeśli C (a n , r)> C (a n-1 , r)
Aby zapisać niektóre bajty, wywołam odpowiedzi jako „w prawo”, „bliżej”, „sam”, „dalej”, w kolejności przedstawionej powyżej.
Oto przykładowa gra z p=1,q=15
.
- 0 = 10
- 1 = 11, odpowiedź „bliżej”
- 2 = 13, odpowiedź: "dalej"
- 3 = 4, reakcji: "dalej"
- 4 = 3, reakcji „bliżej”
- 5 = 5, odpowiedź: "to samo"
- 6 = 7, odpowiedź: "W prawo"
Wynik: 6
.
Wyzwanie
Zaprojektuj deterministyczną strategię gry p=51, q=562
z najlepszym wynikiem.
Odpowiedzi powinny szczegółowo opisywać algorytmy. Możesz dołączyć dowolny kod, który pomoże wyjaśnić algorytm. To nie jest kodegolf, więc zachęcamy do napisania czytelnego kodu.
Odpowiedzi powinny zawierać najgorszy wynik, jaki mogą osiągnąć we wszystkich możliwych przypadkach r
, a ten z najniższym wynikiem najgorszym wygrywa. W przypadku remisu wygrywają algorytmy, które mają lepszy średni wynik dla wszystkich możliwych r
s (co powinno być również zawarte w odpowiedziach). Nie ma już żadnych przerywników remisów i na końcu możemy mieć wielu zwycięzców.
Okular
- Powtarzam,
r
leży w przedziale[51,562]
. - Obowiązują domyślne luki .
Nagroda (dodana po opublikowaniu pierwszej odpowiedzi)
Mogę osobiście zaoferować nagrodę za odpowiedź, w której wszystkie domysły są w zasięgu, [51,562]
ale wciąż mają stosunkowo niski wynik najgorszy.
źródło
Odpowiedzi:
Ruby, 196
To było o wiele trudniejsze, niż początkowo myślałem. Musiałem poradzić sobie z wieloma niejasnymi sprawami i skończyło się to brzydkim kodem. Ale było dużo zabawy! :)
Strategia
Każda sekwencja Collatz kończy się sekwencją potęg 2 (np .: [16, 8, 4, 2, 1]). Gdy tylko napotkamy potęgę 2, dzielimy przez 2, aż osiągniemy 1. Nazwijmy pierwszą potęgę 2 w sekwencji najbliższej pow2 (ponieważ jest to również najbliższa potęga 2 do naszej liczby za pomocą Collatz Distance). Dla danego zakresu (51-562) wszystkie możliwe najbliższe liczby pow2 to: [16, 64, 128, 256, 512, 1024]
Krótka wersja
Algorytm wykonuje:
Szczegółowa wersja
Biorąc pod uwagę grę z numerem docelowym
r
, strategia jest następująca:r
w jak najmniejszej liczbie kroków.Wyniki
Uruchomienie algorytmu dla wszystkich liczb z zakresu 51-562 zajmuje około sekundy na normalnym komputerze, a łączny wynik to 38665.
Kod
Wypróbuj online!
źródło
najgorszy wynik: 11, łączny wynik: 3986
Wszystkie domysły są w zasięgu
[51,562]
.Mój algorytm:
vals
, początkowo zestaw zawiera wszystkie liczby w zakresie[51,562]
.Na każdym kroku wykonaj następujące czynności:
guess
w zakresie[51,562]
takim, że gdy wartości wvals
(bezguess
siebie) dzieli się 3 zestawy odpowiadające możliwych efektówCloser
,Same
iFarther
wielkość maksymalną z tych 3 zestawów jest minimalna.Jeśli istnieje wiele możliwych wartości
guess
spełniających powyższe kryteria, wybierz najmniejszą.guess
.vals
, aby nie mogły dać tego wyniku.Moja referencyjna implementacja napisana w C ++ i Bash działa na moim komputerze w około 7,6 sekundy i daje najgorszy wynik / sumę punktów, jak opisano w tytule.
Wypróbowanie wszystkich możliwych wartości domyślnych zajmie na moim komputerze około 1,5 godziny. Mogę to rozważyć.
źródło