Hasilkan tangga bilangan bulat menggunakan jumlah karakter unik paling sedikit (dalam C ++)

13

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.

LanceHAOH
sumber
5
Tentunya baru meminta tips mengenai kriteria penilaian selain golf kode , tetapi menegaskan, ini sesuai topik, karena halaman tips mengatakan untuk membuatnya menjadi jawaban yang lebih baik untuk tantangan pemrograman yang on-topic .
Adem
8
@LuisMendo Saya tidak benar-benar berpikir itu benar dalam kasus ini, karena banyak bahasa benar-benar meremehkan skema penilaian ini. Jika pengguna ini ingin membantu belajar "golf unik" itu hanya benar-benar masuk akal dalam beberapa bahasa, jadi saya pikir ini jauh lebih baik sebagai tip daripada sebagai tantangan umum. Itu mengatakan masalah dasar mungkin bisa menjadi tantangan jika seseorang ingin mempostingnya.
FryAmTheEggman
3
Saya pikir Anda dapat menggunakan digraf <% dan%> daripada kurung kurawal, dan saya pikir saya melewatkan beberapa.
kata ganti saya adalah monicareinstate
2
Saya pasti melewatkan beberapa. # adalah% :, sehingga Anda dapat menghilangkan tiga karakter dan memperkenalkan satu ({=> <%,} =>%>, # =>% :) dan mencapai 25. Jika Anda menggabungkan ini dengan jawaban di bawah ini, saya pikir Anda bisa mendapatkan 24.
kata ganti saya adalah monicareinstate
2
@LanceHAOH Trigraph sangat umum dalam pertanyaan [licik], dan digraf muncul juga saat membaca tentang trigraph.
kata ganti saya adalah monicareinstate

Jawaban:

12

Saya yakin saya berhasil menghapus karakter = dari kode Anda, meskipun sekarang secara signifikan lebih lambat

#include<iostream>

int i;
int ii;
int iii;
int iiii;

int main() {
    std::cin >> i;
    i++;
    for(ii++; ii < i;) {
    for(;iii>iiii;iii++);
    for(;iii<iiii;iii++);
    ii++;
        for(iii++; iii < ii; iii++) {
            std::cout << iii << " ";
        }
        std::cout << std::endl;
    }
}

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

Data Kedaluwarsa
sumber
2
Anda bisa #include<std>dan menghilangkan semua :itu. Bukan praktik pengkodean yang bagus, tapi itu intinya.
Darrel Hoffman
3
@ DarrelHoffman Saya tidak bisa mendapatkan itu untuk bekerja, tidak harus Anda lakukan using namespace std;yang akan menggunakan p tambahan untuk: sehingga bersih 0
Data Expired
Hmm. Mungkin, C ++ saya sedikit berkarat. Juga itu menambahkan g, jadi rugi bersih saya kira. Jika ini kode emas, kita bisa mengurangi jumlah byte dengan mengganti nama ii,, iiidan iiiiuntuk 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 menggunakan getcdan putcbukannya cin/ cout, harus mencobanya.
Darrel Hoffman
1
Salahku. Saya baru saja membaca checker lagi. Tampaknya karakter baris baru diabaikan. Jadi sebenarnya tidak perlu repot untuk menghapus baris baru. Tetapi dikombinasikan dengan strategi Anda dan solusinya oleh @someone dalam komentar, saya berhasil membuatnya menjadi 24 karakter. Saya membuat program lebih cepat dengan menggunakan short, bukan int. Jadi saya mendapat karakter 'h' tambahan. Tapi ini izinkan saya menggunakan tipe data char tanpa biaya tambahan. Jadi saya menyingkirkan "karakter juga dengan menggunakan kode karakter.
LanceHAOH
@ LanceHAOH: perhatikan bahwa integer yang ditandatangani berlebih adalah perilaku tidak terdefinisi dalam C ++, untuk semua tipe yang ditandatangani termasuk signed char. Jika Anda mengompilasi dengan optimisasi diaktifkan, kode ini mungkin pecah dengan kompiler modern, kecuali jika Anda menggunakan gcc -fwrapvuntuk membuat overflow yang ditandatangani didefinisikan dengan baik sebagai bungkus komplemen 2's. dentang juga mendukung -fwrapv. ( unsignedtipe integer termasuk unsigned charmemiliki perilaku yang jelas (membungkus) dalam ISO C ++). Hal ini tergantung pada ABI apakah charini signed charatau unsigned char, sehingga charbisa ok.
Peter Cordes
10

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.

