23
\$\begingroup\$

Given an integer N as input, output the Nth permutapalindromic number.

A permutapalindromic number is a strictly positive integer such that there is at least one permutation of its digits that results in a palindrome (i.e. a number that is its own reverse).

For example, 117 is a permutapalindromic number since its digits can be permuted into 171, which is a palindrome.

We consider that numbers like 10 are not permutapalindromic numbers, even though 01 = 1 is a palindrome. We impose that the palindromic permutation must not have a leading zero (as such, 0 itself is not permutapalindromic).

Numbers that are already palindromes are also permutapalindromic, since permuting nothing is valid.

Inputs and outputs

  • N may be either 0-indexed or 1-indexed. Please indicate which of the two your answer uses.
  • The input can be taken through STDIN, as a function argument, or anything similar in your language of choice. The output can be written to STDOUT, returned from a function, or anything similar in your language of choice.
  • The input and output must be in the decimal base.

Test cases

The following test cases are 1-indexed. Your program must be able to pass any of the test cases presented here in at most 1 minute.

N      Output

1      1
2      2
3      3
4      4
5      5
6      6
7      7
8      8
9      9
10     11
42     181
100    404
128    511
256    994
270    1166

Scoring

This is , so the shortest answer in bytes wins.

\$\endgroup\$
6
  • \$\begingroup\$ It's quite impossible to not pass the last testcase in one minute... \$\endgroup\$
    – Leaky Nun
    Aug 17, 2016 at 7:41
  • \$\begingroup\$ OEIS A084050 (contains extra cases like 10) \$\endgroup\$
    – Leaky Nun
    Aug 17, 2016 at 7:44
  • \$\begingroup\$ What is the largest input? \$\endgroup\$
    – Adám
    Aug 17, 2016 at 9:01
  • \$\begingroup\$ @Adám Your program should theoretically work for any number, no matter how big. \$\endgroup\$
    – Fatalize
    Aug 17, 2016 at 9:03
  • 2
    \$\begingroup\$ @Adám This is a pretty arbitrary limit that is dependant on the language used. Let's say that it should theoretically work for the biggest integer your language can represent by default (so all integers if bignums is the default in your language). \$\endgroup\$
    – Fatalize
    Aug 17, 2016 at 9:11

22 Answers 22

9
\$\begingroup\$

05AB1E, 15 14 13 bytes

Saved a byte thanks to Emigna! Code:

µNœvyJÂïÊP}_½

Explanation:

µ               # c = 0, when c is equal to the input, print N.
 N              # Push N, the iteration variable.
  œ             # Push all permutations of N.
   vyJ    }     # For each permutation...
      Â         #   Bifurcate, which is short for duplicate and reverse.
       ï        #   Convert the seconds one to int, removing leading zeros.
        Q       #   Check if they are not equal.
         P      #   Product of the stack.
           _    # Logical not.
            ½   # Pop a value, if 1 then increase c by 1.

Uses the CP-1252 encoding. Try it online!.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ µNœvyJÂïQ}O__½ for 14. \$\endgroup\$
    – Emigna
    Aug 17, 2016 at 9:14
  • \$\begingroup\$ @Emigna Thanks! I didn't think of that. \$\endgroup\$
    – Adnan
    Aug 17, 2016 at 9:18
  • \$\begingroup\$ The ÂïÊ approach doesn't work anymore (since "010" == 10 for N=100 for example), in neither the legacy nor new 05AB1E versions. I assume back in 2016 comparing strings with leading 0s with integers was still giving unequal results, but since in 05AB1E strings/integers are interchangeable, this has been invalid for a while. But, here two 12-byters for both the legacy version: µNœε¬Ā*Q}OĀ and new version: µNDœε¬Ā*Q}à. \$\endgroup\$ Oct 28, 2022 at 13:53
8
\$\begingroup\$

Brachylog, 19 bytes

~l<:1at.
.=pPrPl~l?

Try it online!

Takes about 17 seconds for N = 270.

Explanation

  • Main predicate:

    ~l            Create a list whose length is Input.
      <           The list is strictly increasing.
       :1a        Apply predicate 1 to each element of the list.
          t.      Output is the last element of the list.
    
  • Predicate 1:

    .=            Input = Output = an integer
      pPrP        A permutation P of the Output is its own reverse
          l~l?    The length of P is equal to the length of the Input
    
