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
, float
s, unsigned long
s, 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.) char
Diizinkan, 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 char
s diizinkan.)
Anda mungkin tidak mengatasi batasan. Ini termasuk (tetapi tidak terbatas pada) menggunakan tipe numerik di dalam eval
fungsi 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 9999999999
dan 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*b
dan kemudian mengulanginya, jadi harap diingat bahwa jawaban formulir itu tidak akan memenuhi syarat untuk menang.
Ini adalah kode-golf , sehingga solusi terpendek yang valid (dalam byte) menang.
sumber
"12345"
dari STDIN bukan12345
? Atau bisakah kita menerima keduanya sebagai"12345", "42"
?m
dann
dan kembali argumen panjangm*n
. Tetapi karena string harus benar-benar berisi representasi angka ASCII, saya kira itu melanggar aturan.a,b="0123456789x".split('0');c=iter(b).next()
if c=='x':
c='0'
a,b="0123456789x".split(x);c,*d=b
if c=='x':
c='0'
d='123456789';I=dict(zip('0'+d,d+'0'))
Jawaban:
Haskell - 180
206 214Menerapkan multiplikasi melalui penambahan berulang, dan semua jenis sihir digit ditangani dengan menggeser dan memfilter
['0'..'9']
daftar. Menentukan operator#
tipeString -> String -> String
:sumber
"0123456789"
adalah daftar['0'..'9']
. Kedua, dalam Haskell [a..b] adalah enumerasi, tipe-tipe yang telah menyatakan instance dariEnum
typeclass 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.sed,
339338 byteSaya 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 " ...
Skrip sed ini mengharapkan dua angka desimal sebagai input, dipisahkan oleh satu spasi
tes:
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:
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:
Dalam desimal unary, penambahan itu mudah. Kami beralih dari digit paling signifikan ke paling signifikan, menyatukan x:
Kami kemudian menghapus spasi putih, dan menangani carry dengan mengonversi 10 x berurutan menjadi salah satu unit berikutnya:
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
sumber
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:
Penjelasan Luas
12*3
menjadi<1<2*<3
|
karakter itu. Dengan demikian<1<2*<3
menjadi<|<||*<|||
|<
dengan<||||||||||
untuk menggeser tempat desimal yang lebih tinggi semuanya ke posisi unit. Dengan demikian<|<||*<|||
menjadi<||||||||||||*<|||
<
. Dengan demikian<||||||||||||*<|||
menjadi||||||||||||*|||
|
dari RHS*
. Dengan demikian||||||||||||*|||
menjadi||||||||||||*||
|
pada RHS berulang kali dengan semua|
pada LHS. Ini memiliki efek mengalikan LHS dan RHS jumlah|
untuk memberikan jumlah produk|
demikian||||||||||||*||
menjadi||||||||||||||||||||||||||||||||||||*
*
. Dengan demikian||||||||||||||||||||||||||||||||||||*
menjadi||||||||||||||||||||||||||||||||||||
|
kembali ke desimal dengan kebalikan dari beberapa langkah pertama. Dengan demikian||||||||||||||||||||||||||||||||||||
menjadi36
.Keluaran:
Sayangnya itu gagal total pada persyaratan waktu -
200*1000
membutuhkan 41 detik pada VM Ubuntu saya, dan runtime secara empiris tampaknya naik dengan kuadrat dari produk akhir.sumber
length()
yang mengembalikan angka. Yang ini menggunakan subtitusi regex murni tanpa tipe numerik. Saya pikir jawaban Anda berpotensi menjadi pemenang meskipun jika Anda dapat menghapuslength()
- mungkin Anda bisa melakukan substitusi serupa regex bukan?Python -
312286273Jika (banyak) angka nol diijinkan, 12 karakter terakhir tidak diperlukan.
Ini pada dasarnya melakukan perkalian standar dengan tangan. Digit direpresentasikan sebagai string
I
s berulang (seperti angka Romawi primitif). Angka direpresentasikan sebagai daftar digit dalam urutan terbalik. Penambahan satu digit dilakukan dengan string yang dipatenkan dan menghapus sepuluhI
detik jika perlu.Ini adalah versi yang tidak dikoleksi:
sumber
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 itut in i and"1"or""
harus bekerja.S
sebagai 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.Ruby:
752698Ini hanya untuk mendapatkan jawaban di luar sana, hanya karena penasaran. Diedit: sekarang golf sedikit.
Penggunaan: Saya memiliki ini di file bernama peasant.rb:
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.
sumber
Brainfuck (1328 bytes)
Pertimbangan pada awalnya:
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:
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!
sumber
Python,
394349340 karakterJalankan seperti:
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.
U
dikonversi ke unary, menggunakanR
sebagai digit unary. Kami menghitungb/=2
sebagaib=b*5/10
.sumber
def A(a,b):\n r='';c=[]
->def A(a,b,r='',c=[]):
, sama untukdef M
. Anda mungkin dapat mengubahfor 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 sebelumnyaif
. Juga, bisaif list(b).pop()in'13579'
begituif b[:].pop()in'13579'
?b
adalah string, bukan daftar.M
dan menulis program lengkap;a,b=input()
Diperbolehkan.reduce
, yang memungkinkan Anda untukA(b,A(b,A(b,A(b,b))))
melakukannyareduce(A,[b,b,b,b,b])
. Sayangnya, ini tidak mempengaruhi jumlah karakter.JavaScript (E6) 375
395 411 449Sunting 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.
Kurang Golf (mungkin saya akan menambahkan penjelasan besok)
Uji di konsol FireFox / FireBug
Keluaran
sumber
9999999999
kasing seharusnya99999999980000000001
, bukan99999999980000000081
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 ..
Pendekatan ini cukup cepat sehingga bahkan pada laptop 2008 di ghpl REPL yang tidak dioptimalkan, test case hanya membutuhkan sepersekian detik:
Berikut ini cek bahwa semua produk dua digit sudah benar:
sumber
Bash + ImageMagick: 52
Mengharapkan input berada dalam variabel shell
a
danb
. Ini tidak terlalu pintar atau efisien, tetapi menyelesaikan pekerjaan. Mungkin sudah pernah dilakukan sebelumnya.Perhatikan bahwa
x
menunjukkan 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
sumber
9999999999
dan9999999999
.dd if=/dev/zero bs=$a count=$b 2>&-|wc -c
.9999999999x9999999999
gambar 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.$b
bukan${b}
.grep -vc g
alih-alihgrep -v g|wc -l
.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
9999999999x9999999999
dalam 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.
Contoh:
sumber
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
9999999999x9999999999
kasing di bawah 0,03s di mesin saya.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:
r
dans
merupakan fungsi pembukuan. (r
hanya alias untukreversed
, yang membuat iterator terbalik, dans
mengubah iterator menjadi string.)i
menambah angka dalam string dengan 1, termasuk kasus seperti39+1=40
dan99+1=100
.b
menambahx
dany
, tetapiy
harus hanya satu digit. Ini bekerja dengan menambahkanx
y
waktu.a
menambahkan dua angka bersamaan yang keduanya dapat memiliki beberapa digit, dengan memanggilb
setiap digity
.n
mengalikanx
dany
, tetapiy
harus hanya satu digit. Ini bekerja dengan menambah waktux
itu sendiriy
.o
mengalikanx
dany
, di mana kedua argumen dapat memiliki beberapa digit. Ini menggunakan perkalian panjang klasikm
hanya mengubah input stringnya menjadi iterator terbalik dan menyerahkannyao
, lalu membalikkan hasilnya dan mengubahnya menjadi string.sumber
def a(x,y):
->def a(x,y,z=''):
dan hapus baris berikutnya; trik serupa untuk fungsi-fungsi lain, dalamdef o(x,y):
, ubahx=s(x)
tox=s(x);l='';z=''
, di dalam itu untuk loop, juga hapus langkah + baru; alih-alih gunakan;
. Juga, saya pikirif h!='0':h+=s(x)\nelse:h+=i(x)
bisa sajah+=h!='0'and i(x)or s(x)
; bahkan mungkinh+=(h!='0'and i or s)(x)
; jika tidak, cukup ubah keif'0'!=h
. Juga hal-hal sepertidef r(x):return reversed(x)
->r=reversed
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.for
loop 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.JavaScript:
37103604 byteGolf:
Tidak disatukan dengan tes:
Output ini:
sumber
Haskell
507496Ini 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.Untuk referensi, S adalah tipe data seperti integer kustom,
p
adalah 'plus' (penambahan digit + digit),s
dikurangi (untuk reduksi),r
dikurangi (ekspansi ke dekomposisi digital),a
penambahan (penambahan nomor + penambahan),m
adalah multiply (digit * number multiplication),t
adalah times (number * number multiplication),i
adalah 'interpret' (convert string to list ofS
),b
adalah '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.
Hanya untuk ukuran yang baik:
Ayo menjadi gila!
konfirmasi
sumber
Python 2 -
1165, 712, 668664Perhatikan 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:
sumber
Scala, 470 karakter
(
⇒
adalah standar scala tetapi bisa diganti dengan=>
jika kita menghitung byte)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
flatMap
dan baris kita denganreduce
.u
menangani 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.sumber