Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]
share|improve this question
    
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? – Brad Gilbert b2gills Jan 18 at 4:45
    
List, Array, Seq, Range, Buf, Slip are all Positional values. That is they do the Positional Role. – Brad Gilbert b2gills Jan 18 at 5:01

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

share|improve this answer
    
jk is the same as s`M – Maltysen Jan 18 at 4:14

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
share|improve this answer
3  
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; – Martin Ender Jan 18 at 8:22
3  
@MartinBüttner This is why I love PPCG. Everyone is so helpful and friendly! – KoreanwGlasses Jan 18 at 14:15

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!

share|improve this answer
    
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. – Glen O Jan 18 at 16:36
    
Also, I could be mistaken, but if x is an array, then rather than first(x), just use x[]. – Glen O Jan 18 at 16:40
    
@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. – Alex A. Jan 18 at 19:56

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!

share|improve this answer
    
@histocrat That was a mistake on OP's part (see comments on the question). Thanks, that's a neat trick with the splat. – Doorknob Jan 18 at 4:31

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.

share|improve this answer

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]
share|improve this answer

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.

share|improve this answer
    
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") – Neil Jan 19 at 22:26
    
@Neil Thanks, that also happens to be a few times faster than my algorithm! – ETHproductions Jan 21 at 13:28
    
36 bytes? I think that must be a record for me. – Neil Jan 21 at 21:17

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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