Zminimalizuj liczbę czynników pierwszych poprzez wstawienie

12

Biorąc pod uwagę dwie dodatnie liczby całkowite A i B , zwróć pozycję p, która minimalizuje liczbę czynników pierwszych (licząc krotność) wynikowej liczby całkowitej, gdy B zostanie wstawione do A w punkcie p .

Na przykład, biorąc pod uwagę A = 1234 i B = 32 , są to możliwe wstawienia (przy czym p ma indeks 0) i odpowiednie informacje o ich czynnikach głównych:

p | Wynik | Czynniki pierwsze | Ω (N) / Count

0 | 321234 | [2, 3, 37, 1447] | 4
1 | 132234 | [2, 3, 22039] | 3)
2 | 123234 | [2, 3, 19, 23, 47] | 5
3 | 123324 | [2, 2, 3, 43, 239] | 5
4 | 123432 | [2, 2, 2, 3, 37, 139] | 6

Widać, że wynik ma minimalną liczbę czynników pierwszych, 3, gdy p wynosi 1. W tym konkretnym przypadku powinieneś otrzymać 1 .

Okular

  • Jeśli istnieje wiele pozycji p, które minimalizują wynik, możesz wybrać wyjście wszystkich z nich lub dowolnej z nich.

  • Możesz wybrać indeksowanie 0 lub indeksowanie 1 dla p , ale ten wybór musi być spójny.

  • A i B mogą być traktowane jako liczby całkowite, ciągi znaków lub listy cyfr.

  • Możesz konkurować w dowolnym języku programowania i możesz przyjmować dane wejściowe i generować dane wyjściowe za pomocą dowolnej standardowej metody , zwracając uwagę, że te luki są domyślnie zabronione. To jest golf golfowy, więc wygrywa najkrótsze zgłoszenie (w bajtach)!

Przypadki testowe

A, B -> p (indeksowane 0) / p (indeksowane 1)

1234, 32 -> 1/2
3456, 3 -> 4/5
378,1824 -> 0/1
1824, 378 -> 4/5
67, 267 -> Dowolne lub wszystkie spośród: [1, 2] / [2, 3]
435, 1 -> Dowolne lub wszystkie spośród: [1, 2, 3] / [2, 3, 4]
378100, 1878980901 -> Dowolne lub wszystkie spośród: [5, 6] / [6, 7]

Dla wygody oto lista krotek reprezentujących każdą parę danych wejściowych:

[(1234, 32), (3456, 3), (378, 1824), (1824, 378), (67, 267), (435, 1), (378100, 1878980901)]
Pan Xcoder
źródło
1
Mam wrażenie, że jest to stronnicze w stosunku do 05AB1E ...
caird coinheringaahing 10.01.18
1
Czy możemy podać wynikową liczbę, która zminimalizowała czynniki pierwsze zamiast indeksu wstawienia? np. w pierwszym przypadku testowym 132234zamiast 1.
dylnan
2
@dylnan Tym razem powiem nie.
Pan Xcoder,

Odpowiedzi:

8

Łuska , 16 bajtów

§◄öLpr§·++⁰↑↓oΘŀ

Oczekuje wprowadzania jako ciągów, spróbuj online!

Wyjaśnienie

§◄(öLpr§·++⁰↑↓)(Θŀ)  -- input A implicit, B as ⁰ (example "1234" and "32")
§ (           )(  )  -- apply A to the two functions and ..
  (ö          )      --   | "suppose we have an argument N" (eg. 2)
  (    §      )      --   | fork A and ..
  (         ↑ )      --     | take N: "12"
  (          ↓)      --     | drop N: "34"
  (     ·++⁰  )      --   | .. join the result by B: "123234"
  (   r       )      --   | read: 123234
  (  p        )      --   | prime factors: [2,3,19,23,47]
  ( L         )      --   | length: 5
  (öLpr§·++⁰↑↓)      --   : function taking N and returning number of factors
                            in the constructed number
               ( ŀ)  --   | range [1..length A]
               (Θ )  --   | prepend 0
               (Θŀ)  --   : [0,1,2,3,4]
 ◄                   -- .. using the generated function find the min over range
ბიმო
źródło
7

MATL , 25 bajtów

sh"2GX@q:&)1GwhhUYfn]v&X<

