Latar Belakang
Dalam beberapa kemungkinan masa depan, dunia akan mengkonversi sistem numerik mereka dari desimal (basis 10 atau b10
) ke beberapa basis lain (biner b2
, oktal b8
, heksadesimal b16
, atau bahkan unary b1
, dalam hal ini kami mengacaukan!). Jadi, dalam persiapan untuk acara yang mengubah dunia ini, Anda memutuskan untuk membuktikan semua program Anda. Ini dapat dilakukan dengan hanya menggunakan 0
s dan s tunggal 1
dalam hubungannya dengan operator untuk mengganti konstanta angka yang ada.
Namun, hanya ada satu masalah: Anda memiliki banyak program untuk diubah, dan mengonversi setiap angka secara manual ke ekspresi akan membutuhkan waktu berminggu-minggu! Dengan demikian, Anda memutuskan untuk menulis sebuah program (atau fungsi) untuk memutuskan untuk Anda ekspresi apa yang harus diganti setiap angka.
Memasukkan
Input akan berupa bilangan bulat positif. Kode Anda harus mampu menangani bilangan bulat apa pun hingga 1000.
(Jika kode Anda mendukung desimal dan / atau input negatif, lihat Penilaian di bawah ini.)
Keluaran
Kode Anda harus menampilkan ekspresi yang mengevaluasi input dalam setidaknya satu bahasa. Ini mungkin bahasa apa pun; tidak harus sama dengan yang ditulis oleh program atau fungsi Anda. Juga, ungkapan ini tidak harus berupa program atau fungsi lengkap.
Untuk kejelasan, output mungkin mengandung operasi-operasi berikut:
- kenaikan / penurunan
- tambah / jumlah
- kurangi / negasikan
- kalikan / gandakan (hanya jika itu tidak secara langsung melibatkan nomor
2
!) - bagi / modulo
- eksponen / logaritma
- square / sqrt (sekali lagi, hanya jika ini tidak secara langsung melibatkan nomor
2
!) - operasi bitwise (bOR, bAND, bNOT, bXOR, bit-shift)
- pengaturan / mendapatkan variabel
- manipulasi tumpukan
Anda tidak boleh menggunakan eval()
atau fungsi serupa dalam output. Anda juga tidak dapat menggunakan dalam output fungsi apa pun yang melakukan tindakan selain yang disebutkan di atas.
Oh, dan satu hal lagi: karena kita ingin output menjadi valid dalam basis sebanyak mungkin, satu-satunya konstanta angka yang dikandungnya adalah 0
dan 1
. Angka seperti 10
(sepuluh) tidak diizinkan, kecuali bahasa menafsirkannya sebagai a 1
dan a 0
. Menggunakan string untuk memuat angka juga tidak diperbolehkan, seperti halnya menggunakan karakter seperti CJam's A
- K
(yang mewakili 10
- 20
).
Kasus uji
(Semua output dalam JavaScript, tetapi dapat bekerja dalam bahasa lain.)
Input 1:
2
Output yang mungkin 1:
1+1
Input 2:
13
Kemungkinan hasil 2:
(a=1+1+1)*a+a+1
Input 3:
60
Kemungkinan hasil 3:
(b=(a=1+1+1+1)*a)*a-a
Input 4:
777
Kemungkinan hasil 4:
(c=(b=((a=1+1+1+1)*a-a+1)*a)*a+b)+c+c-a+1
Input 5:
1000
Kemungkinan hasil 5:
Math.pow((a=1+1+1)*a+1,a)
Mencetak gol
Tujuan dari tantangan ini adalah untuk mempersingkat output kode Anda sebanyak mungkin. Skor Anda akan dihitung dengan cara ini:
Skor dasar: Penghitungan byte rata-rata dari semua output untuk bilangan bulat 1 hingga 1000.
Skor desimal: Jika kode Anda mendukung setidaknya 3 tempat desimal, ini adalah jumlah byte rata-rata dari semua output dari urutan angka mulai
0.001
dan berakhir pada1000
, meningkat1.001
setiap kali.0.001, 1.002, 2.003...998.999, 1000.000
Kemudian ambil potongan 50% dari skor ini.Nilai negatif: Jika kode Anda mendukung angka negatif dan nol, ini adalah rata-rata byte-output dari semua bilangan bulat dari
-1000
hingga0
. Kemudian ambil potongan 10% dari skor ini.
(Cara termudah untuk menghitung ini kemungkinan akan menjadi loop dengan program / fungsi Anda di dalamnya.)
Skor akhir Anda adalah rata-rata yang mana dari rumus di atas berlaku.
Jika output non-deterministik (yaitu agak acak; beberapa kali berjalan dengan input yang sama menghasilkan beberapa output unik), maka skor untuk setiap input ditentukan oleh output terbesar dari sepuluh berjalan pada CPU saya.
Juga, karena Anda tidak tahu betapa berharganya data komputer di masa depan, jumlah byte kode generator Anda harus kurang dari 512 byte.
Skor terendah dalam dua minggu (pada 30 September) akan dinyatakan sebagai pemenang. Selamat kepada pemenang Anda, @ThomasKwa !
Papan peringkat
Untuk memastikan jawaban Anda muncul dengan benar, silakan mulai dengan tajuk ini:
# Language name/Other language name, X points
Di mana X
skor jawaban Anda. Contoh:
# CJam/Pyth, 25.38 points
Jika Anda memiliki pertanyaan atau saran, beri tahu saya. Semoga berhasil!
sumber
0
atau1
secara default?Integer.parseInt("1000", 1+1+1+1+1+1+1+1+1+1)
? Saya cukup yakinparseInt
hanya menggunakan operasi yang diizinkan ;-)Jawaban:
Kode mesin Python / Zilog Z80,
11.65311.488Bonus: Angka negatif.
Mengasumsikan bahwa
hl
pasangan register awalnya memegang 0, dan mengembalikan hasilnya dalamhl
.Hanya tiga instruksi ini yang digunakan:
Kami menggunakan sedikit modifikasi dari representasi biner seimbang BBR2 berbobot minimum . Karena BBR2 meminimalkan bobot (jumlah digit bukan nol), tetapi kami ingin meminimalkan bobot plus jumlah pergeseran bit, kami mengubah konstanta dalam algoritma dari
3/2
menjadi5/3
.Untuk menghitung skor dan memverifikasi, gunakan kode ini:
Contoh output:
Atau dalam perakitan:
Lebih banyak contoh program:
Kemungkinan pengoptimalan: aturan OP bahwa instruksi
inc h
dandec h
, yang secara langsung mengubah byte atashl
, adalah ilegal, tetapisla h
dan tidak berdokumensl1 h
(bit kiri bergeser 1 padah
shift itu di0
dan1
masing - masing) diizinkan.sla h
dansl1 h
masing-masing dua byte, tetapi terkadang dapat mempersingkat output.sumber
+
menerjemahkannyadec
. Saya terus membaca contoh negatif yang salah.CJam / CJam,
143.26342.71328.89923.90121.90320.468Tidak ada bonus yang berlaku.
Cobalah online: contoh jalankan | skor kalkulator | verifikasi
Contoh berjalan
sumber
%
- masing dengan ekspresi yang lebih panjang. Tautan harus berfungsi sekarang.ß / BrainFuck, 34,201 poin
Sumber ß (194B):
Jika seseorang tertarik, saya akan menambahkan penjelasan. Output BF sudah cukup dioptimalkan, tapi saya kira saya bisa menggunakan 318B kode ß yang tersisa untuk diimplementasikan
penghapusan tabrakan operator.Sampel:
Berjalan di windows:
Berjalan di linux:
Validasikan dalam penerjemah BF online .
Skor:
= 37.495
.= 60.959 * 0.5 = ~30.48
.= 38.4765234765235 * 0.9 = ~34.629
= (37.495 + 30.48 + 34.629)/3 = 34.201
.sumber
Ruby / Ruby, 29.77885
31.873 * 0,9 (negatif) 30,872 (positif).
Strategi dasar adalah representasi basis 3 simetris ("terner seimbang"), yaitu ketika digit
-1,0,1
bukan0,1,2
Inilah output dari 0 hingga 40 sebelum pembersihan
Dan setelah pembersihan
sumber
Ceylon / Ceylon,
49,86 40,95poinVersi ketiga menggunakan Ceylon 1.2 untuk generator dan 509 byte kode:
import ceylon.language{S=String,I=Integer,e=expand}S q(I n)=>n==0then"0"else(n<0then"-"+p(-n,"-")else p(n,"+"));variable Map<[I,S],S>c=map{};S p(I n,S s){S v=c[[n,s]]else(n<8then s.join([1].repeat(n)))else(let(a="+-".replace(s,""))e(e{for(x in 2..8)let(l=(n^(1.0/x)).integer){for(r in l:2)if(r>1)let(w=r^x){if(w-n<n)"("+p(r,"+")+")^("+p(x,"+")+")"+(w<n then s+p(n-w,s)else(n<w then a+p(w-n,a)else""))}}}).reduce<S>((x,y)=>x.size<y.size then x else y))else"";c=[n,s]in c then c else map{[n,s]->v,*c};return v;}
Ini turun menjadi 35,22 poin, tapi saya tidak akan menempatkan ini di baris judul karena Celyon 1.2 hanya diterbitkan pada 29 Oktober. Saya tidak berpikir saya akan dapat mengimplementasikan algoritma ini dalam Ceylon 1.1 dalam ukuran ini.). Lebih detail di sana, di sini saya akan menjelaskan versi kedua. (Versi pertama dapat dilihat dalam sejarah - versi ini hanya mendukung angka positif, tetapi cocok dengan 256 byte.)
Versi kedua
Sekarang versi kedua, yang mendukung bilangan bulat negatif (dan 0), dan umumnya menghasilkan keluaran yang sedikit lebih pendek dengan menggunakan tambahan
-
. (Versi ini sebenarnya menggunakan panjang yang diizinkan, yang pertama mencoba untuk tetap di bawah 256 byte, bukan 512.)Kode memiliki panjang 487, jadi masih ada ruang untuk optimisasi lebih lanjut nanti. (Ada juga banyak cadangan dalam bentuk spasi putih dan nama variabel panjang.)
Skor:
Beberapa output sampel:
Seperti yang Anda lihat, yang negatif selalu satu byte (yang
-
lebih dulu) lebih lama dari yang positif.Ide dasarnya sama dengan program sebelumnya: temukan kotak di dekat nomor target kami, dan tampilkan akar dan sisanya secara rekursif. Tapi sekarang kami mengizinkan kuadrat kami juga beberapa lebih besar dari jumlah target, yang kemudian membuat sisanya negatif. (
+0.5
Dapat diubah ke konstanta yang berbeda untuk mengubah algoritma, tetapi tampaknya saya sudah mencapai yang optimal di sini - baik 0,4 dan 0,6 memberikan hasil yang lebih buruk.)Untuk membuat nilai negatif negatif (dan selain itu memiliki struktur yang sama dengan yang positif, kami meneruskan operator
sign
ke fungsi rekursif kamip
- baik itu"+"
atau"-"
. Kita dapat menggunakannya untuk joiner dalam kasus sepele (yaitu n <9) juga adapun sisanya jika positif, dan gunakan tanda sebaliknya untuk sisanya jika negatif.The
proof
menangani fungsi awal tanda (dengan kasus khusus untuk 0),p
fungsi melakukan pekerjaan yang sebenarnya, dengan rekursi.Versi ketiga, untuk Ceylon 1.2
Versi golf (yaitu komentar dan spasi kosong dihapus) diposting di bagian atas, tepatnya 509 byte kode.
Ini menggunakan prinsip dasar yang sama dengan versi kedua, tetapi alih-alih hanya kuadrat, ia juga mencoba menggunakan kekuatan angka yang lebih tinggi (mencoba eksponen dari 2 hingga 8), dan menggunakan hasil terpendek. Itu juga cache hasil, karena kalau tidak, ini akan sangat lambat untuk nomor yang lebih besar dengan banyak panggilan rekursif.
Mencetak:
Konstruksi lekukan besar di tengah adalah tiga pemahaman yang tersusun berulang, dua batin di dalam ekspresi let. Ini kemudian diuji menggunakan fungsi memperluas dua kali, dan
reduce
fungsi menemukan yang terpendek dari string itu.Saya telah mengajukan permintaan fitur untuk dapat melakukan ini dalam satu pemahaman.
Di dalam pemahaman, kita sedang membangun string dari root
r
, eksponenx
dan sisanya (n-w
atauw-n
).The
let
ekspresi danmap
fungsi baru di Ceylon 1.2.map
bisa digantikan olehHashMap
(yang akan membutuhkan lebih banyak karakter untuk impor, meskipun mungkin akan lebih cepat, karena saya tidak akan membuat peta baru untuk setiap entri baru). Thelet
ekspresi sepertilet (w = r ^ x)
harus diganti dengan menggunakanif
klausa sepertiif(exists w = true then r ^ x)
(dan kemudian aku tidak akan diperlukan duaexpand
panggilan baik), tapi ini masih akan sedikit lebih lama, tidak pas dalam 511 byte diperbolehkan.Di sini sampel keluaran sesuai dengan yang dipilih di atas, semuanya kecuali jumlah yang sangat kecil lebih pendek:
Sebagai contoh, sekarang kita memiliki 1000 = (3 ^ 2 + 1) ^ 3, bukan 1000 = (6 ^ 2-4) ^ 2-5 ^ 2 + 1.
sumber
less than 512
. Sou, Anda bisa menggunakan maks. dari 511 bytes;)Ruby / dc,
20.29618.41416.968Pemrograman dinamis! Menentukan daftar fungsi yang, diberikan instruksi dc, mengembalikan ekspresi baru dan nilai numerik ekspresi itu. Kemudian, dimulai dengan
1
prefined, ia membangun daftar semua nilai yang dapat dijangkau hingga dan termasuk nilai yang diinginkan.edit:
Menambahkan fungsi untuk n-1 dan membuatnya menjalankan algoritma melalui beberapa lintasan. Tampaknya perlu 7 operan untuk menstabilkan. Harus mempersingkat beberapa nama variabel agar tetap dalam 512 byte.
edit 2:
Menambahkan fungsi untuk n (n-1) , n (n + 1) dan n ^ 3 saat saya masih di sana. Memperpendek kode lagi, mendarat tepat 512 byte.
Angka yang dihasilkan:
Keluaran seluruhnya terdiri dari lima karakter yang berbeda:
1
mendorong nilai 1 pada tumpukan;d
menggandakan bagian atas tumpukan;+
,,-
dan*
muncul dua nilai teratas dan mendorong jumlah, perbedaan, dan produknya masing-masing. Setiap ekspresi yang dihasilkan menambahkan hanya satu nilai ke stack setelah eksekusi....
sumber
-
operator sambil tetap dalam hitungan byte?Python 2.6,
78.069- 66.265 poinMenyerahkan jawaban saya untuk apa nilainya (tidak banyak dalam kasus ini ... tapi jelas menunjukkan bahwa untuk tantangan ini tidak cukup hanya dengan memikirkan menyusun output sebagai jumlah nilai bit-shifted; ketika diperhitungkan bahwa tidak ada digit di luar 0 atau 1 dapat muncul di output). Saya mungkin akan kembali lagi nanti dengan cara yang berbeda untuk menghasilkan output.
Kode itu sendiri tidak terlalu panjang (176 karakter):
Ini menghasilkan output yang benar tetapi verbose:
Cuplikan yang menghitung skor:
sumber