Палиндромные Прайм Факторы

15

Палиндромные простые проблемы довольно распространены, но это не тот вопрос, о котором идет речь. В этом вызове число не обязательно должно быть палиндромом, а его основными факторами.

задача

Ваш код должен принимать одно положительное целое число в качестве входных данных. Затем проверьте, являются ли какие-либо перестановки простых факторов этого целого числа палиндромными при конкатенации. Если это так, выведите один из них (список факторов, а не объединенную строку). Иначе вы должны вывести-1 .

Это , поэтому выигрывает самый короткий код в байтах !

Тестовые случаи

11 -> [11]
4 -> [2, 2]
39 -> [3, 13]
6 -> -1
1207 -> [17, 71]
393 -> -1
2352 -> [2, 2, 7, 3, 7, 2, 2]
Maltysen
источник
1
Могут ли -1быть возвращены другие отличимые значения ? В Perl 6 Я думаю о том Nil, Failили другие неопределенные значения. Также может ли выход быть любым позиционным значением?
Брэд Гилберт b2gills
List, Array, Seq, Range, Buf, Slip являются позиционными значениями. То есть они выполняют позиционную роль.
Брэд Гилберт b2gills
Итак ... мы должны вывести пустой список для 1или -1?
Джо Кинг
-1 как элемент отличается от одного массива, который содержит только -1
RosLuP

Ответы:

4

05AB1E , 7 байтов

Òœ.ΔJÂQ

Попробуйте онлайн!

Объяснение:

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

( удобно по умолчанию -1, поэтому дополнительная работа не требуется)

Grimmy
источник
3

Pyth, 14 байт

-2 байта @FryAmTheEggman

h+f_IjkT.pPQ_1

Объяснение:

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

Спасибо @FryAmTheEggman за напоминание о I. Я не думаю, что использовал это раньше.

Тестирование

