Seberapa kecil itu bisa didapat?

42

Dimulai dengan bilangan bulat positif N , temukan bilangan bulat terkecil N ' yang dapat dihitung dengan berulang kali membagi N dengan salah satu digitnya (dalam basis-10). Setiap digit yang dipilih harus merupakan pembagi N lebih besar dari 1 .

Contoh 1

Output yang diharapkan untuk N = 230 adalah N '= 23 :

230/2 = 115, 115/5 = 23

Contoh # 2

Output yang diharapkan untuk N = 129528 adalah N '= 257 :

129528/8 = 16191, 16191/9 = 1799, 1799/7 = 257

Waspadalah terhadap jalur yang tidak optimal!

Kita bisa mulai dengan 129528/9 = 14392 , tetapi itu tidak akan menghasilkan hasil sekecil mungkin. Yang terbaik yang bisa kita lakukan jika kita membagi 9 adalah:

129528/9 = 14392, 14392/2 = 7196, 7196/7 = 1028, 1028/2 = 514 -> salah!

Aturan

  • Input dapat diambil dalam format apa pun yang wajar (integer, string, array digit, ...).
  • Ini , jadi jawaban tersingkat dalam byte menang!

Uji kasus

1         --> 1
7         --> 1
10        --> 10
24        --> 1
230       --> 23
234       --> 78
10800     --> 1
10801     --> 10801
50976     --> 118
129500    --> 37
129528    --> 257
8377128   --> 38783
655294464 --> 1111
Arnauld
sumber
1
Saya ingin tahu apakah seri ini (1, 1, ..., 10, 11, 1, 13, ..., 1, ...) memiliki entri OEIS
Draco18s
Itu belum (belum), AFAICS.
GNiklasch

Jawaban:

11

Haskell , 67 61 byte

f n=minimum$n:[f$div n d|d<-read.pure<$>show n,d>1,mod n d<1]

Cobalah online!

Penjelasan:

  • read.pure<$>show nmentransformasikan integer input nmenjadi daftar digit.
  • Untuk setiap digit ddari daftar ini, kami memeriksa d>1dan mod n d<1, yaitu apakah dmembagi n.
  • Jika pemeriksaan berhasil, kita membagi noleh ddan rekursif berlaku f: f$div n d.
  • Secara keseluruhan, ini menghasilkan daftar bilangan bulat minimal dari semua sub-pohon dari n.
  • Karena daftar mungkin kosong, kami menambahkannya ndan mengembalikan minimumdaftar.
Laikoni
sumber
11

Jelly , 8 byte

÷DfḶ߀Ṃo

Cobalah online!

Versi alternatif, jauh lebih cepat, 9 byte

÷DfÆḌ߀Ṃo

Cobalah online!

Bagaimana itu bekerja

÷DfḶ߀Ṃo  Main link. Argument: n

 D        Decimal; yield the digits of n.
÷         Divide n by each of its digits.
   Ḷ      Unlength; yield [0, ..., n-1].
  f       Filter; keep quotients that belong to the range.
    ߀    Recursively map this link over the resulting list.
      Ṃ   Take the minimum. This yields 0 if the list is empty.
       o  Logical OR; replace 0 with n.
Dennis
sumber
5

Ruby ,52 47 byte

Bersaing untuk grup bahasa non-eksotis! (Catatan: ide yang bagus, jika tidak bermain golf, adalah menambahkan .uniqsetelah .digitskarena semua cabang serupa memiliki hasil yang sama)

f=->n{n.digits.map{|x|x>1&&n%x<1?f[n/x]:n}.min}

Cobalah online!

Penjelasan