\$\endgroup\$
7
\$\begingroup\$

Pyth, 14

e.ff&_ITshT.p`

Try it here or run a Test Suite

Expansion:

e.ff&_ITshT.p`ZQ   # Auto-fill variables
 .f            Q   # Find the first input number of numbers that give truthy on ...
           .p`Z    # Take all the permutations of the current number
   f&              # Keep those that give a truthy value for both:
     _IT           # Invariance on reversing (is a palindrome)
        shT        # The integer value of the first digit (doesn't start with zero)
                   # A list with any values in it it truthy, so if any permutation matches
                   # these conditions, the number was a permutapalindrome
e                  # Take only the last number
\$\endgroup\$
6
\$\begingroup\$

Brachylog, 21 20 bytes

1 byte thanks to Fatalize.

Did you design the challenge for Brachylog?

:1yt.
0<.={@epcPrP!}

Try it online!

270 takes about half a minute here.

Z = 1166
real    0m27.066s
user    0m26.983s
sys     0m0.030s

Exit code:     0

Predicate 0 (main predicate)

:1yt.
:1y    find the first Input solutions to predicate 1
   t.  unify the output with the last element

Predicate 1 (auxiliary predicate)

0<.={@epcPrP!}
0<.              0 < Output
  .=             Assign a value to Output (choice point)
    {        }   Inline predicate:
     @e              Digits of the Output
       p             A permutation (choice point)
        c            Concatenate (fails if leading zero present)
         P           store as P
          rP         assert that P reversed is still P
            !        remove the choice point in this predicate, so
                     that it will not return twice for the same number.
\$\endgroup\$
0
6
\$\begingroup\$

JavaScript (ES6), 99 bytes

f=(n,i=1)=>(n-=/^.0+$/.test(i)</^((.),\2,)*(.)(,\3)?(,(.),\6)*$/.test([...i+''].sort()))?f(n,i+1):i

Explanation:

f=(n,i=1)=>             look for n numbers starting at 1
 (n-=                   test whether current guess is
  /^.0+$/.test(i)<      not a round number and
  /^((.),\2,)*          pairs of comma-separated digits
   (.)(,\3)?            possible single digit
   (,(.),\6)*$/         pairs of comma-separated digits
   .test(               matches the comma-joined
    [...i+''].sort()))  digits in ascending order
 ?f(n,i+1)              if not n numbers found try next number
 :i                     found it!
\$\endgroup\$
4
  • \$\begingroup\$ 1100 is a round permutapalindromic number. \$\endgroup\$
    – Adám
    Aug 17, 2016 at 9:40
  • \$\begingroup\$ @Adám It's not round, it contains at least two nonzero digits. \$\endgroup\$
    – Neil
    Aug 17, 2016 at 9:46
  • \$\begingroup\$ @Neil: +2 bytes -- you really ought to count the f= when you refer to it later \$\endgroup\$
    – charlie
    Aug 17, 2016 at 17:24
  • \$\begingroup\$ @charlie Sorry, I always forget to do that. \$\endgroup\$
    – Neil
    Aug 17, 2016 at 17:30
5
\$\begingroup\$

R, 145 bytes

g=function(n){d=b=0 
while(d<n){b=b+1
if(sum(a<-table(strsplit(n<-as.character(b),""))%%2)==nchar(n)%%2&(!names(a)[1]==0|a[1]|sum(!a)>1))d=d+1}
b}

ungolfed

f=function(b){
    a<-table(strsplit(n<-as.character(b),""))%%2
    sum(a)==nchar(n)%%2&(!names(a)[1]==0|a[1]|sum(!a)>1)
}
g=function(n){
    d=b=0
    while(d<n){
         b=b+a
         if(f(b)) d=d+1
    }
    b
}

Essentially -- a function checking membership in permutapalindromic set, and a while loop incrementing until it finds the nth member.

\$\endgroup\$
4
\$\begingroup\$

Python 2.7, 163 154 bytes:

from itertools import*;I,F,Q=input(),[],2
while len(F)<I:F=[g for g in range(1,Q)if any(i==i[::-1]*(i[0]>'0')for i in permutations(`g`))];Q+=1
print F[-1]

Simple enough. Basically uses a while loop to repeatedly create arrays containing permutapalindromic numbers the the range [1,Q) until Q is large enough such that the array contains Input number of items. It then outputs the last element in that array.

Try It Online! (Ideone)

\$\endgroup\$
4
\$\begingroup\$

Dyalog APL, 51 bytes

One-indexed.

{⍵⊃{⍵/⍨{(⍵≤9)∨(1<≢c~'0')∧1≥+/2|+⌿c∘.=∪c←⍕⍵}¨⍵}⍳5×⍵}

{ a function where ⍵ represents the argument

⍵⊃{ use the argument to pick from the result of the function

⍵/⍨{ filter the argument with the result of the function

(⍵≤9)∨ the argument is less or equal to 9, OR

(1<≢c~'0')∧ there remains more than one digit when zeros are removed AND

1≥+/ 0 or 1 is the sum of

2| the oddnesses of

+⌿ of the column sums of

c∘.=∪c the comparison table of c and the unique elements of c, where c...

←⍕⍵ is the string representation of the argument

}¨⍵ applied to each of the arguments

}⍳5×⍵ applied to {1, 2, 3, ..., 5 times the argument}

} [end of function]

Finishes all the test cases instantly on TryAPL

\$\endgroup\$
8
  • \$\begingroup\$ Can you prove that a(n) <= 5n? \$\endgroup\$
    – Leaky Nun
    Aug 17, 2016 at 8:25
  • \$\begingroup\$ The second solution generates incorrect results. \$\endgroup\$
    – Leaky Nun
    Aug 17, 2016 at 8:31
  • \$\begingroup\$ The first solution also generates incorrect results. \$\endgroup\$
    – Leaky Nun
    Aug 17, 2016 at 8:32
  • \$\begingroup\$ @LeakyNun Which ones are incorrect? And if 5× isn't enough, there's space for 9×... \$\endgroup\$
    – Adám
    Aug 17, 2016 at 8:38
  • 2
    \$\begingroup\$ The problem is not whether 5n is enough for the testcase. The problem is whether you can prove it. \$\endgroup\$
    – Leaky Nun
    Aug 17, 2016 at 8:49
4
\$\begingroup\$

JavaScript (ES6), 92

n=>eval("for(a=0;n-=(a++<9||(b=[...a+``].sort().join``)>9&!b.replace(/(.)\\1/g,``)[1]););a")

Less golfed

n=>{
  for( a = 0;
       n -= // decrement n (and exit when 0) if the check below is true == a is permutapalindromic
            (a ++ < 9 // single digit (meanwhile, increment a)
             || // or...
             ( b=[...a+``].sort().join`` )// build a string with the digits sorted
               > 9 // required at least 2 non zero digits
             & ! b.replace(/(.)\1/g,``)[1] // removed all digits pair, there must be just 1 or no single digits remaining
            );
     );
   return a;
}

Test

f=n=>eval("for(a=0;n-=(a++<9||(b=[...a+``].sort().join``)>9&!b.replace(/(.)\\1/g,``)[1]););a")

function update() {
  O.textContent=f(+I.value)
}

update()
<input id=I oninput=update() type=number value=100>
<pre id=O></pre>

\$\endgroup\$
4
\$\begingroup\$

Japt, 13 bytes

_ì á fÎdêQ}iU

Try it

0-indexed

_ì á fÎdêQ}iU
_         }iU # Find the N-th number that meets this condition:
 ì            #  Get the digits as an array
   á          #  Get all permutations of that array
     f        #  Keep only permutations where:
      Î       #   The first digit is not zero
       d      #  Return true if any remaining permutation:
        êQ    #   Is a palindrome
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice! Tried this one earlier but the best I could manage was 14. And then I realised it didn't work! \$\endgroup\$
    – Shaggy
    Oct 28, 2022 at 22:27
3
\$\begingroup\$

Perl 6, 66 bytes

{(1..*).grep(*.comb.permutations.grep({+.join.flip eq.join}))[$_]}

0 based

Explanation:

# bare block lambda which takes an implicit parameter 「$_」
{
  # all numbers greater than 0
  (1..*)\

  # remove any which aren't permutapalindromic
  .grep(

    # 「*」 here starts a Whatever lambda
    *\
    # split into list of digits
    .comb\
    # get all of the permutations of the digits
    .permutations\
    # find out if there are any palindromes
    .grep(

      # another bare block lambda taking 「$_」 as implicit parameter
      {
        # compare the current permutation with its reverse stringwise
        # numify only one side to get rid of leading 「0」
        +$_.join.flip eq $_.join
      }
    )

  # get the value at the index
  )[$_]
}

Test:

#! /usr/bin/env perl6
use v6.c;
use Test;

my &permutapalindromic = {(1..*).grep(*.comb.permutations.grep({+.join.flip eq.join}))[$_]}

my @tests = (
  1   => 1,
  2   => 2,
  3   => 3,
  4   => 4,
  5   => 5,
  6   => 6,
  7   => 7,
  8   => 8,
  9   => 9,
  10  => 11,
  42  => 181,
  100 => 404,
  128 => 511,
  256 => 994,
  270 => 1166,
);

plan +@tests + 1;

my $start-time = now;
for @tests -> $_ ( :key($input), :value($expected) ) {
  # zero based instead of one based, so subtract 1
  is-deeply permutapalindromic( $input - 1 ), $expected, .gist;
}
my $finish-time = now;

my $total-time = $finish-time - $start-time;

cmp-ok $total-time, &[<], 60, 'Less than 60 seconds for the tests';
diag "$total-time seconds";
\$\endgroup\$
3
\$\begingroup\$

Brachylog v2, 16 bytes

<~l<₁{≜.pX↔Xp}ᵐt

Try it online!

Borrows Fatalize's ~l trick because my attempt at a -based solution is a bit too slow...

<                   The input is less than
 ~l                 the length of some list
   <₁               which is strictly increasing
     {       }ᵐ     where each element:
      ≜.            is an integer chosen such that
        pX          some permutation X
          ↔X        is X reversed,
            p       a permutation of which is the element.
               t    Output the final element of that list.
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 10 9 bytes

SṖ'Ṙ⌊=)ȯt

Try it Online!

You say any test case presented in the challenge should pass in under a minute? All test cases presented in the challenge pass in under 30 seconds. That's what I call gaming (no doubt the other answers do too though lol).

Explained

SṖ'Ṙ⌊=)ȯt
      )ȯ  # Starting at 1, get the first (input)th numbers where:
SṖ        #   From the permutation of the digits of the number,
  '       #   There exists at least 1 such that:
   Ṙ⌊     #   The reverse (cast to int)
     =    #   Equals that permutation
        t # Print the tail of the list
\$\endgroup\$
2
  • \$\begingroup\$ 7 \$\endgroup\$
    – emanresu A
    Oct 31, 2022 at 1:08
  • \$\begingroup\$ @emanresuA that considers 100 to be a valid number, even though it isn't \$\endgroup\$
    – lyxal
    Oct 31, 2022 at 1:12
3
\$\begingroup\$

Gaia, 15 bytes

:vdṙ=
ṙf↑¦Σ
↑#)

Try it online!

First ever code golf, so please tell me if I'm doing anything wrong.

Explained

:vdṙ= # Helper function 2 (hf2)
:     # Push two copies of the function argument
 vdṙ  # str(int(argument[::-1]))
    = # does that equal the original function argument?
-----
ṙf↑¦Σ # Helper function 1 (hf1)
ṙf    # Get all permutations of the string representation of the function argument
  ↑¦  # Map hf2 to each item
    Σ # and summate the result
-----
↑#)   # Main function
↑#    # First (input) items where hf1 is true
  )   # get the last item of that
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$
    – u-ndefined
    Oct 30, 2022 at 12:49
  • \$\begingroup\$ @u-ndefined thank you! I really look forward to posting some more code golf answers here! \$\endgroup\$
    – Cliff
    Oct 31, 2022 at 11:33
2
\$\begingroup\$

Javascript (using external library - Enumerable) (142 bytes)

   n=>_.Sequence(n,i=>{l=i+"";p=_.Permutations(_.From(l),l.length).Any(y=>y.First()!="0"&&y.SequenceEqual(y.Reverse()));if(p){return i;}}).Last()

Link to lib:https://github.com/mvegh1/Enumerable/

Code explanation: _.Sequence creates an enumerable for a count of "n" elements, based on the predicate of signature ("i"teration,"a"ccumulated array). Cast the current iteration to a string, and create an enumerable of all permutations from it. Test if any of the permutations satisfy the test of not starting with "0" and that the reversal of the permutation equals the permutation. Return the last element in the sequence because that is the desired output as per OP

enter image description here

\$\endgroup\$
2
\$\begingroup\$

Python 2, 93 bytes

S=sorted
f=lambda n,i=1:n and-~f(n-(S(`i`)in[S(`k`)for k in range(9*i)if`k`==`k`[::-1]]),i+1)

1-indexed. Depending on your system, the last test case may exceed the allowed recursion depth.

Does not compute permutations. Instead, uses the fact that two strings are permutations if they are equal when sorted. To test if a number is permutapalindromic, checks if its sorted digits equal the sorted digits of any palindrome up to a bound.


96 bytes:

f=lambda n,i=1:n and-~f(n-(sum(`i`.count(`d`)%2for d in range(10))<2*(set(`i`[1:])!={'0'})),i+1)

1-indexed. Depending on your system, the last test case may exceed the allowed recursion depth.

This doesn't look at permutations and instead uses the following characterization:

A number is permutapalindromic exactly when

  • At most one of its digits appears an odd number of times, and
  • It does not have the form d00...00 with one or more zeroes.

This is true because a palindrome must pair off digits from the start and end, except for a possible center digit. The exception comes from the requirement that the leading digit be nonzero, and so some nonzero digit must appear twice unless the number is single-digit.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 89 87 bytes

import Data.List
(filter(any(show.floor.read.reverse>>=(==)).permutations.show)[0..]!!)
\$\endgroup\$
2
\$\begingroup\$

Jelly, 14 bytes

1DŒ!ŒḂ×ḢƊ€ẸƲ#Ṫ

Try it online!

How it works

1DŒ!ŒḂ×ḢƊ€ẸƲ#Ṫ - Main link. Takes an argument n on the left
           Ʋ   - Group the previous 4 links into a monad f(k):
 D             -   Convert k to digits
  Œ!           -   Permutations of k's digits
        Ɗ€     -   Over each permutation p:
    ŒḂ         -     Is p a palindrome?
      ×Ḣ       -     And is the first digit non-zero?
          Ẹ    -   Is that true for any permutation?
1           #  - Count up k = 1, 2, 3, ... until n k return true under f(k)
                 Return those k
             Ṫ - Return the n'th k
\$\endgroup\$
2
\$\begingroup\$

Perl 5 -p, 69 bytes

1while$_-=(join'',sort++$\=~/./g)=~s/(.)\1//gr=~y///c<2*$\!~/^.0+$/}{

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python + golfing-shortcuts, 128 bytes

A port of R. Kap's answer.

from s import*
I,F,Q=e(i()),[],2
while l(F)<I:F=[G for G in r(1,Q)if a(I==I[::-1]*(I[0]>'0')for I in Im(repr(G)))];Q+=1
p(F[-1])
\$\endgroup\$
1
\$\begingroup\$

C, 254 bytes

#define W while
#define R return
f(j){int c=0,a[16]={0};do++a[j%10],++c;W(j/=10);if(c>1&&a[0]>=c-1)R 0;c%=2;W(j<10)if(a[j++]%2&&(!c||++c>2))R 0;R 1;}g(n){int k=0,i=1;W(k<n)if(f(i++))++k;R i-1;}main(a){printf("N>");scanf("%d",&a);printf("%d\n",g(a));}
\$\endgroup\$
1
\$\begingroup\$

Jelly, 13 bytes

Dœ^/LỊaṢ-ịø#Ṫ

Try it online!

Out of curiosity, I decided to see how far I could get without actually computing permutations, and two hours of head bashing later it ties caird's existing answer (modulo a golf to use ø). The logic boils down to checking two conditions:

  • At most one digit occurs an odd number of times.

  • There must be multiple nonzero digits if at least one digit is zero.

and stuck in a blender for five minutes on high, that's:

           #     Count up collecting the first n integers
          ø      starting from 0 which satisfy:
D                Do the digits
 œ^/             reduced by symmetric multiset difference
    LỊ           have length ≤ 1?
       Ṣ         Sort the digits,
      a          replace them all with 0 if the previous condition is not met,
        -ị       and take the second to last element (wrapping around if length 1),
           #     succeeding if it's nonzero.
            Ṫ    Return the last result.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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