Palindromische Primfaktoren

15

Palindromische Hauptprobleme sind ziemlich häufig, aber darum geht es in dieser Frage nicht. Bei dieser Herausforderung muss die Zahl kein Palindrom sein, sondern ihre Primfaktoren.

Aufgabe

Ihr Code muss eine einzelne positive Ganzzahl als Eingabe verwenden. Überprüfen Sie dann, ob eine der Permutationen der Primfaktoren dieser Ganzzahl bei der Verkettung palindrom ist. Wenn ja, geben Sie einen von ihnen aus (die Liste der Faktoren, nicht die verkettete Zeichenfolge). Sonst muss man ausgeben -1.

Das ist , also gewinnt der kürzeste Code in Bytes !

Testfälle

11 -> [11]
4 -> [2, 2]
39 -> [3, 13]
6 -> -1
1207 -> [17, 71]
393 -> -1
2352 -> [2, 2, 7, 3, 7, 2, 2]
Maltysen
quelle
1
Können andere unterscheidbare Werte als -1zurückgegeben werden? In Perl 6 Ich denke darüber nach Nil, Failoder andere undefinierte Werte. Kann der Ausgang auch ein beliebiger Positionswert sein?
Brad Gilbert b2gills
List, Array, Seq, Range, Buf, Slip sind alle Positionswerte. Das heißt, sie übernehmen die positionelle Rolle.
Brad Gilbert b2gills
Also ... sollen wir eine leere Liste ausgeben für 1, oder -1?
Jo King
-1 als Element unterscheidet sich von einem Array, das nur -1 enthält
RosLuP

Antworten:

4

05AB1E , 7 Bytes

Òœ.ΔJÂQ

Probieren Sie es online!

Erläuterung:

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

(Die Standardeinstellung ist -1, daher ist keine zusätzliche Arbeit erforderlich.)

Grimmig
quelle
3

Pyth, 14 Bytes

-2 Bytes von @FryAmTheEggman

h+f_IjkT.pPQ_1

Erläuterung:

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

Vielen Dank an @FryAmTheEggman, dass Sie mich daran erinnert haben I. Ich glaube nicht, dass ich es vorher benutzt habe.

Testsuite