%:include<iostream>

short i;
short ii;
short iii;
short iiii;
char iiiii;

main() <%
    std::cin >> i;
    iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;
    iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;
    iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;
    iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;iiiii++;
    i++;
    for(ii++; ii < i; ii++) <%
        for(;iii;iii++);
        for(iii++; iii < ii; iii++)
            std::cout << iii << iiiii;
        std::cout << iii << std::endl;
    %>
%>
LanceHAOH
sumber
@KevinCruijssen ia menggunakannya dalam char iiiii;, inisialisasi variabel terakhir.
Rɪᴋᴇʀ
1
@KevinCruijssen Itu benar. Tapi itu memungkinkan saya untuk menghapus "karakter karena saya dapat menggunakan kode karakter untuk mewakili karakter spasi. Jadi perbedaan bersih dalam karakter unik yang digunakan = 0.
LanceHAOH
9

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 =dan 0. (Atau dalam kasus Anda, menghindari global iiii). 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 -fwrapvuntuk 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_tdiperlukan sebagai komplemen 2's jika didefinisikan sama sekali, tetapi perilaku overflow tidak terdefinisi sehingga masih dapat menjadi typedef untuk intatau longpada 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)atau int a{b}setara denganint a = b;

Tetapi int b();mendeklarasikan fungsi alih-alih variabel diinisialisasi ke nol.

Juga, Anda bisa mendapatkan nol dengan int()atau char(), 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 dari for()untuk membuat 0 menjadi 1.

    // comments aren't intended as part of the final golfed version
    int n;
    std::cin >> n;      // end condition

    for(int r{}; r < n;) {      // r = rows from 0 .. n-1
        ++r;
        for(int i{}; i < r;) {
            ++i;
            std::cout << i << ' ';
        }
        std::cout << std::endl;
    }

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 chardengan nilai 32. Kita dapat membuat itu dalam variabel dengan cukup mudah, lalucout << c;

    char c{};
    c++; c++;            // c=2
    char cc(c+c+c+c);    // cc=8
    char s(cc+cc+cc+cc); // s=32 = ' ' = space in ASCII/UTF-8

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 halih-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 -Wpedanticdan denganclang++ . -std=c++11adalah 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 abaikang++ -E . Dan tidak termasuk ruang dan baris baru seperti penghitung Anda. Saya menggunakan sed 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -ic dari askubuntu ini untuk menghitung kemunculan setiap karakter, dan memasukkannya wcke dalam untuk menghitung berapa banyak karakter unik yang saya miliki.

#include<iostream>

int main() {
    char c{};
    c++; c++;            // c=2
    char cc(c+c+c+c);    // cc=8
    char s(cc+cc+cc+cc); // s=32 = ' ' = space in ASCII/UTF-8

    int n;
    std::cin >> n;      // end condition

    for(int r{}; r < n;) {      // r = rows counting from 0
        ++r;
        for(int i{}; i < r;) {
            ++i;
            std::cout << i << s;
        }
        std::cout << std::endl;
    }
}

Hanya 2 fkarakter yang berasal for. Kita bisa menggunakan whileloop sebagai gantinya jika ada gunanya w.

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 menggunakan orbukannya ||). Tidak, itu tidak berhasil. gotoadalah pernyataan suka ifdan tidak bisa menjadi sub-komponen dari ekspresi seperti itu di Perl. Kalau tidak, kita bisa menggunakannya untuk menghapus (dan )karakter.

