To wyzwanie jest hołdem dla użytkownika PPCG Dennisa za wygraną części rabusiów w The Programming Language Quiz .
Patrząc na stronę profilu Dennisa PPCG możemy zobaczyć całkiem imponujące rzeczy:
Obecnie ma ponad sześćdziesiąt osiem tysięcy reputacji, co czyni go drugim w klasyfikacji generalnej , przekraczając trzecie miejsce o prawie trzydzieści tysięcy. Niedawno wygrał nasze wybory na nowego moderatora i otrzymał błyszczący nowy diament obok swojego nazwiska. Ale osobiście uważam, że najbardziej interesującą częścią Dennisa jest jego identyfikator użytkownika PPCG: 12012.
Na pierwszy rzut oka 12012
wygląda prawie jak palindrom , liczba ta odczytuje to samo po odwróceniu, ale jest trochę poza. Może stać się palindromem, 21012
jeśli zamienimy pozycje pierwszego 1
i 2
, i może stać się palindromem, 12021
jeśli zamienimy ostatnie 1
i 2
. Ponadto, zgodnie z konwencją, że wiodące zera w liczbach nie są zapisywane, zamiana pierwszego 1
i 0
wyników na, 02112
a raczej na 2112
inny palindrom.
Zdefiniujmy liczbę Dennisa jako dodatnią liczbę całkowitą, która nie jest sama palindromiczna, ale może zostać przekształcona w palindrom poprzez zamianę pozycji co najmniej jednej pary dowolnych dwóch cyfr. Celu z szeregu Dennis liczba różnych par cyfr, które mogą być wymieniane w celu dokonania (niekoniecznie wyraźną) palindrom.
Tak więc kolejność 12012
jest 3 od 3 różnych par cyfr ( 12012
, , ) może być zastąpiony około produkować Palindromes. akurat jest najmniejszym numerem 3 Dennisa.12012
12012
12012
10
jest najmniejszą liczbą Dennisa i ma porządek 1, ponieważ przełączanie wokół 1
i 0
daje 01
aka, 1
czyli palindrom.
Urojone zera wiodące liczby nie liczą się jako cyfry przełączalne. Na przykład, zmieniając 8908
się 08908
i wymieniając dwie pierwsze cyfry uzyskać palindrom 80908
jest nieprawidłowy. 8908
nie jest liczbą Dennisa.
Można powiedzieć, że numery spoza Dennisa mają porządek 0.
Wyzwanie
Napisz program lub funkcję, która przyjmuje dodatnią liczbę całkowitą N i wypisuje lub zwraca N-tą najmniejszą liczbę Dennisa wraz z kolejnością w rozsądnym formacie, takim jak 12012 3
lub (12012, 3)
.
Na przykład 12012
jest 774-tym numerem Dennisa, więc jeśli 774
jest wejściem do twojego programu, wyjście powinno być coś w rodzaju 12012 3
. (Co ciekawe, 774 to kolejny numer Dennisa.)
Najkrótszy kod w bajtach wygrywa.
Oto pierwsze 20 liczb Dennisa i ich zamówienia w celach informacyjnych:
N Dennis Order
1 10 1
2 20 1
3 30 1
4 40 1
5 50 1
6 60 1
7 70 1
8 80 1
9 90 1
10 100 1
11 110 2
12 112 1
13 113 1
14 114 1
15 115 1
16 116 1
17 117 1
18 118 1
19 119 1
20 122 1
źródło
Odpowiedzi:
Pyth, 44 bajty
Wypróbuj online: demonstracja pakiet lub testowy
Głupi mały błąd (?) W Pyth zniszczył 41-bajtowe rozwiązanie.
Wyjaśnienie:
źródło
.f
. Oto żądanie ściągnięcia, które zadałem z powodu tego pytania: github.com/isaacg1/pyth/pull/151CJam, 45 bajtów
Wypróbuj online!
Jak to działa
źródło
Haskell, 174 bajty
p
sprawdza, czy lista jest palindromem.x!y
jestTrue
na listachx
iy
(które powinny mieć taką samą długość) różnią się dokładnie w dwóch miejscach. W szczególności, jeślix
jest permutacjąy
,x!y
określa, czy jest to „zamiana”.o n
znajduje porządek Dennisan
. Filtruje pod kątem zamiany wśród permutacjix = show n
, a następnie liczy, ile z tych zamian to palindromy. Analiza listy, która wykonuje tę liczbę, ma dodatkową ochronęnot (p x)
, co oznacza, że powróci,0
jeśli na początkun
był palindrom.snd (span (<'1') v)
Bit jest po prostudropWhile
tylko jeden bajt krótszy; zamienia się"01221"
w"1221"
.f
indeksuje z listy(i, o i)
gdzieo i > 0
(tj.i
jest liczbą Dennisa). Zwykle występowałby tutaj błąd off-by-one, ponieważ(!!)
liczy się od 0, ale problem liczy się od 1. Udało mi się temu zaradzić, rozpoczynając wyszukiwanie-10
( od którego okazało się być uważane przez mój program za liczbę Dennisa!), w ten sposób popychając wszystkie liczby we właściwe miejsca.f 774
jest(12012,3)
.źródło
Python 2, 176
Nie mogę sobie wyobrazić, że mój kod wymiany jest szczególnie optymalny, ale jest to najlepszy, jaki udało mi się uzyskać. Nie podoba mi się również to, jak często przekształcam ciąg znaków na liczbę całkowitą ...
Dla każdej liczby tworzy listę, czy wszystkie zamiany dwóch cyfr są palindromami. Zmniejsza licznik, gdy co najmniej jedna z tych wartości jest prawdziwa, a pierwotna liczba nie jest palindromem. Ponieważ
0+True
w python ocenia1
sumę końcowej listy działa dla porządku liczby Dennisa.źródło
Rdza, 390 bajtów
Nowa Java? : /
Nie golfił i skomentował:
źródło
Galaretka , 33 bajty (niekonkurujące)
Wypróbuj online!
Jak to działa
źródło
APL, 87
Ciało pętli zwraca wektor 4 liczb: 1) jego lewy argument
⍺
odczytany z wejścia, 2) liczbę dotychczasowych liczb Dennisa, 3) aktualną wartośćX
- licznika pętli, oraz 4) jego kolejnośćK
obliczoną jako suma palindromów w ramach permutacji 1-zamiany. Kończy się, gdy pierwsze dwa elementy stają się równe, a ostatnie dwa są zwracane w wyniku.źródło
JavaScript (ES6), 229
Jak zwykle JavaScript błyszczy z powodu swojej nieudolności w kombinatorykach (a może to moja nieudolność ...). Tutaj otrzymuję wszystkie możliwe pozycje zamiany, znajdując wszystkie liczby binarne o podanej długości i tylko 2 ustawione.
Przetestuj poniższy fragment kodu w przeglądarce Firefox (ponieważ MSIE jest daleki od zgodności z EcmaScript 6, a Chrome wciąż nie ma parametrów domyślnych)
źródło
awk, 199
Struktura
Stosowanie
Wklej to do konsoli i
echo
, jeśli chcesz, zastąp numer poPrzy wyższych liczbach robi się powoli;)
Wersja wielokrotnego użytku bez golfa
źródło
Ruby, 156
Używa funkcji Ruby, w której wywoływanie
"19".next!
powraca,"20"
aby uniknąć konieczności konwersji typów tam iz powrotem; po prostu używamy wyrażenia regularnego, aby zignorować wiodące0s
. Iteruje po wszystkich parach pozycji łańcucha, aby sprawdzić przełączniki palindromiczne. Pierwotnie napisałem tę funkcję rekurencyjną, ale psuje stos.Dane wyjściowe dla 774 to
["12012", 3]
(usunięcie znaków cudzysłowu kosztowałoby 4 bajty więcej, ale myślę, że specyfikacja na to pozwala).źródło