Jak sama nazwa może sugerować, problem ten jest pół-zainspirowany uprzejmy pobliżu widzących Pijany Bot przez @NP

Nasz biedny bot jest umieszczany na kartezjańskiej siatce u źródła, a po każdej minucie przesuwa 1 jednostkę w jednym z czterech kierunków (w górę, w dół, w lewo, w prawo).

Po n minutach wszystkie utajone miny na siatce aktywują się, zabijając każdego biednego bota, który mógłby się nad nimi znaleźć. Kopalnie znajdują się przy wszystkich współrzędnych całkowitych spełniających równanie | y | = | x |.

Wyzwanie

Otrzymasz n , liczbę minut przed wybuchem min, jako dane wejściowe, a jako dane wyjściowe musisz znaleźć prawdopodobieństwo, że bot nie żyje .

Dane wejściowe : liczba naturalna reprezentująca n .

Wyjście : Niech prawdopodobieństwo, że bot nie żyje, wynosi p / q, gdzie p i q są względnie pierwszymi liczbami całkowitymi (q nie może być 0, ale p może). Wyjście p.

Zasady

Twój algorytm nie może działać w wykładniczym lub wyższym czasie. Idealnie powinien działać w czasie wielomianowym lub krótszym.
Twój algorytm musi być w stanie obsłużyć dane wejściowe n<20 (można je zmienić, jeśli są zbyt trudne) w rozsądnym czasie.
To wyzwanie dla golfa .
Iteracja wszystkich możliwości dla danego n zdecydowanie nie zostanie zaakceptowana jako odpowiedź.

Przypadki testowe

1->0

2->3

4->39

6->135

8->7735

10->28287

Przykładowe obliczenia dla n = 6

Mamy 4 możliwe ruchy: U, D, R i L. Całkowita liczba ścieżek, które można wybrać, to 4 ^ 6 lub 4096. Istnieją 4 możliwe przypadki, które lądują wzdłuż linii y = x: x, y = ± 1; x, y = ± 2; x, y = ± 3; lub x = y = 0. Policzymy liczbę sposobów, aby skończyć na (1,1), (2,2) i (3,3), pomnóż je przez 4, aby uwzględnić pozostałe kwadranty i dodaj to liczba sposobów, aby skończyć na (0,0).

Przypadek 1: Bot kończy się na (3, 3). Aby bot się tu znalazł, musiał mieć 3 ruchy w prawo i 3 ruchy w górę. Innymi słowy, łączna liczba sposobów na dotarcie tutaj to sposoby zmiany kolejności liter w sekwencji RRRUUU, czyli 6 wybierz 3 = 20.

Przypadek 2: Bot kończy się na (2,2). Aby bot mógł się tutaj znaleźć, mógł mieć 2 ruchy w górę, 3 ruchy w prawo i 1 ruch w lewo; lub 2 ruchy w prawo, 3 ruchy w górę i 1 ruch w dół. Tak więc łączna liczba sposobów na dotarcie tutaj to suma sposobów zmiany kolejności liter w sekwencjach RRRLUU i UUUDRR, z których oba to (6 wybierz 1) * (5 wybierz 2) = 60, w sumie 120 możliwości .

Przypadek 3: Bot kończy się na (1,1). Aby bot mógł się tutaj znaleźć, mógł mieć: 1 ruch w prawo, 3 ruchy w górę i 2 ruchy w dół. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji RUUUDD wynosi (6 wybierz 1) * (5 wybierz 2) = 60.

1 ruch w górę, 3 ruchy w prawo i 2 ruchy w lewo. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji URRRLL wynosi (6 wybierz 1) * (5 wybierz 2) = 60.

2 ruchy w prawo, 1 ruch w lewo, 2 ruchy w górę i 1 ruch w dół. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji UUDRRL wynosi (6 wybierz 1) * (5 wybierz 1) * (4 wybierz 2) = 180.

Zatem łączna liczba sposobów, aby skończyć na (1,1) wynosi 300.

Przypadek 4: Bot kończy się na (0,0). Aby bot się tutaj znalazł, mógł mieć:

3 ruchy w prawo i 3 ruchy w lewo. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji RRRLLL wynosi (6 wybierz 3) = 20.

3 ruchy w górę i 3 ruchy w dół. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji UUUDDD wynosi (6 wybierz 3) = 20.

1 ruch w prawo, 1 ruch w lewo, 2 ruchy w górę i 2 ruchy w dół. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji RLUUDD wynosi (6 wybierz 1) * (5 wybierz 1) * (4 wybierz 2) = 180.

1 ruch w górę, 1 ruch w dół, 2 ruchy w prawo i 2 ruchy w lewo. W takim przypadku liczba sposobów zmiany kolejności liter w sekwencji RRLLUD wynosi (6 wybierz 1) * (5 wybierz 1) * (4 wybierz 2) = 180.

Zatem łączna liczba sposobów, aby skończyć na (0,0) wynosi 400.

Łącząc te przypadki razem, otrzymujemy całkowitą liczbę sposobów, aby skończyć na | y | = | x | wynosi 4 (20 + 120 + 300) + 400 = 2160. Zatem nasze prawdopodobieństwo wynosi 2160/4096. Gdy ta frakcja zostanie w pełni zmniejszona, wynosi 135/256, więc nasza odpowiedź to 135 .

code-golf restricted-complexity Don Thousand
źródło

Podoba mi się to wyzwanie, ale myślę, że skorzystałoby na nim przykładowy przykład dla jednego z bardzo małych przypadków testowych (2 lub 3).

Pan Xcoder,

@ Mr.Xcoder Dodam jeden, gdy będę miał czas.

Don Thousand

Ciekawe wyzwanie. Zauważ, że użycie słowa „idealnie” w regule sprawia, że nie jest to reguła. Przydałoby się powiedzieć zdecydowanie tak czy inaczej.