Dane wejściowe są łańcuchami w odwrotnej kolejności. Wyjście jest oparte na 1. W przypadku remisu generowana jest najniższa pozycja.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

s         % Implicitly input B as a string. Sum (of code points). Gives a number
h         % Implicitly input A as a string. Concatenate. Gives a string of length
          % N+1, where N is the length of A
"         % For each (that is, do N+1 times)
  2G      %   Push second input
  X@      %   Push 1-based iteration index
  q       %   Subtract 1
  :       %   Range from 1 to that. Gives [] in the first iteration, [1] in
          %   the second, ..., [1 2 ... N] in the last
  &)      %   Two-output indexing. Gives a substring with the selected elements,
          %   and then a substring with the remaining elements
  1G      %   Push first input
  whh     %   Swap and concatenate twice. This builds the string with B inserted
          %   in A at position given by the iteration index minus 1
  U       %   Convert to string
  Yf      %   Prime factors
  n       %   Number of elements
]         % End
v         % Concatenate stack vertically
&X<       % 1-based index of minimum. Implicitly display
Luis Mendo
źródło
6

Pyth, 20 13 11 bajtów

.mlPsXbQzhl

Wypróbuj online

Wyjaśnienie

.mlPsXbQzhl
.m    b         Find the minimum value...
         hl     ... over the indices [0, ..., len(first input)]...
  lP            ... of the number of prime factors...
    sX Qz       ... of the second input inserted into the first.

źródło
3

Japt , 22 21 bajtów

Wydawało mi się, że jest to zbyt długo, kiedy to pisałem, ale patrząc na niektóre inne rozwiązania, wydaje się to nieco konkurencyjne. Mimo to prawdopodobnie jest trochę miejsca na ulepszenia - cNq)w szczególności mnie to denerwuje. Wyjaśnienie do naśladowania.

Pobiera pierwsze wejście jako ciąg znaków, a drugie jako liczbę całkowitą lub ciąg znaków. Wynik jest indeksowany na 0 i zwróci pierwszy indeks, jeśli istnieje wiele rozwiązań.

ÊÆiYVÃcNq)®°k Ê
b@e¨X

Spróbuj


Wyjaśnienie

      :Implicit input of string U and integer V.
Ê     :Get the length of U.
Æ     :Generate an array of the range [0,length) and map over each element returning ...
iYV   :  U with V inserted at index Y.
à    :End mapping
c     :Append ...
Nq    :  The array of inputs joined to a string.
®     :Map over the array.
°     :Postfix increment - casts the current element to an integer.
k     :Get the prime divisors.
Ê     :Get the length.
\n    :The newline allows the array above to be assigned to variable U.
b     :Get the first index in U that returns true ...
@     :  when passed through a function that ...
e     :    checks that every element in U...
¨     :    is greater than or equal to...
X     :    the current element.
      : Implicit output of resulting integer.
Kudłaty
źródło
2

PowerShell , 228 bajtów

param($a,$b)function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
$p=@{};,"$b$a"+(0..($x=$a.length-2)|%{-join($a[0..$_++]+$b+$a[$_..($x+1)])})+"$a$b"|%{$p[$i++]=(f $_).count};($p.GetEnumerator()|sort value)[0].Name

Wypróbuj online!

(Wydaje się, że długie / golfowe sugestie są mile widziane. Również limit czasu dla TIO dla ostatniego przypadku testowego, ale algorytm powinien działać dla tego przypadku bez problemu.)

Program PowerShell nie ma żadnych wbudowanych głównych faktoryzacji, więc pożycza kod z mojej odpowiedzi na temat znajomych Prime Factors . To functiondeklaracja pierwszego wiersza .

Bierzemy dane wejściowe, $a,$ba następnie ustawiamy $psię jako pusta tablica mieszająca. Następnie bierzemy ciąg $b$a, zamieniamy go w tablicę singletonową za pomocą operatora przecinka ,i konkatenujemy tablicę za pomocą rzeczy . Materiał jest pętla poprzez $awstawienie $bw każdym punkcie, w końcu łączone z macierzach $a$b.

W tym momencie mamy tablicę $bwstawioną w każdym punkcie $a. Następnie wysyłamy tę tablicę przez pętlę for |%{...}. Każda iteracja, możemy wstawić do naszej hashtable w pozycji o ile czynniki pierwsze , że dany element ma.$i++.countf$_

