Generate Dennis Numbers

Question

This challenge is a tribute to PPCG user Dennis for winning the robbers' part of The Programming Language Quiz.

Looking at Dennis' PPCG profile page we can see some pretty impressive stuff:

He currently has over sixty-eight thousand reputation, making him second in rep overall, surpassing third place by almost thirty thousand. He recently won our election for a new moderator and got a shiny new diamond next to his name. But I personally think the most interesting part about Dennis is his PPCG user ID number: 12012.

At first glance 12012 almost looks like a palindrome, a number that reads the same when reversed, but it's a little off. It can become the palindrome 21012 if we swap the positions of the first 1 and 2, and it can become the palindrome 12021 if we swap the last 1 and 2. Also, following the convention that leading zeroes in a number are not written, swapping the first 1 and the 0 results in 02112 or rather 2112 which is another palindrome.

Let's define a Dennis number as a positive integer that is not palindromic itself but can be made into a palindrome by swapping the positions of at least one pair of any two digits. The order of a Dennis number is the number of distinct pairs of digits that can be swapped to make a (not necessarily distinct) palindrome.

So the order of 12012 is 3 since 3 distinct pairs of its digits (12012, 12012, 12012) can be swapped around to produce palindromes. 12012 happens to be the smallest order 3 Dennis number.

10 is the smallest Dennis number and has order 1 because switching around the 1 and 0 gives 01 a.k.a. 1 which is a palindrome.

The imaginary leading zeroes of a number don't count as switchable digits. For example, changing 8908 to 08908 and swapping the first two digits to get the palindrome 80908 is invalid. 8908 is not a Dennis number.

Non-Dennis numbers could be said to have order 0.

Challenge

Write a program or function that takes in a positive integer N and prints or returns the Nth smallest Dennis number along with its order in some reasonable format such as 12012 3 or (12012, 3).

For example, 12012 is the 774th Dennis number so if 774 is the input to your program, the output should be something like 12012 3. (Curiously, 774 is another Dennis number.)

The shortest code in bytes wins.

Here is are the first 20 Dennis numbers and their orders for reference:

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

Here is the same list up to N = 1000.

\$\begingroup\$ This has got to be added to OEIS \$\endgroup\$
– Claudiu
Commented Sep 12, 2015 at 7:37 — Claudiu, Commented Sep 12, 2015 at 7:37
\$\begingroup\$ @Claudiu this is added to the OEIS. \$\endgroup\$
– user48538
Commented Jan 12, 2016 at 15:17 — user48538, Commented Jan 12, 2016 at 15:17

Dennis · Accepted Answer · 2016-05-17 23:19:44Z

CJam, 45 bytes

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

Try it online!

How it works

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.

I've hit the rep cap already, but I had to post the first answer. — Dennis, Commented Sep 11, 2015 at 23:14
Ugh. How do I force myself to upvote a comment with 42 upvotes? — Maya, Commented Aug 13, 2017 at 17:19

Jakube · Accepted Answer · 2015-09-13 07:45:35Z

Pyth, 44 bytes

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

Try it online: Demonstration or Test Suite

A stupid little bug (?) in Pyth ruined a 41 byte solution.

Explanation:

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)]

@CatsAreFluffy Had to look up the Github history. It concerns .f. Here's the pull request that I made because of this question: github.com/isaacg1/pyth/pull/151 — Jakube, Commented Mar 1, 2016 at 22:39

Community · Accepted Answer · 2020-06-17 09:04:33Z

Haskell, 174 bytes

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 checks whether a list is a palindrome.

x!y is True iff the lists x and y (which should have the same length) differ in exactly two places. Specifically, if x is a permutation of y, x!y determines whether it is a "swap".

o n finds the Dennis-order of n. It filters for swaps among the permutations of x = show n, and then counts how many of those swaps are palindromes. The list comprehension that performs this count has an extra guard not (p x), which means it will return 0 if n was a palindrome to begin with.

The snd (span (<'1') v) bit is just dropWhile but one byte shorter; it turns "01221" into "1221".

f indexes from a list of (i, o i) where o i > 0 (i.e. i is a Dennis number.) There would normally be an off-by-one error here, as (!!) counts from 0 but the problem counts from 1. I managed to remedy this by starting the search from -10 (which turned out to be considered a Dennis number by my program!) thereby pushing all the numbers into the right spots.

f 774 is (12012,3).

Doorknob · Accepted Answer · 2015-09-12 03:15:13Z

Rust, 390 bytes

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)}

The new Java? :/

Ungolfed and commented:

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
}

\$\begingroup\$ 323 bytes \$\endgroup\$
– Maya
Commented Jul 17, 2023 at 0:25 — Maya, Commented Jul 17, 2023 at 0:25

Community · Accepted Answer · 2020-06-17 09:04:33Z

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)

I can't imagine that my swapping code is particularly optimal, but this is the best I've been able to get. I also don't like how often I convert between string and integer...

For each number, it creates a list of a whether all of the swaps of two digits are palindromes. It decrements the counter when at least one of these values is true, and the original number is not a palindrome. Since 0+True in python evaluates to 1 the sum of the final list works for the order of the Dennis number.

emanresu A · Accepted Answer · 2022-09-04 06:29:22Z

Jelly, 33 bytes

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

Try it online!

How it works

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.

user44932 · Accepted Answer · 2015-09-13 14:32:14Z

APL, 87

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

The body of the loop returns a vector of 4 numbers: 1) its left argument ⍺ read from input, 2) count of Dennis numbers so far, 3) current value of X — the loop counter, and 4) its order K computed as sum of palindromes within 1-swap permutations. It terminates when the first two elements become equal and last two are then returned as result.