trichoplax

Ale nikt nie mówi o algorytmie uczenia się pierwszej generacji?

Programy Redwolf

@RedwolfPrograms ahaha tak, ale ten bot ma fajniejszą nazwę

Don Thousand

Python 2 , 65 bajtów

def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)

Wypróbuj online!

Prawdopodobieństwo śmierci bota można wyrazić jako:

$f (n) = 2 s - s^{2}, where s = \frac{1}{2^{n}} (\binom{n}{n / 2})$ $f(n) = 2s-s^2\text{, where } s=\frac{1}{2^n}\binom{n}{n/2}$

a dwumianowy jest rozumiany jako równy gdy nie jest całe. $0$ $n/2$

Możemy tak rozumować. Jakie jest prawdopodobieństwo, że bot wyląduje na linii ? Dzieje się tak, jeśli całkowita liczba ruchów w górę i w lewo jest równa łącznej liczbie ruchów w dół i w prawo. Jest to takie samo prawdopodobieństwo, że powiedzmy, że rzucisz monetą razy i dostaniesz tyle ogonów, ile głów. Musisz wybrać rzutów, aby być głowami rzutów, co można zrobić na sposobów, z możliwych sekwencji ogólnie, co daje prawdopodobieństwo $y=x$ $n$ $n/2$ $n$ $\binom{n}{n/2}$ $2^n$

s = \frac{1}{2^{n}} (\binom{n}{n / 2})

$s=\frac{1}{2^n}\binom{n}{n/2}$

Prawdopodobieństwo lądowania linii wynosi również . Prawdopodobieństwo lądowania na którejkolwiek linii jest sumą tych lub , z wyjątkiem podwójnego liczenia prawdopodobieństwa lądowania w obu liniach i musimy je odjąć, aby to zrekompensować. $y=-x$ $s$ $2s$ $x=y=0$

Okazuje się, że prawdopodobieństwo lądowania na to po prostu , iloczyn prawdopodobieństwa lądowania na każdej linii. Możemy argumentować, że zdarzenia są niezależne w następujący sposób: jeśli wybierzemy losową sekwencję równych liczb „w górę lub w lewo” i „w dół lub w prawo”, aby wylądować na i podobnie z „w górę lub w prawo” i „w dół lub w lewo "dla możemy jednoznacznie połączyć je w sekwencję Góra, Dół, Lewo, Prawo, biorąc przecięcie par kierunków w każdej pozycji. $x=y=0$ $s^2$ $x=y$ $x=-y$

Zatem prawdopodobieństwo lądowania na lub wynosi . $x=y$ $x=-y$ $2s-s^2$

Kod oblicza dwumianowy przy użyciu tego wyrażenia jak w przypadku podstawy . Aby wyodrębnić licznik z ułamka prawdopodobieństwa, zauważamy, że mianownik jest potęgą 2, więc używamy wyrażenia do podzielenia maksymalnej potęgi 2 , wyrażonej jako klasyczna sztuczka bitowa . $\binom{n}{n/2}$ (b+1)**n/b**(n/2)%bb=2**nr/(r&-r)rr&-r

Rozgrywka polega na zapisaniu jako dzięki czemu jest przywoływany tylko raz, i działa bez ułamków aby pozostać w liczbach całkowitych. Obliczenia są czasem wielomianowym w nawet przy funkcyjnym sposobie obliczania dwumianów. $2s-s^2$ $1-(1-s)^2$ $s$ $1/2^n$ $n$

Po napisaniu dowodu prawdopodobieństwa śmierci bota znalazłem prawdopodobnie czystszy sposób, aby to udowodnić i przedstawić.

Trzymajmy utwór z wartości i po każdym ruchu bot. Każdy z czterech kierunkach, w górę, w dół, w lewo lub w prawo albo zwiększa lub zmniejsza każdy z i , z czterech kierunków odpowiadających czterech kombinacjach. $a=x+y$ $b=x-y$ $a$ $b$

Tak więc losowy ruch jest równoważny losowemu dodaniu do i niezależnie do . Jest to równoważne robi oddzielne losowe spacery na i . $\pm 1$ $a$ $\pm 1$ $b$ $a$ $b$

Teraz robot kończy się na linii lub dokładnie wtedy, gdy lub . Prawdopodobieństwo zakończenia na to i podobnie dla . Ponieważ spacery są niezależne, prawdopodobieństwo, że i wynosi , więc prawdopodobieństwo, że co najmniej jeden wynosi zero, jest uzupełnieniem . $x=y$ $x=-y$ $a=0$ $b=0$ $a=0$ $s=\frac{1}{2^n}\binom{n}{n/2}$ $b=0$ $a\neq 0$ $b\neq 0$ $(1-s)^2$ $1-(1-s)^2$

xnor
źródło

Fantastyczny! Czekałem, aż ktoś to wyciągnie. Nie wyobrażałem sobie, że to takie szybkie. Minusem jest to, że większość innych odpowiedzi nie będzie musiała zbyt wiele myśleć :(. Doskonałe +1

Don Thousand

ciesz się małą nagrodą (nie mam za co przepraszać)

Don Thousand

@RushabhMehta Dziękuję, to bardzo miłe z twojej strony! Twoja nagroda zmotywowała mnie do napisania czystszego dowodu, o którym myślałem później.

xnor 24.08.18

Prawdziwą inspiracją dla tego problemu był problem 11 AIME I 2014, jeśli chcesz go sprawdzić.

Don Thousand

Uprzejmy, niedowidzący pijany bot na polu minowym

Wyzwanie

Zasady

Przypadki testowe

Przykładowe obliczenia dla n = 6

Odpowiedzi:

Python 2 , 65 bajtów