Lirtosiast
quelle
jkist das gleiche wies`M
Maltysen
3

CJam - 17 Bytes

Vielen Dank an Martin Büttner, der mir 10 Bytes gespart hat !

Wqimfe!{s_W%=}=p;

Ich schreibe zum ersten Mal in CJam! Erläuterung:

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
Koreanische Brillen
quelle
3
Sie können eine Zeichenfolge (oder ein Array) mit umkehren W%. Sie können auch =einen Block verwenden, um die erste palindromische Primfaktorisierung zu erhalten. Das ergibt 18 Bytes: Wrimfe!{s_W%=}=p];... Sie können noch eins sparen, indem Sie mit einem Fehler abbrechen (da die Fehlerausgabe an STDERR geht):Wrimfe!{s_W%=}=p;
Martin Ender
3
@ MartinBüttner Deshalb liebe ich PPCG. Jeder ist so hilfsbereit und freundlich!
KoreanwGlasses
2

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 für die -rprimeFlagge.

Seufz , einig Ruby - builtins hat eine so lange Namen ... zumindest , dass der Code ziemlich selbsterklärend macht.

Das flat_mapBit ist, weil prime_divisionex zurückgibt. [[2, 2], [3, 1]]für die Eingabe 12(die darstellt ).2231

Vielen Dank an @histocrat für 13 Bytes!

Türknauf
quelle
@histocrat Das war ein Fehler von OP (siehe Kommentare zu der Frage). Danke, das ist ein toller Trick mit dem Splat.
Türklinke
2

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)

Dies ist eine Lambda-Funktion, die eine Ganzzahl akzeptiert und entweder ein Array oder -1 zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

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

10 Bytes gespart dank Glen O!

Alex A.
quelle
Auf einen Blick sehe ich ein paar Möglichkeiten, um dies zu verbessern (nur auf der Basis des einfachen Golfspiels). Verwenden Sie foldlstattdessen reduce(sie tun dasselbe, haben jedoch foldleine definierte Reihenfolge und sind ein Byte kürzer). Verwenden Sie stattdessen einen direkten Vergleich mit einer leeren Struktur isempty(ich bin nicht zu 100% sicher, welcher Typ es xist, aber wenn es sich beispielsweise um eine Menge handelt, verwenden Sie x==[]). Und benutze (q=join(p))und dann einfach qim Filter, um zwei weitere Bytes zu sparen.
Glen O
Ich könnte mich auch irren, aber wenn xes sich um ein Array handelt, verwenden Sie es lieber als first(x)nur x[].
Glen O
@ GlenO Vielen Dank wie immer! Ich hatte es anfangs versucht ==[]und es gab mir Fehler, aber ich habe es jetzt erneut versucht und es funktioniert. Ich muss vorher etwas durcheinander gebracht haben. ¯ \ _ (ツ) _ / ¯ Der einzige Vorschlag, den ich nicht verwenden konnte, ist, mich loszuwerden first. In diesem Fall muss ich verwenden, firstweil xes sich um einen Iterator / eine Sammlung / etwas handelt, das nicht getindexdefiniert wurde.
Alex A.
2

Brachylog , 10 Bytes

ḋp.cX↔X∨_1

Probieren Sie es 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.

Anfangs hatte ich damit gerechnet, dass das Ausgeben -1statt das Versagen zuzulassen mit einem relativ hohen Byte-Aufwand verbunden ist. Da die Ausgabe im Erfolgsfall jedoch nicht verkettet werden kann, kostet es nur die zwei zum Schreiben erforderlichen Bytes _1(if wir entfernt diejenigen, verlassen würde es die Ausgabe auf ungezwungene säumige 0, und wenn wir die zusätzlich geändert zu , würde das Prädikat nicht statt), weil wir mit der impliziten Ausgabe entweder Weg brechen Vereinigung müssen. (Wäre die Verkettung die Ausgabe für den Erfolg, aber -1immer noch die Ausgabe für den Fehler, hätten wir ḋpc.↔|∧_1oder ḋpc.↔.∨_1. Im kürzesten Fall, wenn die Ausgabe verkettet ist und das Prädikat fehlschlagen kann, besteht das Ganze nur aus fünf Bytes:ḋpc.↔. Obwohl die tatsächlichen Faktoren nicht ausgegeben werden, ist dies eher ein ...)

Nicht verwandte Zeichenfolge
quelle
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]]

Anwendungsbeispiel: f 39-> [3,13].

Der offensichtliche Brute-Force-Ansatz. Durchlaufen Sie alle Permutationen der Primfaktoren und suchen Sie nach Palindromen. Wähle den ersten aus. Wenn es keine gibt, ist die Liste leer und der Anhang [-1]springt ein.

nimi
quelle
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
}

Verwendung:

# 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

Etwa die Hälfte davon (53 Bytes) wird mit dem Primfaktor-Code belegt.

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

Wenn es eine prime-factorizeMethode gäbe , könnte das Ganze deutlich kürzer sein.

{.prime-factorize.permutations.first({.join.flip eq.join})||-1} # 63
Brad Gilbert b2gills
quelle
Ein kürzerer Abschnitt mit dem Primfaktorcode könnte sein$!=$_;({+$!/($!/=1+(2...$!%%*))}...{2>$!})
Jo King,
1

Gelee , 16 Bytes

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

Länger als erwartet, sowohl in der Byteanzahl als auch in der Zeit, die zum Schreiben benötigt wurde.

Probieren Sie es online!

Erläuterung:

Æ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.
Genosse SparklePony
quelle
1

Japt -F-1 , 9 Bytes

k á æ_¬êS

Versuch es

Oliver
quelle
Ihr Link ist in diesem Fenster-Telefon nicht in
Ordnung
@RosLuP Der Interpreter ist noch ziemlich neu. Ich werde Shaggy, den Schöpfer, anpingen. Hier ist ein TIO- Link
Oliver
1
@ RosLuP, welchen Browser benutzt du?
Shaggy
Internet Explorer für Windows Phone 8.1: (Handy) etwas, das verschwindet, möglicherweise ist es besser, ich benutze mein brandneues Telefon Android oder den Browser von Windows 10 (Edge, wie es scheint, rufen sie an)
RosLuP
0

Japt, 18 Bytes

Fast so kurz wie CJam ...

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

Probieren Sie es online!

Wie es funktioniert

        // 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
quelle
0

JavaScript (ES6), 256 244 208 187 Bytes

36 Bytes dank @Neil gespeichert

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")

Definiert eine anonyme Funktion. voranstellen, zB F=um es zu benutzen. Bei der Eingabe von 2352 ist es eigentlich recht schnell, es dauert nur ~ 150 Millisekunden, um auf meinem Computer fertig zu werden.

ETHproductions
quelle
Ich weiß nicht über schneller, aber auf jeden Fall kürzer: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 Danke, das ist zufällig auch ein paar mal schneller als mein Algorithmus!
ETHproductions
36 Bytes? Ich denke, das muss ein Rekord für mich sein.
Neil
0

APL (NARS), 169 Zeichen, 338 Byte

∇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 wäre die Funktion, die Permutationen zu finden, und f ist die Funktion dieser Übung; Prüfung:

  ⎕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
quelle