edc65 · Accepted Answer · 2015-09-14 17:13:42Z

JavaScript (ES6), 229

As usual, JavaScript shines for its ineptitude for combinatorics (or, maybe it's my ineptitude...). Here I get all possibile swap positions finding all binary numbers of the given length and just 2 ones set.

Test running the snippet below in Firefox (as MSIE is far from EcmaScript 6 compliant and Chrome is still missing default parameters)

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>

Cabbie407 · Accepted Answer · 2015-09-13 11:02:56Z

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}

Structure

{
    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
}

Usage

Paste this to your console and replace the number after echo, if you want

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}'

It gets slow at higher numbers ;)

Ungolfed reusable version

{
    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
}

histocrat · Accepted Answer · 2015-09-14 16:31:02Z

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]}

Uses the Ruby feature where calling "19".next! returns "20" to avoid having to convert types back and forth; we just use a regex to ignore leading 0s. Iterates over all pairs of string positions to check for palindromic switches. I originally wrote this a recursive function but it busts the stack.

Output for 774 is ["12012", 3] (removing the quotation marks would cost 4 more bytes but I think the spec allows them).

Kevin Cruijssen · Accepted Answer · 2020-06-17 15:09:13Z

05AB1E, 34 bytes

∞ʒÂÊ}ε©ā<2.Æε®DrèRyǝïÂQ}O‚}ʒθĀ}I<è

Try it online or output the first \$n\$ Dennis numbers.

Explanation:

∞            # Push an infinite positive list: [1,2,3,...]
 ʒ           # Filter it by:
  Â          #  Bifurcate the current number (short for Duplicate & Reverse Copy)
   Ê         #  Check that the reverse copy does NOT equal the number itself
 }ε          # After we've filtered out all palindromes: map over the remaining numbers:
   ©         #  Store it in variable `®` (without popping)
    ā        #  Push a list in the range [1, length] (without popping)
     <       #  Decrease each by 1 to make the range [0, length)
      2.Æ    #  Get all possible pairs of this list
    ε        #  Map each pair of indices to:
     ®D      #   Push the number from variable `®` twice
       r     #   Reverse the stack order from [indices,nr,nr] to [nr,nr,indices]
        è    #   Get the digits of the number at these indices
         R   #   Reverse this pair
          y  #   Push the indices we're mapping over again
           ǝ #   And insert the reversed digits back into the number at the indices
     ï       #   Cast it to an integer to remove leading 0s
      Â      #   Bifurcate it (short for Duplicate & Reverse Copy)
       Q     #   Check that the reverse copy equals the number itself,
             #   resulting in 1 if its a palindrome, and 0 if not
    }O       #  After the inner map: sum all truthy values together
      ‚      #  And pair it with the number
 }ʒ          # After the outer map: filter again:
   θ         #  Where the last value of the pair (the calculated order)
    Ā        #  Is not 0
  }I         # After the filter: push the input-integer
    <        # Decrease it by 1 (because 05AB1E uses 0-based indexing)
     è       # And get the pair at that index in the infinite list
             # (after which it is output implicitly as result)

Arnauld · Accepted Answer · 2020-06-17 14:33:45Z

0

JavaScript (ES6), 151 bytes

f=(n,x)=>(g=a=>(a=[...+a.join``+''])+''==a.reverse(k=0))(a=[...x+''])|a.map((p,i)=>a.map((q,j)=>k+=g(b=[...a],b[i]=q,b[j]=p)))|!k||--n?f(n,-~x):[x,k/2]

Try it online!

answered Jun 17, 2020 at 14:33

Arnauld

198k20 gold badges179 silver badges650 bronze badges

Add a comment |

Xcali · Accepted Answer · 2020-07-09 18:59:07Z

0

Perl 5 `-alp`, 148 bytes

$_=9;while(!$o||--$F[0]){$o=0;if(++$_ ne reverse){for$i(0..(@a=/./g)){map{@b=@a;@b[$i,$_]=@b[$_,$i];$o+=($t=1*join'',@b)eq reverse$t}$i..$#a}}}say$o

Try it online!

Output is on two lines. First line is the order; second line is the number.

answered Jul 9, 2020 at 18:59

Xcali

16.2k2 gold badges15 silver badges39 bronze badges

Add a comment |

Stack Exchange Network

Generate Dennis Numbers

Challenge

13 Answers 13

CJam, 45 bytes

How it works

Pyth, 44 bytes

Explanation:

Haskell, 174 bytes

Rust, 390 bytes

Python 2, 176

Jelly, 33 bytes

How it works

APL, 87

JavaScript (ES6), 229

awk, 199

Structure

Usage

Ungolfed reusable version

Ruby, 156

05AB1E, 34 bytes

JavaScript (ES6), 151 bytes

Perl 5 `-alp`, 148 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
number
sequence
palindrome
or ask your own question.

Linked

Hot Network Questions

Generate Dennis Numbers

Challenge

13 Answers 13

CJam, 45 bytes

How it works

Pyth, 44 bytes

Explanation:

Haskell, 174 bytes

Rust, 390 bytes

Python 2, 176

Jelly, 33 bytes

How it works

APL, 87

JavaScript (ES6), 229

awk, 199

Structure

Usage

Ungolfed reusable version

Ruby, 156

05AB1E, 34 bytes

JavaScript (ES6), 151 bytes

Perl 5 -alp, 148 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfnumbersequencepalindrome or ask your own question.

Linked

Related

Hot Network Questions

Perl 5 `-alp`, 148 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
number
sequence
palindrome
or ask your own question.