Lipat gandakan dua angka tanpa menggunakan angka apa pun

30

Anda diberikan sebagai input dua string yang mewakili bilangan bulat positif di basis 10, seperti "12345"dan "42". Tugas Anda adalah menghasilkan string yang berisi produk mereka, "518490"dalam hal ini.

Gilirannya adalah Anda tidak boleh menggunakan tipe numerik apa pun dalam kode Anda. Tidak ints, floats, unsigned longs, dll., Tidak ada tipe bilangan kompleks bawaan atau bilangan bulat presisi sewenang-wenang, atau apa pun di sepanjang garis itu. Anda banyak yang tidak menggunakan literal dari tipe-tipe itu, atau fungsi, metode, operator dll. Yang mengembalikannya.

Anda dapat menggunakan string, boolean, array, atau apa pun yang biasanya tidak digunakan untuk mewakili angka. (Tetapi perhatikan bahwa pengindeksan ke dalam array maupun panjangnya tidak akan mungkin dilakukan tanpa memanggil tipe numerik.) charDiizinkan, tetapi Anda tidak boleh melakukan operasi aritmatika atau bitwise pada mereka atau memperlakukannya sebagai hal lain selain token yang mewakili bagian dari string. (Perbandingan leksikografis chars diizinkan.)

Anda mungkin tidak mengatasi batasan. Ini termasuk (tetapi tidak terbatas pada) menggunakan tipe numerik di dalam evalfungsi tipe, konversi tipe implisit menjadi tipe numerik, menggunakan operator numerik atau bitwise pada tipe non-numerik yang mendukungnya, menggunakan tipe numerik yang disimpan di dalam tipe kontainer, atau fungsi panggilan atau program eksternal yang mengembalikan hasil numerik dalam bentuk string. (Saya berhak menambahkan ke daftar ini jika pemecahan masalah lain muncul dalam jawaban.) Anda harus menerapkan perkalian sendiri hanya dengan menggunakan tipe non-numerik.

Input dan output mungkin dengan metode apa pun, selama data masuk dan keluar dari kode Anda dalam bentuk string. Anda dapat mengasumsikan masing-masing dari dua argumen input hanya berisi karakter ASCII [0-9]dan tidak akan dimulai dengan 0. Output Anda seharusnya tidak memiliki nol terkemuka juga.

Satu hal lagi: kode Anda harus benar - benar menangani input hingga setidaknya 10 karakter panjangnya , dan harus berjalan di bawah satu menit pada komputer modern untuk semua input dalam rentang itu. Sebelum memposting, harap periksa bahwa ketika diberi input 9999999999dan 9999999999, program Anda memberikan output 99999999980000000001, dalam waktu kurang dari satu menit. Pembatasan ini ada khusus untuk mencegah jawaban yang berfungsi dengan mengalokasikan array ukuran a*bdan kemudian mengulanginya, jadi harap diingat bahwa jawaban formulir itu tidak akan memenuhi syarat untuk menang.

Ini adalah , sehingga solusi terpendek yang valid (dalam byte) menang.

Nathaniel
sumber
Bisakah kita menerima "12345"dari STDIN bukan 12345? Atau bisakah kita menerima keduanya sebagai "12345", "42"?
Justin
Pikiran pertama saya adalah untuk menulis fungsi mengambil argumen string panjang mdan ndan kembali argumen panjang m*n. Tetapi karena string harus benar-benar berisi representasi angka ASCII, saya kira itu melanggar aturan.
Level River St
1
@ xnor dalam banyak bahasa mungkin lebih pendek untuk menulis semua kasing. Tetapi saya menemukan cara ini dalam Python:a,b="0123456789x".split('0');c=iter(b).next() if c=='x': c='0'
Nathaniel
1
atau dengan Python 3,a,b="0123456789x".split(x);c,*d=b if c=='x': c='0'
Nathaniel
2
@Nathanield='123456789';I=dict(zip('0'+d,d+'0'))
Justin

Jawaban:

6

Haskell - 180 206 214

r=reverse
f=filter
z=['0'..'9']
a?f|f="1"!a
a?_=a
(a:b)!(c:d)=e:b!d?(e<a)where e=fst$last$zip(f(>=c)z++z)$f(<=a)z
a!c=a++c
a%(b:c)=foldr(!)('0':a%c)$f(<b)z>>[a]
_%b=b
a#b=r$r a%r b

Menerapkan multiplikasi melalui penambahan berulang, dan semua jenis sihir digit ditangani dengan menggeser dan memfilter ['0'..'9']daftar. Menentukan operator #tipe String -> String -> String:

*> :set +s
*> "9990123456789"#"9999876543210"
"99900001219316321126352690"
(0.02 secs, 9862288 bytes)
mniip
sumber
Sepertinya kita memiliki pemenang baru! (Meskipun seperti sebelumnya, saya tidak bisa membaca Haskell dari tingkat kecanggihan ini - dapatkah seseorang memeriksanya secara independen memenuhi spesifikasi?)
Nathaniel
(Juga ['0' .. '9'] terasa agak seperti secara implisit memperlakukan karakter sebagai angka yang dapat diulang - apakah ada cara singkat untuk menghasilkan daftar itu dari string "0123456789" sebagai gantinya?)
Nathaniel
@Nathaniel Yah pertama-tama string "0123456789" adalah daftar ['0'..'9']. Kedua, dalam Haskell [a..b] adalah enumerasi, tipe-tipe yang telah menyatakan instance dari Enumtypeclass dapat disebutkan seperti itu, dan deklarasi tersebut menjelaskan cara kerja enumerasi. Bool, tipe boolean juga memiliki instance, dan karenanya Anda juga dapat melakukannya [False..True]. Hampir tidak ada angka yang terlibat.
mniip
14

sed, 339 338 byte

Saya tahu ini sudah lama, tapi saya browsing dan ini menarik minat saya. Cukup untuk mendaftar sebagai pengguna! Saya kira saya terombang-ambing oleh " Saya ingin melihat solusi lengkap - Nathaniel " ...

s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g
:o
s/\( .*\)0$/0\1/
/x$/{
x
G
s/ .*/\n/
:a
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
ta
s/\n//g
:c
s/^x/0x/
s/0xxxxxxxxxx/x0/
tc
x
s/x$//
}
/ 0/bo
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g

Skrip sed ini mengharapkan dua angka desimal sebagai input, dipisahkan oleh satu spasi

tes:

time test 518490 = $(./40297.sed <<<)"12345 42" || echo fail
time test 99999999980000000001 = $(./40297.sed <<<"9999999999 9999999999") || echo fail
time test 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 = $(./40297.sed <<<"37975227936943673922808872755445627854565536638199 40094690950920881030683735292761468389214899724061") || echo fail
time test 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 = $(./40297.sed <<<"33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917") || echo fail

Anda mungkin mengenali dua yang terakhir sebagai RSA-100 (50 x 50 digit) dan RSA-768 (116 x 116 digit).