f=->n{      # Function "f" n ->
   n.digits # n's digits (in reverse order (<- doesn't matter))
            # fun fact: all numbers always have at least one digit
    .map{|x|# Map function for every digit "x" ->
       x>1&&    # x is 2-9 and
       n%x<1    # n mod x == 0, or, "n is divisible by x"
       ? f[n/x] # then recursively find smallest of f[n/x]
       : n      # otherwise: n (no shortest path in tree)
     }.min  # Smallest option out of the above
            # if we reach a dead end, we should get n in this step
}
Unihedron
sumber
Dapatkah Anda menggunakan x<2|n%x?n:f[n/x]untuk menyimpan dua atau tiga byte (tergantung pada apakah Anda memerlukan satu |atau dua)?
Neil
@ Neil Sayangnya, ruby ​​memperlakukan value%zerosebagai pembagian dengan nol, sehingga hubungan arus pendek tidak akan berfungsi. Juga, 0adalah nilai kebenaran di ruby ​​(satu-satunya nilai falsey adalah false dan nil).
Unihedron
Jadi, apakah itu akan bekerja dengan dua ||s?
Neil
Tidak, karena 0 dianggap benar, itu akan dengan >0, tetapi kemudian itu adalah jumlah char yang sama.
Unihedron
Maaf, saya tidak melihat dari mana 0datangnya jika Anda tidak menggunakan |?
Neil
5

Common Lisp , 136 byte

