Temukan jumlah angka x-digit yang produk digitnya adalah N

8

Diberi dua angka N dan x, cari jumlah angka x-digit yang produk digitnya adalah N

limits: N(<10^6) and x(<12)

Sample Input:
8 3
Sample Output:
10
code-golf number-theory fR0DDY
sumber
Panjang kode terpendek atau runtime terpendek? Tampaknya untuk yang ini, runtime terpendek dengan codelength? <1000 (katakanlah) akan menjadi target yang lebih bermakna.
smci
Saya tidak mengerti: 2 digit x dan N, x = 8, N = 3 berarti 8 digit di mana produk tersebut adalah 3. Karena 3 adalah prima, maka hanya 3111 ... 1, 1311 ... 1, 113 ... - 8 kemungkinan. Apa yang saya lewatkan?
pengguna tidak dikenal
@ penggunaunknown Ini sebaliknya: tiga digit di mana produk itu delapan. (222, 811, 181, 118, dan enam cara untuk mengatur 1,2,4, saya percaya.)
kotak roti
@breadbox: Sementara itu saya mengenali itu, tetapi deskripsi harus diperbaiki. Jika saya memberikan dua angka N dan x, tidak boleh diklaim bahwa saya diberi dua angka x dan N (yang merupakan urutan dalam informasi utama juga).
pengguna tidak diketahui

Jawaban:

3

Python 208 karakter

def dec(num, num_dig):
    if num_dig==0:
        return int(num==1)
    else:
        return sum(dec(num/i, num_dig-1) for i in range(1,10) if num/i*i==num)

if __name__ == "__main__":    
    print dec(8,3)
Wok
sumber
3

Golfscript 42 31

~10\?.10/\,>{10base{*}*1$=},,\;

Input: Mengharapkan angka Ndan xsebagai argumen baris perintah (dipisahkan oleh spasi).

Program dapat diuji di sini .

Cristian Lupascu
sumber
Saya menguji dan mendapat Code took longer than 5 seconds to run, so it was aborted.dengan parameter terbalik. :)
pengguna tidak diketahui
@ penggunaunknown Anda benar. Kode ini sangat tidak efisien ketika xberjalan di atas 4. Misalnya, jika saya menjalankannya di mesin saya dengan parameter 3 5saya mendapatkan hasilnya setelah 30+ detik. Jadi, 3 8kurasa itu bisa berjam-jam ...
Cristian Lupascu
Saya tidak pernah melihat naskah Golf ini. Apakah ini hampir selalu lambat?
pengguna tidak diketahui
Tujuan @userunknown Golfscript bukanlah kecepatan dan itu diketahui agak lambat. Namun, dalam hal ini algoritma yang sangat tidak efisien. Tetapi kodenya pendek :)
Cristian Lupascu
1
@userunknown, GolfScript ditafsirkan dalam Ruby. Juga, semua nilai tidak berubah, jadi ada banyak penyalinan yang terlibat. Itu tidak cenderung cepat, dan sering dapat menambahkan satu atau dua dari n ke runtime algoritma asimptotik yang biasanya dianalisis dalam model RAM.
Peter Taylor
2

Brachylog (2), 13 byte, tantangan tanggal bahasa

{h.&t~lℕẹ≜×}ᶜ

Cobalah online!

Penjelasan

{h.&t~lℕẹ≜×}ᶜ
{          }ᶜ   Count the number of
         ≜      values at this point
   &t           formed via taking the last element of the input,
       ℕ        generating an integer
     ~l         of that length,
        ẹ       and splitting it into digits
          ×     such that the product of those digits
 h.             is the first element of {the input}

Salah satu trik golf rapi yang digunakan di sini adalah tidak seperti hampir semua metapredicate, ᶜtidak peduli sama sekali tentang nilai aktual .(yang biasanya digunakan untuk membangun output untuk metapredicate); dengan demikian, .dapat digunakan seperti variabel lain (menyimpan byte karena itu muncul secara implisit sebelumnya }). Tidak ada labelisasi implisit di mana pun di sini, jadi saya harus menambahkan labelisasi eksplisit menggunakan ≜untuk memberikan ᶜsesuatu untuk dihitung.


sumber
1

Scala 107:

