14
\$\begingroup\$

Palindromic prime problems are pretty common, but that's not what this question is about. In this challenge, the number doesn't have to be a palindrome, its prime factors do.

Task

Your code has to take a single positive integer as input. Then check if any of the permutations of the prime factors of that integer are palindromic when concatenated. If so, output one of them (the list of factors, not the concatenated string). Else, you have to output -1.

This is , so shortest code in bytes wins!

Test Cases

11 -> [11]
4 -> [2, 2]
39 -> [3, 13]
6 -> -1
1207 -> [17, 71]
393 -> -1
2352 -> [2, 2, 7, 3, 7, 2, 2]
\$\endgroup\$
  • 1
    \$\begingroup\$ Can other distinguishable values than -1 be returned? In Perl 6 I'm thinking about Nil,Fail or other undefined values. Also can the output be any Positional value? \$\endgroup\$ – Brad Gilbert b2gills Jan 18 '16 at 4:45
  • \$\begingroup\$ List, Array, Seq, Range, Buf, Slip are all Positional values. That is they do the Positional Role. \$\endgroup\$ – Brad Gilbert b2gills Jan 18 '16 at 5:01
  • \$\begingroup\$ So.. should we output an empty list for 1, or -1? \$\endgroup\$ – Jo King Apr 10 at 7:30
  • \$\begingroup\$ -1 as element is different to one array that contain only -1 \$\endgroup\$ – RosLuP May 10 at 9:41

13 Answers 13

4
\$\begingroup\$

05AB1E, 7 bytes

Òœ.ΔJÂQ

Try it online!

Explanation:

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

( conveniently defaults to -1, so no extra work needed)

\$\endgroup\$
3
\$\begingroup\$

Pyth, 14 bytes

-2 bytes by @FryAmTheEggman

h+f_IjkT.pPQ_1

Explanation:

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

Thanks @FryAmTheEggman for reminding me about I. I don't think I've used it before.

Test suite

