Factores primos palindrómicos

15

Los problemas primarios palindrómicos son bastante comunes, pero de eso no se trata esta pregunta. En este desafío, el número no tiene que ser un palíndromo, sino sus factores primos.

Tarea

Su código tiene que tomar un solo entero positivo como entrada. Luego verifique si alguna de las permutaciones de los factores primos de ese entero son palindrómicas cuando se concatenan. Si es así, envíe uno de ellos (la lista de factores, no la cadena concatenada). De lo contrario, tienes que dar salida -1.

Este es el , por lo que gana el código más corto en bytes .

Casos de prueba

11 -> [11]
4 -> [2, 2]
39 -> [3, 13]
6 -> -1
1207 -> [17, 71]
393 -> -1
2352 -> [2, 2, 7, 3, 7, 2, 2]
Maltysen
fuente
1
¿Se -1pueden devolver otros valores distinguibles ? En Perl 6 que estoy pensando Nil, Failu otros valores no definidos. ¿También puede la salida ser cualquier valor posicional?
Brad Gilbert b2gills
List, Array, Seq, Range, Buf, Slip son valores posicionales. Es decir, hacen el papel posicional.
Brad Gilbert b2gills
Entonces ... ¿deberíamos generar una lista vacía para 1, o -1?
Jo King
-1 como elemento es diferente a una matriz que contiene solo -1
RosLuP

Respuestas:

4

05AB1E , 7 bytes

Òœ.ΔJÂQ

Pruébalo en línea!

Explicación:

Ò            # prime factorization of the input
 œ           # permutations
  .Δ         # find the first one such that
    J        # concatenated
     ÂQ      # is a palindrome

(por defecto convenientemente a -1, por lo que no se necesita trabajo adicional)

Mugriento
fuente
3

Pyth, 14 bytes

-2 bytes por @FryAmTheEggman

h+f_IjkT.pPQ_1

Explicación:

h                 first element of
 +                (append a -1 to the end in case the filter is empty)
  f                 filter by lambda T:
   _I                 is invariant under reversing
     jkT              stringified list
   .p                over permutations of
     P Q             prime factors of Q with duplicates
  _1              -1

Gracias @FryAmTheEggman por recordarme I. No creo que lo haya usado antes.

Banco de pruebas