Kami bisa perdagangan funtuk gdengan if(stuff) goto label;bukan for, dan kedua loop selalu berjalan minimal 1 iterasi sehingga kita hanya akan membutuhkan satu loop-cabang di bagian bawah, seperti asm yang normal do{}whilestruktur 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 notuntuk !operator, atau bitoruntuk |operator. Dengan xor_equntuk ^=, Anda dapat nol variabel i 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 -trigraphsuntuk mengaktifkannya, -std=c++11atau sesuatu untuk kesesuaian ketat dengan standar ISO yang menyertakannya.

23 byte unik:

%:include<iostream>

int main() <%
    int n;
    std::cin >> n;

    for(int r<% %>; r < n;) <%
        ++r;
        for(int i<%%>; i < r;) <%
            ++i;
            std::cout << i << ' ';
        %>
        std::cout << std::endl;
    %>
%>

Cobalah online!

Versi terakhir menggunakan 'kutipan tunggal, bukan hatau "untuk pemisah ruang. Saya tidak ingin membuat digraf char c{}barang jadi saya menghapusnya. Mencetak char lebih efisien daripada mencetak string, jadi saya menggunakannya.

Histogram:

$ sed 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -ic  | tee /dev/tty | wc -l
     15         // newline
     95         // space
     11 %
      2 '
      3 (
      3 )
      4 +
      9 :
     10 ;
     14 <
      8 >
      2 a
      4 c
      6 d
      3 e
      2 f
     12 i
      2 l
      2 m
     11 n
      5 o
      7 r
      5 s
     11 t
      3 u
25   // total lines, including space and newline

Pemisah ruang (masih belum terpecahkan)

Dalam jawaban yang sekarang dihapus, Johan Du Toit mengusulkan menggunakan pemisah alternatif, khususnya std::ends. Itu karakter NUL char(0),, dan mencetak sebagai lebar nol pada sebagian besar terminal. Jadi hasilnya akan seperti 1234, bukan 1 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 0mudah dibuat cout << some_zeroed_var. Tapi tidak ada yang mau 10203040, itu bahkan lebih buruk daripada tidak ada pemisah.

Saya mencoba memikirkan cara untuk membuat std::stringholding" " tanpa menggunakan charatau string literal. Mungkin menambahkan sesuatu padanya? Mungkin dengan digraf untuk []mengatur byte pertama ke nilai 32, setelah membuat satu dengan panjang 1 melalui salah satu konstruktor?

Johan juga menyarankan fungsi std::iosfill () anggota yang mengembalikan karakter isian saat ini. Default untuk streaming ditetapkan oleh std::basic_ios::init(), dan ' '.

std::cout << i << std::cout.fill();menggantikan << ' ';tetapi menggunakan .bukan' .

Dengan -, kita dapat mengambil pointer ke coutdan penggunaan ->fill()untuk memanggil fungsi anggota:
std::cout << (bitand std::cout)->fill(). Atau tidak, kami tidak menggunakan bbaik 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(); }

// not digraphed
struct ss : std::ostream {  // default = private inheritance
//      ss() { init(); }  // ostream's constructor calls this for us
        operator char() { return fill(); }
}

Lalu ss s{}sebelum loop, dan std::cout << i << s;di dalam loop. Hebat, itu mengkompilasi dan bekerja dengan baik, tetapi kami harus menggunakan pdan huntuk operator char(), kerugian bersih 1. Setidaknya kami menghindari bmembuat fungsi anggota publicdengan menggunakan structalih-alih class. (Dan kita bisa mengganti warisan dengan protectedkalau-kalau ada yang membantu).