Na koniec mamy sorttablicę mieszającą opartą na values, weźmy 0jej i wybierz jej Name(tj. $iIndeks). Pozostaje to w potoku, a dane wyjściowe są niejawne.

AdmBorkBork
źródło
2

05AB1E , 27 21 bajtów

ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk

Wypróbuj online!

Zwraca najniższą p -indeksowaną przez 0 .

Dzięki @Enigma za -6 bajtów!

Wyjaśnienie

ηõ¸ì                  # Push the prefixes of A with a leading empty string -- [, 1, 12, 123, 1234]
    ¹.sRõ¸«)          # Push the suffixes of A with a tailing empty space. -- [1234, 123, 12, 1, ]
            ø         # Zip the prefixes and suffixes
             ε    }   # Map each pair with...
              IýÒg    # Push B, join prefix - B - suffix, map with number of primes
                   Wk # Push the index of the minimum p
Kaldo
źródło
1
Korzystając z tej samej metody, można zapisać 6 bajtów, przepisując to jako ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk.
Emigna
1

Czysty , 165 ... 154 bajtów

import StdEnv,StdLib
@n h#d=hd[i\\i<-[2..h]|h rem i<1]
|d<h= @(n+1)(h/d)=n
?a b=snd(hd(sort[(@0(toInt(a%(0,i-1)+++b+++a%(i,size a))),i)\\i<-[0..size a]]))

Wypróbuj online!

Obrzydliwe
źródło
1

Python 2 , 165 146 bajtów

O=lambda n:n>1and-~O(n/min(d for d in range(2,n+1)if n%d<1))
def f(A,B):L=[int(A[:j]+B+A[j:])for j in range(len(A)+1)];print L.index(min(L,key=O))

Wypróbuj online!

Jonathan Frech
źródło
146 bajtów
Erik the Outgolfer
@EriktheOutgolfer Dziękujemy.
Jonathan Frech
0

JavaScript (ES6), 120 bajtów

Pobiera dane wejściowe jako 2 ciągi. Zwraca pozycję z indeksowaniem 0.

f=(a,b,i=0,m=a)=>a[i>>1]?f(a,b,i+1,eval('for(n=a.slice(0,i)+b+a.slice(i),x=k=2;k<n;n%k?k++:n/=x++&&k);x')<m?(r=i,x):m):r

Przypadki testowe

Arnauld
źródło
0

J, 60 bajtów

4 :'(i.<./)#@q:>".@(,(":y)&,)&.>/"1({.;}.)&(":x)"0 i.>:#":x'

Wyraźna diada. Bierze B po prawej, A po lewej.

Wyjście indeksowane 0.

Może być możliwe ulepszenie poprzez nieużywanie skrzynek.

Wyjaśnienie:

  4 :'(i.<./)#@q:>".@(,(":x)&,)&.>/"1({.;}.)&(":y)"0 i.>:#":y'  | Whole program
  4 :'                                                       '  | Define an explicit dyad
                                                     i.>:#":y   | Integers from 0 to length of y
                                                  "0            | To each element
                                     ({.;}.)&(":y)              | Split y at the given index (result is boxed)
                     (,(":x)&,)&.>/"1                           | Put x inbetween, as a string
                  ".@                                           | Evaluate
                 >                                              | Unbox, makes list
             #@q:                                               | Number of prime factors of each
      (i.>./)                                                   | Index of the minimum
Bolce Bussiere
źródło
0

Python 3, 128 bajtów

0-indeksowane; przyjmuje parametry jako parametry. -6 bajtów dzięki Jonathanowi Frechowi.

from sympy.ntheory import*
def f(n,m):a=[sum(factorint(int(n[:i]+m+n[i:])).values())for i in range(len(n)+1)];return a.index(min(a))
0WJYxW9FMN
źródło
:\n a-> :a.
Jonathan Frech
0

Python, 122 bajty

f=lambda n,i=2:n>1and(n%i and f(n,i+1)or 1+f(n/i,i))
g=lambda A,B:min(range(len(A)+1),key=lambda p:f(int(A[:p]+B+A[p:])))

W praktyce dość szybko przekracza domyślną maksymalną głębokość rekurencji.

użytkownik84207
źródło