Pojedyncze ruchy
Plansza jest nieskończoną 2-wymiarową kwadratową siatką, niczym nieograniczona szachownica. Kawałek o wartości N (ruchomy N ) może przesunąć się na dowolny kwadrat, który jest dokładnie o pierwiastku kwadratowym N z jego obecnego kwadratu (odległość euklidesowa mierzona od środka do środka).
Na przykład:
- 1-poruszający się gracz może przejść do dowolnego kwadratu sąsiadującego poziomo lub pionowo
- 2-poruszający się może przesunąć się na dowolny kwadrat, który sąsiaduje po przekątnej
- 5-poruszający się porusza się jak rycerz szachowy
Pamiętaj, że nie wszystkie ruchy N mogą się poruszać. 3-poruszający się nigdy nie może opuścić swojego aktualnego kwadratu, ponieważ żaden z kwadratów na planszy nie jest w odległości dokładnie 3 pierwiastków od bieżącego kwadratu.
Wiele ruchów
Jeśli pozwolą ci się poruszać wielokrotnie, niektóre pionki mogą dosięgnąć dowolnego kwadratu na planszy. Na przykład zarówno 1-mover, jak i 5-mover mogą to zrobić. 2-poruszający się może poruszać się tylko po przekątnej i może dotrzeć tylko do połowy kwadratów. Element, który nie może się poruszyć, podobnie jak 3-poruszający się, nie może dosięgnąć żadnego z kwadratów (kwadrat początkowy nie jest liczony jako „osiągnięty”, jeśli nie nastąpi ruch) .
Obrazy pokazują, do których kwadratów można dotrzeć. Więcej informacji na temat aktywowania. Kliknij, aby powiększyć obraz.
- Kwadraty osiągalne w 1 lub więcej ruchach są zaznaczone na czarno
- Kwadraty osiągalne w dokładnie 1 ruchu są oznaczone czerwonymi pionkami
(poza 3-ruchomym, który nie może się poruszać)
Jaką część planszy może osiągnąć dany N-mover?
Wejście
- Dodatnia liczba całkowita N
Wynik
- Część planszy, którą może osiągnąć N-mover
- Jest to liczba od 0 do 1 (obie włącznie)
- W przypadku tego wyzwania dozwolona jest produkcja jako ułamek w najniższych kategoriach, takich jak 1/4
Więc dla wejścia 10
, zarówno 1/2
i 0.5
są dopuszczalne wyjścia. Dane wyjściowe jako oddzielny licznik i mianownik są również dopuszczalne, ponieważ obejmują języki, które nie obsługują liczb zmiennoprzecinkowych ani ułamkowych. Na przykład 1 2
lub [1, 2]
.
W przypadku liczb całkowitych (0 i 1) akceptowalne są dowolne z poniższych formatów:
- 0:
0
,0.0
,0/1
,0 1
,[0, 1]
- do 1:
1
,1.0
,1/1
,1 1
,[1, 1]
Punktacja
To jest kod golfowy. Wynik to długość kodu w bajtach. W każdym języku wygrywa najkrótszy kod.
Przypadki testowe
W formacie input : output as fraction : output as decimal
1 : 1 : 1
2 : 1/2 : 0.5
3 : 0 : 0
4 : 1/4 : 0.25
5 : 1 : 1
6 : 0 : 0
7 : 0 : 0
8 : 1/8 : 0.125
9 : 1/9 : 0.1111111111111111111111111111
10 : 1/2 : 0.5
13 : 1 : 1
16 : 1/16 : 0.0625
18 : 1/18 : 0.05555555555555555555555555556
20 : 1/4 : 0.25
25 : 1 : 1
26 : 1/2 : 0.5
64 : 1/64 : 0.015625
65 : 1 : 1
72 : 1/72 : 0.01388888888888888888888888889
73 : 1 : 1
74 : 1/2 : 0.5
80 : 1/16 : 0.0625
81 : 1/81 : 0.01234567901234567901234567901
82 : 1/2 : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1 : 1
146 : 1/2 : 0.5
148 : 1/4 : 0.25
153 : 1/9 : 0.1111111111111111111111111111
160 : 1/32 : 0.03125
161 : 0 : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0 : 0
164 : 1/4 : 0.25
241 : 1 : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4 : 0.25
245 : 1/49 : 0.02040816326530612244897959184
260 : 1/4 : 0.25
261 : 1/9 : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2 : 0.5
292 : 1/4 : 0.25
293 : 1 : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1 : 1
326 : 0 : 0
360 : 1/72 : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2 : 0.5
369 : 1/9 : 0.1111111111111111111111111111
370 : 1/2 : 0.5
449 : 1 : 1
450 : 1/18 : 0.05555555555555555555555555556
488 : 1/8 : 0.125
489 : 0 : 0
490 : 1/98 : 0.01020408163265306122448979592
520 : 1/8 : 0.125
521 : 1 : 1
522 : 1/18 : 0.05555555555555555555555555556
544 : 1/32 : 0.03125
548 : 1/4 : 0.25
549 : 1/9 : 0.1111111111111111111111111111
584 : 1/8 : 0.125
585 : 1/9 : 0.1111111111111111111111111111
586 : 1/2 : 0.5
592 : 1/16 : 0.0625
593 : 1 : 1
596 : 1/4 : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2 : 0.5
611 : 0 : 0
612 : 1/36 : 0.02777777777777777777777777778
613 : 1 : 1
624 : 0 : 0
625 : 1 : 1
źródło
Odpowiedzi:
JavaScript (Node.js) ,
144138125747370 bajtówWypróbuj online!
-4 bajty dzięki @Arnauld!
Oryginalne podejście, 125 bajtów
Wypróbuj online!
Zainspirowany filmem Pi ukrywającym się w najlepszych regularnościach przez 3Blue1Brown.
Dla każdego czynnika pierwszego w faktoryzacji liczby obliczyć :pn fa( pn)
Pomnóż wszystkie te wartości funkcji, oto jesteśmy.
Aktualizacja
Dzięki wysiłkom autorów Math.SE algorytm jest teraz poparty dowodem
źródło
Mathematica, 80 bajtów
Ten kod opiera się głównie na twierdzeniu matematycznym. Podstawową ideą jest to, że kod pyta o gęstość sieci, biorąc pod uwagę pewien zestaw generacyjny.
Mówiąc dokładniej, otrzymaliśmy zbiór wektorów - mianowicie tych, których długość do kwadratu wynosi N - i poprosiliśmy o obliczenie gęstości zbioru możliwych sum tych wektorów w porównaniu do wszystkich wektorów całkowitych. Matematyka w grze polega na tym, że zawsze możemy znaleźć dwa wektory (i ich przeciwieństwa), które „generują” (tj. Których sumy są) taki sam zestaw jak oryginalna kolekcja. LatticeReduce robi dokładnie to.
Jeśli masz tylko dwa wektory, możesz sobie wyobrazić, że narysujesz identyczny równoległobok wyśrodkowany w każdym osiągalnym punkcie, ale którego długości krawędzi są podanymi wektorami, tak że płaszczyzna jest całkowicie ułożona sąsiadująco przez te równoległoboki. (Wyobraź sobie na przykład sieć kształtów „diamentowych” dla n = 2). Obszar każdego równoległoboku jest wyznacznikiem dwóch wektorów generujących. Pożądana proporcja płaszczyzny jest odwrotnością tego obszaru, ponieważ każdy równoległobok ma tylko jeden osiągalny punkt.
Kod jest dość prostą implementacją: generuj wektory, użyj LatticeReduce, weź wyznacznik, a następnie weź odwrotność. (Prawdopodobnie można lepiej grać w golfa)
źródło
d@n_:=Boole[#!={}]/Det@LatticeReduce@#&@Select[Range[-n,n]~Tuples~2,#.#==n&]
Czysty ,
189185172171 bajtówWypróbuj online!
Znajduje każdą pozycję
n
możliwą do osiągnięcia w kwadracie o boku wzdłuż narożnika na początku w pierwszym kwadrancie, a następnie dzieli przez,n^2
aby uzyskać dostęp do części wszystkich komórek.Działa to, ponieważ:
n
kwadratu o boku długości, z których każdy jest osaczony w osiągalnym punkcie od początku, jakby był początkiem.++ +- -+ --
, co pozwala na przedłużenie nakładających się kafelków przez pozostałe trzy kwadranty poprzez odbicie lustrzane i obrót.źródło
Retina 0.8.2 ,
12682 bajtówWypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:
Konwertuj na unary.
Wielokrotnie dziel przez główne czynniki formy
4k+1
.Jeśli wynikiem nie jest ani kwadrat, ani dwa razy kwadrat, wynik wynosi zero.
Oblicz odwrotność jako ułamek dziesiętny.
źródło
Regex (ECMAScript, wzajemność),
256163157948382 bajtów-93 bajtów dzięki Neilowi
-6 bajtów dzięki Neilowi
-63 bajtów dzięki podziałowi bez przechwytywania dzielnika
-11 bajtów dzięki jednoczesnemu opcjonalnemu dzieleniu przez stałą Grimy i pierwiastkowi kwadratowemu
-1 bajtu poprzez przesunięcie warunku dopasowania końcowego i przechwytywanie wartości zwrotnej w pętli jako druga alternatywa, dzięki Grimy
Wykorzystuje to tę samą matematykę, co odpowiedź JavaScript Shieru Asakoto .
Dane wejściowe są jednoargumentowe. Ponieważ czysty wyrażenie regularne może zwracać jako dane wyjściowe tylko podłańcuch z wejścia (tj. Liczbę naturalną mniejszą lub równą wartości wejściowej) lub „brak dopasowania”, to wyrażenie regularne zwraca odwrotność proporcji płyty, którą przesuwa N może osiągnąć. Ponieważ odwrotnością 0 jest nieskończoność, w takim przypadku zwraca „brak dopasowania”.
OSTRZEŻENIE SPOILERA : W przypadku pierwiastka kwadratowego, wyrażenie regularne używa wariantu uogólnionego algorytmu mnożenia, co nie jest oczywiste i może być satysfakcjonującą łamigłówką do samodzielnego opracowania. Aby uzyskać więcej informacji, zobacz wyjaśnienie tej formy algorytmu w Znajdź liczbę Rocco .
^(?=((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5|((xx?)(\8*))(?=(\7*)\9+$)\7*$\10)+$)\1
Wypróbuj online!
Wypróbuj online! (tylko przypadki testowe)
Regex (ECMAScript + (? *), Wyjście wzajemne),
207138132bajtówPrzestarzały przez podział bez przechwytywania dzielnika (tj. Jest teraz identyczny z powyższym).
Regex (ECMAScript 2018, wyjście wzajemne),
212140134bajtówPrzestarzały przez podział bez przechwytywania dzielnika (tj. Jest teraz identyczny z powyższym).
Regex (ECMAScript, wyjście ułamkowe), 80 bajtów
W tej wersji licznik jest zwracany w
\10
(zero, jeśli nie jest ustawiony / NPCG), a mianownik w\7
.W przeciwieństwie do wersji z wyjściem wzajemnym:
Dużym minusem takiej specyfikacji wyjściowej jest to, że nie jest ona zawarta w samym programie.
((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5)*((((x)x?)(\9*))(?=(\8*)\11+$)\8*$\12|x)
Wypróbuj online!
Wypróbuj online! (tylko przypadki testowe)
źródło
(((xx?)(\9*))(?=(\8*)\10+$)\8*$\11)
aby sprawdzić, czy N lub N / 2 jest kwadratem.Galaretka ,
2524 bajtówŁącze monadyczne wykorzystujące trasę czynnika pierwotnego.
Wypróbuj online!
W jaki sposób?
Poprzednie 25 to:
Pełny program brutal forcer
; być możedłuższy kodniż trasa pierwszego czynnika (mógłbym spróbować później).Wypróbuj online!
Rozpoczyna się od utworzenia pojedynczych ruchów jak współrzędne następnie wielokrotnie ruchy ze wszystkich miejscach nagromadzenia osiągnięte wyniki, przy modulo
n
każdej współrzędnej (ograniczyć don
przezn
ćwiartkę) i utrzymywania tych, które są różne, aż do osiągnięcia punktu stałego; następnie dzieli liczbę przezn^2
źródło
05AB1E ,
272625 bajtówPort @ShieruAsakoto JavaScript odpowiedź „s , więc upewnij się upvote go tak dobrze!
Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie:
źródło
APL (Dyalog Extended) , 21 bajtów
Ten program używa trasy czynnika podstawowego. Jestem wdzięczny Adamowi, dzaimie, H.PWizowi, J.Sallé i ngn. APL Orchard to świetne miejsce do nauki APL i zawsze są chętni do pomocy
Wypróbuj online!
Ungolfing
Część 2 tego kodu jest taka sama jak w poniższej wersji Dyalog Unicode, dlatego w tym wyjaśnieniu skupię się na
⍭*1≠4|⍭
APL (Dyalog Unicode) ,
41403635 bajtów SBCSTen program używa trasy czynnika podstawowego. Nauczyłem się kilku trików podczas pisania tego i jestem głęboko wdzięczny Adamowi, dzaimie, H.PWizowi, J.Sallé i ngn. APL Orchard to świetne miejsce do nauki APL i zawsze są chętni do pomocy (lub ten post nigdy by nie powstał :)
Edycja: -1 bajt od ngn. -2 bajty z Adám i -2 więcej z ngn. -1 bajt od ngn.
Wypróbuj online!
Ungolfing
To jest program składający się z dwóch części:
źródło