Peter Cordes
sumber
@JohanduToit: ide bagus dengan 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 ke coutatau aliran lain?
Peter Cordes
Ups, << (bitand std::cout)->fill()kompilasi, tetapi gunakan -. (Terlepas dari nama token, bitandhanya 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 ->?
Peter Cordes
1
Satu-satunya hal lain yang saya temukan adalah yang std::ios::leftdidefinisikan 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 :-)
Johan du Toit
@JohanduToit: Membuat int32 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, atau std::function. Atau std::stringidenya. Tapi kami tidak menggunakannya guntuk kami tidak bisa benar-benar mendeklarasikan std::stringtanpa kehilangan; ide saya untuk menggunakan gotobukannya fortidak berjalan dengan baik. decltype(something)bisa memberi kita chartipe, tetapi biaya kita a y.
Peter Cordes
1
Anda dapat menggunakan otomatis alih-alih char untuk opeator: struct ss : std::ostream { operator auto () { return fill(); } };tetapi tidak banyak membantu.
Johan du Toit
7

C ++ (gcc) x86_64 Khusus Linux, 9295 8900 8712 6812 5590 byte, 18 karakter unik

int m[]={111111111111111+1111111111111+1111111111111+1111111111111+1111111111111+1111111111111+1111111111111+111111111+111111111+1111111+111111+11111+11111+11+11+11+11+11+1+1+1,11111111111+11111111111+11111111111+1111111111+111111111+111111111+111111111+111111+1111+1111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1,111111111111111+111111111111111+111111111111+111111111111+1111111111+1111111+1111111+11111+11111+11111+1111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1,111111111111111+111111111111111+1111111111111+1111111111111+11111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+11111+1111+111+111+11+1+1+1,1111111111111+1111111111111+11111111111+11111111111+1111111111+1111111111+1111111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+11,11111111111111+1111111111111+11111111111+11111111111+11111111111+1111111111+111111111+11111111+11111111+11111111+11111111+1111+1111+1111+1111+1111+1111+1111+1111+1111+111+1+1+1+1,111111111111111+1111111111111+1111111111111+1111111111111+1111111111111+11111111111+11111111111+1111111+11111+11111+1111+1111+11+11+11+11+11+11+11+1+1+1+1,111111111111+11111111111+1111111111+1111111111+1111111111+1111111111+1111111111+1111111111+11111111+11111+11111+11111+11111+11111+11111+1+1,111111111111111+11111111111111+11111111111+11111111111+1111111111+1111111+1111111+11111+111+111+111+111+111+111+111+111+11+11+1+1+1+1+1+1,11111111111+1111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11+1+1+1+1+1+1+1,111111111111+11111111111+11111111111+11111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+111+111+111+111+111+111+111+1+1+1+1+1+1+1,11==1,1111111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+1+1+1,1111111111111+111111111111+11111111111+1111111111+111111111+111111111+11111111+111111+111111+111111+11111+1111+111+111+1+1,111111111111+111111111111+11111111111+11111111111+11111111111+11111111111+111111111+111111111+11111111+111111+1111+1111+111+111+111,111111111111+11111111111+1111111111+1111111111+111111111+1111111+111+111+1+1+1+1,111111111111111+11111111111111+1111111111111+1111111111111+111111111111+1111111111+1111111111+1111111111+1111111+111111+111111+111111+11111+11111+11111+1111+1111+111+11+11+1+1+1+1,111111111111111+1111111111111+1111111111111+11111111111+1111111111+11111111+11111111+1111+1111+1111+111+111+111+111+11+11,111111111+111111111+11111111+11111111+11111111+1111111+1111111+111111+11111+1111+1111+1111+1111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1,11111111111111+111111111111+111111111111+11111111111+111111111+111111+111111+111111+1111+1111+1111+1+1+1+1+1+1+1+1,11111111111+11111111111+11111111111+11111111111+1111111111+1111111111+11111111+1111111+1111111+1111111+1111111+111111+11111+11+11+11+1+1+1+1+1+1+1+1,111111111111111+111111111111111+111111111111+1111111111+1111111111+11111111+11111111+1111111+1111111+111111+111111+11111+11111+111+11+11+1+1+1+1+1+1+1+1+1+1,11111111111111+11111111111111+111111111111+11111111111+11111111111+1111111+1111111+1111111+1111111+1111111+1111111+11+11+11+11+11+11+11+11+1,11111111111111+11111111111111+11111111111+1111111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+11111+11111+1111+1111+1111+111+111+111+111+111+111+11,111111111111111+1111111111111+111111111111+111111111111+111111111111+11111111111+1111111111+1111111111+111111111+111111+111111+111111+111111+1111+11+1+1,111111111111111+11111111111111+111111111111+111111111111+1111111111+1111111111+111111111+11111111+1111+1111+1111+111+111+111+111+111+11+11+11+11+11+11+11+11+1+1+1+1,11111111111111+11111111111111+11111111111111+11111111111+11111111111+1111111111+11111111+1111111+11111+11111+11111+1111+111+111+111+11+11+11+11+1+1+1+1+1+1,111111111111111+11111111111111+1111111111+111111111+111111111+111111111+11111111+1111111+111111+11111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1,111111111111111+1111111111111+1111111111111+1111111111111+1111111111+111111111+111111111+111111111+11111111+1111111+11111+1111+1111+1111+111+111+111+11,1111111111111+1111111111+11111111+11111111+11111111+11111+1111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1,11111111111111+1111111111+1111111111+111111111+11111111+1111111+1111111+1111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+11+11+11+11+11+11+11+1+1+1+1+1+1+1,11111111111111+1111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+11111+1111+1111+111+111+111+111+111+111+1+1+1+1+1+1,111111111111111+1111111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+111111+11111+11111+11111+1111+111+111+111+11+11+11+11+11,1111111111+111111111+1111111+1111111+111111+111111+11111+11111+11111+11111+11111+11111+1111+1111+1111+11+11+11+11+11+11+11+11+11+1+1+1,111111111111111+111111111111+111111111111+111111111111+11111111111+1111111111+1111111111+1111111111+11111111+11111+1111+1111+111+111+111+111+111+111+111+111+1,1111111111+111111111+111111111+11111111+1111111+1111111+1111111+111111+11111+11111+11111+11111+11111+111+111+111+11+11+11+1,11111111111111+11111111111111+1111111111+1111111111+1111111111+1111111111+11111111+11111111+11111111+11111111+1111111+1111111+111+111+111+111+11+11+11+11+11+11+11+1+1,111111111111+11111111111+1111111111+111111111+111111111+111111+111111+111111+111111+11111+11111+11+11+11+11+11+1,111111111+11111+11111+111+11+1+1+1+1+1+1+1+1+1};main(){((int(*)())m)();}

