Dodatnie liczby wymierne można wykazać jako możliwe do numerowania w następujący sposób:
- Zero ma numer porządkowy 0
- Ułóż pozostałe liczby w siatce, tak aby wiersz a, kolumna b zawierała a / b
- Narysuj przekątną zygzakowatą górę od prawej do lewej u dołu
- Sprawdzaj bieżącą liczbę unikalnych liczb napotykanych wzdłuż zygzaka
Oto zdjęcie zygzaka:
Tak więc napotkane liczby są w kolejności
1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 2/4, 3/3, 4/2, 5/1, 6/1, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 2/6, 3/5, 4/4, 5/3 ...
A spotykane są uproszczone, unikalne liczby
1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5, 5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3, ...
Wyzwanie:
- Biorąc pod uwagę dwie liczby całkowite większe od zera p i q , wypisz liczbę porządkową p / q
- p i q niekoniecznie są równoczesne
- Najkrótszy kod wygrywa
- Standardowe luki są zabronione
Przypadki testowe:
Oto pierwsze 24 napotkane liczby wymierne i pożądane dane wyjściowe dla każdej z nich:
1/1: 1
2/1: 2
1/2: 3
1/3: 4
2/2: 1
3/1: 5
4/1: 6
3/2: 7
2/3: 8
1/4: 9
1/5: 10
2/4: 3
3/3: 1
4/2: 2
5/1: 11
6/1: 12
5/2: 13
4/3: 14
3/4: 15
2/5: 16
1/6: 17
1/7: 18
2/6: 4
3/5: 19
Dla dalszych przypadków testowych oto 200 pierwszych dodatnich liczb wymiernych w kolejności:
1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5,
5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3,
7, 8, 7/2, 5/4, 4/5, 2/7, 1/8, 1/9, 3/7, 7/3,
9, 10, 9/2, 8/3, 7/4, 6/5, 5/6, 4/7, 3/8, 2/9,
1/10, 1/11, 5/7, 7/5, 11, 12, 11/2, 10/3, 9/4, 8/5,
7/6, 6/7, 5/8, 4/9, 3/10, 2/11, 1/12, 1/13, 3/11, 5/9,
9/5, 11/3, 13, 14, 13/2, 11/4, 8/7, 7/8, 4/11, 2/13,
1/14, 1/15, 3/13, 5/11, 7/9, 9/7, 11/5, 13/3, 15, 16,
15/2, 14/3, 13/4, 12/5, 11/6, 10/7, 9/8, 8/9, 7/10, 6/11,
5/12, 4/13, 3/14, 2/15, 1/16, 1/17, 5/13, 7/11, 11/7, 13/5,
17, 18, 17/2, 16/3, 15/4, 14/5, 13/6, 12/7, 11/8, 10/9,
9/10, 8/11, 7/12, 6/13, 5/14, 4/15, 3/16, 2/17, 1/18, 1/19,
3/17, 7/13, 9/11, 11/9, 13/7, 17/3, 19, 20, 19/2, 17/4,
16/5, 13/8, 11/10, 10/11, 8/13, 5/16, 4/17, 2/19, 1/20, 1/21,
3/19, 5/17, 7/15, 9/13, 13/9, 15/7, 17/5, 19/3, 21, 22,
21/2, 20/3, 19/4, 18/5, 17/6, 16/7, 15/8, 14/9, 13/10, 12/11,
11/12, 10/13, 9/14, 8/15, 7/16, 6/17, 5/18, 4/19, 3/20, 2/21,
1/22, 1/23, 5/19, 7/17, 11/13, 13/11, 17/7, 19/5, 23, 24,
23/2, 22/3, 21/4, 19/6, 18/7, 17/8, 16/9, 14/11, 13/12, 12/13,
11/14, 9/16, 8/17, 7/18, 6/19, 4/21, 3/22, 2/23, 1/24, 1/25
Krzycz na odwrotne pytanie , gdzie pierwszy ruch jest w dół, więc nie możesz użyć odpowiedzi do wygenerowania dodatkowych przypadków testowych.
Odpowiedzi:
Galaretka ,
2120 bajtówPrawdopodobnie do pokonania przez wiele bajtów przy użyciu sprytnej matematyki ...
Łącze monadyczne akceptujące listę,
[p,q]
która zwraca liczbę naturalną przypisanąp/q
.Wypróbuj online! Lub zobacz pakiet testowy .
W jaki sposób?
Po pierwsze zauważ, że N- ta przekątna zawiera wszystkie racjonalne liczby siatki, dla których suma licznika i mianownika wynosi N + 1 , więc biorąc pod uwagę funkcję, która redukuje
[p,q]
parę do najprostszej postaci ([p/gcd(p,q),q/gcd(p,q)]
), możemy zbudować przekątne do tego stopnia, że trzeba być *, zmniejsz wszystkie wpisy, usuń duplikaty i znajdź indeks uproszczonego wejścia.* faktycznie jeszcze jeden, aby zaoszczędzić bajt
źródło
Perl 6 ,
9490 bajtówSprawdź to
Sprawdź to
Generalnie generuje całą sekwencję wartości i zatrzymuje się, gdy znajdzie dopasowanie.
Rozszerzony:
({1…($+=2)…1}…*)
generuje nieskończoną sekwencję liczników (|(…)
służy do spłaszczania powyżej)(1,{1…(($||=1)+=2)…1}…*)
generuje nieskończoną sekwencję mianownikówźródło
Python 2 ,
157144137134126 126125 bajtówWypróbuj online!
4 bajty zapisane z powodu pana Xcodera ; 1 bajt od Jonathona Frecha .
Jak zauważył pan Xcoder, możemy trochę lepiej poradzić sobie w Pythonie 3, ponieważ między innymi domyślny podział liczb całkowitych domyślnie wyświetla zmienne wyniki i możemy łatwiej rozpakować
list
s:Python 3 , 117 bajtów
Wypróbuj online!
źródło
**(j%-2|1)
ip-~q
.+1
na końcu, ponieważ1,1
„musi” dać1
, nie0
.Python 3 ,
157,146,140, 133 bajtówWypróbuj online!
wygrał 11 bajtów dzięki Jonathanowi Frechowi
wygrał jeszcze 6 bajtów, a potem 7 dzięki Chasowi Brownowi
źródło
range(max(p,q)+1)
jerange(p+q)
.{*a}
zamiastset(a)
.JOT,
41,35, 30 bajtów-11 bajtów dzięki FrownyFrog
Wypróbuj online!
oryginalny 41 bajtów postu z wyjaśnieniem
bez golfa
wyjaśnienie
Wypróbuj online!
źródło
1+~.@;@([:<@|.`</.%~/~)@(1+i.@*)i.%
%i.~0~.@,@,[:]`|./.[:%/~1+i.@*
Python 3, 121 bajtów
źródło
Rdza, 244 bajty
Stworzyłem prostą formułę, aby znaleźć „zwykły” porządek „zwykłego” zygzaka, bez ograniczeń układanki, używając wzorów liczb trójkątnych: https://www.mathsisfun.com/algebra/triangular-numbers.html . Zostało to zmodyfikowane za pomocą modulo 2, aby uwzględnić zygzaki zmieniające kierunek w każdym ukośnym rzędzie układanki. To jest funkcja h ()
Następnie główna sztuczka tej łamigłówki: jak „nie liczyć” pewnych powtarzających się wartości, takich jak 3/3 vs 1/1, 4/2 vs 2/1, na zygzakowatym szlaku. Przejrzałem 1-200 przykładów i zauważyłem różnicę między prostym zygzakowatym trójkątnym blatem, a tym, którego pragnie łamigłówka, ma wzór. Wzór „brakujących” liczb to 5, 12, 13, 14, 23 itd., Co spowodowało trafienie w OEIS. Jest to jeden opisany przez Roberta A. Stumpa w https://oeis.org/A076537 , aby „deduplikować” liczby takie jak 3/3, 4/2 i 1/1, możesz sprawdzić, czy GCD> 1 dla x, y wszystkich „poprzednich” rzędnych w zygzaku. Jest to pętla „for” ig (), która jest gcd.
Wydaje mi się, że z jakimś wbudowanym gcd byłby krótszy, ale nie mogłem znaleźć jednego bardzo łatwo (jestem trochę nowy w Rust i Integer, pomyliłem się) i podoba mi się fakt, że ten używa prostej arytmetyki liczb całkowitych, i żadnych wbudowanych bibliotek.
źródło
JavaScript (ES6), 86 bajtów
Pobiera dane wejściowe w składni curry
(p)(q)
.Wypróbuj online!
źródło
JavaScript, 79 bajtów
(Jestem nowy w kodowaniu golfa, więc prawdopodobnie można to łatwo poprawić)
Wyjaśnienie
źródło
(3,5)
powinno skutkować19
(nie24
), ponieważ(1,1)==(2,2)==(3,3)
,(2,4)==(1,2)
,(4,2)==(2,1)
i(2,6)==(1,3)
. (tj.(2,2)
powinno to skutkować1
nie5
, itp ...)