Menggunakan GNU pada yang tidak terlalu modern (Intel Core 2 era 2007), yang terakhir membutuhkan waktu lebih dari satu menit, tetapi lebih cepat pada prosesor yang lebih baru:

  • Q6600:> 1 menit
  • i7-3770: 26 detik
  • i7-6700: 22 detik

Perkalian 10 digit kecil yang ditentukan dalam pertanyaan ini membutuhkan waktu di bawah satu detik untuk semua ini (meskipun penuh dengan sembilan patologis).

Saya percaya itu sed standar, tanpa ekstensi. POSIX menjamin ruang penyimpanan hanya 8192 byte, yang membatasi kami untuk mengalikan angka 400x400 digit, tetapi implementasinya dapat memberikan lebih banyak. GNU sed hanya dibatasi oleh memori yang tersedia, sehingga dapat mengelola sesuatu yang jauh lebih besar, jika Anda mau menunggu.

Dan saya yakin bahwa saya telah mematuhi aturan - itu hampir diberikan dalam bahasa yang tidak memiliki angka. :-)

Penjelasan

Saya menggunakan hibrida unary / desimal, mengubah angka desimal menjadi urutan unary:

 42 => _xxxx_xx

Dalam desimal unary, penambahan itu mudah. Kami beralih dari digit paling signifikan ke paling signifikan, menyatukan x:

   X=965                   Y=106                                 SUM
   _xxxxxxxxx_xxxxxx_xxxxx _x__xxxxxx
   _xxxxxxxxx_xxxxxx       _x_                          _xxxxxxxxxxx
   _xxxxxxxxx              _x                    _xxxxxx_xxxxxxxxxxx
                                      _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx

Kami kemudian menghapus spasi putih, dan menangani carry dengan mengonversi 10 x berurutan menjadi salah satu unit berikutnya:

 _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx       10.6.11
 _xxxxxxxxxx_xxxxxxx_x                10.7.1
 _x__xxxxxxx_x                        1.0.7.1 

Setelah kami memiliki penambahan, perkalian adalah mungkin. Kami mengalikan x * y dengan mempertimbangkan digit terakhir y. Tambahkan x ke akumulator yang berkali-kali, kemudian pindah ke digit berikutnya dan geser x satu tempat desimal ke kiri. Ulangi sampai y adalah nol.

Kode diperluas

#!/bin/sed -f

# Convert to unary decimal.  We save two or three bytes of code by
# reusing 0 as the digit separator.
s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g

# until y==0

:one

# y ends in zero => x *= 10 and y /= 10
s/\( .*\)0$/0\1/

# while y%10, acc += x, y -= 1
/x$/{
x
G
s/ .*/\n/
# Add x
:add
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
tadd
s/\n//g
:carry
s/^x/0x/
s/0xxxxxxxxxx/x0/
tcarry

# repeat for each unit of y
x
s/x$//
}

# y?
/ 0/bone


# convert hold space to decimal
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g
Toby Speight
sumber
1
Jawabannya sangat memuaskan, terima kasih!
Nathaniel
9

sed, 379 byte

Penghargaan untuk jawaban cemerlang ini jatuh ke @LuigiTiburzi di Unix & Linux.SE: https://unix.stackexchange.com/a/37213/34061 . Saya kebetulan menemukan ini beberapa hari yang lalu:

s/[0-9]/<&/g
s/0//g
s/1/|/g
s/2/||/g
s/3/|||/g
s/4/||||/g
s/5/|||||/g
s/6/||||||/g
s/7/|||||||/g
s/8/||||||||/g
s/9/|||||||||/g
:t
s/|</<||||||||||/g
tt
s/<//g
s/.*\*$/0/
s/^\*.*/0/
s/*|/*/
:m
s/\(|*\)\*|/\1<\1*/
tm
s/*//g
s/<//g
:b
s/||||||||||/</g
s/<\([0-9]*\)$/<0\1/
s/|||||||||/9/
s/||||||||/8/
s/|||||||/7/
s/||||||/6/
s/|||||/5/
s/||||/4/
s/|||/3/
s/||/2/
s/|/1/
s/</|/g
tb

Penjelasan Luas

  • Pisahkan setiap digit. Dengan demikian 12*3menjadi<1<2*<3
  • Konversi setiap digit ke jumlah |karakter itu. Dengan demikian <1<2*<3menjadi<|<||*<|||
  • Ganti berulang kali |<dengan <||||||||||untuk menggeser tempat desimal yang lebih tinggi semuanya ke posisi unit. Dengan demikian <|<||*<|||menjadi<||||||||||||*<|||
  • Hapus <. Dengan demikian <||||||||||||*<|||menjadi||||||||||||*|||
  • Hapus 1 |dari RHS *. Dengan demikian ||||||||||||*|||menjadi||||||||||||*||
  • Ganti masing-masing |pada RHS berulang kali dengan semua |pada LHS. Ini memiliki efek mengalikan LHS dan RHS jumlah |untuk memberikan jumlah produk | demikian ||||||||||||*||menjadi||||||||||||||||||||||||||||||||||||*
  • Hapus *. Dengan demikian ||||||||||||||||||||||||||||||||||||*menjadi||||||||||||||||||||||||||||||||||||
  • konversi jumlah |kembali ke desimal dengan kebalikan dari beberapa langkah pertama. Dengan demikian ||||||||||||||||||||||||||||||||||||menjadi 36.

Keluaran:

$ echo "04*3
4*3
40*3
42*32
150*20
1*3
3*1
0*3
3*0" | sed -f mult.sed
12
12
120
1344
3000
3
3
0
0
$

Sayangnya itu gagal total pada persyaratan waktu - 200*1000membutuhkan 41 detik pada VM Ubuntu saya, dan runtime secara empiris tampaknya naik dengan kuadrat dari produk akhir.

Trauma Digital
sumber
1
Ini hampir secara algoritmik setara dengan jawaban JS saya yang dihapus kecuali untuk konversi kembali ke bagian nomor.
Pengoptimal
@Optimizer Setuju. Perbedaannya adalah bahwa Anda menggunakan length()yang mengembalikan angka. Yang ini menggunakan subtitusi regex murni tanpa tipe numerik. Saya pikir jawaban Anda berpotensi menjadi pemenang meskipun jika Anda dapat menghapus length()- mungkin Anda bisa melakukan substitusi serupa regex bukan?
Digital Trauma
1
Sangat bagus, tetapi pembatasan satu menit secara khusus dimaksudkan untuk mencegah solusi yang bekerja dengan menghitung hingga jawabannya. Saya cukup ingin melihat solusi sed penuh.
Nathaniel
1
Saya punya jawaban yang bekerja pada angka besar (mis. Lebih besar dari ruang alamat sistem).
Toby Speight
@TobySpeight ya, sangat bagus. Saya pikir saya pasti sudah melakukan upgrade Anda beberapa saat yang lalu :)
Digital Trauma
9

Python - 312 286 273

D={}
e=t=""
N=[e]
for c in"0123456789":D[c]=t;D[t]=c;t+="I";N+=N
B=lambda s:[D[c]for c in reversed(s)]
Y=B(input())+N
for a in B(input())+N:
 for c in a:
    s=[];o=e
    for a,b in zip(N,Y):i=a+b+o;o=t<=i and"I"or e;s+=i.replace(t,e),;N=s
 Y=[e]+Y
print e.join(B(N)).lstrip("0")

Jika (banyak) angka nol diijinkan, 12 karakter terakhir tidak diperlukan.

Ini pada dasarnya melakukan perkalian standar dengan tangan. Digit direpresentasikan sebagai string Is berulang (seperti angka Romawi primitif). Angka direpresentasikan sebagai daftar digit dalam urutan terbalik. Penambahan satu digit dilakukan dengan string yang dipatenkan dan menghapus sepuluh Idetik jika perlu.

Ini adalah versi yang tidak dikoleksi:

N = [""] # zero object: list with a lot of empty strings
D = {}   # dictionary for conversion from and to digits
i = ""   # iterates over digits
for c in "0123456789":
    D[c] = i  # map digit to Roman digit
    D[i] = c  # and vice versa
    i += "I"  # increments Roman digit
    N += N    # add leading zeros to zero

ten = "IIIIIIIIII" # Roman digit ten

# Conversion function
B = lambda s: [D[c] for c in reversed(s)]

def Add(x,y):
    Sum = []
    carryover = ""
    for a,b in zip(x,y):
        increment = a+b+carryover
        carryover = "I" if ten in increment else ""
        increment = increment.replace(ten,"") # take increment modulo ten
        Sum += [increment]
    return Sum

def M(x,y):
    Sum = N[:] # Initiate Sum as zero
    X = B(x)+N # Convert and add leading zeros
    Y = B(y)+N
    for a in X:
        for c in a:
            Sum = Add(Sum,p+Y)
        Y = [""] + Y # multiply Y by 10
    return "".join(B(Sum)).lstrip("0") # Convert back and to string, remove leading zeros.

M(input(),input())
Wrzlprmft
sumber
1
Apa sihir ini! Bagaimana cara kerjanya! Wow. Juga, inilah golf lain yang bisa Anda lakukan: def A(x,y):\n S=[];o=""-> def A(x,y,S=[],o=""):. Juga, sayangnya, ["","1"][t in i]tidak diperbolehkan; menggunakan bool untuk mengindeks, memperlakukannya sebagai angka. Saya pikir itu t in i and"1"or""harus bekerja.
Justin
@ Quincunx: Mendefinisikan Ssebagai argumen dengan default tidak akan berhasil, karena akan selalu menjadi daftar yang sama bahkan untuk panggilan fungsi yang berbeda dan dengan demikian tidak diatur ulang ke []. Anda benar tentang ["","1"][t in i], saya memperbaikinya. Saya juga menambahkan penjelasan.
Wrzlprmft
Ini luar biasa. Ia mendapat centang hijau untuk saat ini. (Saya telah mengedit pertanyaan untuk mengklarifikasi bahwa memimpin nol dalam output tidak diizinkan - maaf!)
Nathaniel
7

Ruby: 752 698

Ini hanya untuk mendapatkan jawaban di luar sana, hanya karena penasaran. Diedit: sekarang golf sedikit.

$F='0123456789'
$G="#{$F}abcdefghij"
def x(a,b);p(a=~/[13579]$/?b:"",a==""?"":x(Hash[*%w(b0 5 b1 6 b2 7 b3 8 b4 9)].to_a.inject(a.tr($F,'0011223344').chars.zip(a.tr($F,'ababababab').chars).flatten.join("")){|n,q|k,v=q;n.gsub(k,v)}.gsub(/[ab]/,'').sub(/^0*/,''),p(b,b)));end
def p(a,b);j,k=["0#{a}","0#{b}"].map{|c|c.gsub(/./,'0')};c="#{k}#{a}".chars.zip("#{j}#{b}".chars).drop_while{|z|z==%w(0 0)}.map{|m|$G.sub(/#{m.map{|n|"122333444455555666666777777788888888999999999".chars.select{|c|c==n}}.flatten.map{|c|'.'}.join("")}/,"").chars.first}.flatten.join("");d=nil;
while c!=d
 d=c;c="0#{d}".gsub(/[0-9][a-j]/) {|m| m.tr($G,"123456789a#{$F}")}.sub(/^0/,'')
end;c;end
puts x(ARGV.shift,ARGV.shift)

Penggunaan: Saya memiliki ini di file bernama peasant.rb:

$ time ruby peasant.rb 9999999999 9999999999
99999999980000000001

real    0m0.129s
user    0m0.096s
sys 0m0.027s

Penjelasan: ini multiplikasi petani, jadi saya berulang kali membagi dua & ganda. Membagi dua dilakukan dengan membagi dua digit & menandai sisa seperti: 1234 -> 0b1a1b2a; kemudian temukan dan ganti pada b's: 06a17a; lalu bersihkan -> 617.

Selain itu dilakukan seperti itu ... pertama-tama, saya pad kedua string dengan panjang yang sama dan membuat pasangan dari digit. Kemudian saya menambahkan digit dengan membangun string yang memiliki panjang setiap digit dan menyatukan; Saya menghapus string yang panjangnya dari awal '0123456789abcdefghij', dan kemudian menyimpan char pertama. Jadi, misalnya, "9" + "9" -> "i". NB Saya benar-benar menghindari menggunakan fungsi panjang di sini untuk menghindari jenis angka seluruhnya; menghapus awalan dilakukan dengan regexp sebagai gantinya.

Jadi sekarang saya memiliki string yang berisi campuran angka dan huruf. Huruf-huruf tersebut mewakili angka dengan digit carry; Saya menambahkan 0 ke nomor tersebut, lalu berulang kali mengganti pola huruf-digit dengan hasil carry hingga penambahan selesai.

bazzargh
sumber
1
Jawaban yang sangat cerdik, persis seperti yang saya harapkan!
Nathaniel
1
Saya benar-benar berharap seseorang akan memposting satu dengan angka Gereja!
bazzargh
Itu akan keren, meskipun saya tidak yakin apakah itu akan bekerja dengan persyaratan efisiensi - Saya pikir mengubah antara string dan angka Gereja akan secara efektif melibatkan penghitungan hingga 99999999980000000000001.
Nathaniel
7

Brainfuck (1328 bytes)

Pertimbangan pada awalnya:

  • Tidak yakin apakah brainfuck adalah jawaban yang valid untuk pertanyaan ini karena saya tidak yakin apakah Anda menganggap nilai sel sebagai 'tipe numerik' atau tidak. Saya tidak berpikir begitu karena bf tidak tahu tipe, tapi itu pendapat saya sendiri, tolong perbaiki saya jika saya salah.
  • Diperlukan implementasi yang mendukung (hampir) nilai tidak terbatas.
  • Mungkin terlalu lambat, berdasarkan implementasinya.

Saya hanya menguji program dengan juru bahasa saya sendiri, Anda dapat menemukannya di sini .

Input harus berupa angka yang dipisahkan oleh ruang ASCII tunggal.

Golf:

,>++++++[<----->-]<--[>,>++++++[<----->-]<--]>>>+<<<<[>>++++[<<---->>-]<<[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<,[>,]>>>+<<<<[>>+++++++[<<------->>-]<<+[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<<<<<[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]

Tidak Disatukan:

,
>++++++[<----->-]<--
[                                           # read input until space
    >,
    >++++++[<----->-]<--                    # decrease cell by 32 to check if it's a space
]
>>>+<<<<                                    # set multiplier to 1

[

    >>++++[<<---->>-]<<                     # decrease by 16 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<                                    # delete old multiplier

,[>,]                                       # read second number until end of input
>>>+<<<<                                    # set new multiplier

[

    >>+++++++[<<------->>-]<<+              # decrease by 48 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<<<<<                                # delete multiplier

[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>          # multiply both values

# magical algorithm for printing cell value as number taken from Cedric Mamo's code from a previous question
[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]

Saya telah mengambil kode untuk output nilai dari jawaban ini , terima kasih kepada penulis untuk itu!

Program ini mungkin tidak valid, tetapi dengan cara apa pun saya ingin membaginya dengan Anda ^^

Pembaruan: Anda sekarang dapat mengujinya (hanya untuk multiplikasi kecil) di sini, terima kasih atas jawaban @ Sp3000 untuk kontes ini dan Cuplikan Stack SE baru!

var NUM_CELLS = 30000;var ITERS_PER_SEC = 100000;var TIMEOUT_MILLISECS = 5000;function clear_output(){document.getElementById("output").value="";document.getElementById("stderr").innerHTML=""}function stop(){running=false;document.getElementById("run").disabled=false;document.getElementById("stop").disabled=true;document.getElementById("clear").disabled=false;document.getElementById("wrap").disabled=false;document.getElementById("timeout").disabled=false;document.getElementById("eof").disabled=false}function interrupt(){error(ERROR_INTERRUPT)}function error(e){document.getElementById("stderr").innerHTML=e;stop()}function run(){clear_output();document.getElementById("run").disabled=true;document.getElementById("stop").disabled=false;document.getElementById("clear").disabled=true;document.getElementById("wrap").disabled=true;document.getElementById("timeout").disabled=true;document.getElementById("eof").disabled=true;code=document.getElementById("code").value;input=document.getElementById("input").value;wrap=document.getElementById("wrap").value;timeout=document.getElementById("timeout").checked;eof=document.getElementById("eof").value;loop_stack=[];loop_map={};for(var e=0;e<code.length;++e){if(code[e]=="["){loop_stack.push(e)}else if(code[e]=="]"){if(loop_stack.length==0){error(ERROR_BRACKET);return}else{var t=loop_stack.pop();loop_map[t]=e;loop_map[e]=t}}}if(loop_stack.length>0){error(ERROR_BRACKET);return}running=true;start_time=Date.now();code_ptr=0;input_ptr=0;cell_ptr=Math.floor(NUM_CELLS/2);cells={};iterations=0;bf_iter(1)}function bf_iter(e){if(code_ptr>=code.length||!running){stop();return}var t=Date.now();for(var n=0;n<e;++n){if(cells[cell_ptr]==undefined){cells[cell_ptr]=0}switch(code[code_ptr]){case"+":if(wrap=="8"&&cells[cell_ptr]==255||wrap=="16"&&cells[cell_ptr]==65535||wrap=="32"&&cells[cell_ptr]==2147483647){cells[cell_ptr]=0}else{cells[cell_ptr]++}break;case"-":if(cells[cell_ptr]==0){if(wrap=="8"){cells[cell_ptr]=255}if(wrap=="16"){cells[cell_ptr]=65535}if(wrap=="32"){cells[cell_ptr]=2147483647}}else{cells[cell_ptr]--}break;case"<":cell_ptr--;break;case">":cell_ptr++;break;case".":document.getElementById("output").value+=String.fromCharCode(cells[cell_ptr]);break;case",":if(input_ptr>=input.length){if(eof!="nochange"){cells[cell_ptr]=parseInt(eof)}}else{cells[cell_ptr]=input.charCodeAt(input_ptr);input_ptr++}break;case"[":if(cells[cell_ptr]==0){code_ptr=loop_map[code_ptr]}break;case"]":if(cells[cell_ptr]!=0){code_ptr=loop_map[code_ptr]}break}code_ptr++;iterations++;if(timeout&&Date.now()-start_time>TIMEOUT_MILLISECS){error(ERROR_TIMEOUT);return}}setTimeout(function(){bf_iter(ITERS_PER_SEC*(Date.now()-t)/1e3)},0)}var ERROR_BRACKET="Mismatched brackets";var ERROR_TIMEOUT="Timeout";var ERROR_INTERRUPT="Interrupted by user";var code,input,wrap,timeout,eof,loop_stack,loop_map;var running,start_time,code_ptr,input_ptr,cell_ptr,cells,iterations
<div style="font-size:12px;font-family:Verdana, Geneva, sans-serif;"> <div style="float:left; width:50%;"> Code: <br> <textarea id="code" rows="4" style="overflow:scroll;overflow-x:hidden;width:90%;">,>++++++[<----->-]<--[>,>++++++[<----->-]<--]>>>+<<<<[>>++++[<<---->>-]<<[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<,[>,]>>>+<<<<[>>+++++++[<<------->>-]<<+[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<<<<<[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]</textarea> <br>Input: <br> <textarea id="input" rows="2" style="overflow:scroll;overflow-x:hidden;width:90%;">7 6</textarea> <p> Wrap: <select id="wrap"> <option value="8">8-bit</option> <option value="16">16-bit</option> <option value="32" selected="selected">32-bit</option> </select> &nbsp; Timeout: <input id="timeout" type="checkbox"></input>&nbsp; EOF: <select id="eof"> <option value="nochange">Same</option> <option value="0" selected="selected">0</option> <option value="-1">-1</option> </select> </p> </div> <div style="float:left; width:50%;"> Output: <br> <textarea id="output" rows="6" style="overflow:scroll;width:90%;"></textarea> <p> <input id="run" type="button" value="Run" onclick="run()"></input> <input id="stop" type="button" value="Stop" onclick="interrupt()" disabled="true"></input> <input id="clear" type="button" value="Clear" onclick="clear_output()"></input> &nbsp; <span id="stderr" style="color:red"></span></p></div></div>

Sandi
sumber
Saya juga tidak tahu apakah itu valid! Saya kira semuanya nomor di Brainfuck, atau tidak ada.
Nathaniel
Saya suka jawaban ini. Saya telah mengacaukan diri saya sendiri belakangan ini. itu semacam menyoroti fakta bahwa pada tingkat mesin, semuanya token saja. Sulit mengatakan apakah ini benar-benar mengikuti aturan atau tidak.
Octopus
6

Python, 394 349 340 karakter

D='0123456789'
R=reversed
U=lambda x:[R for y in D if y<x]
T=U(':')
def A(a,b,r='',c=[]):
 for x,y in map(None,R(a),R(b)):
    d=U(x)+U(y)+c;t=T;c=[R]
    if d<T:t=c=[]
    r=min(k for k in D if U(k)+t>=d)+r
 if c:r='1'+r
 return r
a,b=input()
m=''
while b:
 if list(b).pop()in'13579':m=A(m,a)
 b=list(A(b,A(b,A(b,A(b,b)))));b.pop();a=A(a,a)
print m

Jalankan seperti:

echo '"9999999999","9999999999"' | ./mulstr.py

Membutuhkan 50 milidetik.

Menggunakan multiplikasi Petani Rusia . Saat menambahkan angka, kami mengonversinya menjadi unary ('5' => [R, R, R, R, R]), menyatukan daftar, lalu mengonversi kembali. Udikonversi ke unary, menggunakan Rsebagai digit unary. Kami menghitung b/=2sebagai b=b*5/10.

Keith Randall
sumber
Beberapa golf: def A(a,b):\n r='';c=[]-> def A(a,b,r='',c=[]):, sama untuk def M. Anda mungkin dapat mengubah for z in D:d.pop()\n c=['X']ke [d.pop()for z in D];c=['X'], dalam hal ini Anda bahkan dapat menutupnya ke sebelumnya if. Juga, bisa if list(b).pop()in'13579'begitu if b[:].pop()in'13579'?
Justin
@ Quincunx: Terima kasih. Yang terakhir tidak akan berfungsi karena pada iterasi pertama badalah string, bukan daftar.
Keith Randall
Anda dapat melewati Mdan menulis program lengkap; a,b=input() Diperbolehkan.
Justin
1
b * 5/10 adalah trik yang bagus.
bazzargh
Saya baru saja menemukan reduce, yang memungkinkan Anda untuk A(b,A(b,A(b,A(b,b))))melakukannya reduce(A,[b,b,b,b,b]). Sayangnya, ini tidak mempengaruhi jumlah karakter.
Wrzlprmft
5

JavaScript (E6) 375 395 411 449

Sunting Golfed,
Sunting Bug yang diperbaiki: tidak ada membersihkan bendera carry

Ini dapat dilakukan hanya dengan manipulasi simbol dalam waktu mendekati 0.
Dalam versi ini Anda bisa menggunakan karakter apa saja, bukan digit, asalkan simbol dalam urutan menaik.

Catatan: menggunakan string, hashmap dengan kunci string, array digunakan sebagai daftar. Tanpa pengindeksan, array dilintasi menggunakan 'peta' atau diputar menggunakan push & shift.
Semua '+' adalah penggabungan string.

M=(x,y,S=a=>a.shift()||z,R=a=>[...a].reverse(),e=R('9876543210'),d=[...e])=>
  R(y)[T='map'](b=>
     R(x)[T](a=>(
       u=R[e[a+=b]+v],
       v=R[S[a]+(u<v?'1':z)],
       p[P](t=R[S(o)+u]),
       t<u?v=R[v+'1']:v
     ),o=p,p=[])
    +(v>z&&p[P](v),x+=v=z),
    d[T](a=>d[T](b=>e[P='push'](R[a+b]=S(e)))+e[P](S(e))),  
    d[T](a=>d[T](b=>e[d[T](c=>v=c<a?(u=R[u+b])<b?R[v+'1']:v:v,v=u=z='0'),S[a+b]=v,a+b]=u)),
    p=[v=z]
  )&&R(p).join(o)

Kurang Golf (mungkin saya akan menambahkan penjelasan besok)

M=(x,y)=>(
  R=a=>[...a].reverse(),
  // Addition table s 
  s={},
  e=[...'9012345678'],
  [for(a of(d='0123456789'))for(b of(e.push(e.shift()),d))e.push(s[a+b]=c=e.shift())],
  // Multiplication table m,n
  m={},n={},
  [for(a of d)for(b of d)(
     [for(c of(z=u=v='0',d))
     c<a&&(t=s[u+b],t<u?v=s[v+'1']:v,u=t)
     ],m[a+b]=u,n[a+b]=v
  )],
  x=R(x),v=z,o=[],p=[],
  [for(b of R(y))(
     [for(a of x)(
       u=s[m[a+b]+v],v=s[n[a+b]+(u<v?'1':z)],
       p.push(t=s[(o.shift()||z)+u]),
       t<u?v=s[v+'1']:v
     )],
     v>z?p.push(v):o,o=p,p=[],x.unshift(v=z)
  )],
  R(o).join('')
)

Uji di konsol FireFox / FireBug

t0=-new Date
r=M('9999999999','9999999999')
t1=-new Date
console.log("Result",r, "time ms", t0-t1)

Keluaran

Result 99999999980000000001 time ms 14
edc65
sumber
Mungkin ada sedikit bug - keluaran dari 9999999999kasing seharusnya 99999999980000000001, bukan99999999980000000081
Nathaniel
:( akan memeriksa
edc65
Jika Anda menggunakan tabel perkalian, bagaimana Anda mengatasi fakta bahwa penjumlahan tidak diizinkan?
COTO
1
Penjumlahan IS diizinkan menggunakan hashtable (s dalam kode). Ex. s ['34 '] ->' 7 '. Hanya simbol, bukan angka. Bisa jadi s ['cd'] -> 'g'
edc65
5

Haskell, 231 byte

Ini mendefinisikan operator yang mengalikan dua representasi string dari bilangan asli. Ia bekerja dengan mendefinisikan operasi kenaikan / penurunan dasar pada string, kemudian menggunakannya untuk membangun penambahan dan perkalian. Sedikit sihir ekstra memberi beberapa speedup eksponensial yang memungkinkan semuanya terjadi ..

r=reverse
n="9876543210"
t=True
c&(x:y)|c==x=head y|t=c&y
m%[]="1";m%(c:s)|c==last m=head m:m%s|t=c&m:s
[]!y=y;x![]=x;(x:a)!('0':b)=x:a!b;x!y=(r n%x)!(n%y)
"0"?_="0";x?('0':y)|all(=='0')y="0"|t=('0':x)?y;x?y=x?(n%y)!x
x#y=r$r x?r y

Pendekatan ini cukup cepat sehingga bahkan pada laptop 2008 di ghpl REPL yang tidak dioptimalkan, test case hanya membutuhkan sepersekian detik:

λ> :set +s
λ> let test = replicate 10 '9'
(0.00 secs, 0 bytes)
λ> test
"9999999999"
(0.00 secs, 1069784 bytes)
λ> test # test
"99999999980000000001"
(0.06 secs, 13451288 bytes)

Berikut ini cek bahwa semua produk dua digit sudah benar:

λ> and [ show (x * y) == (show x # show y) | x <- [0..100], y <- [0..100] ]
True
Matt Noonan
sumber
Sepertinya kita memiliki pemimpin baru! (Saya tidak bisa membaca Haskell - bisakah seseorang secara independen mengkonfirmasi bahwa itu sesuai dengan spesifikasi?)
Nathaniel
1
Ya, itu haskell sempurna cromulent, itu cocok dengan spec, dan berfungsi seperti yang diiklankan. Kerja bagus!
bazzargh
4

Bash + ImageMagick: 52

convert -size ${a}x${b} xc:red txt:-|grep -v g|wc -l

Mengharapkan input berada dalam variabel shell adan b. Ini tidak terlalu pintar atau efisien, tetapi menyelesaikan pekerjaan. Mungkin sudah pernah dilakukan sebelumnya.

Perhatikan bahwa xmenunjukkan dimensi gambar; ini bukan operator aritmatika dalam konteks ini.

Saya belum menguji ini, tetapi saya bersedia berasumsi bahwa untuk input non-ekstrim, ini akan selesai dalam waktu kurang dari satu menit. Saya bisa mengujinya besok.

Jika ada bisnis lucu dengan versi ImageMagick, ini adalah yang saya gunakan: ImageMagick 6.7.7-10

milinon
sumber
Usaha yang bagus, tapi saya yakin ini tidak akan bekerja dalam waktu kurang dari satu menit (atau memang sama sekali pada mesin yang ada) untuk input 9999999999dan 9999999999.
Nathaniel
4
Ini juga bekerja: dd if=/dev/zero bs=$a count=$b 2>&-|wc -c.
jimmy23013
1
Sebuah 9999999999x9999999999gambar dalam format 8bit akan mengambil semua ruang hard drive yang saat ini ada di Bumi. Tentu saja, png akan jauh lebih kecil, jika Anda dapat membuatnya tanpa terlebih dahulu membuat gambar mentah. (Meskipun saya sangat curiga Anda akan memiliki masalah overflow bilangan bulat dengan gambar sebesar itu.) Namun demikian, metode seperti itu hampir pasti akan jatuh dari celah panggilan-hal-yang-kembali-numerik-hasil-sebagai-string.
Nathaniel
1
Anda dapat menyimpan 2 byte dengan menggunakan $bbukan ${b}.
nyuszika7h
1
Anda juga dapat menyimpan 5 byte dengan menggunakan grep -vc galih-alih grep -v g|wc -l.
nyuszika7h
2

Python 2 (bukti konsep)

Solusi ini hanya bekerja menggunakan string dan daftar, dan sedikit regex. Saya percaya itu cocok dengan spesifikasi sepenuhnya, kecuali bahwa tidak ada cara yang bisa dilakukan 9999999999x9999999999dalam satu menit. Meskipun diberi cukup waktu, itu akan berhasil. Ini dapat melipatgandakan angka 4 digit dengan cukup cepat.

Karena secara teknis tidak valid saya belum repot-repot untuk golf sepenuhnya. Saya akan melakukannya jika aturannya berubah.

import re
D='123456789'
D=dict(zip('0'+D,D+'0'))

def toRlist(s):
    if s:t,h=re.match(r'(\d*)(\d)',s).groups();return[h,toRlist(t)]
    return''

def increment(r):
    if not r:return['1','']
    h,t=r
    return[D[h],increment(t)if h=='9'else t]

def toString(r):
    if not r:return''
    h,t=r
    return h+toString(t)

def listify(r,L):
    if not r:return
    h,t=r
    if h=='1':L.append('')
    if h=='2':L.extend(['',''])
    if h=='3':L.extend(['','',''])
    if h=='4':L.extend(['','','',''])
    if h=='5':L.extend(['','','','',''])
    if h=='6':L.extend(['','','','','',''])
    if h=='7':L.extend(['','','','','','',''])
    if h=='8':L.extend(['','','','','','','',''])
    if h=='9':L.extend(['','','','','','','','',''])
    listify(t,L);listify(t,L);listify(t,L);listify(t,L);listify(t,L)
    listify(t,L);listify(t,L);listify(t,L);listify(t,L);listify(t,L)

def add(r1,r2):
    L=[];listify(r2,L)
    for _ in L:r1=increment(r1)
    return r1

def multiply(a,b):
    total=''
    r=toRlist(a)
    L=[];listify(toRlist(b),L)
    for _ in L:total=r if total=='' else add(total,r)
    return''.join(reversed(toString(total)))

Contoh:

multiply('12','5') #returns the string 60

multiply('1869','1243') #returns the string 2323167
Hobi Calvin
sumber
1
1 karena memenuhi spesifikasi (terlepas dari persyaratan efisiensi) sejauh yang saya tahu
Nathaniel
2

Python 2 (555)

Saya biasanya tidak akan menjawab tantangan saya sendiri begitu cepat (atau sama sekali), tetapi saya ingin membuktikan itu bisa dilakukan. (Untungnya ada jawaban lain yang melakukannya sebelum ini, tetapi saya tidak bisa tidak ingin menyelesaikannya.) Ada lagi golf yang bisa dilakukan, tetapi saya pikir ini masuk akal. Ini menangani 9999999999x9999999999kasing di bawah 0,03s di mesin saya.

d="123456789";I=dict(zip('0'+d,d+'0'))
def r(x):return reversed(x)
def s(x):return''.join(x)
def i(x):
    try:
        h=I[x.next()]
        if h!='0':h+=s(x)
        else:h+=i(x)
        return h
    except:return'1'
def b(x,y):
    for c in'0'+d:
        if c==y:break
        x=iter(i(x))
    return x
def a(x,y):
    z=''
    for c in y:
        x=b(x,c)
        try:z+=x.next()
        except:z+='0'
    return z+s(x)
def n(x,y):
    z='0'
    for c in'0'+d:
        if c==y:break
        z=a(iter(z),x)
    return z
def o(x,y):
    x=s(x)
    l='';z=''
    for c in y:
        z=a(iter(z),l+s(n(x,c)))
        l+='0'
    return z
def m(x,y):
    return s(r(o(r(x),r(y))))

Contoh penggunaan: m("12345","42")

Ini bekerja dengan melakukan perkalian panjang menggunakan manipulasi string. Kadang-kadang variabel adalah string dan kadang-kadang mereka iterator atas string, yang memungkinkan untuk mendapatkan elemen pertama tanpa menggunakan integer literal. Semuanya disimpan dengan digit terbalik, sehingga elemen pertama adalah digit paling signifikan.

Berikut ini penjelasan fungsi-demi-fungsi:

  • rdan smerupakan fungsi pembukuan. ( rhanya alias untuk reversed, yang membuat iterator terbalik, dans mengubah iterator menjadi string.)

  • imenambah angka dalam string dengan 1, termasuk kasus seperti 39+1=40dan99+1=100 .

  • bmenambah xdan y, tetapi yharus hanya satu digit. Ini bekerja dengan menambahkanx y waktu.

  • amenambahkan dua angka bersamaan yang keduanya dapat memiliki beberapa digit, dengan memanggil bsetiap digity .

  • nmengalikan xdan y, tetapi yharus hanya satu digit. Ini bekerja dengan menambah waktu xitu sendiri y.

  • omengalikan xdan y, di mana kedua argumen dapat memiliki beberapa digit. Ini menggunakan perkalian panjang klasik

  • mhanya mengubah input stringnya menjadi iterator terbalik dan menyerahkannya o, lalu membalikkan hasilnya dan mengubahnya menjadi string.

Nathaniel
sumber
Golf pasangan: def a(x,y):-> def a(x,y,z=''):dan hapus baris berikutnya; trik serupa untuk fungsi-fungsi lain, dalam def o(x,y):, ubah x=s(x)to x=s(x);l='';z='', di dalam itu untuk loop, juga hapus langkah + baru; alih-alih gunakan ;. Juga, saya pikir if h!='0':h+=s(x)\nelse:h+=i(x)bisa saja h+=h!='0'and i(x)or s(x); bahkan mungkin h+=(h!='0'and i or s)(x); jika tidak, cukup ubah ke if'0'!=h. Juga hal-hal seperti def r(x):return reversed(x)->r=reversed
Justin
Juga, saya lupa menyebutkan untuk s, m: s=lambda x:''.join(x), m=lambda x,y:s(r(o(r(x),r(y))))alih-alih seluruh deklarasi fungsi. Dengan hanya hal-hal yang saya tahu berhasil, ini membuat byte-count Anda turun ke 521.
Justin
Oh, dan satu lagi: untuk forloop Anda : for c in'0'+d:\nif c==y:break\nz=a(iter(z),x)-> for c in'0'+d:\nif c!=y:z=a(iter(z),x), meskipun ini dapat secara signifikan mengubah kecepatan program Anda.
Justin
@ Quincunx terima kasih! Saya bisa melihat beberapa perbaikan lain pagi ini. (Sebagian besar bersarang loop daripada mendefinisikan fungsi.) Saya akan membuat perubahan ini jika beberapa jawaban yang lebih kompetitif muncul, yang tampaknya mungkin - saat ini mereka akan menempatkan saya di depan, yang tampaknya sedikit tidak adil karena itu adalah pertanyaan saya dan saya ' Sudah lebih lama memikirkannya.
Nathaniel
2

JavaScript: 3710 3604 byte

  • Menggunakan tabel pencarian string dengan 1 digit perkalian dan tambahkan dengan carry.
  • Perkalian dilakukan dengan digit x digit alih-alih digit x garis.

Golf:

var M={
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};
var A={
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
} 
Array.prototype.e=function(){return(''+this)==='';}
String.prototype.s=function(){return this.split('').reverse();}
function B(a,b,c) {
var r='',s='';
a=a.s();
b=b.s();
while (!a.e()||!b.e()||c!=='0') {
x=a.e()?'0':a.shift();
y=b.e()?'0':b.shift();
s=A[c+x+y];
s=s.s();
r=s.shift()+r;
c=s.e()?'0':'1';
}
return r;
}
function m(a,b) {
var s='0',m='';
b.split('').reverse().forEach(function(e){
var z=m;
a.split('').reverse().forEach(function(f){s=B(s,M[e+f]+z,'0');z+='0';});
m+='0';
});
return s;
}

Tidak disatukan dengan tes:

var mul = {
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};

var adc = {
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
} 

Array.prototype.isEmpty = function() {
  return (''+this) === '';
}

function add(a, b, c) {
  var r = '', s = '';
  a = a.split("").reverse();
  b = b.split("").reverse();
  while (!a.isEmpty() || !b.isEmpty() || c !== '0') {
    x = a.isEmpty() ? '0' : a.shift();
    y = b.isEmpty() ? '0' : b.shift();
    s = adc[c + x + y];
    s = s.split("").reverse();
    r = (s.shift()) + r;
    c = (s.isEmpty()) ? '0' : '1';
  }
  return r;
}

function mult(a, b) {
  var s = '0';
  var m = '';
  b.split('').reverse().forEach(function(e) {
    var z = m;
    a.split('').reverse().forEach(function(f) {
      s = add(s, mul[e + f] + z, '0');
      z = z + '0';
    });
    m = m + '0';
  } );
  return s;
}

function test(a, b) {
  var t0 = (new Date()).getTime();
  var r = mult(a,b);
  var t1 = (new Date()).getTime();
  var e = t1 - t0;
  console.log('mult ' + a + ' * ' + b + ' = ' + r + " (" + e + " ms)");
}

test('12345', '42');
test('9999999999', '9999999999');

Output ini:

mult 12345 * 42 = 518490 (3 ms) 
mult 9999999999 * 9999999999 = 99999999980000000001 (47 ms) 
Stephen Quan
sumber
2

Haskell 507 496

Ini berfungsi untuk bilangan bulat besar yang sewenang-wenang. Saya mendefinisikan representasi kustom untuk bilangan asli dari 0 hingga 18 (bilangan alami terbesar sama dengan jumlah dua digit), dan mendefinisikan penggandaan little-endian dalam hal penggandaan angka * angka, yang saya tentukan dalam hal penambahan nomor + angka , yang saya definisikan dalam hal penambahan digit + digit. Saya memiliki fungsi reduksi yang memperluas nilai 10--18 ke dalam dekomposisi digital mereka. Ini kemudian hanya membaca dan membalikkan dua string, menerjemahkan ke binding kustom, mengalikan, dan menerjemahkan kembali, membalikkan untuk mendapatkan hasil yang benar.

Edit 2

Saya menyimpan beberapa karakter dengan membuat alias lokal pendek untuk perintah multi-karakter yang saya gunakan lebih dari sekali, serta menghilangkan spasi dan tanda kurung, dan dengan mengganti (- )pasangkan dengan $bila memungkinkan.

data S=Z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R deriving(Enum, Ord, Eq)
p Z=id
p x=succ.p(pred x)
s Z=id
s x=pred.s(pred x)
z=s J
r[]=[]
r(x:y)|x<J=x:r y
r(x:[])=z x:[A]
r(x:y)=z x:(r$p A a:b)where(a:b)=r y
a x y=r$w(r x)(r y)
m Z _=[]
m _[]=[]
m x y=r$a y(m(pred x)y)
t[]_=[Z]
t _[]=[Z]
t(x:z)y=r$a(m x y)(Z:r(t z y))
i '0'=Z
i x=succ.i.pred$x
b Z='0'
b x=succ.b.pred$x
w[]y=y
w x[]=x
w(x:c)(y:d)=p x y:(w c d)
o=map
v=reverse
f=(o i).v
g=v.o b
main=getLine>>=putStrLn.(\[x,y]->g$t(f x)(f y)).words

Untuk referensi, S adalah tipe data seperti integer kustom, padalah 'plus' (penambahan digit + digit), sdikurangi (untuk reduksi), rdikurangi (ekspansi ke dekomposisi digital), apenambahan (penambahan nomor + penambahan), madalah multiply (digit * number multiplication), tadalah times (number * number multiplication), iadalah 'interpret' (convert string to list of S), badalah 'back' (daftar S to string), dan f dan g hanyalah kependekan dari bermain golf tujuan. Saya tidak menggunakan angka, bahkan secara implisit; yang paling dekat yang saya dapatkan adalah menggunakan penerus dan pendahulu, yang merupakan konsep matematika tingkat yang jauh lebih tinggi daripada penambahan dan penggandaan bilangan alami.

Edit

Lupa memasukkan profil waktu.

> time echo "9999999999 9999999999" | runhaskell multnonum.hs
99999999980000000001

real    0m0.246s
user    0m0.228s
sys     0m0.012s

Hanya untuk ukuran yang baik:

> time echo "99999999980000000001 99999999980000000001" | runhaskell multnonum.hs
9999999996000000000599999999960000000001

real    0m0.244s
user    0m0.224s
sys     0m0.016s

Ayo menjadi gila!

> time echo "9999999996000000000599999999960000000001 9999999996000000000599999999960000000001" | runhaskell multnonum.hs
99999999920000000027999999994400000000699999999944000000002799999999920000000001

real    0m0.433s
user    0m0.424s
sys     0m0.004s

konfirmasi

archaephyrryx
sumber
1

Python 2 - 1165, 712, 668 664

I,T,V,N,X,J=raw_input,dict,reversed,None,zip,''.join
D='0123456789'
z,o='01'
A,B=I(),I()
r=i=""
K=map(J,X('666622222222911111551111555884444447773333333','678945672389954132987698765898967457989837654'))
P=T(X(K,map(J,X('344501110011800000440000332673322124652202211','628480244668154132507698505422648609367491852'))))
S=T(X(K,'cdef678945abi65243ed87a9cbaghcdab89egfcb6a987'))
for d in D:P[z+d]=z;S[z+d]=d
def Z(A,B,R=r):
 for a,b in V(map(N,V(z+A),V(z+B))):c=(a or z)+(b or z);s=S[min(c)+max(c)];R=Z(R,o)+T(X('abcdefghi',D))[s]if s>"?"else R+s
 return R
for a in V(A):
 j=""
 for b in V(B):r=Z(r,P[min(a+b)+max(a+b)]+i+j).lstrip(z);j+=z
 i+=z
print r if r else z

Perhatikan bahwa saya tidak menggunakan pengindeksan logis seperti Z = [X, Y][N == "0"], karena ini dapat diartikan sebagai boolean yang dilemparkan ke indeks numerik.

Tidak Disatukan:

A = raw_input()
B = raw_input()

P = {'00':'00','01':'00','02':'00','03':'00','04':'00','05':'00','06':'00','07':'00','08':'00','09':'00',
     '10':'00','11':'01','12':'02','13':'03','14':'04','15':'05','16':'06','17':'07','18':'08','19':'09',
     '20':'00','21':'02','22':'04','23':'06','24':'08','25':'10','26':'12','27':'14','28':'16','29':'18',
     '30':'00','31':'03','32':'06','33':'09','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
     '40':'00','41':'04','42':'08','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
     '50':'00','51':'05','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
     '60':'00','61':'06','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
     '70':'00','71':'07','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
     '80':'00','81':'08','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
     '90':'00','91':'09','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81',
     }
S = {'00':'0','01':'1','02':'2','03':'3','04':'4','05':'5','06':'6','07':'7','08':'8','09':'9',
     '10':'1','11':'2','12':'3','13':'4','14':'5','15':'6','16':'7','17':'8','18':'9','19':'a',
     '20':'2','21':'3','22':'4','23':'5','24':'6','25':'7','26':'8','27':'9','28':'a','29':'b',
     '30':'3','31':'4','32':'5','33':'6','34':'7','35':'8','36':'9','37':'a','38':'b','39':'c',
     '40':'4','41':'5','42':'6','43':'7','44':'8','45':'9','46':'a','47':'b','48':'c','49':'d',
     '50':'5','51':'6','52':'7','53':'8','54':'9','55':'a','56':'b','57':'c','58':'d','59':'e',
     '60':'6','61':'7','62':'8','63':'9','64':'a','65':'b','66':'c','67':'d','68':'e','69':'f',
     '70':'7','71':'8','72':'9','73':'a','74':'b','75':'c','76':'d','77':'e','78':'f','79':'g',
     '80':'8','81':'9','82':'a','83':'b','84':'c','85':'d','86':'e','87':'f','88':'g','89':'h',
     '90':'9','91':'a','92':'b','93':'c','94':'d','95':'e','96':'f','97':'g','98':'h','99':'i',
     }
L = {'a':'0','b':'1','c':'2','d':'3','e':'4','f':'5','g':'6','h':'7','i':'8'}

def strSum(A, B):
    R = ""
    for a, b in reversed(map(None, reversed("0" + A), reversed("0" + B))):
        if a == None: a = '0'
        if b == None: b = '0'
        s = S[a + b]
        if s.isdigit():
            R += s
        else:
            R = strSum(R, "1") + L[s]
    return R

i = ""
r = "0"
for a in reversed(A):
    j = ""
    for b in reversed(B):
        p = P[a + b] + i + j
        r = strSum(r, p)
        j += "0"
    i += "0"

r = r.lstrip("0")
if r == "":
    r = "0"

print r
Falko
sumber
Saya akan mengatakan bahwa menggunakan fungsi min () dan maks () tidak boleh diizinkan karena mereka membandingkan nilai integer aktual, bukan?
WorldSEnder
@WorldSEnder: Saya katakan mereka membandingkan karakter, yang diizinkan dalam tantangan ini. ("Perbandingan karakter kamus diperbolehkan.")
Falko
1

Scala, 470 karakter

( adalah standar scala tetapi bisa diganti dengan =>jika kita menghitung byte)

def p(a: String,b: String)={type D=List[Char]
val d="0123456789".toList
def v(s: String)=s.toList.map{c⇒d.takeWhile(c.!=)}
def u(l:D, a:D):(Char,D)=l match {
case _::_::_::_::_::_::_::_::_::_::m⇒u(m,'a'::a)
case _⇒(('a'::l).zip(d).last._2,a)}
val o=(("", List[Char]())/:v(a).tails.toList.init.map{l⇒(v(b) map {_.flatMap(_⇒l.head)})++l.tail.map(_⇒Nil) reverse}.reduce(_.zipAll(_, Nil, Nil).map{t⇒t._1++t._2}))({(t,e)⇒val s=u(t._2++e,Nil);(s._1+t._1,s._2)})
u(o._2, Nil)._1+o._1}

Di sini kami meniru digit menggunakan panjang daftar, berhati-hati untuk tidak menggunakan operasi numerik - hanya lipatan, peta, ritsleting dan sejenisnya. Angka adalah daftar angka-angka ini (urutan dibalik secara strategis setengah dari perhitungan); kita gandakan digit individu dengan flatMapdan baris kita dengan reduce. umenangani mencari tahu carry (dengan langsung mencocokkan dengan daftar> 10 elemen, dan berulang) dan mengubah angka kembali ke karakter, dan kami menggunakan a /:untuk bekerja melalui tumpukan dengan itu. Contoh yang diperlukan selesai dalam waktu kurang dari satu detik.

lmm
sumber