def f(N:Int,x:Int,s:Int=1):Int=if(s==N&&x==0)1 else
if(s>N||x==0)0 else
((1 to 9).map(i=>f(N,x-1,s*i))).sum

ungolfed, versi debugfriendly:

def findProduct (N: Int, sofar: Int, togo:Int, collected:String=""):Int={
  if (sofar == N && togo == 0) {
    println (collected)
    1
  } else
  if (sofar > N || togo == 0) 0 else 
  (1 to 9).map (x=> findProduct (N, sofar*x, togo-1, collected + " " + x)).sum
}

Doa dengan hasil debug:

scala> findProduct (3, 1, 8)
 1 1 1 1 1 1 1 3
 1 1 1 1 1 1 3 1
 1 1 1 1 1 3 1 1
 1 1 1 1 3 1 1 1
 1 1 1 3 1 1 1 1
 1 1 3 1 1 1 1 1
 1 3 1 1 1 1 1 1
 3 1 1 1 1 1 1 1
res175: Int = 8

scala> findProduct (8, 1, 3)
 1 1 8
 1 2 4
 1 4 2
 1 8 1
 2 1 4
 2 2 2
 2 4 1
 4 1 2
 4 2 1
 8 1 1
res176: Int = 10
Pengguna tidak diketahui
sumber
Saya sudah mengujinya di simplyscala.com dan itu sangat cepat. +1 untuk kinerja.
Cristian Lupascu
0

Python (masih mengerjakannya) 164

from itertools import *
N,x=map(int,raw_input().split())
print len([c for c in product([d for d in range(1,10)if N%d==0],repeat=x) if reduce(lambda x,y:x*y,c)==N])
st0le
sumber
0

C # 128

int Z(int n,int x){var i=(int)Math.Pow(10,x-1);return Enumerable.Range(i,i*9).Count(j=>(j+"").Aggregate(1,(a,c)=>a*(c-48))==n);}

Metode C # ini mengembalikan jumlah xangka -digit yang produk digitnya adalah n. Ini membutuhkan ruang nama Systemdan System.Linqdiimpor dalam konteks saat ini.

Versi online: http://ideone.com/0krup

Cristian Lupascu
sumber
0

Haskell 117 karakter

import Data.Char
main = print $ f 3 8
f n t = length[x|x<-[10^(n-1)..(10^n-1)],foldr(*)1(map digitToInt $ show x)==t]
Romain
sumber
0

K, 49

{+/x=*/'"I"$''${x@&~x in y}.!:'"i"$10 xexp y,y-1}

.

k){+/x=*/'"I"$''${x@&~x in y}.!:'"i"$10 xexp y,y-1}[8;3]
10
tmartin
sumber
0

J, 40 byte

[:+/[=[:*/"1(10#~])#:(10^<:@])}.[:i.10^]

Menghasilkan semua xangka -digit, mengonversi masing-masing ke basis 10, kemudian menemukan produk dari masing-masing angka, dan menguji apakah setiap angka sama dengan sisi kiri, dan kemudian menemukan jumlah masing-masing boolean.

Biarawati Bocor
sumber
0

Jelly , 12 byte, tantangan tanggal kiriman bahasa

,’⁵*r/ḊDP€ċƓ

Cobalah online!

Mengambil x sebagai argumen baris perintah dan N pada input standar.

Penjelasan

,’⁵*r/ḊDP€ċƓ
,             On {the input} and
 ’            {the input} minus 1
  ⁵*          take 10 to the power of each of those numbers
    r/        then form a range between them
      Ḋ       without its first element;
       D      treat each element as a list of digits,
        P€    take the product of each of those digit lists,
          ċ   then count the number of times
           Ɠ  the value from standard input appears

Bagian yang sulit adalah membuat daftar angka dengan x digit; angka terendah adalah 10 x −1 , tertinggi adalah 10 x −1. Kisaran di sini dihasilkan melalui pertama-tama menghasilkan pasangan ( x , x −1), kemudian mengambil 10 pangkat keduanya, dan kemudian menghasilkan kisaran di antara mereka. Rentang ini mencakup kedua titik akhir secara default; untuk berjaga-jaga jika N adalah 0, kita perlu menghapus ujung atas dari rentang (yang didahulukan karena itu adalah rentang "mundur") menggunakan Ḋ.


sumber