Czynniki palindromiczne

15

Problemy z palindromicznymi liczbami pierwszymi są dość powszechne, ale nie o to chodzi w tym pytaniu. W tym wyzwaniu liczba nie musi być palindromem, a czynniki pierwsze.

Zadanie

Twój kod musi przyjmować jedną dodatnią liczbę całkowitą jako dane wejściowe. Następnie sprawdź, czy któraś z permutacji czynników pierwszych tej liczby całkowitej jest palindromiczna po połączeniu. Jeśli tak, wypisz jeden z nich (listę czynników, a nie połączony ciąg). W przeciwnym razie musisz wyjść -1.

To jest , więc wygrywa najkrótszy kod w bajtach !

Przypadki testowe

11 -> [11]
4 -> [2, 2]
39 -> [3, 13]
6 -> -1
1207 -> [17, 71]
393 -> -1
2352 -> [2, 2, 7, 3, 7, 2, 2]
Maltysen
źródło
1
Czy mogą -1zostać zwrócone inne wartości odróżnialne ? W Perl 6 myślę o Nil, Faillub inne wartości nieokreślone. Czy wynik może być dowolną wartością pozycyjną?
Brad Gilbert b2gills 18.01.16
List, Array, Seq, Range, Buf, Slip są wartościami pozycyjnymi. To znaczy, że wykonują rolę pozycyjną.
Brad Gilbert b2gills 18.01.16
Więc ... czy powinniśmy wypisać pustą listę dla 1, czy -1?
Jo King
-1 jako element różni się od jednej tablicy zawierającej tylko -1
RosLuP

Odpowiedzi:

4

05AB1E , 7 bajtów

Òœ.ΔJÂQ

Wypróbuj online!

Wyjaśnienie:

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

( wygodnie domyślnie na -1, więc nie wymaga dodatkowej pracy)

Ponury
źródło
3

Pyth, 14 bajtów

-2 bajty autorstwa @FryAmTheEggman

h+f_IjkT.pPQ_1

Wyjaśnienie:

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

Dzięki @FryAmTheEggman za przypomnienie mi o I. Nie sądzę, żebym go wcześniej używał.

Zestaw testowy

