Penjelasan
Befunge adalah program dua dimensi yang menggunakan tumpukan .
Itu berarti, untuk melakukan 5 + 6, Anda menulis 56+
, yang berarti:
56+
5 push 5 into stack
6 push 6 into stack
+ pop the first two items in the stack and add them up, and push the result into stack
(to those of you who do not know stacks, "push" just means add and "pop" just means take off)
Namun, kami tidak dapat menekan nomor tersebut 56
langsung ke tumpukan.
Untuk melakukannya, kita harus menulis 78*
sebaliknya, yang mengalikan 7
dan 8
dan mendorong produk ke dalam stack.
Detail
Untuk setiap angka dari 1
hinggan
, temukan string yang hanya terdiri dari karakter-karakter ini: 0123456789+-*/:
(Saya tidak akan menggunakan %
modulo.)
Tujuannya adalah untuk menemukan string terpendek yang dapat mewakili angka, menggunakan format yang dijelaskan di atas.
Misalnya, jika inputnya adalah 123
, maka outputnya adalah 67*9:*+
. Keluaran harus dievaluasi dari kiri ke kanan.
Jika ada lebih dari satu output yang dapat diterima (mis. 99*67*+
Juga dapat diterima), ada yang bisa dicetak (tidak ada bonus untuk mencetak semuanya).
Penjelasan lebih lanjut
Jika Anda masih tidak mengerti bagaimana cara 67*9:*+
mengevaluasi 123
, berikut adalah penjelasan terperinci.
stack |operation|explanation
67*9:*+
[6] 6 push 6 to stack
[6,7] 7 push 7 to stack
[42] * pop two from stack and multiply, then put result to stack
[42,9] 9 push 9 to stack
[42,9,9] : duplicate the top of stack
[42,81] * pop two from stack and multiply, then put result to stack
[123] + pop two from stack and add, then put result to stack
TL; DR
Program perlu menemukan string terpendek yang dapat mewakili input (angka), menggunakan format yang ditentukan di atas.
SKOR
- Kami sudah melakukannya dalam jumlah kode terpendek . Kali ini, ukuran tidak masalah.
- Bahasa pilihan Anda harus memiliki kompiler / juru bahasa gratis untuk sistem operasi saya (Windows 7 Enterprise).
- Bonus jika Anda memasukkan tautan ke kompiler / juru bahasa (saya terlalu malas).
- Jika memungkinkan, harap sertakan penghitung waktu untuk kenyamanan saya. Output dari timer valid.
- Skor akan menjadi yang terbesar
n
dalam 1 menit. - Itu berarti, program perlu mencetak representasi yang diperlukan dari
1
sekarang. - Tidak ada hard-coding, kecuali
0
untuk9
.
(selengkapnya) SPESIFIKASI
- Program tidak valid jika menghasilkan string yang lebih panjang dari yang dibutuhkan untuk nomor apa pun.
1/0=ERROR
5/2=2
,(-5)/2=-2
,(-5)/(-2)=2
,5/(-2)=-2
Disambiguasi
The -
adalah second-top minus top
, yang berarti bahwa 92-
pengembalian 7
.
Demikian pula, /
adalah second-top divide top
, yang berarti bahwa 92/
pengembalian 4
.
Program sampel
Lua
Gunakan pencarian kedalaman-pertama.
local function div(a,b)
if b == 0 then
return "error"
end
local result = a/b
if result > 0 then
return math.floor(result)
else
return math.ceil(result)
end
end
local function eval(expr)
local stack = {}
for i=1,#expr do
local c = expr:sub(i,i)
if c:match('[0-9]') then
table.insert(stack, tonumber(c))
elseif c == ':' then
local a = table.remove(stack)
if a then
table.insert(stack,a)
table.insert(stack,a)
else
return -1
end
else
local a = table.remove(stack)
local b = table.remove(stack)
if a and b then
if c == '+' then
table.insert(stack, a+b)
elseif c == '-' then
table.insert(stack, b-a)
elseif c == '*' then
table.insert(stack, a*b)
elseif c == '/' then
local test = div(b,a)
if test == "error" then
return -1
else
table.insert(stack, test)
end
end
else
return -1
end
end
end
return table.remove(stack) or -1
end
local samples, temp = {""}, {}
while true do
temp = {}
for i=1,#samples do
local s = samples[i]
if eval(s) ~= -1 or s == "" then for n in ("9876543210+-*/:"):gmatch(".") do
table.insert(temp, s..n)
end end
end
for i=1,#temp do
local test = eval(temp[i])
if input == test then
print(temp[i])
return
end
end
samples = temp
end
sumber
56
langsung ke stack, bagaimana kita bisa mendorong78
ke stack?56
lima puluh enam langsung ke tumpukan, tetapi kita bisa mendorong7
tujuh dan8
delapan secara terpisah ke tumpukan.56
di Befunge, Anda mendorong angka , sehingga Anda berakhir dengan setumpuk[5, 6]
. Untuk mendapatkan nomor 56, Anda harus mendorong7
, lalu8
ke tumpukan, dan kemudian mengalikannya untuk mendapatkan nomor 56 di tumpukan.:
membuat banyak hal lebih rumit, jadi saya akan merekomendasikan menyediakan daftar kasus uji yang baik, misalnya86387
Jawaban:
C ++, meledak semua memori pada komputer di dekat Anda
Menghasilkan string terpendek di mana perhitungan tidak menyebabkan limpahan bilangan bulat 32-bit yang ditandatangani (sehingga semua hasil antara berada dalam kisaran
[-2147483648, 2147483647]
Pada sistem saya ini menghasilkan solusi untuk semua nomor hingga dan termasuk
483432
dalam 30 detik saat menggunakan memori 1,8G. Bahkan angka yang lebih tinggi akan dengan cepat meledak penggunaan memori. Angka tertinggi yang dapat saya tangani pada sistem saya adalah5113906
. Perhitungannya memakan waktu hampir 9 menit dan 24GB. Ketika selesai secara internal memiliki solusi untuk398499338
nilai - nilai, sekitar 9% dari semua integer 32 bit (positif dan negatif)Membutuhkan kompiler C ++ 11. Di kompilasi linux dengan:
Tambahkan
-DINT64
sebagai opsi untuk menggunakan rentang bilangan bulat 64-bit alih-alih 32-bit untuk hasil antara (ini akan menggunakan sekitar 50% lebih banyak waktu dan memori). Ini membutuhkan tipe 128 bit bawaan. Anda mungkin perlu mengubah jenis gcc__int128
. Tidak ada hasil setidaknya[1..483432]
perubahan rentang dengan memungkinkan hasil antara yang lebih besar.Tambahkan
-DOVERFLOW
sebagai opsi untuk tidak menggunakan tipe integer yang lebih besar untuk memeriksa overflow. Ini memiliki efek memungkinkan pelimpahan dan pembungkus nilai.Jika sistem Anda memiliki tcmalloc ( https://github.com/gperftools/gperftools ), Anda dapat menautkannya dengan yang menghasilkan program yang umumnya sedikit lebih cepat dan menggunakan sedikit memori. Pada beberapa sistem UNIX Anda dapat menggunakan preload, misalnya
Penggunaan dasar: hasilkan dan cetak semua angka hingga target:
Pilihan:
-a
Juga cetak semua angka yang dihasilkan saat berolahraga target-c
Juga cetak semua angka yang dihasilkan mulai dengan "carry" (dup)-f
Temukan dan cetak angka pertama di luar target yang tidak dihasilkan-s
Hentikan jika target dihasilkan meskipun tidak semua angka sebelumnya dihasilkan-S
Suka-s
dan-f
dalam loop otomatis. Segera setelah target dihasilkan, temukan nomor pertama yang belum dihasilkan dan buat itu menjadi target baru-E
Jangan langsung keluar saat tujuan tercapai. Pertama, selesaikan semua string dari panjang saat ini-O
Jangan tampilkan string untuk semua angka hingga target. hanya string untuk target-o
Instruksi yang diizinkan (default ke+-*/:
-b num
Literal terendah yang dapat didorong (default ke0
)-B num
Literal tertinggi yang dapat didorong (default ke9
)-r num
Hasil antara terendah yang diizinkan. Digunakan untuk menghindari underflow. (standarnya adalahINT32_MIN
,-2147483648
-R num
Hasil antara tertinggi yang diizinkan. Digunakan untuk menghindari overflow. (standarnya adalahINT32_MAX
,2147483647
-m memory
(hanya linux) keluar ketika kira-kira banyak memori tambahan ini telah dialokasikanBeberapa kombinasi opsi yang menarik:
Hasilkan semua angka hingga target dan hitung angka terkecil yang membutuhkan generator lebih lama dari semua angka ini:
Hasilkan hanya target (-s), cetak hanya target (-O)
Temukan angka tertinggi yang dapat dihasilkan pada sistem Anda dengan batasan waktu dan / atau memori (Ini akan membuat sistem Anda kehabisan memori jika Anda membiarkannya berjalan. Kurangi 1 dari keluaran "cari" terakhir yang Anda lihat sebagai nilai aman terakhir ):
Hasilkan solusi tanpa pernah menggunakan hasil antara negatif (
30932
adalah nilai pertama yang membutuhkan hasil antara negatif untuk string terpendek):Hasilkan solusi tanpa mendorong
0
(sepertinya ini tidak mengarah ke solusi suboptimal):Hasilkan solusi termasuk
a..f (10..15)
:Hasilkan solusi tanpa menggunakan dup
:
(tambahkan-r0
karena nilai tengah negatif tidak pernah menarik untuk kasus ini)Menemukan nilai pertama yang tidak dapat dihasilkan untuk panjang string yang diberikan hanya menggunakan
+
,-
,*
dan/
:Ini sebenarnya akan menghasilkan beberapa istilah pertama https://oeis.org/A181898 , tetapi akan mulai menyimpang
14771
karena kami menggunakan divisi pemotongan sehingga angka dapat dilakukan dengan panjang 13 string, bukan panjang 15 sebagai seri OEIS mengharapkan:dari pada
Karena tanpa pembagian pemotongan tampaknya tidak ada gunanya, seri OEIS dapat dibuat dengan menggunakan
Dengan asumsi pembagian tetap tidak berguna, ini memberi saya 3 syarat tambahan sebelum saya keluar dari ingatan:
Versi lain dari program ini menyimpan bagian dari data dalam file eksternal menambahkan 135153107 dan 675854293 setelah semua bilangan bulat 32-bit telah dihasilkan.
befour.cpp
Beberapa test case:
1: 1: 1
11: 3: 29+
26: 5: 29*8+
27: 3: 39*
100: 5: 19+:*
2431: 9: 56*9*9*1+
3727: 9: 69*7+:*6+
86387: 11: 67*:*1-7*7*
265729: 11: 39*:*:*2/9+
265620: 13: 99*::*6/*7+3*
1921600: 9: 77*:*:*3/
21523360: 9: 99*:*:*2/
57168721: 11: 99*6+:*8-:*
30932: 11: 159*-:4*:*+
sumber
38950002
program Anda memberi89*7+:::**1-*
, yang cukup bagus, tetapi Anda dapat melakukannya299*-::*:*+
untuk lebih pendek. Saya pikir ini mengkonfirmasi keraguan yang saya miliki tentang angka negatif ...int main(int argc, char const* const* argv)
Saya tidak tahu C lebih baik dari rata-rata Joe tetapi apa ini? pointer const ke pointer const ke char? Bukankah seharusnyachar const *argv[]
begitu (atauchar const **argv
jika Anda memang se-hardcore itu)?JavaScript Node Brute Force
File program bfCodes.js
Berjalan di bawah Windows
cmd.exe
cmd.exe
menggunakan pintasan dan periksa bisikan DOS yang dimulai dengan direktori kerjaOptimasi
Algoritme menggilir semua kombinasi karakter befunge yang dimulai dengan string kode panjang 1. Anggap saja sebagai pemintalan odometer basis 15 dari digit paling tidak signifikan. Digit pesanan yang lebih tinggi mengklik dengan meningkatnya kelambatan.
bfCodes
tidak mengevaluasi kode yang dihasilkan yang akan membuat panjang tumpukan nol atau negatif atau meninggalkan lebih dari satu nomor di tumpukan dalam upaya untuk mengoptimalkan kecepatan eksekusi.Masalah Brute Force
Untuk kumpulan kode 15 karakter, waktu yang diperlukan untuk menjalankan semua kombinasi dengan panjang tertentu diberikan oleh
yang mengatakan bahwa jika program Anda berjalan lima belas kali lebih cepat daripada milikku, Anda hanya akan dapat memeriksa satu string kode karakter tambahan dalam waktu yang bersamaan. Untuk memeriksa dua karakter lagi dalam waktu yang bersamaan, sebuah program harus dijalankan 225 kali lebih cepat. Waktu yang diambil dengan pendekatan brute force meningkat secara eksponensial saat panjang string kode meningkat. Dan besarnya angka tidak selalu mengindikasikan jumlah byte befunge yang diperlukan untuk menghasilkannya.
Beberapa tokoh.
Perkiraan waktu untuk menghasilkan daftar kode pada notepad Windows 7 32 bit hingga bilangan bulat
Untuk menghasilkan befunge untuk 3727 (yang 66 kuadrat ditambah 6) dengan sendirinya membutuhkan waktu 1 jam 47 menit dan dihasilkan
578*+:*6+
Pembuatan kode yang optimal
Menghasilkan befunge untuk angka tanpa memeriksa panjang terpendek relatif sederhana. Menggunakan algoritma rekursif yang menggunakan akar kuadrat dan sisa bilangan bulat, pengkodean untuk nomor hingga 132 membutuhkan waktu sekitar 3 msec, bukan 28 detik. Mereka tidak optimal. Karena cara kerjanya, algoritma khusus ini diproduksi
638:*-:*+
untuk 3727 dalam waktu sekitar 1 msec (bukannya satu jam atau lebih) yang kebetulan menjadi optimal.Masalah dengan menyediakan metode non brute force membuktikan bahwa itu optimal dalam setiap kasus. Semoga berhasil!
sumber
+-*/
di node batin dan0-9
dan:
di daun (dan:
tidak bisa paling kiri). Jadi hasilkan dan evaluasi semua pohon ukuran 2 * n + 1 yang valid pada langkah n (n dimulai dari 0) dan konversikan menjadi string ketika dibutuhkanJavaScript
Apa yang bisa dilakukan dengan cuplikan JS? Di mesin saya, Firefox 64 bit, 416 dalam 60 detik
sumber