Números permutapalindrômicos

18

Dado um número inteiro Ncomo entrada, Nimprima o número permutapalindrômico.

Um número permutapalindrômico é um número inteiro estritamente positivo, de modo que exista pelo menos uma permutação de seus dígitos que resulte em um palíndromo (isto é, um número que é seu próprio reverso).

Por exemplo, 117é um número permutapalindrômico, pois seus dígitos podem ser permutados 171, o que é um palíndromo.

Consideramos que números como 10não são números permutapalindrômicos, mesmo sendo 01 = 1um palíndromo. Nós impomos que a permutação palindrômica não deve ter um zero inicial (como tal, 0ela própria não é permutapalindrômica).

Números que já são palíndromos também são permutapalindrômicos, pois permutar nada é válido.

Entradas e saídas

  • Npode ser 0 ou 1. Indique qual dos dois a sua resposta usa.
  • A entrada pode ser acessada STDIN, como argumento de função, ou qualquer coisa semelhante no idioma de sua escolha. A saída pode ser gravada STDOUT, retornada de uma função ou qualquer coisa semelhante no idioma de sua escolha.
  • A entrada e a saída devem estar na base decimal.

Casos de teste

Os seguintes casos de teste são indexados 1. Seu programa deve ser capaz de passar em qualquer um dos casos de teste apresentados aqui em no máximo 1 minuto.

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

Pontuação

Isso é , então a resposta mais curta em bytes vence.

Fatalizar
fonte
É completamente impossível não passar o último testcase em um minuto ...
Leaky Nun
OEIS A084050 (contém casos adicionais, como 10) #
Leaky Nun
Qual é o maior insumo?
Adám 17/08/16
@ Adám Seu programa deve, teoricamente, funcionar para qualquer número, não importa o tamanho.
Fatalize 17/08/16
1
@ Adám Este é um limite bastante arbitrário que depende do idioma usado. Digamos que, teoricamente, ele funcione para o maior número inteiro que seu idioma pode representar por padrão (portanto, todos os números inteiros se bignums forem o padrão em seu idioma).
Fatalize 17/08/16

Respostas:

8

05AB1E , 15 14 13 bytes

Guardou um byte graças a Emigna ! Código:

µNœvyJÂïÊP}_½

Explicação:

µ               # 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.

Usa a codificação CP-1252 . Experimente online! .

Adnan
fonte
1
µNœvyJÂïQ}O__½para 14.
Emigna 17/08/16
@Emigna Thanks! Eu não pensei nisso.
Adnan
7

Braquilog, 19 bytes

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

Experimente online!

Demora cerca de 17 segundos para N = 270.

Explicação

  • Predicado principal:

    ~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.
    
  • Predicado 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
    
Fatalizar
fonte
5

Braquilog , 21 20 bytes

1 byte graças a Fatalize.

Você criou o desafio para o Brachylog?

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

Experimente online!

270 leva cerca de meio minuto aqui.

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

Exit code:     0

Predicado 0 (predicado principal)

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

Predicado 1 (predicado auxiliar)

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.
Freira Furada
fonte
5

Pyth, 14

e.ff&_ITshT.p`

Experimente aqui ou execute um Conjunto de Testes

Expansão:

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
FryAmTheEggman
fonte
5

JavaScript (ES6), 99 bytes

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

Explicação:

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!
Neil
fonte
1100 é um número permutapalindrômico redondo.
Adám 17/08/16
@ Adám Não é redondo, contém pelo menos dois dígitos diferentes de zero.
Neil
@Neil: +2 bytes - você realmente deveria contar o f=quando você se referir a ele mais tarde
charlie
@ charlie Desculpe, eu sempre esqueço de fazer isso.
Neil
4

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}

destroçado

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
}

Essencialmente - uma função que verifica a associação no conjunto permutapalindromic e um loop while incrementa até encontrar o enésimo membro.

user5957401
fonte
3

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]

Simples o suficiente. Basicamente, usa um whileloop para criar repetidamente matrizes contendo números permutapalindrômicos [1,Q)até o intervalo até que Qseja grande o suficiente para que a matriz contenha um Inputnúmero de itens. Em seguida, ele gera o último elemento nessa matriz.

Experimente Online! (Ideona)

R. Kap
fonte
2

Perl 6 , 66 bytes

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

Baseado em 0

Explicação:

# 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
  )[$_]
}

Teste:

#! /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";
Brad Gilbert b2gills
fonte
2

Dyalog APL , 51 bytes

Um indexado.

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

{ uma função em que ⍵ representa o argumento

⍵⊃{ use o argumento para escolher o resultado da função

⍵/⍨{ filtrar o argumento com o resultado da função

(⍵≤9)∨ o argumento é menor ou igual a 9, OR

(1<≢c~'0')∧ permanece mais de um dígito quando os zeros são removidos E

1≥+/ 0 ou 1 é a soma de

2| as estranhezas de

+⌿ da coluna somas de

c∘.=∪ca tabela de comparação de c e os elementos únicos de c , onde c ...

←⍕⍵ é a representação em cadeia do argumento

}¨⍵ aplicado a cada um dos argumentos

}⍳5×⍵ aplicado a {1, 2, 3, ..., 5 vezes o argumento}

} [fim da função]

Conclui todos os casos de teste instantaneamente no TryAPL

Adão
fonte
Você pode provar isso a(n) <= 5n?
Freira vazada
A segunda solução gera resultados incorretos.
Leaky Nun
A primeira solução também gera resultados incorretos.
Freira Furada
@LeakyNun Quais estão incorretas? E se 5 × não for suficiente, há espaço para 9 × ...
Adám
@LeakyNun Certo, incluo 100 etc. que não são permitidos.
Adám 17/08/16
2

JavaScript (ES6), 92

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

Menos golfe

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

Teste

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>

edc65
fonte
1

Javascript (usando biblioteca externa - 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 para lib: https://github.com/mvegh1/Enumerable/

Explicação do código: _.Sequence cria um enumerável para uma contagem de "n" elementos, com base no predicado de assinatura ("i" declaração , "uma" matriz acumulada ). Converta a iteração atual em uma string e crie um enumerável de todas as permutações dela. Teste se alguma das permutações satisfaz o teste de não começar com "0" e que a reversão da permutação é igual à permutação. Retorne o último elemento na sequência porque essa é a saída desejada conforme OP

insira a descrição da imagem aqui

applejacks01
fonte
1

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 indexado. Dependendo do seu sistema, o último caso de teste pode exceder a profundidade de recursão permitida.

Não calcula permutações. Em vez disso, usa o fato de que duas strings são permutações se forem iguais quando ordenadas. Para testar se um número é permutapalindrômico, verifica se seus dígitos classificados são iguais aos dígitos classificados de qualquer palíndromo até um limite.


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 indexado. Dependendo do seu sistema, o último caso de teste pode exceder a profundidade de recursão permitida.

Isso não considera permutações e usa a seguinte caracterização:

Um número é permutapalindrômico exatamente quando

  • No máximo, um de seus dígitos aparece um número ímpar de vezes e
  • Não possui o formato d00 ... 00 com um ou mais zeros.

Isso ocorre porque um palíndromo deve emparelhar dígitos do início e do fim, exceto por um possível dígito central. A exceção vem do requisito de que o dígito inicial seja diferente de zero e, portanto, algum dígito diferente de zero deve aparecer duas vezes, a menos que o número seja de um dígito.

xnor
fonte
1

Haskell, 89 87 bytes

import Data.List
(filter(any(show.floor.read.reverse>>=(==)).permutations.show)[0..]!!)
Damien
fonte
0

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));}
RosLuP
fonte