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 12012wygląda prawie jak palindrom , liczba ta odczytuje to samo po odwróceniu, ale jest trochę poza. Może stać się palindromem, 21012jeśli zamienimy pozycje pierwszego 1i 2, i może stać się palindromem, 12021jeśli zamienimy ostatnie 1i 2. Ponadto, zgodnie z konwencją, że wiodące zera w liczbach nie są zapisywane, zamiana pierwszego 1i 0wyników na, 02112a raczej na 2112inny 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ść 12012jest 3 od 3 różnych par cyfr ( 12012, , ) może być zastąpiony około produkować Palindromes. akurat jest najmniejszym numerem 3 Dennisa.120121201212012

10jest najmniejszą liczbą Dennisa i ma porządek 1, ponieważ przełączanie wokół 1i 0daje 01aka, 1czyli palindrom.

Urojone zera wiodące liczby nie liczą się jako cyfry przełączalne. Na przykład, zmieniając 8908się 08908i wymieniając dwie pierwsze cyfry uzyskać palindrom 80908jest nieprawidłowy. 8908nie 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 3lub (12012, 3).

Na przykład 12012jest 774-tym numerem Dennisa, więc jeśli 774jest 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

Oto ta sama lista do N = 1000.

Pyth, 44 bajty

L/lf_ITs.e.e`sXXNkZYbN=N`b2,Je.f&!_I`ZyZQ0yJ

Wypróbuj online: demonstracja pakiet lub testowy

Głupi mały błąd (?) W Pyth zniszczył 41-bajtowe rozwiązanie.

Wyjaśnienie:

L/lf_ITs.e.e`sXXNkZYbN=N`b2
L                             define a function y(b), which returns:
                      =N`b       assign the string representation of b to N
        .e             N         map each (k=Index, b=Value) of N to:
          .e         N             map each (Y=Index, Z=Value) of N to:
              XXNkZbN                switch the kth and Yth value in N
            `s                       get rid of leading zeros
       s                         combine these lists
   f_IT                          filter for palindromes
  l                              length
 /                        2      and divide by 2

,Je.f&!_I`ZyZQ0yJ
   .f        Q0     find the first input() numbers Z >= 0, which satisfy
      !_I`Z            Z is not a palindrom
     &                 and 
           yZ          y(Z) != 0
  e                 get the last number
 J                  and store in J
,J             yJ   print the pair [J, y(J)]

CJam, 45 bajtów

0{{)_s:C,2m*{~Ce\is_W%=},,2/:O!CCW%=|}g}ri*SO

Wypróbuj online!

Jak to działa

0          e# Push 0 (candidate).
{          e# Loop:
  {        e#   Loop:
    )_     e#     Increment the candidate and push a copy.
    s:C    e#     Cast to string and save in C.
    ,      e#     Get the length of C, i.e., the number of digits.
    2m*    e#     Push all pairs [i j] where 0 ≤ i,j < length(C).
    {      e#     Filter:
      ~    e#       Unwrap, pushing i and j on the stack.
      Ce\  e#       Swap the elements of C at those indices.
      is   e#       Cast to int, then to string, removing leading zeroes.
      _W%= e#       Copy, reverse and compare.
    },     e#     Keep the pairs for which = returned 1, i.e., palindromes.
    ,2/    e#     Count them and divide the count by 2 ([i j] ~ [j i]).
    :O     e#     Save the result (the order) in O.
    !      e#     Negate logically, so 0 -> 1.
    CCW%=  e#     Compare C with C reversed.
    |      e#     Compute the bitwise NOT of both Booleans.
           e#     This gives 0 iff O is 0 or C is a palindrome.
  }g       e#   Repeat the loop while the result is non-zero.
}ri*       e# Repeat the loop n times, where n is an integer read from STDIN.
           e# This leaves the last candidate (the n-th Dennis number) on the stack.
SO         e# Push a space and the order.

Haskell, 174 bajty

import Data.List
p x=x==reverse x
x!y=sum[1|(a,b)<-zip x y,a/=b]==2
o n|x<-show n=sum[1|v<-nub$permutations x,x!v,p$snd$span(<'1')v,not$p x]
f=([(x,o x)|x<-[-10..],o x>0]!!)

p sprawdza, czy lista jest palindromem.

x!yjest Truena listach xi y(które powinny mieć taką samą długość) różnią się dokładnie w dwóch miejscach. W szczególności, jeśli xjest permutacją y, x!yokreśla, czy jest to „zamiana”.

o nznajduje porządek Dennisa n. Filtruje pod kątem zamiany wśród permutacji x = 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, 0jeśli na początku nbył palindrom.

snd (span (<'1') v)Bit jest po prostu dropWhiletylko jeden bajt krótszy; zamienia się "01221"w "1221".

findeksuje z listy (i, o i)gdzie o i > 0(tj. ijest 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 774jest (12012,3).

Python 2, 176

i=input()
n=9
c=lambda p:`p`[::-1]==`p`
while i:n+=1;x=`n`;R=range(len(x));r=[c(int(x[:s]+x[t]+x[s+1:t]+x[s]+x[t+1:]))for s in R for t in R[s+1:]];i-=any(r)^c(n)
print n,sum(r)

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+Truew python ocenia 1sumę końcowej listy działa dla porządku liczby Dennisa.

Rdza, 390 bajtów

fn d(mut i:u64)->(u64,i32){for n in 1..{let mut o=0;if n.to_string()==n.to_string().chars().rev().collect::<String>(){continue}let mut s=n.to_string().into_bytes();for a in 0..s.len(){for b in a+1..s.len(){s.swap(a,b);{let t=s.iter().skip_while(|&x|*x==48).collect::<Vec<&u8>>();if t.iter().cloned().rev().collect::<Vec<&u8>>()==t{o+=1}}s.swap(a,b);}}if o>0{i-=1;if i<1{return(n,o)}}}(0,0)}

Nowa Java? : /

Nie golfił i skomentował:

fn main() {
    let (num, order) = dennis_ungolfed(774);
    println!("{} {}", num, order);  //=> 12012 3
}

fn dennis_ungolfed(mut i: u64) -> (u64, i32) {
    for n in 1.. {
        let mut o = 0;  // the order of the Dennis number
        if n.to_string() == n.to_string().chars().rev().collect::<String>() {
            // already a palindrome
            continue
        }
        let mut s = n.to_string().into_bytes();  // so we can use swap()
        for a in 0..s.len() {  // iterate over every combination of (i, j)
            for b in a+1..s.len() {
                s.swap(a, b);
                // need to start a new block because we're borrowing s
                {
                    let t = s.iter().skip_while(|&x| *x == 48).collect::<Vec<&u8>>();
                    if t.iter().cloned().rev().collect::<Vec<&u8>>() == t { o += 1 }
                }
                s.swap(a, b);
            }
        }
        // is this a Dennis number (order at least 1)?
        if o > 0 {
            // if this is the i'th Dennis number, return
            i -= 1;
            if i == 0 { return (n, o) }
        }
    }
    (0, 0)  // grr this is necessary
}

Galaretka , 33 bajty (niekonkurujące)

ṚḌ=
=ċ0^2°;ḌÇ
DŒ!Qç@ÐfDL©Ṡ>ѵ#Ṫ,®

Wypróbuj online!

Jak to działa

DŒ!Qç@ÐfDL©Ṡ>ѵ#Ṫ,®  Main link. No arguments.

              µ      Combine the chain to the left into a link.
               #     Find; execute the chain with arguments k = 0, 1, 2, ...
                     until n values of k result in a truthy value, where n is an
                     integer read implicitly from STDIN. Return those n values.

D                      Decimal; convert k to the list of its digits in base 10.
 Œ!                    Generate all permutations of the digits.
   Q                   Unique; deduplicate the list of permutations.
      Ðf               Filter:
    ç@  D                Call the helper link on the second line with the
                         unpermuted digits (D) as left argument, and each
                         permutation as the right one.
                       Keep permutations for which ç returns a truthy value.
         L©            Compute the length (amount of kept permutations) and save
                       it in the register.
           Ṡ           Sign; yield 1 if the length is positive, and 0 otherwise.
            >Ṅ         Compare the sign with the result from the helper link on
                       the first line. This will return 1 if and only if the
                       length is positive and Ñ returns 0.
                Ṫ      Tail; extract the last value of k.
                 ,®    Pair it with the value in the register.


=ċ0^2°;ḌÇ              Helper link. Arguments: A, B (lists of digits)

=                      Compare the corresponding integers in A and B.
 ċ0                    Count the zeroes, i.e., the non-matching integers.
   ^2                  Bitwise XOR the amount with 2.
     °                 Convert to radians. This will yield 0 if exactly two
                       corresponding items of A and B are different ,and a
                       non-integral number otherwise.
      ;                Prepend the result to B.
       Ḍ               Convert the result from decimal to integer. Note that
                       leading zeroes in the argument won't alter the outcome.
        Ç              Call the helper link on the first line.


ṚḌ=                    Helper link. Argument: m (integer)

Ṛ                      Convert m to decimal and reverse the digits.
 Ḍ                     Convert back to integer.
  =                    Compare the result with m.

APL, 87

2↓⎕{⍺(2⊃⍵+K⌊~A∧.=⌽A)X,K←+/{⍵∧.=⌽⍵}¨1↓∪,{⍕⍎Y⊣Y[⌽⍵]←⍵⊃¨⊂Y←A}¨∘.,⍨⍳⍴A←⍕X←1+3⊃⍵}⍣{=/2↑⍺}3⍴0

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ść Kobliczoną 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.

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)

F=c=>(P=>{for(a=9;c;o&&--c)if(P(n=++a+'',o=0))for(i=1<<n.length;k=--i;[x,y,z]=q,u=n[x],v=n[y],!z&&u-v&&(m=[...n],m[x]=v,m[y]=u,P(+(m.join``))||++o))for(j=0,q=[];k&1?q.push(j):k;k>>=1)++j;})(x=>x-[...x+''].reverse().join``)||[a,o]

// TEST

function go(){ O.innerHTML=F(I.value)}


// Less Golfed
U=c=>{
  P=x=>x-[...x+''].reverse().join``; // return 0 if palindrome 
  
  for(a = 9; // start at 9 to get the first that is known == 10
      c; // loop while counter > 0
      o && --c // decrement only if a Dennis number found
      )
  {  
    o = 0; // reset order count
    ++a;
    if (P(a)) // if not palindrome
    {  
      n = a+''; // convert a to string
      for(i = 1 << n.length; --i; ) 
      {
        j = 0;
        q = [];
        for(k = i; k; k >>= 1)
        {
          if (k & 1) q.push(j); // if bit set, add bit position to q
          ++j;
        } 
        [x,y,z] = q; // position of first,second and third '1' (x,y must be present, z must be undefined)
        u = n[x], v = n[y]; // digits to swap (not valid if they are equal)
        if (!z && u - v) // fails if z>0 and if u==v or u or v are undefined
        {
          m=[...n]; // convert to array
          m[x] = v, m[y] = u; // swap digits
          m = +(m.join``); // from array to number (evenutally losing leading zeroes)
          if (!P(m)) // If palindrome ...
            ++o; // increase order count 
        }  
      }
    }
  }  
  return [a,o];
}

//////
go()

<input id=I value=774><button onclick="go()">-></button> <span id=O></span>

awk, 199

{for(;++i&&d<$0;d+=o>0)for(o=j=_;j++<l=length(i);)for(k=j;k++<l;o+=v!=i&&+r~s){split(t=i,c,v=s=r=_);c[j]+=c[k]-(c[k]=c[j]);for(e in c){r=r c[e];s=s||c[e]?c[e]s:s;v=t?v t%10:v;t=int(t/10)}}print--i,o}

Struktura

{
    for(;++i&&d<$0;d+=o>0)
        for(o=j=_;j++<l=length(i);)
            for(k=j;k++<l;o+=v!=i&&+r~s)
            {
                split(t=i,c,v=s=r=_);
                c[j]+=c[k]-(c[k]=c[j]);
                for(e in c)
                {
                    r=r c[e];
                    s=s||c[e]?c[e]s:s;
                    v=t?v t%10:v;
                    t=int(t/10)
                }
            }
    print--i,o
}

Stosowanie

Wklej to do konsoli i echo, jeśli chcesz, zastąp numer po

echo 20 | awk '{for(;++i&&d<$0;d+=o>0)for(o=j=_;j++<l=length(i);)for(k=j;k++<l;o+=v!=i&&+r~s){split(t=i,c,v=s=r=_);c[j]+=c[k]-(c[k]=c[j]);for(e in c){r=r c[e];s=s||c[e]?c[e]s:s;v=t?v t%10:v;t=int(t/10)}}print--i,o}'

Przy wyższych liczbach robi się powoli;)

Wersja wielokrotnego użytku bez golfa

{
    dennisFound=0

    for(i=0; dennisFound<$0; )
    {
        i++
        order=0

        for(j=0; j++<length(i); )
        {
            for(k=j; k++<length(i); )
            {
                split(i, digit, "")
                digit[j]+=digit[k]-(digit[k]=digit[j]) # swap digits

                tmp=i
                iRev=iFlip=iFlipRev=""

                for(e in digit)
                {
                    if(tmp>0)                        # assemble reversed i
                        iRev=iRev tmp%10
                    tmp = int( tmp/10 )

                    iFlip=iFlip digit[e]             # assemble flipped i

                    if(iFlipRev>0 || digit[e]>0)     # assemble reversed flipped i
                        iFlipRev=digit[e] iFlipRev   # without leading zeros
                }
                if(iRev!=i && 0+iFlip==iFlipRev) order++  # i is not a palindrome,
            }                                             # but flipped i is
        }
        if(order>0) dennisFound++
    }
    print i, order
}

Ruby, 156

->i{s=?9
(o=0;(a=0...s.size).map{|x|a.map{|y|j=s+'';j[x],j[y]=j[y],j[x];x>y&&j[/[^0].*/]==$&.reverse&&o+=1}}
o<1||s==s.reverse||i-=1)while i>0&&s.next!;[s,o]}

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ące 0s. 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).