lirtosiast
źródło
jkjest taki sam jaks`M
Maltysen
3

CJam - 17 bajtów

Dzięki Martin Büttner za uratowanie mi 10 bajtów!

Wqimfe!{s_W%=}=p;

Mój pierwszy raz pisałem w CJam! Wyjaśnienie:

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
źródło
3
Możesz odwrócić ciąg (lub tablicę) za pomocą W%. Możesz także użyć =z blokiem, aby uzyskać pierwszą palindromową pierwszą faktoryzację. To daje 18 bajtów: Wrimfe!{s_W%=}=p];... możesz zapisać jeszcze jeden, kończąc z błędem (ponieważ wyjście błędu przechodzi do STDERR):Wrimfe!{s_W%=}=p;
Martin Ender
3
@ MartinBüttner Właśnie dlatego kocham PPCG. Wszyscy są bardzo pomocni i przyjaźni!
KoreanwGlasses
2

Rubin, 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 za -rprimeflagę.

Westchnienie , niektóre wbudowane Ruby mają tak długie nazwy ... przynajmniej to sprawia, że ​​kod jest dość oczywisty.

flat_mapNieco dlatego prime_divisionzwrotów ex. [[2, 2], [3, 1]]dla danych wejściowych 12(które reprezentują ).2231

Dzięki @histocrat za 13 bajtów!

Klamka
źródło
@histocrat To był błąd OP (patrz komentarze do pytania). Dzięki, to fajna sztuczka z ikoną.
Klamka
2

Julia, 132 122 bajty

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

Jest to funkcja lambda, która przyjmuje liczbę całkowitą i zwraca tablicę lub -1. Aby go wywołać, przypisz go do zmiennej.

Nie golfowany:

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

Zaoszczędź 10 bajtów dzięki Glen O!

Alex A.
źródło
Na pierwszy rzut oka widzę kilka sposobów, aby to poprawić (w oparciu o podstawową grę w golfa). Użyj foldlraczej niż reduce(robią to samo, ale foldlmają określoną kolejność i są o jeden bajt krótsze). Zamiast tego użyj bezpośredniego porównania z pustą strukturą isempty(nie jestem w 100% pewien, jaki xjest typ , ale jeśli jest to na przykład zestaw, użyj x==[]). I użyj, (q=join(p))a następnie tylko qw filtrze, aby zapisać dwa kolejne bajty.
Glen O
Mogę się również mylić, ale jeśli xjest tablicą, to zamiast tego first(x)po prostu użyj x[].
Glen O
@GlenO Dziękuję jak zawsze! Początkowo próbowałem ==[]i dawało mi to błędy, ale próbowałem teraz ponownie i działa. Musiałem coś wcześniej zepsuć. ¯ \ _ (ツ) _ / ¯ Jedyną sugestią, której nie mogłem zastosować, jest pozbycie się first; w tym przypadku muszę użyć, firstponieważ xjest to iterator / kolekcja / coś, co nie zostało getindexzdefiniowane.
Alex A.
2

Brachylog , 10 bajtów

ḋp.cX↔X∨_1

Wypróbuj 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.

Początkowo spodziewałem się, że wyjście, -1zamiast pozwolić na awarię, wiązałoby się z dość dużym kosztem bajtów, ale ponieważ dane wyjściowe w przypadku sukcesu nie mogą zostać połączone, kosztuje to tylko dwa bajty niezbędne do zapisu _1(jeśli usunęliśmy je, pozostawiając wyjście nieograniczone domyślnie na 0, a jeśli dodatkowo zmienimy na , predykat nie powiedzie się zamiast tego), ponieważ musimy przerwać unifikację z niejawnym wyjściem. (Gdyby konkatenacja była wyjściem do sukcesu, ale -1nadal była wyjściem do niepowodzenia, mielibyśmy ḋpc.↔|∧_1lub ḋpc.↔.∨_1. W najkrótszym przypadku, gdy wynik jest konkatenowany, a predykat może się nie powieść, całość ma tylko pięć bajtów:ḋpc.↔. Chociaż nie wyprowadzanie faktycznych czynników daje więcej wrażenia z ...)

Niepowiązany ciąg
źródło
1

Haskell, 122 bajty

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

Przykład użycia: f 39-> [3,13].

Oczywiste podejście brutalnej siły. Iterowanie po wszystkich permutacjach czynników pierwszych i sprawdzanie palindromów. Wybierz pierwszy. Jeśli nie ma, lista jest pusta i dołącza się dołączona [-1].

nimi
źródło
1

Perl 6 , 100 bajtów

{$/=$_;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
}

Stosowanie:

# 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

Około połowa (53 bajty) jest zajęta przez główny kod faktoryzacji.

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

Gdyby istniała prime-factorizemetoda, całość mogłaby być znacznie krótsza.

{.prime-factorize.permutations.first({.join.flip eq.join})||-1} # 63
Brad Gilbert b2gills
źródło
Krótsza sekcja kodu czynnika pierwszego może być$!=$_;({+$!/($!/=1+(2...$!%%*))}...{2>$!})
Jo King
1

Galaretka , 16 bajtów

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

Dłużej niż się spodziewałem, zarówno pod względem liczby bajtów, jak i czasu potrzebnego na napisanie.

Wypróbuj online!

Wyjaśnienie:

Æ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.
Towarzyszu SparklePony
źródło
1

Japt -F-1 , 9 bajtów

k á æ_¬êS

Spróbuj

Oliver
źródło
Twój link nie jest
poprawny
@RosLuP Tłumacz jest wciąż dość nowy. Śpiewam Kudłatego, twórcę. Oto link do TIO
Oliver
1
@RosLuP, jakiej przeglądarki używasz?
Kudłaty
Internet Explorer dla Windows Phone 8.1: (telefon) coś, co znika, być może lepiej jest używać mojego nowego telefonu z Androidem lub przeglądarki Windows 10 (Edge wydaje się, że dzwonią)
RosLuP
0

Japt, 18 bajtów

Prawie tak krótki jak CJam ...

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

Wypróbuj online!

Jak to działa

        // 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]
ETHprodukcje
źródło
0

JavaScript (ES6), 256 244 208 187 bajtów

Zaoszczędź 36 bajtów dzięki @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")

Definiuje anonimową funkcję; przygotuj np. F=aby go użyć. W rzeczywistości jest dość szybki na wejściu 2352, zajmuje tylko ~ 150 milisekund, aby zakończyć na moim komputerze.

ETHprodukcje
źródło
Nie wiem o szybszym, ale zdecydowanie krótszym: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 Dzięki, to także dzieje się kilka razy szybciej niż mój algorytm!
ETHprodukcje
36 bajtów? Myślę, że to musi być dla mnie rekord.
Neil
0

APL (NARS), 169 znaków, 338 bajtów

∇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 byłoby funkcją znajdowania permutacji, a f jest funkcją tego ćwiczenia; 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
└∊───────────────────────────────────────────────────┘
RosLuP
źródło