\$\endgroup\$
  • \$\begingroup\$ jk is the same as s`M \$\endgroup\$ – Maltysen Jan 18 '16 at 4:14
3
\$\begingroup\$

CJam - 17 bytes

Thanks to Martin Büttner for saving me 10 bytes!

Wqimfe!{s_W%=}=p;

My first time writing in CJam! Explanation:

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
\$\endgroup\$
  • 3
    \$\begingroup\$ You can reverse a string (or array) with W%. You can also use = with a block to get the first palindromic prime factorisation. That makes for 18 bytes: Wrimfe!{s_W%=}=p]; ... you can save one more by terminating with an error (since the error output goes to STDERR): Wrimfe!{s_W%=}=p; \$\endgroup\$ – Martin Ender Jan 18 '16 at 8:22
  • 3
    \$\begingroup\$ @MartinBüttner This is why I love PPCG. Everyone is so helpful and friendly! \$\endgroup\$ – KoreanwGlasses Jan 18 '16 at 14:15
2
\$\begingroup\$

Ruby, 89+7=96 102+7=109

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

+7 for the -rprime flag.

Sigh, some Ruby builtins have such long names... at least that makes the code fairly self-explanatory.

The flat_map bit is because prime_division returns ex. [[2, 2], [3, 1]] for input 12 (which represents 2231).

Thanks to @histocrat for 13 bytes!

\$\endgroup\$
  • \$\begingroup\$ @histocrat That was a mistake on OP's part (see comments on the question). Thanks, that's a neat trick with the splat. \$\endgroup\$ – Doorknob Jan 18 '16 at 4:31
2
\$\begingroup\$

Julia, 132 122 bytes

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

This is a lambda function that accepts an integer and returns either an array or -1. To call it, assign it to a variable.

Ungolfed:

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

Saved 10 bytes thanks to Glen O!

\$\endgroup\$
  • \$\begingroup\$ At a glance, I see a few ways to improve this (just based on basic golfing). Use foldl rather than reduce (they do the same thing, but foldl has defined order and is one byte shorter). Use a direct comparison with an empty structure instead of isempty (I'm not 100% sure what type x is, but if it's a set, for instance, use x==[]). And use (q=join(p)) and then just q in the filter to save two more bytes. \$\endgroup\$ – Glen O Jan 18 '16 at 16:36
  • \$\begingroup\$ Also, I could be mistaken, but if x is an array, then rather than first(x), just use x[]. \$\endgroup\$ – Glen O Jan 18 '16 at 16:40
  • \$\begingroup\$ @GlenO Thanks so much as always! I had initially tried ==[] and it was giving me errors but I tried again now and it's working. I must have messed something up before. ¯\_(ツ)_/¯ The only suggestion I couldn't use is getting rid of first; in this case I have to use first because x is an iterator/collection/something that doesn't have getindex defined. \$\endgroup\$ – Alex A. Jan 18 '16 at 19:56
2
\$\begingroup\$

Brachylog, 10 bytes

ḋp.cX↔X∨_1

Try it online!

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

Initially, I had expected that having to output -1 instead of being allowed to fail would be at a fairly large byte cost, but since the output in the case of success can't be concatenated, it only costs the two bytes necessary to write _1 (if we removed those, it would leave the output unconstrained defaulting to 0, and if we additionally changed the to , the predicate would fail instead), because we need to break unification with the implicit output either way. (If the concatenation was the output for success but -1 was still the output for failure, we'd have ḋpc.↔|∧_1 or ḋpc.↔.∨_1. In the shortest case, where the output is concatenated and the predicate can fail, the whole thing is only five bytes: ḋpc.↔. Although not outputting the actual factors gives it more of a feel...)

\$\endgroup\$
1
\$\begingroup\$

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

Usage example: f 39 -> [3,13].

The obvious brute force approach. Iterating over all permutations of the prime factors and check for palindroms. Pick the first one. If there are none, the list is empty and the appended [-1] jumps in.

\$\endgroup\$
1
\$\begingroup\$

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
}

Usage:

# 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

About half of it (53 bytes) is taken up with the prime factorization code.

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

If there were a prime-factorize method the whole thing could be significantly shorter.

{.prime-factorize.permutations.first({.join.flip eq.join})||-1} # 63
\$\endgroup\$
  • \$\begingroup\$ A shorter prime factor code section could be $!=$_;({+$!/($!/=1+(2...$!%%*))}...{2>$!}) \$\endgroup\$ – Jo King Apr 10 at 13:06
1
\$\begingroup\$

Jelly, 16 bytes

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

Longer than I expected, both in the byte count and the time it took to write.

Try it online!

Explanation:

Æ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.
\$\endgroup\$
1
\$\begingroup\$

Japt -F-1, 9 bytes

k á æ_¬êS

Try it

\$\endgroup\$
  • \$\begingroup\$ Your link is not ok in this window phone... \$\endgroup\$ – RosLuP May 10 at 12:31
  • \$\begingroup\$ @RosLuP The interpreter is still fairly new. I'll ping Shaggy, the creator. Here's a TIO link \$\endgroup\$ – Oliver May 10 at 13:24
  • 1
    \$\begingroup\$ @RosLuP, what browser are you using? \$\endgroup\$ – Shaggy May 10 at 16:17
  • \$\begingroup\$ Internet Explorer for Windows Phone 8.1: (cellphone) something that is disappearing , possibly it is better I use my brand new phone android or the browser of windows 10 (Edge it seems they call) \$\endgroup\$ – RosLuP May 11 at 15:33
0
\$\begingroup\$

Japt, 18 bytes

Almost as short as CJam...

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

Try it online!

How it works

        // 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]
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 256 244 208 187 bytes

Saved 36 bytes thanks to @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")

Defines an anonymous function; prepend e.g. F= to use it. It's actually quite fast on input of 2352, only taking ~150 milliseconds to finish on my computer.

\$\endgroup\$
  • \$\begingroup\$ I don't know about faster but definitely shorter: 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") \$\endgroup\$ – Neil Jan 19 '16 at 22:26
  • \$\begingroup\$ @Neil Thanks, that also happens to be a few times faster than my algorithm! \$\endgroup\$ – ETHproductions Jan 21 '16 at 13:28
  • \$\begingroup\$ 36 bytes? I think that must be a record for me. \$\endgroup\$ – Neil Jan 21 '16 at 21:17
0
\$\begingroup\$

APL(NARS), 169 chars, 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 would be the function find the permutations and f is the function of this exercise; test:

  ⎕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
└∊───────────────────────────────────────────────────┘
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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