(defun f(n)(apply 'min(or(loop for z in(map'list #'digit-char-p(write-to-string n))if(and(> z 1)(<(mod n z)1))collect(f(/ n z)))`(,n))))

Cobalah online!

Versi yang dapat dibaca:

(defun f (n)
  (apply 'min
         (or (loop for z in (map 'list
                                 #'digit-char-p
                                 (write-to-string n))
                   if (and (> z 1)
                           (< (mod n z) 1))
                   collect (f (/ n z)))
             `(,n))))
Traut
sumber
3
Selamat datang di PPCG!
Laikoni
@Laikoni terima kasih! Bukan pengiriman terkecil tapi masih cukup menyenangkan
Traut
@Laikoni kesalahan saya, diperbaiki. Terima kasih!
Traut
@Arnauld terima kasih telah memperhatikan! Saya memperbaiki cuplikan dan mengubah tautan.
Traut
@Laikoni memang! Saya turun ke 205b.
Traut
4

Jelly , 21 byte

Dðḍ>Ị{
DxÇ⁸:߀µÇẸ$¡FṂ

Cobalah online!

Erik the Outgolfer
sumber
4

Bahasa Wolfram (Mathematica) , 44 byte

-7 byte berkat Misha Lavrov.

Min[#0/@(#/IntegerDigits@#⋂Range[#-1]),#]&

Cobalah online!

alephalpha
sumber
1
Golfier agak adalah solusi 44-byte ini didasarkan pada penggunaan karakter untuk Intersection. Tapi ada kasus besar yang tidak bisa lagi ditangani karena kehabisan memori yang dihasilkan Range[#-1].
Misha Lavrov
1
Kita dapat menggunakan Most@Divisors@#alih-alih Range[#-1]untuk menghindari masalah memori, tetapi hasilnya adalah 49 byte .
Misha Lavrov
4

JavaScript (Firefox 30-57), 49 byte

f=n=>Math.min(...(for(c of''+n)c<2|n%c?n:f(n/c)))

Versi kompatibel ES6, 52 byte:

f=n=>Math.min(...[...''+n].map(c=>c<2|n%c?n:f(n/c)))
<input type=number oninput=o.textContent=f(this.value)><pre id=o>

Awalnya saya mencoba memfilter angka yang tidak relevan tetapi ternyata sedikit lebih panjang pada 54 byte:

f=n=>Math.min(n,...(for(c of''+n)if(c>1&n%c<1)f(n/c)))
Neil
sumber
3

Kotlin , 100 99 byte

fun f(i:Int):Int{return i.toString().map{it.toInt()-48}.filter{it>1&&i%it<1}.map{f(i/it)}.min()?:i}

Yg diperindahkan

fun f(i:Int):Int{
    return i.toString()
        .map { it.toInt()-48 }
        .filter { it >1 && i % it < 1}
        .map { f(i/it) }
        .min() ?: i
}

Uji

fun f(i:Int):Int{return i.toString().map{it.toInt()-48}.filter{it>1&&i%it<1}.map{f(i/it)}.min()?:i}

val tests = listOf(
        1 to 1,
        7 to 1,
        10 to 10,
        24 to 1,
        230 to 23,
        234 to 78,
        10800 to 1,
        10801 to 10801,
        50976 to 118,
        129500 to 37,
        129528 to 257,
        8377128 to 38783,
        655294464 to 1111)

fun main(args: Array<String>) {
    for ( test in tests) {
        val computed = f(test.first)
        val expected = test.second
        if (computed != expected) {
            throw AssertionError("$computed != $expected")
        }
    }
}

Suntingan

jrtapsell
sumber
3

Jelly , 15 byte

ÆDḊfD
:Ç߀µÇ¡FṂ

Cobalah online!

Saya harus mengakui bahwa ߀bagian itu dipinjam dari jawaban Erik . Selebihnya dikembangkan secara terpisah, sebagian karena saya bahkan tidak mengerti bagaimana sisa jawaban itu bekerja: P.

Bagaimana itu bekerja?

ÆDḊfD ~ Helper link (monadic). I'll call the argument N.

ÆD    ~ Take the divisors.
  Ḋ   ~ Dequeue (drop the first element). This serves the purpose of removing 1.
   fD ~ Take the intersection with the decimal digits.

:Ç߀µÇ¡FṂ ~ Main link.

 Ç        ~ Apply the helper link to the first input.
:         ~ And perform element-wise integer division.
     Ç¡   ~ If the helper link applied again is non-empty*, then...
  ߀µ     ~ Apply this link to each (recurse).
       FṂ ~ Flatten and get the maximum.

* Saya terkejut bahwa ¡berfungsi seperti itu pada daftar, karena makna normal berlaku ini n kali .

Setelah Dennis menjelaskan mengapa ߀tidak memerlukan persyaratan, kita memiliki versi 12-byter ini , atau versi 8 byte-nya: P.

Tuan Xcoder
sumber
3

R , 101 98 byte

f=function(x,e=(d=x%/%10^(0:nchar(x))%%10)[d>1])"if"(sum(y<-which(!x%%e)),min(sapply(x/e[y],f)),x)

Cobalah online!

Satu ton byte digunakan untuk mengekstraksi digit dan mana yang dibagi x; mungkin diperlukan pendekatan lain.

Giuseppe
sumber
3

Excel Vba, 153 byte

Golf kode pertama dalam satu-satunya bahasa yang saya tahu :( Tidak ramah golf ...

Function S(X)
S = X
For I = 1 To Len(CStr(X))
A = Mid(X, I, 1)
If A > 1 Then If X Mod A = 0 Then N = S(X / A)
If N < S And N > 0 Then S = N
Next I
End Function

Panggil seperti ini:

Sub callS()

result = S(655294464)

MsgBox result

End Sub

Saya belum tahu ke mana harus menguji ini secara online.

Durielblood
sumber
1
Selamat datang di PPCG! Saya tidak benar-benar tahu Vba tetapi saya curiga Anda dapat mengganti And N > 0 dengan N = Spada baris sebelumnya. (Juga, jika saya memiliki cara untuk mengujinya, insting pertama saya adalah memeriksa apakah ada ruang yang bisa dihilangkan.)
Ørjan Johansen
2

APL (Dyalog) , 33 byte

{⍬≡do/⍨0=⍵|⍨o1~⍨⍎¨⍕⍵:⍵⋄⌊/∇¨⍵÷d}

Cobalah online!

Bagaimana?

⍎¨⍕⍵ - ambil digit n

1~⍨ - tidak termasuk 1 s

o/⍨ - filter menurut

0=⍵|⍨o - pembagian dari n oleh digit

⍬≡...:⍵ - jika kosong, kembali n

⌊/ - jika tidak, kembalikan minimum

∇¨ - rekursi untuk setiap nomor dalam

⍵÷d- pembagian noleh masing-masing digit yang difilter di atas

Uriel
sumber
2

Perl 5, 87 + 1 ( -p) = 88 byte

$r=0,map{$\=$_,$r++if!$\|$_<$\;for$i(/[2-9]/g){$_%$i||$h{$_/$i}++}}$_,keys%h;$r&&redo}{

coba online

Nahuel Fouilleul
sumber
2

PHP, 120 byte

<?php function f($n){$r=array_map(function($x)use($n){return$x>1&&!($n%$x)?f($n/$x):$n;},str_split($n));return min($r);}

Cobalah online!

Zerquix18
sumber
3
Selamat datang di situs ini! :)
DJMcMayhem
2
Anda dapat menghilangkan tag PHP pembuka dan menyimpan 6 byte :-)
Daniel W.
2

Pari / GP , 49 byte

f(n)=vecmin([if(d<2||n%d,n,f(n/d))|d<-digits(n)])

Cobalah online!

alephalpha
sumber