lirtosiast
fuente
jkes lo mismo ques`M
Maltysen
3

CJam - 17 bytes

¡Gracias a Martin Büttner por salvarme 10 bytes!

Wqimfe!{s_W%=}=p;

¡La primera vez que escribo en CJam! Explicación:

W              # Push a -1 onto the stack
q               # Get input
i               # Convert to integer
mf              # Find prime factorization
e!              # Find all permutations
{...}=          # Find permutation which...
s               # Convert to string
_               # Copy string
W%              # Get inverse
=               # Check if inverse == original
p;              # Print top of stack and discard the rest
KoreanwGlasses
fuente
3
Puede invertir una cadena (o matriz) con W%. También se puede usar =con un bloque para obtener la primera factorización palindrómica prima. Eso equivale a 18 bytes: Wrimfe!{s_W%=}=p];... puede guardar uno más terminando con un error (ya que la salida del error va a STDERR):Wrimfe!{s_W%=}=p;
Martin Ender
3
@ MartinBüttner Por eso me encanta PPCG. ¡Todos son muy amables y serviciales!
KoreanwGlasses
2

Rubí, 89 + 7 = 96102 + 7 = 109

->n{n.prime_division.flat_map{|*a,b|a*b}.permutation.find{|x|x.join==x.join.reverse}||-1}

+7 para la -rprimebandera.

Suspiro , algunos componentes de Ruby tienen nombres tan largos ... al menos eso hace que el código se explique por sí mismo.

El flat_mapbit es porque prime_divisiondevuelve ex. [[2, 2], [3, 1]]para entrada 12(que representa ).2231

¡Gracias a @histocrat por 13 bytes!

Pomo de la puerta
fuente
@histocrat Eso fue un error por parte de OP (ver comentarios sobre la pregunta). Gracias, es un buen truco con el splat.
Pomo de la puerta
2

Julia, 132122 bytes

n->(x=filter(p->(q=join(p))==reverse(q),permutations(foldl(vcat,[[repeated(k,v)...]for(k,v)=factor(n)]))))==[]?-1:first(x)

Esta es una función lambda que acepta un número entero y devuelve una matriz o -1. Para llamarlo, asígnelo a una variable.

Sin golf:

function f(n::Int)
    # Construct an array of all prime factors of n
    P = foldl(vcat, [[repeated(k, v)...] for (k, v) in factor(n)])

    # Filter the set of permutations of this array to only
    # those such that the string constructed by concatenating
    # all elements is a palindrome
    x = filter(p -> (q = join(p)) == reverse(q), P)

    # If x is empty, return -1, otherwise get the first array
    # in the collection
    return x == [] ? -1 : first(x)
end

Guardado 10 bytes gracias a Glen O!

Alex A.
fuente
De un vistazo, veo algunas formas de mejorar esto (solo basado en el golf básico). Usar en foldllugar de reduce(hacen lo mismo, pero foldltiene un orden definido y es un byte más corto). Use una comparación directa con una estructura vacía en lugar de isempty(no estoy 100% seguro de qué tipo xes, pero si es un conjunto, por ejemplo, use x==[]). Y use (q=join(p))y luego solo qen el filtro para guardar dos bytes más.
Glen O
Además, podría estar equivocado, pero si xes una matriz, entonces, en lugar de first(x), simplemente use x[].
Glen O
@GlenO ¡Muchas gracias como siempre! Inicialmente lo había intentado ==[]y me estaba dando errores, pero lo intenté nuevamente ahora y está funcionando. Debo haber estropeado algo antes. ¯ \ _ (ツ) _ / ¯ La única sugerencia que no pude usar es deshacerme de él first; en este caso tengo que usarlo firstporque xes un iterador / colección / algo que no se ha getindexdefinido.
Alex A.
2

Brachylog , 10 bytes

ḋp.cX↔X∨_1

Pruébalo en línea!

  .           The output is
 p            a permutation of
ḋ             the prime factorization of
              the input
   c          such that concatenated
    X         it is the variable X
     ↔        which reversed
      X       is still X;
       ∨      if this is not possible,
              the output is
        _1    -1.

Inicialmente, esperaba que tener que generar en -1lugar de permitir que fallara tendría un costo de byte bastante grande, pero dado que la salida en el caso de éxito no se puede concatenar, solo cuesta los dos bytes necesarios para escribir _1(si si los quitáramos, dejaría la salida sin restricciones por defecto 0, y si además cambiamos el a , el predicado fallaría en su lugar), porque necesitamos romper la unificación con la salida implícita de cualquier manera. (Si la concatenación era la salida para el éxito pero -1todavía era la salida para el fracaso, tendríamos ḋpc.↔|∧_1o ḋpc.↔.∨_1. En el caso más corto, donde la salida se concatena y el predicado puede fallar, todo es solo cinco bytes:ḋpc.↔. Aunque no generar los factores reales le da más sensación de ...)

Cadena no relacionada
fuente
1

Haskell, 122 bytes

import Data.Numbers.Primes
import Data.List
f x=head$[p|p<-permutations$primeFactors x,s<-[show=<<p],s==reverse s]++[[-1]]

Ejemplo de uso: f 39-> [3,13].

El obvio enfoque de la fuerza bruta. Iterando sobre todas las permutaciones de los factores primos y verificando si hay palíndromos. Elige el primero. Si no hay ninguno, la lista está vacía y los anexos [-1]saltan.

nimi
fuente
1

Perl 6 , 100 bytes

{$/=$_;map(->\f{|({$/%f||($//=f)&&f}...^*!==f)},2..$_).permutations.first({.join.flip eq.join})||-1}
{
  # store copy of argument in $/
  $/ = $_;
  # uses $/ so that I don't have to declare a variable

  # find the prime factors
  map(
    ->\f{
      # Slip so that outer list of all prime factors is flat
      |(
        {
          $/ % f    # return modulus
          ||        # or
          ($/ /= f) # factor the prime out of $/
          &&        # and
          f         # return factor
        }
        # produce a list of them and
        # stop when it returns something other than the factor
        # also ignoring the last non-factor value
        ...^ * !== f
      )
    },
    # find the factors out of the values from 2
    # up to the original argument
    2..$_
    # don't need to skip the non-primes as their
    # prime factorization will have already be
    # factored out of $/
  )

  # try all permutations of the prime factors
  .permutations

  # find the first palindromic one
  .first({ .join.flip eq .join })

  # return -1 if .first returned Nil or empty list
  || -1
}

Uso:

# give it a lexical name
my &prime-palindrome = {...}

say prime-palindrome    1; # -1
say prime-palindrome    2; # (2)
say prime-palindrome   11; # (11)
say prime-palindrome   13; # -1
say prime-palindrome   39; # (3 13)
say prime-palindrome   93; # (31 3)
say prime-palindrome    6; # -1
say prime-palindrome 1207; # (17 71)
say prime-palindrome  393; # -1
say prime-palindrome 2352; # (2 2 7 3 7 2 2)
say prime-palindrome 2351; # -1
say prime-palindrome 2350; # -1

Aproximadamente la mitad (53 bytes) se utiliza con el código de factorización prima.

$/=$_;map(->\f{|({$/%f||($//=f)&&f}...^*!= f)},2..$_)

Si hubiera un prime-factorizemétodo, todo podría ser significativamente más corto.

{.prime-factorize.permutations.first({.join.flip eq.join})||-1} # 63
Brad Gilbert b2gills
fuente
Una sección de código de factor primo más corta podría ser$!=$_;({+$!/($!/=1+(2...$!%%*))}...{2>$!})
Jo King
1

Jalea , 16 bytes

ÆFŒṙŒ!VŒḂ$ƇḢ¹-¹?

Más tiempo de lo que esperaba, tanto en el recuento de bytes como en el tiempo que tardó en escribir.

Pruébalo en línea!

Explicación:

ÆFŒṙŒ!VŒḂ$ƇḢ¹-¹?
ÆFŒṙ                Get the prime factors (gets them as exponents then run-length decodes).
    Œ!              Get the permutations.
          Ƈ         Filter (keep) the ones that...
       ŒḂ$          ...are palindromic when...
      V             ...joined.
           Ḣ        Take the first.
              ¹?    If the value is truthy...
            ¹       ...return the value...
             -      else return -1.
Camarada SparklePony
fuente
1

Japt -F-1 , 9 bytes

k á æ_¬êS

Intentalo

Oliver
fuente
Su enlace no está bien en este teléfono con ventana ...
RosLuP
@RosLuP El intérprete todavía es bastante nuevo. Haré un ping a Shaggy, el creador. Aquí hay un enlace TIO
Oliver
1
@RosLuP, ¿qué navegador estás usando?
Shaggy
Internet Explorer para Windows Phone 8.1: (teléfono celular) algo que está desapareciendo, posiblemente sea mejor que use mi nuevo teléfono Android o el navegador de Windows 10 (Edge parece que llaman)
RosLuP
0

Japt, 18 bytes

Casi tan corto como CJam ...

Uk á f_¬¥Z¬w} g ªJ

Pruébalo en línea!

Cómo funciona

        // Implicit: U = input, e.g. 2352
Uk      // Factorize the input.      [2,2,2,2,3,7,7]
á       // Take permutations.        [[2,2,2,2,3,7,7],[2,2,2,2,7,3,7],[2,2,2,7,2,3,7],...]
f_   }  // Filter to only the ones that return truthily to this function:
Z¬¥Z¬w  //  Return Z.join('') == Z.join('').reverse().
        //                           [[2,2,7,3,7,2,2],[2,7,2,3,2,7,2],[7,2,2,3,2,2,7]]
g       // Take the first item.      [2,2,7,3,7,2,2]
ªJ      // If falsy, resort to -1.   [2,2,7,3,7,2,2]
ETHproductions
fuente
0

JavaScript (ES6), 256 244 208 187 bytes

Guardado 36 bytes gracias a @Neil

x=>eval("for(a=[],i=2;x>1;x%i?i++:(a.push(i),x/=i));p=-1,f=(z,t=[])=>z[0]?z.map((u,i)=>f([...z.slice(0,i),...z.slice(i+1)],[...t,u])):(y=t.join``)==[...y].reverse().join``&&(p=t),f(a),p")

Define una función anónima; anteponer, por ejemplo, F=para usarlo. En realidad, es bastante rápido en la entrada de 2352, solo tarda ~ 150 milisegundos en terminar en mi computadora.

ETHproductions
fuente
No sé más rápido, pero definitivamente más corto:x=>eval("for(a=[],i=2;x>1;x%i?i++:(a.push(i),x/=i));p=[],f=(z,t=[])=>z.length?z.map((u,i)=>f([...z.slice(0,i),...z.slice(i+1)],[...t,u])):(y=t.join``)==[...y].reverse().join``&&p.push(t),f(a),p[0]||-1")
Neil
@Neil ¡Gracias, también es un poco más rápido que mi algoritmo!
ETHproductions
36 bytes? Creo que debe ser un récord para mí.
Neil
0

APL (NARS), 169 caracteres, 338 bytes

∇r←F w;i;k;a;m;j
  r←⊂,w⋄→0×⍳1≥k←↑⍴w⋄a←⍳k⋄j←i←1⋄r←⍬⋄→C
A: m←i⊃w⋄→B×⍳(i≠1)∧j=m⋄r←r,m,¨∇w[a∼i]⋄j←m
B: i+←1
C: →A×⍳i≤k
∇
G←{F⍵[⍋⍵]}
f←{∨/k←{⍵≡⌽⍵}¨∊¨⍕¨¨v←Gπ⍵:↑k/v⋄¯1}

G sería la función de encontrar las permutaciones yf es la función de este ejercicio; prueba:

  ⎕fmt f¨11 4 39 6 1207 393 2352 
┌7───────────────────────────────────────────────────┐
│┌1──┐ ┌2───┐ ┌2────┐    ┌2─────┐    ┌7─────────────┐│
││ 11│ │ 2 2│ │ 3 13│ ¯1 │ 17 71│ ¯1 │ 2 2 7 3 7 2 2││
│└~──┘ └~───┘ └~────┘ ~~ └~─────┘ ~~ └~─────────────┘2
└∊───────────────────────────────────────────────────┘
RosLuP
fuente