Saya baru mengenal olahraga kode golf. Saya mencoba untuk menghasilkan tangga integer menggunakan paling sedikit karakter unik di C ++.
Katakanlah kita diberi bilangan bulat 4.
Kami akan menghasilkan tangga berikut:
1
1 2
1 2 3
1 2 3 4
Singkatnya, program saya akan membaca bilangan bulat positif dari stdin dan mencetak tangga ini ke output. Saya mencoba melakukannya dengan jumlah karakter unik yang paling sedikit .
Program saya adalah sebagai berikut:
#include<iostream>
int i;
int ii;
int iii;
int iiii;
main() {
std::cin >> i;
for(ii++; ii <= i; ii++) {
int iii = iiii;
for(iii++; iii <= ii; iii++) {
std::cout << iii << " ";
}
std::cout << std::endl;
}
}
Inilah pemeriksa yang saya gunakan untuk memeriksa jumlah karakter unik dalam program saya:
#include <cstdio>
#include <cstring>
using namespace std;
int check[300],diffcnt=0,cnt=0,t;
char c;
double score;
int main(){
memset(check,0,sizeof(check));
FILE *in=fopen("ans.cpp","r");
while(fscanf(in,"%c",&c)!=EOF){
cnt++;
if(!check[c]){
check[c]=1;
if(c=='\r'||c=='\n') continue;
diffcnt++;
}
}
if(diffcnt<25) printf("100\n");
else if(diffcnt<30){
printf("%.3lf\n",20.0*100.0/cnt+20.0*(29-diffcnt));
}
else{
score=20.0;
for(int x=95;x<cnt;x++) score*=0.9;
printf("%.3lf\n",score);
}
printf("Unique Characters: %d\n", diffcnt);
printf("Total Characters: %d\n", cnt);
return 0;
}
Lebih disukai saya ingin menggunakan kurang dari 25 karakter unik untuk menyelesaikan program ini (tidak termasuk karakter baris baru tetapi termasuk spasi). Saat ini, program saya menggunakan 27. Saya tidak yakin bagaimana cara mengoptimalkannya lebih lanjut.
Bisakah seseorang tolong beri tahu saya tentang cara mengoptimalkannya lebih lanjut (dalam hal jumlah karakter unik yang digunakan)? Harap dicatat bahwa hanya C ++ yang dapat digunakan.
sumber
Jawaban:
Saya yakin saya berhasil menghapus karakter = dari kode Anda, meskipun sekarang secara signifikan lebih lambat
Ini tidak cantik, tetapi dengan menyalahgunakan bilangan bulat integer kita dapat kembali ke 0 tanpa menggunakan =
Kami juga harus mengubah penjaga sedikit. Sayangnya karena menyertakan saya tidak bisa menghilangkan semua karakter baris baru (meskipun dekat) sehingga mungkin menjadi jalan berikutnya untuk diselidiki.
Sunting: Kehabisan waktu untuk saat ini, tetapi jika Anda memasukkan dan menggunakan strstream dan berbagai pustaka lainnya, saya pikir Anda mungkin dapat menghapus "karakter juga, sekali lagi menggunakan bilangan bulat untuk sampai pada karakter yang benar untuk ruang dan meneruskannya ke strstream
sumber
#include<std>
dan menghilangkan semua:
itu. Bukan praktik pengkodean yang bagus, tapi itu intinya.using namespace std;
yang akan menggunakan p tambahan untuk: sehingga bersih 0g
, jadi rugi bersih saya kira. Jika ini kode emas, kita bisa mengurangi jumlah byte dengan mengganti namaii
,,iii
daniiii
untuk nama huruf tunggal lainnya (pilih huruf lain yang sudah digunakan), tapi bukan itu yang dimaksud dengan tantangan ini, jadi saya rasa tidak. Saya bertanya-tanya apakah akan ada keuntungan menggunakangetc
danputc
bukannyacin
/cout
, harus mencobanya.signed char
. Jika Anda mengompilasi dengan optimisasi diaktifkan, kode ini mungkin pecah dengan kompiler modern, kecuali jika Anda menggunakangcc -fwrapv
untuk membuat overflow yang ditandatangani didefinisikan dengan baik sebagai bungkus komplemen 2's. dentang juga mendukung-fwrapv
. (unsigned
tipe integer termasukunsigned char
memiliki perilaku yang jelas (membungkus) dalam ISO C ++). Hal ini tergantung pada ABI apakahchar
inisigned char
atauunsigned char
, sehinggachar
bisa ok.Saya akhirnya mendapatkan 24 karakter unik dengan menggabungkan jawaban @ExpiredData dan @someone. Juga, menggunakan tipe data pendek sebagai ganti int membantu mempercepat program saya karena butuh waktu yang lebih singkat untuk melimpahi tipe data pendek.
Kode saya adalah sebagai berikut.
sumber
char iiiii;
, inisialisasi variabel terakhir.23 karakter unik menggunakan Digraphs. (25 tanpa). Tidak ada UB
Gunakan sintaksis penyangga penguat C ++ 11 untuk membuat daftar-inisialisasi integer ke nol dengan
int var{};
menghindari=
dan0
. (Atau dalam kasus Anda, menghindari globaliiii
). Ini memberi Anda sumber nol selain variabel global (yang diinisialisasi secara statis ke nol, tidak seperti penduduk lokal).Kompiler saat ini menerima sintaks ini secara default, tanpa harus mengaktifkan opsi khusus apa pun.
(Trik sampul integer menyenangkan, dan ok untuk bermain golf dengan optimasi dinonaktifkan, tetapi limpahan yang ditandatangani adalah perilaku tidak terdefinisi dalam ISO C ++. Mengaktifkan optimasi akan mengubah loop sampul menjadi loop tak terbatas, kecuali jika Anda mengkompilasi dengan gcc / dentang
-fwrapv
untuk memberikan limpahan bilangan bulat yang ditandatangani dengan baik -definisi perilaku: sampul komplemen 2's.Fakta menyenangkan: ISO C ++
std::atomic<int>
memiliki bungkus komplemen 2 yang terdefinisi dengan baik!int32_t
diperlukan sebagai komplemen 2's jika didefinisikan sama sekali, tetapi perilaku overflow tidak terdefinisi sehingga masih dapat menjadi typedef untukint
ataulong
pada mesin mana pun di mana salah satu tipe tersebut adalah 32 bit, tanpa padding, dan komplemen 2's.)Tidak berguna untuk kasus khusus ini:
Anda juga dapat menginisialisasi variabel baru sebagai salinan dari yang sudah ada, dengan kurung kurawal atau (dengan inisialisasi non-kosong), parens untuk inisialisasi langsung .
int a(b)
atauint a{b}
setara denganint a = b;
Tetapi
int b();
mendeklarasikan fungsi alih-alih variabel diinisialisasi ke nol.Juga, Anda bisa mendapatkan nol dengan
int()
atauchar()
, yaitu nol-inisialisasi objek anonim.Kami dapat mengganti
<=
perbandingan Anda dengan<
membandingkan dengan transformasi logika sederhana : lakukan kenaikan loop-counter tepat setelah membandingkan, bukan di bagian bawah loop. IMO ini lebih sederhana daripada alternatif yang diusulkan orang, seperti menggunakan++
di bagian pertama darifor()
untuk membuat 0 menjadi 1.Kita bisa bermain golf hingga
for(int r{}; r++ < n;)
tetapi IMO yang kurang mudah bagi manusia untuk membaca. Kami tidak mengoptimalkan jumlah byte total.Jika kami sudah menggunakan
h
, kami bisa menghemat'
atau"
untuk ruang.Dengan asumsi lingkungan ASCII atau UTF-8, ruang adalah
char
dengan nilai 32. Kita dapat membuat itu dalam variabel dengan cukup mudah, lalucout << c;
Dan nilai-nilai lain jelas dapat dibuat dari urutan
++
dan penggandaan, berdasarkan bit dari representasi biner mereka. Secara efektif menggeser 0 (tidak ada) atau 1 (++) ke dalam LSB sebelum menggandakannya menjadi variabel baru.Versi ini menggunakan
h
alih-alih'
atau"
.Ini jauh lebih cepat daripada versi yang ada (tidak bergantung pada loop panjang), dan bebas dari Perilaku Tidak Terdefinisi . Itu mengkompilasi tanpa peringatan dengan
g++ -O3 -Wall -Wextra -Wpedantic
dan denganclang++
.-std=c++11
adalah opsional. Ini legal dan portabel ISO C ++ 11 :)Itu juga tidak bergantung pada variabel global. Dan saya membuatnya lebih bisa dibaca manusia dengan nama variabel yang memiliki arti.
Hitungan byte unik: 25 , tidak termasuk komentar yang saya abaikan
g++ -E
. Dan tidak termasuk ruang dan baris baru seperti penghitung Anda. Saya menggunakansed 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -ic
dari askubuntu ini untuk menghitung kemunculan setiap karakter, dan memasukkannyawc
ke dalam untuk menghitung berapa banyak karakter unik yang saya miliki.Hanya 2
f
karakter yang berasalfor
. Kita bisa menggunakanwhile
loop sebagai gantinya jika ada gunanyaw
.Kita mungkin dapat menulis ulang loop ke gaya bahasa assembly
i < r || goto some_label;
untuk menulis lompatan bersyarat di bagian bawah loop, atau apa pun. (Tetapi menggunakanor
bukannya||
). Tidak, itu tidak berhasil.goto
adalah pernyataan sukaif
dan tidak bisa menjadi sub-komponen dari ekspresi seperti itu di Perl. Kalau tidak, kita bisa menggunakannya untuk menghapus(
dan)
karakter.Kami bisa perdagangan
f
untukg
denganif(stuff) goto label;
bukanfor
, dan kedua loop selalu berjalan minimal 1 iterasi sehingga kita hanya akan membutuhkan satu loop-cabang di bagian bawah, seperti asm yang normaldo{}while
struktur lingkaran. Dengan asumsi pengguna memasukkan bilangan bulat> 0 ...Digraphs dan Trigraphs
Untungnya, trigraph telah dihapus pada ISO C ++ 17 jadi kami tidak harus menggunakan
??>
alih-alih}
jika kami bermain golf khusus untuk revisi C ++ terbaru.Tetapi hanya trigraph yang spesifik: ISO C ++ 17 masih memiliki digraf seperti
:>
untuk]
dan%>
untuk}
. Jadi dengan biaya penggunaan%
, kita dapat menghindari keduanya{
dan}
, dan menggunakannya%:
untuk#
penghematan bersih 2 karakter unik lebih sedikit.Dan C ++ memiliki kata kunci operator seperti
not
untuk!
operator, ataubitor
untuk|
operator. Denganxor_eq
untuk^=
, Anda dapat nol variabeli xor_eq i
, tetapi memiliki beberapa karakter yang tidak Anda gunakan.Saat ini
g++
sudah mengabaikan trigraph secara default bahkan tanpa-std=gnu++17
; Anda harus menggunakan-trigraphs
untuk mengaktifkannya,-std=c++11
atau sesuatu untuk kesesuaian ketat dengan standar ISO yang menyertakannya.23 byte unik:
Cobalah online!
Versi terakhir menggunakan
'
kutipan tunggal, bukanh
atau"
untuk pemisah ruang. Saya tidak ingin membuat digrafchar c{}
barang jadi saya menghapusnya. Mencetak char lebih efisien daripada mencetak string, jadi saya menggunakannya.Histogram:
Pemisah ruang (masih belum terpecahkan)
Dalam jawaban yang sekarang dihapus, Johan Du Toit mengusulkan menggunakan pemisah alternatif, khususnya
std::ends
. Itu karakter NULchar(0)
,, dan mencetak sebagai lebar nol pada sebagian besar terminal. Jadi hasilnya akan seperti1234
, bukan1 2 3 4
. Atau lebih buruk, dipisahkan oleh sampah pada apa pun yang tidak runtuh diam-diam'\0'
.Jika Anda dapat menggunakan pemisah arbitrer, saat digit
0
mudah dibuatcout << some_zeroed_var
. Tapi tidak ada yang mau10203040
, itu bahkan lebih buruk daripada tidak ada pemisah.Saya mencoba memikirkan cara untuk membuat
std::string
holding" "
tanpa menggunakanchar
atau string literal. Mungkin menambahkan sesuatu padanya? Mungkin dengan digraf untuk[]
mengatur byte pertama ke nilai32
, setelah membuat satu dengan panjang 1 melalui salah satu konstruktor?Johan juga menyarankan fungsi
std::ios
fill () anggota yang mengembalikan karakter isian saat ini. Default untuk streaming ditetapkan olehstd::basic_ios::init()
, dan' '
.std::cout << i << std::cout.fill();
menggantikan<< ' ';
tetapi menggunakan.
bukan'
.Dengan
-
, kita dapat mengambil pointer kecout
dan penggunaan->fill()
untuk memanggil fungsi anggota:std::cout << (bitand std::cout)->fill()
. Atau tidak, kami tidak menggunakanb
baik jadi kami mungkin juga telah digunakan&
sebagai pengganti setara leksikal nya,bitand
.Memanggil fungsi anggota tanpa
.
atau->
Letakkan di dalam kelas, dan tentukan
operator char() { fill(); }
Lalu
ss s{}
sebelum loop, danstd::cout << i << s;
di dalam loop. Hebat, itu mengkompilasi dan bekerja dengan baik, tetapi kami harus menggunakanp
danh
untukoperator char()
, kerugian bersih 1. Setidaknya kami menghindarib
membuat fungsi anggotapublic
dengan menggunakanstruct
alih-alihclass
. (Dan kita bisa mengganti warisan denganprotected
kalau-kalau ada yang membantu).sumber
cout.fill()
daristd::ios
, tapi kami sebelumnya tidak menggunakan..
Mungkin kita bisa memanggilnya dengan mengambil pointer dan menggunakan->fill()
fungsi anggota? Apakah ada yang mengembalikan pointer kecout
atau aliran lain?<< (bitand std::cout)->fill()
kompilasi, tetapi gunakan-
. (Terlepas dari nama token,bitand
hanya setara dengan leksikal&
, tidak secara khusus bitwise-dan operator. Ia juga berfungsi sebagai alamat-operator.) Hmm, apakah ada beberapa templat atau hal-hal lambda yang bisa mendapatkan pointer ke fungsi anggota yang kita dapat()
tanpa menggunakan.
atau->
?std::ios::left
didefinisikan sebagai 32, dalam gcc, tetapi saya tidak dapat menemukan cara untuk memanfaatkannya. Saya pikir saya akan membiarkan yang satu ini pergi dan menyelesaikan beberapa pekerjaan aktual :-)int
32 bukan masalah, jawaban saya sudah menunjukkan bagaimana melakukannya dengan++
mulai dariint c{};
nol. Tapi ya, saya tidak akan pergi ke lubang kelinci melihat ke lambda, template, ataustd::function
. Ataustd::string
idenya. Tapi kami tidak menggunakannyag
untuk kami tidak bisa benar-benar mendeklarasikanstd::string
tanpa kehilangan; ide saya untuk menggunakangoto
bukannyafor
tidak berjalan dengan baik.decltype(something)
bisa memberi kitachar
tipe, tetapi biaya kita ay
.struct ss : std::ostream { operator auto () { return fill(); } };
tetapi tidak banyak membantu.C ++ (gcc) x86_64 Khusus Linux,
9295 8900 8712 68125590 byte, 18 karakter unikCobalah online!
Ini didasarkan pada ide-ide dari jawaban PPCG ini . Program bahasa mesin dinyatakan sebagai array int 32 bit, yang masing-masing diwakili sebagai jumlah
1+11+111...
. Ternyata bahwa mungkin lebih efisien untuk encodex
sebagaiy
sehinggay%(1<<32)==x
. Program bahasa mesin yang disandikan adalah sebagai berikut... yang didasarkan pada kode C berikut.
Sunting: Sekarang menerima input dari
stdin
alih-alihargv[1]
. Terima kasih hanya untuk @ ASCII dan @PeterCordes untuk saran mereka!Sunting4: Pengkodean
sedikitditingkatkan secara signifikan.sumber
-w
Tandai pls: P (juga Anda dapat mengubah namaii
menjadia
)gcc -zexecstack
ini, kan? Karenaint m[]
tidakconst
. (Dan toolchains baru-baru ini dimasukkan ke.rodata
dalam halaman yang tidak dapat dieksekusi sehingga bahkanconst int m[]
tidak berfungsi misalnya sistem Linux Arch sayagcc
8.2.1 20181127 danld
(GNU Binutils) 2.31.1.) Bagaimanapun, Anda lupa menyebutkan itu dalam jawaban Anda, tapi itu ada di tautan TIO Anda.1
denganpush %rax
/pop %rdi
bukannya push-langsung lainnya. Atau lebih sederhana, untuk nilai yang tidak 64-bit, yaitu non-pointer, 2-bytemov %eax, %edi
. Selain itu, Linuxsyscall
tidak merusak register inputnya, hanyarax
dengan nilai pengembalian dan RCX + R11 dengan RIP dan RFLAGS yang disimpan sebagai bagian dari cara kerjasyscall
instruksi. Jadi Anda dapat pergirdi
danrdx
mengatur1
panggilan lintas, dan menggunakan regs berbeda. Juga, RBX dipelihara dengan panggilan, jadi itu tidak benar-benar menyimpan ke RBX utama. Ini terjadi karena kode mulai CRT tidak peduli.21 karakter unik + 1 baris baru yang tidak dapat dilepas
Spasi putih tidak diperlukan kecuali untuk baris baru pertama. Dikompilasi dalam g ++ 7.3.0.
Karakter yang digunakan:
%:include<ostram>()f-
.Perbaikan untuk jawaban lain:
for
loop keif
dan rekursi.std::addressof(std::cout)->fill()
, aliasstd::cout.fill()
.sumber
2120 karakter unik tidak termasuk spasi putihSemua spasi putih dapat diubah menjadi baris baru.
Keluar dengan segfault. Karakter yang digunakan:
%:include<ostram>;-h
.Ia bekerja di versi kompiler khusus ini di Linux 64 bit:
Dengan parameter:
Meski begitu, saya tidak yakin itu akan selalu berhasil. Itu mungkin juga tergantung pada banyak hal lainnya.
cia
danciu
apakah offset memori dibagi 4 antaraia
iu
dani
. (int
versi 32 bit dalam versi ini.) Anda mungkin harus mengubah angka agar cocok dengan offset aktual. Alamat akan jauh lebih mudah diprediksi jika mereka semua terkandung dalam sebuah struct. Sayangnya non-statisauto
tidak diizinkan dalam sebuah struct.e
adalah array 0-elemen dari tipe elemen dengan ukuran (2 32 -1) × 2 32 byte. Jika tipe pointer yang sesuaie
dikurangi, setengah dari pointer yang lebih tinggi akan dikurangi oleh (2 32) -1), yang setara dengan penambahan satu. Ini dapat mengatur ulang penghitung yang dikurangi tanpa menggunakan tanda kesetaraan.Versi yang lebih masuk akal yang harus bekerja lebih andal, tetapi menggunakan satu karakter lagi
=
:Bahkan ini tidak berfungsi di versi terbaru g ++ karena sepertinya tidak mengizinkan mendefinisikan
main
dalam tipe arbitrer lagi.Kedua program ini tidak menggunakan tanda kurung. Tapi titik koma sepertinya tidak bisa dihindari.
sumber
22 karakter unik tidak termasuk spasi putih. Memisahkan angka dengan karakter NUL yang ditampilkan dengan benar di Windows.
Cobalah online
Histogram:
sumber
char(0)
), bukan spasi (char(32)
dalam ASCII / UTF-8). en.cppreference.com/w/cpp/io/manip/ends . Saya mencobanya di desktop Linux saya hanya untuk memastikan, dan hasilnya terlihat seperti1234
tidak1 2 3 4
. Ini terlihat sama pada output TIO Anda!"
untuk" "
jika mereka bisa menggunakaniiii
untuk memisahkan dengan'0'
untuk10203040
? Saya kira Anda dapat membuat kasus bahwa ada pemisah yang masih dalam output biner dari program, tetapi menunjukkan perubahan ini dan menjelaskannya dalam bahasa Inggris adalah penting untuk jawaban Anda, karena ini bukan pengganti drop-in! Saya akan senang menghapus downvote saya jika Anda memperluas jawaban Anda untuk menjelaskan dan menjustifikasi itu.