Cobalah 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 encode xsebagai ysehingga y%(1<<32)==x. Program bahasa mesin yang disandikan adalah sebagai berikut

0x0000000000000000:  55                         push    rbp
0x0000000000000001:  31 ED                      xor     ebp, ebp
0x0000000000000003:  53                         push    rbx
0x0000000000000004:  48 83 EC 18                sub     rsp, 0x18
0x0000000000000008:  48 8D 74 24 0C             lea     rsi, [rsp + 0xc]
0x000000000000000d:  31 C0                      xor     eax, eax
0x000000000000000f:  31 FF                      xor     edi, edi
0x0000000000000011:  6A 01                      push    1
0x0000000000000013:  5A                         pop     rdx
0x0000000000000014:  0F 05                      syscall 
0x0000000000000016:  89 C3                      mov     ebx, eax
0x0000000000000018:  85 C0                      test    eax, eax
0x000000000000001a:  74 0C                      je      0x28
0x000000000000001c:  6B ED 0A                   imul    ebp, ebp, 0xa
0x000000000000001f:  03 6C 24 0C                add     ebp, dword ptr [rsp + 0xc]
0x0000000000000023:  83 ED 30                   sub     ebp, 0x30
0x0000000000000026:  EB E0                      jmp     8
0x0000000000000028:  C7 44 24 0C 00 00 00 00    mov     dword ptr [rsp + 0xc], 0
0x0000000000000030:  FF C3                      inc     ebx
0x0000000000000032:  8B 44 24 0C                mov     eax, dword ptr [rsp + 0xc]
0x0000000000000036:  8D 78 01                   lea     edi, [rax + 1]
0x0000000000000039:  89 7C 24 0C                mov     dword ptr [rsp + 0xc], edi
0x000000000000003d:  E8 27 00 00 00             call    0x69
0x0000000000000042:  6A 20                      push    0x20
0x0000000000000044:  48 89 E6                   mov     rsi, rsp
0x0000000000000047:  52                         push    rdx
0x0000000000000048:  58                         pop     rax
0x0000000000000049:  50                         push    rax
0x000000000000004a:  5F                         pop     rdi
0x000000000000004b:  0F 05                      syscall 
0x000000000000004d:  5E                         pop     rsi
0x000000000000004e:  39 5C 24 0C                cmp     dword ptr [rsp + 0xc], ebx
0x0000000000000052:  7C DE                      jl      0x32
0x0000000000000054:  6A 0A                      push    0xa
0x0000000000000056:  48 89 E6                   mov     rsi, rsp
0x0000000000000059:  52                         push    rdx
0x000000000000005a:  58                         pop     rax
0x000000000000005b:  0F 05                      syscall 
0x000000000000005d:  5E                         pop     rsi
0x000000000000005e:  39 DD                      cmp     ebp, ebx
0x0000000000000060:  7F C6                      jg      0x28
0x0000000000000062:  48 83 C4 18                add     rsp, 0x18
0x0000000000000066:  5B                         pop     rbx
0x0000000000000067:  5D                         pop     rbp
0x0000000000000068:  C3                         ret     
0x0000000000000069:  85 FF                      test    edi, edi
0x000000000000006b:  74 2C                      je      0x99
0x000000000000006d:  89 F8                      mov     eax, edi
0x000000000000006f:  6A 0A                      push    0xa
0x0000000000000071:  59                         pop     rcx
0x0000000000000072:  48 83 EC 18                sub     rsp, 0x18
0x0000000000000076:  99                         cdq     
0x0000000000000077:  F7 F9                      idiv    ecx
0x0000000000000079:  89 C7                      mov     edi, eax
0x000000000000007b:  8D 42 30                   lea     eax, [rdx + 0x30]
0x000000000000007e:  89 44 24 0C                mov     dword ptr [rsp + 0xc], eax
0x0000000000000082:  E8 E2 FF FF FF             call    0x69
0x0000000000000087:  48 8D 74 24 0C             lea     rsi, [rsp + 0xc]
0x000000000000008c:  6A 01                      push    1
0x000000000000008e:  58                         pop     rax
0x000000000000008f:  50                         push    rax
0x0000000000000090:  5F                         pop     rdi
0x0000000000000091:  50                         push    rax
0x0000000000000092:  5A                         pop     rdx
0x0000000000000093:  0F 05                      syscall 
0x0000000000000095:  48 83 C4 18                add     rsp, 0x18
0x0000000000000099:  C3                         ret