lirtosiast
источник
jkтак же, какs`M
Maltysen
3

CJam - 17 байтов

Спасибо Мартину Бюттнеру за то, что он сэкономил мне 10 байтов!

Wqimfe!{s_W%=}=p;

Я впервые пишу в CJam! Объяснение:

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
источник
3
Вы можете обратить строку (или массив) с помощью W%. Вы также можете использовать =блок, чтобы получить первую палиндромную простую факторизацию. Это составляет 18 байт: Wrimfe!{s_W%=}=p];... вы можете сохранить еще один, завершив с ошибкой (поскольку вывод ошибки идет в STDERR):Wrimfe!{s_W%=}=p;
Мартин Эндер
3
@ MartinBüttner Вот почему я люблю PPCG. Все так полезны и дружелюбны!
KoreanwGlasses
2

Рубин, 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 за -rprimeфлаг.

Вздох , некоторые встроенные в Ruby имена имеют такие длинные имена ... по крайней мере, это делает код довольно понятным.

flat_mapБит , потому что prime_divisionвозвращается отл. [[2, 2], [3, 1]]для ввода 12(который представляет ).2231

Спасибо @histocrat за 13 байтов!

Дверная ручка
источник
@histocrat Это была ошибка со стороны ОП (см. комментарии к вопросу). Спасибо, это аккуратный трюк со сплатом.
Дверная ручка
2

Юлия, 132 122 байта

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

Это лямбда-функция, которая принимает целое число и возвращает либо массив, либо -1. Чтобы вызвать его, присвойте его переменной.

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 байтов благодаря Glen O!

Алекс А.
источник
На первый взгляд, я вижу несколько способов улучшить это (только на основе базового игры в гольф). Используйте foldlвместо reduce(они делают то же самое, но foldlимеют определенный порядок и на один байт короче). Вместо этого используйте прямое сравнение с пустой структурой isempty(я не уверен на 100%, что это за тип x, но, если это, например, набор, используйте x==[]). И использовать, (q=join(p))а затем просто qв фильтре, чтобы сохранить еще два байта.
Глен О
Кроме того, я могу ошибаться, но если xэто массив, а не first(x)просто использовать x[].
Глен О
@GlenO Большое спасибо, как всегда! Первоначально я пытался, ==[]и это давало мне ошибки, но я попробовал снова сейчас, и это работает. Должно быть, я что-то испортил раньше. ¯ \ _ (ツ) _ / ¯ Единственное предложение, которое я не смог использовать, - это избавиться от него first; в этом случае я должен использовать, firstпотому что xэто итератор / коллекция / что-то, что не getindexопределено.
Алекс А.
2

Брахилог , 10 байт

ḋp.cX↔X∨_1

Попробуйте онлайн!

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

Первоначально я ожидал, что необходимость вывода -1вместо того, чтобы позволить потерпеть неудачу, будет иметь довольно большую стоимость в байтах, но поскольку вывод в случае успеха не может быть объединен, он стоит только два байта, необходимых для записи _1(если мы удалили те, что оставило бы выход безусловной недобросовестный 0, и если мы дополнительно изменили на предикат потерпит неудачу , а), потому что нам нужно разорвать объединение с неявным выходом либо образом. (Если бы конкатенация была выходом для успеха, но -1все равно была выходом для неудачи, мы бы имели ḋpc.↔|∧_1или выводятся, этоḋpc.↔.∨_1 . В самом коротком случае, когда выход объединяется, и предикат может потерпеть неудачу, все это только пять байтов:ḋpc.↔, Хотя фактические факторы не выводятся, это создает ощущение ...)

Несвязанная строка
источник
1

Haskell, 122 байта

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

Пример использования: f 39-> [3,13].

Очевидный подход грубой силы. Итерирование по всем перестановкам простых факторов и проверка на палиндромы. Выберите первый. Если их нет, список пуст и добавляется добавленный [-1].

Ними
источник
1

Perl 6 , 100 байт

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

Использование:

# 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

Около половины этого (53 байта) занято основным кодом факторизации.

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

Если бы существовал prime-factorizeметод, все могло бы быть значительно короче.

{.prime-factorize.permutations.first({.join.flip eq.join})||-1} # 63
Брэд Гилберт b2gills
источник
Более короткая секция кода простого множителя могла бы быть$!=$_;({+$!/($!/=1+(2...$!%%*))}...{2>$!})
Джо Кинг
1

Желе , 16 байт

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

Дольше, чем я ожидал, как по количеству байтов, так и по времени, которое потребовалось для записи.

Попробуйте онлайн!

Объяснение:

Æ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.
Товарищ Спаркл Пони
источник
1

Japt -F-1 , 9 байт

k á æ_¬êS

Попытайся

Оливер
источник
Ваша ссылка не в порядке в этом окне телефона ...
RosLuP
@RosLuP Переводчик все еще довольно новый. Я пинг Shaggy, создатель. Вот TIO ссылка
Оливер
1
@RosLuP, какой браузер вы используете?
Лохматый
Internet Explorer для Windows Phone 8.1: (мобильный телефон) что-то, что исчезает, возможно, лучше использовать мой новый телефон Android или браузер Windows 10 (кажется, что они звонят в Edge)
RosLuP
0

Japt, 18 байт

Почти такой же короткий, как CJam ...

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

Попробуйте онлайн!

Как это устроено

        // 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
источник
0

JavaScript (ES6), 256 244 208 187 байт

Сохранено 36 байтов благодаря @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")

Определяет анонимную функцию; например, F=использовать его. Это на самом деле довольно быстро при вводе 2352, всего около 150 миллисекунд, чтобы закончить на моем компьютере.

ETHproductions
источник
Я не знаю, быстрее, но определенно короче: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 Спасибо, это также происходит в несколько раз быстрее, чем мой алгоритм!
ETHproductions
36 байт? Я думаю, что это должно быть рекорд для меня.
Нил
0

APL (NARS), 169 символов, 338 байтов

∇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 - это функция поиска перестановок, а f - функция этого упражнения; тестовое задание:

  ⎕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
источник