Minimalkan jumlah faktor prima melalui penyisipan

12

Mengingat dua bilangan bulat positif A dan B , mengembalikan posisi p yang meminimalkan jumlah faktor prima (penghitungan multiplicities) integer yang dihasilkan, ketika B adalah dimasukkan dalam A di p .

Misalnya, mengingat A = 1234 dan B = 32 , ini adalah kemungkinan penyisipan (dengan p diindeks 0) dan informasi terkait tentang faktor utama mereka:

p | Hasil | Faktor prima | Ω (N) / Hitung

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

Anda dapat melihat bahwa hasilnya memiliki jumlah minimal faktor prima, 3, ketika p adalah 1. Jadi dalam kasus khusus ini, Anda harus menghasilkan 1 .

Spesifikasi

  • Jika ada beberapa posisi p yang meminimalkan hasil, Anda dapat memilih untuk mengeluarkan semuanya atau salah satunya.

  • Anda dapat memilih 0-indexing atau 1-indexing untuk p , tetapi pilihan ini harus konsisten.

  • A dan B dapat diambil sebagai bilangan bulat, string atau daftar digit.

  • Anda dapat bersaing dalam bahasa pemrograman apa pun dan dapat mengambil input dan memberikan output melalui metode standar apa pun , sambil memperhatikan bahwa celah ini dilarang secara default. Ini adalah kode-golf, jadi pengajuan terpendek (skor dalam byte) menang!

Uji kasus

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

1234, 32 -> 1/2
3456, 3 -> 4/5
378, 1824 -> 0/1
1824, 378 -> 4/5
67, 267 -> Setiap atau semua di antara: [1, 2] / [2, 3]
435, 1 -> Setiap atau semua di antara: [1, 2, 3] / [2, 3, 4]
378100, 1878980901 -> Setiap atau semua di antara: [5, 6] / [6, 7]

Untuk kenyamanan, berikut adalah daftar tupel yang mewakili setiap pasangan input:

[(1234, 32), (3456, 3), (378, 1824), (1824, 378), (67, 267), (435, 1), (378100, 1878980901)]
Tuan Xcoder
sumber
1
Saya merasa ini bias terhadap 05AB1E ...
caird coinheringaahing
1
Bisakah kita menampilkan angka yang dihasilkan yang meminimalkan faktor prima dan bukan indeks penyisipan? misalnya dalam test case pertama Anda, 132234bukan 1.
dylnan
2
@ Dylnan saya akan mengatakan tidak saat ini.
Tn. Xcoder

Jawaban:

8

Sekam , 16 byte

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

Harapkan input sebagai string, coba online!

Penjelasan

§◄(ö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
ბიმო
sumber
7

MATL , 25 byte

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

Input adalah string dalam urutan terbalik. Output berbasis 1. Jika ada ikatan, posisi terendah adalah keluaran.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

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
sumber
6

Pyth, 20 13 11 byte

.mlPsXbQzhl

Cobalah online

Penjelasan

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

sumber
3

Jelly , 21 byte

D©L‘Ṭœṗ¥€®żF¥€VÆfL€NM

Cobalah online!

-1 terima kasih kepada Tn . Xcoder .

Mengembalikan semua posisi yang memungkinkan.

Erik the Outgolfer
sumber
3

Japt , 22 21 byte

Ini terasa terlalu lama ketika saya menulisnya tetapi, melihat beberapa solusi lain, itu sebenarnya tampak agak kompetitif. Namun, mungkin ada sedikit ruang untuk perbaikan - Secara cNq)khusus mengganggu saya. Penjelasan untuk diikuti.

Mengambil input pertama sebagai string dan yang kedua sebagai integer atau string. Hasilnya adalah 0-diindeks dan akan mengembalikan indeks pertama jika ada beberapa solusi.

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

Cobalah


Penjelasan

      :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.
Shaggy
sumber
2

PowerShell , 228 byte

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

Cobalah online!

(Sepertinya saran panjang / golf diterima. Juga keluar pada TIO untuk kasus uji terakhir, tetapi algoritme harus berfungsi untuk kasus itu tanpa masalah.)

PowerShell tidak memiliki built-in faktorisasi utama, jadi ini meminjam kode dari jawaban saya pada Prime Factors Buddies . Itu functiondeklarasi baris pertama .

Kami mengambil input $a,$bdan kemudian menetapkan $phashtable kosong. Selanjutnya kita ambil string $b$a, mengubahnya menjadi array tunggal dengan koma-operator ,, dan array-menyatukannya dengan barang . Barang - barang adalah loop through $a, memasukkan $bdi setiap titik, akhirnya array-concatenated with $a$b.

Pada titik ini, kami memiliki array yang $bdisisipkan di setiap titik di $a. Kami kemudian mengirim array melalui loop untuk |%{...}. Setiap iterasi, kita masukkan ke hashtable kami di posisi $i++yang .countberapa faktor utama fyang elemen tertentu $_memiliki.

Akhirnya, kita sorthashtable berdasarkan values, ambil yang hashtable 0-nya, dan pilih Name(yaitu, $iindeks). Yang tersisa pada pipa dan output tersirat.

AdmBorkBork
sumber
2

05AB1E , 27 21 byte

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

Cobalah online!

Ini mengembalikan p -indexed 0 terendah .

Berkat @ Enigma untuk -6 byte!

Penjelasan

ηõ¸ì                  # 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
sumber
1
Dengan menggunakan metode yang sama, Anda bisa menghemat 6 byte dengan menulis ulang ini sebagai ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk.
Emigna
1

Bersih , 165 ... 154 byte

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

Cobalah online!

Suram
sumber
1

Python 2 , 165 146 byte

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

Cobalah online!

Jonathan Frech
sumber
146 bytes
Erik the Outgolfer
@EriktheOutgolfer Terima kasih.
Jonathan Frech
0

JavaScript (ES6), 120 byte

Mengambil input sebagai 2 string. Mengembalikan posisi 0-diindeks.

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

Uji kasus

Arnauld
sumber
0

J, 60 Bytes

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

Pasangan angka eksplisit. Mengambil B di kanan, A di kiri.

Output terindeks 0.

Mungkin dimungkinkan untuk meningkatkan dengan tidak menggunakan kotak.

Penjelasan:

  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
sumber
0

Python 3, 128 byte

0-diindeks; mengambil string sebagai parameter. -6 byte terima kasih kepada Jonathan Frech.

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
sumber
:\n a-> :a.
Jonathan Frech
0

Python, 122 byte

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:])))

Dalam praktiknya, ini melampaui kedalaman rekursi maksimum default dengan cukup cepat.

pengguna84207
sumber