... yang didasarkan pada kode C berikut.

void print(int x){
  if( x ) {
    int y=x%10+'0';
    print(x/10);
    write(1,&y,1);
  }
}
void f() {
  int i=0,j=0,k;
  for( ;read(0,&k,1);i=i*10+k-'0' );
  do {
    for( j++,k=0; print( ++k ), write(1," ",1), k<j; );
    write(1,"\n",1);
  } while(j<i );
}

Sunting: Sekarang menerima input dari stdinalih-alih argv[1]. Terima kasih hanya untuk @ ASCII dan @PeterCordes untuk saran mereka!

Sunting4: Pengkodean sedikit ditingkatkan secara signifikan.

plafon
sumber
-wTandai pls: P (juga Anda dapat mengubah nama iimenjadi a)
ASCII-hanya
Anda perlu gcc -zexecstackini, kan? Karena int m[]tidak const. (Dan toolchains baru-baru ini dimasukkan ke .rodatadalam halaman yang tidak dapat dieksekusi sehingga bahkan const int m[]tidak berfungsi misalnya sistem Linux Arch sayagcc 8.2.1 20181127 dan ld(GNU Binutils) 2.31.1.) Bagaimanapun, Anda lupa menyebutkan itu dalam jawaban Anda, tapi itu ada di tautan TIO Anda.
Peter Cordes
BTW, algoritma penghitungan angka unik OP tidak menghitung ruang dan baris baru, jadi Anda tidak perlu membuat semuanya menjadi buruk untuk dibaca, cukup array: P
Peter Cordes
Anda dapat menyimpan byte kode mesin dengan menyalin 1dengan push %rax/pop %rdi bukannya push-langsung lainnya. Atau lebih sederhana, untuk nilai yang tidak 64-bit, yaitu non-pointer, 2-byte mov %eax, %edi. Selain itu, Linux syscalltidak merusak register inputnya, hanya raxdengan nilai pengembalian dan RCX + R11 dengan RIP dan RFLAGS yang disimpan sebagai bagian dari cara kerja syscallinstruksi. Jadi Anda dapat pergi rdidan rdxmengatur 1panggilan 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.
Peter Cordes
6

21 karakter unik + 1 baris baru yang tidak dapat dilepas

%:include<iostream>
int(n)(int(i))<%
    if(--i)if(n(i))<%%>
    if(i)if(std::cout<<i<<std::addressof(std::cout)->fill())<%%>
%>
int(l)(int(i))<%
    if(n(-(--i)))<%%>
%>
int(m)(int(i))<%
    if(--i)if(m(i))<%%>
    if(i)if(l(-i))<%%>
    if(i)if(std::cout<<std::endl)<%%>
%>
int(c)(int(i))<%
    if(m(-(--i)))<%%>
%>
int(main)(int(i))<%
    if(std::cin>>i)<%%>
    if(c(-i))<%%>
%>

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:

  1. Titik koma dihapus dengan mengubah for loop ke ifdan rekursi.
  2. Punya karakter spasi oleh std::addressof(std::cout)->fill(), alias std::cout.fill().
jimmy23013
sumber
std :: addressof, bagus!
Johan du Toit
2

21 20 karakter unik tidak termasuk spasi putih

Semua spasi putih dapat diubah menjadi baris baru.

%:include<iostream>
%:include<list>
int n;
const int co<%%>;
const int ci<%not co%>;
const int cmu<%-ci-ci-ci-ci%>;
const char ctd<%-cmu-cmu-cmu-cmu-cmu-cmu-cmu-cmu%>;
const int cia<%-ctd-ctd-ctd-ctd-ctd-cmu%>;
const int ciu<%cia- -ci- -ci%>;

struct<%struct<%struct<%struct<%struct<%struct<%struct<%
int c<:ctd-ci:>;
%>d<:ctd:>;int c<:ctd-ci:>;%>d<:ctd:>;int c<:ctd-ci:>;
%>d<:ctd:>;int c<:ctd-ci:>;%>d<:ctd:>;int c<:ctd-ci:>;
%>d<:ctd:>;int c<:ctd-ci:>;%>d<:-cmu:>;int c<:-ci-cmu:>;
%>e<:co:><:ctd:><:ctd:><:ctd:><:ctd:><:ctd:><:ctd:>;

int i<:co:>;
auto ia<%e%>;
auto iu<%e%>;
int l<%std::cin>>n and co%>;

struct s<%
    int c<%std::cout<<i<:ciu:>- --i<:cia:><<ctd and n%>;
%>;
struct o<%
    int c<%--ia and n%>;
%>;
struct t<%
    std::list<s>c<%- --l%>;
    std::list<o>r<%-l%>;
    int m<%std::cout<<std::endl and n%>;
%>;
std::list<t>a<%n%>;
int main;

Keluar dengan segfault. Karakter yang digunakan:%:include<ostram>;-h .

Ia bekerja di versi kompiler khusus ini di Linux 64 bit:

g++-5 (Ubuntu 5.5.0-12ubuntu1) 5.5.0 20171010

Dengan parameter:

-std=c++17

Meski begitu, saya tidak yakin itu akan selalu berhasil. Itu mungkin juga tergantung pada banyak hal lainnya. ciadan ciuapakah offset memori dibagi 4 antara ia iudan i. ( intversi 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-statis autotidak diizinkan dalam sebuah struct.

eadalah array 0-elemen dari tipe elemen dengan ukuran (2 32 -1) × 2 32 byte. Jika tipe pointer yang sesuai edikurangi, 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 =:

%:include<iostream>
%:include<list>
int n;
int ci<%not n%>;
int cmu<%-ci-ci-ci-ci%>;
char ctd<%-cmu-cmu-cmu-cmu-cmu-cmu-cmu-cmu%>;
int i;
int l<%std::cin>>n and n-n%>;

struct s<%
    int c<%std::cout<<- --i<<ctd and n%>;
%>;
struct t<%
    std::list<s>c<%- --l%>;
    int r<%i=n-n%>;
    int m<%std::cout<<std::endl and n%>;
%>;
std::list<t>a<%n%>;
int main;

Bahkan ini tidak berfungsi di versi terbaru g ++ karena sepertinya tidak mengizinkan mendefinisikan maindalam tipe arbitrer lagi.

Kedua program ini tidak menggunakan tanda kurung. Tapi titik koma sepertinya tidak bisa dihindari.

jimmy23013
sumber
1

22 karakter unik tidak termasuk spasi putih. Memisahkan angka dengan karakter NUL yang ditampilkan dengan benar di Windows.

%:include<iostream>
int main(int n)<%
    std::cin>>n;
    for(int r<%%>;r++<n;)<%
        for(int i<%%>;i<r;)
            std::cout<<++i<<std::ends;
        std::cout<<std::endl;
    %>
%>

Cobalah online

Histogram:

[%] 0x25 = 9
[:] 0x3A = 11
[)] 0x29 = 3
[i] 0x69 = 11
[n] 0x6E = 12
[c] 0x63 = 4
[l] 0x6C = 2
[u] 0x75 = 3
[d] 0x64 = 8
[e] 0x65 = 4
[<] 0x3C = 13
[o] 0x6F = 5
[s] 0x73 = 7
[t] 0x74 = 12
[r] 0x72 = 6
[a] 0x61 = 2
[m] 0x6D = 2
[>] 0x3E = 7
[(] 0x28 = 3
[;] 0x3B = 7
[f] 0x66 = 2
[+] 0x2B = 4
Unique Characters: 22
Total Characters: 189
Johan du Toit
sumber
std :: ends adalah karakter NUL ( 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 seperti 1234tidak 1 2 3 4. Ini terlihat sama pada output TIO Anda!
Peter Cordes
@PeterCordes, OP tidak menentukan bagaimana angka-angka harus dipisahkan ;-)
Johan du Toit
Apakah Anda benar-benar berpikir mereka akan menyia-nyiakan karakter pada "untuk " "jika mereka bisa menggunakan iiiiuntuk memisahkan dengan '0'untuk 10203040? 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.
Peter Cordes
1
@PeterCordes, Poin diambil.
Johan du Toit