Wygeneruj drabinkę liczb całkowitych, używając najmniejszej liczby unikalnych znaków (w C ++)

13

Jestem nowy w sporcie golfowym. Próbuję wygenerować drabinkę liczb całkowitych, używając najmniejszej liczby unikalnych znaków w C ++.

Powiedzmy, że otrzymaliśmy liczbę całkowitą 4.

Wygenerujemy następującą drabinę:

1
1 2
1 2 3
1 2 3 4

W skrócie, mój program odczyta dodatnią liczbę całkowitą ze standardowego wejścia i wydrukuje tę drabinę na wyjściu. Próbuję to zrobić z możliwie najmniejszą liczbą unikalnych postaci .

Mój program jest następujący:

#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;
    }
}

Oto sprawdzanie, którego użyłem do sprawdzenia liczby unikalnych znaków w moim programie:

#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;
}

Najlepiej, jeśli chcę użyć mniej niż 25 unikalnych znaków, aby ukończyć ten program (oprócz znaków nowego wiersza, ale z odstępami). Obecnie mój program używa 27. Nie jestem pewien, jak dalej go zoptymalizować.

Czy ktoś mógłby mi doradzić, jak dalej go zoptymalizować (pod względem liczby użytych unikalnych znaków)? Pamiętaj, że można używać tylko C ++.

code-challenge tips c++ LanceHAOH
źródło
5
Z pewnością nowością jest prosić o wskazówki dotyczące jakichkolwiek innych kryteriów punktacji niż kod-golf , ale jest to temat na temat, ponieważ strony z poradami mówią, że jest to lepsza odpowiedź na wyzwanie programistyczne, które jest na temat .
Adám
8
@LuisMendo Nie sądzę, aby było to prawdą w tym przypadku, ponieważ wiele języków całkowicie trywializuje ten schemat punktacji. Jeśli ten użytkownik chce pomóc w nauce „unikalnego golfa”, ma to sens tylko w podzbiorze języków, więc myślę, że jest to o wiele lepsza wskazówka niż ogólne wyzwanie. To powiedziawszy, podstawowy problem może być wyzwaniem, jeśli ktoś chce go opublikować.
FryAmTheEggman
3
Myślę, że możesz użyć digraphs <% i%> zamiast nawiasów klamrowych, i myślę, że trochę mi brakowało.
mój zaimek to monicareinstate
2
Zdecydowanie za mną tęskniłem. # to% :, więc możesz pozbyć się trzech znaków i wprowadzić jeden ({=> <%,} =>%>, # =>% :) i dostać się do 25. Jeśli połączysz to z odpowiedzią poniżej, ja myślę, że możesz dostać 24.
mój zaimek to monicareinstate
2
@LanceHAOH Trigrafie są niezwykle powszechne w [podstępnych] pytaniach, a digrafy pojawiają się również podczas czytania o trigrafiach.
mój zaimek to monicareinstate

Odpowiedzi:

12

Myślę, że udało mi się usunąć znak = z twojego kodu, chociaż teraz jest on znacznie wolniejszy

#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;
    }
}

To nie jest ładne, ale nadużywając przepełnienia liczb całkowitych możemy wrócić do 0 bez użycia =

Musieliśmy też trochę zmienić strażników. Niestety z powodu dołączenia nie mogłem pozbyć się wszystkich nowych znaków linii (chociaż jest blisko), więc może to być kolejna droga do zbadania.

Edycja: na razie zabrakło czasu, ale jeśli uwzględnisz i używasz strstream i różnych innych bibliotek, myślę, że możesz być w stanie usunąć również znak „, ponownie używając liczb całkowitych, aby uzyskać właściwy znak dla spacji i przekazać go do strstream

Wygasły dane
źródło
2
Możesz #include<std>i wyeliminować wszystkie :s. Niezbyt dobra praktyka kodowania, ale to nie ma znaczenia.
Darrel Hoffman
3
@DarrelHoffman Nie mogę tego uruchomić, nie musisz tego robić, using namespace std;który użyłby dodatkowego p dla: więc netto 0
Data wygasła
Hmm Może mój C ++ jest trochę zardzewiały. To także dodaje g, więc myślę, że strata netto. Gdyby to był kod złota, możemy zmniejszyć liczbę bajtów przez zmianę nazwy ii, iiioraz iiiido innych nazw pojedynczy list (pick innych już używanych liter), ale to nie to, co jest o to wyzwanie, więc nie sądzę. Zastanawiam się, czy przyniosłyby jakieś korzyści getci putczamiast cin/ coutmusiałbym spróbować.
Darrel Hoffman
1
Mój błąd. Właśnie przeczytałem ponownie kontroler. Wygląda na to, że znak nowej linii jest ignorowany. Tak więc nie ma potrzeby przejmować się usuwaniem nowych linii. Ale w połączeniu z twoją strategią i rozwiązaniem autorstwa @someone w komentarzach udało mi się uzyskać 24 znaki. Zrobiłem program jeszcze szybciej, używając short zamiast int. Mam więc dodatkową postać „h”. Ale to pozwala mi użyć typu danych char bez dodatkowych kosztów. Pozbyłem się więc również „znaku, używając kodu znaku.
LanceHAOH
@LanceHAOH: zauważ, że przepełnienie całkowitą ze znakiem jest zachowaniem niezdefiniowanym w C ++ dla wszystkich podpisanych typów, w tym signed char. Jeśli kompilujesz z włączoną optymalizacją, ten kod może zepsuć się z nowoczesnymi kompilatorami, chyba że użyjesz gcc -fwrapvdo tego, aby podpisane przepełnienie było dobrze zdefiniowane jako zawijanie dopełniacza 2. obsługuje także clang -fwrapv. (w unsignedtym typy całkowite unsigned charmają dobrze zdefiniowane zachowanie (zawijanie) w ISO C ++). To zależy od ABI, czy charjest signed charlub unsigned char, więc charmoże być w porządku.
Peter Cordes
10

W końcu uzyskałem 24 unikalne postacie, łącząc odpowiedzi @ExpiredData i @someone. Ponadto użycie krótkiego typu danych zamiast int pomogło przyspieszyć mój program, ponieważ przepełnienie krótkiego typu danych zajmuje krócej.

Mój kod jest następujący.

%: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
źródło
@KevinCruijssen używa go w char iiiii;ostatniej inicjalizacji zmiennej.
Rɪᴋᴇʀ
1
@KevinCruijssen To prawda. Ale to pozwala mi usunąć znak „, ponieważ mogę użyć kodu znakowego do przedstawienia znaku spacji. Więc zastosowana różnica netto w unikatowych znakach = 0.
LanceHAOH
9

23 unikalne postacie za pomocą Digraphs. (25 bez). Bez UB.

Użyj składni inicjalizatora wzmocnionego C ++ 11, aby zainicjować listę liczb całkowitych do zera, int var{};unikając =i 0. (Lub w twoim przypadku, unikając globalnego iiii). Daje to źródło zer innych niż zmienne globalne (które są statycznie inicjowane na zero, w przeciwieństwie do miejscowych).

Obecne kompilatory domyślnie akceptują tę składnię, bez konieczności włączania żadnych specjalnych opcji.

(Sztuczka z zawijaniem liczb całkowitych jest fajna i dobra do gry w golfa z wyłączoną optymalizacją, ale podpisane przepełnienie jest niezdefiniowanym zachowaniem w ISO C ++. Włączenie optymalizacji przekształci te zawinięte pętle w nieskończone pętle, chyba że skompilujesz z gcc / clang, -fwrapvaby dobrze podpisać przepełnienie liczb całkowitych -definiowane zachowanie: objęcie dopełniacza 2.

Ciekawostka: ISO C ++ std::atomic<int>ma dobrze zdefiniowane dopełnienie komplementu 2! int32_tmusi być uzupełnieniem 2, jeśli w ogóle jest zdefiniowane, ale zachowanie przepełnienia jest niezdefiniowane, więc nadal może być typem zdefiniowanym dla intlub longna dowolnym komputerze, na którym jeden z tych typów ma 32 bity, bez dopełniania i uzupełnienia 2).

Nieprzydatne w tym konkretnym przypadku:

Możesz także zainicjować nową zmienną jako kopię istniejącej, za pomocą nawiasów klamrowych lub (z niepustym inicjatorem) parens do bezpośredniej inicjalizacji .
int a(b)lub int a{b}są równoważne zint a = b;

Ale int b();deklaruje funkcję zamiast zmiennej zainicjowanej na zero.

Można także uzyskać zero za pomocą int()lub char(), tj. Inicjalizację zera anonimowego obiektu.

Możemy zamienić twoje <=porównania na <porównania przez prostą transformację logiczną : wykonaj przyrost licznika pętli bezpośrednio po porównaniu, zamiast na dole pętli. IMO jest to prostsze niż alternatywy proponowane przez ludzi, takie jak użycie ++w pierwszej części a, for()aby zamienić 0 na 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;
    }

Moglibyśmy grać w golfa, for(int r{}; r++ < n;)ale IMO jest trudniejsze do odczytania dla ludzi. Nie optymalizujemy całkowitej liczby bajtów.

Gdybyśmy już używali h, moglibyśmy zaoszczędzić miejsce 'lub ".

Zakładając środowisko ASCII lub UTF-8, przestrzeń ma charwartość 32. Możemy ją łatwo utworzyć w zmiennej, a następniecout << 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

A inne wartości można oczywiście utworzyć z sekwencji ++podwojenia i na podstawie bitów ich reprezentacji binarnej. Skutecznie przesuwając 0 (nic) lub 1 (++) do LSB przed podwojeniem do nowej zmiennej.

Ta wersja używa hzamiast 'lub ".

Jest znacznie szybszy niż którakolwiek z istniejących wersji (nie opiera się na długiej pętli) i jest wolny od niezdefiniowanego zachowania . To kompiluje bez ostrzeżenia ze g++ -O3 -Wall -Wextra -Wpedanticizclang++ . -std=c++11jest opcjonalne. Jest to legalne i przenośne ISO C ++ 11 :)

Nie opiera się również na zmiennych globalnych. I uczyniłem go bardziej czytelnym dla człowieka dzięki nazwom zmiennych, które mają znaczenie.

Liczba bajtów unikalnych: 25 , z wyłączeniem komentarzy, które usunąłemg++ -E . I wykluczając spację i znak nowej linii, jak twój licznik. Użyłem sed 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -ic tego askubuntu, aby policzyć wystąpienia każdej postaci, i wcprzeliczyłem to, aby policzyć, ile unikalnych postaci miałem.

#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;
    }
}

Jedyne 2 fznaki pochodzą z for. whileZamiast tego moglibyśmy użyć pętli w.

Moglibyśmy przepisać pętle na styl asemblera, i < r || goto some_label;aby napisać warunkowy skok na dole pętli lub cokolwiek innego. (Ale używając orzamiast ||). Nie, to nie działa. gotojest instrukcją podobną do ifi nie może być podskładnikiem wyrażenia tak jak w Perlu. W przeciwnym razie moglibyśmy go użyć do usunięcia znaków (i ).

Możemy handlować fna gze if(stuff) goto label;zamiast for, a obie pętle zawsze uruchomić co najmniej 1 iteracji tak musielibyśmy jednej pętli oddziałem na dole tylko, jak normalny ASM do{}whilestrukturze pętli. Zakładając, że użytkownik wprowadzi liczbę całkowitą> 0 ...

Digraphs and Trigrafs

Na szczęście, trygrafy zostały usunięte od ISO C ++ 17, więc nie musimy ich używać ??>zamiast, }jeśli jesteśmy wyjątkowymi golfistami w najnowszej wersji C ++.

Ale tylko trygrafy: ISO C ++ 17 nadal ma digrafy, takie jak :>for ]i %>for} . Więc kosztem użyciu %, możemy uniknąć zarówno {a }i używać %:dla #dla oszczędności netto 2 mniej unikalnych znaków.

C ++ i ma kluczowe operatora jak notdla !operatora, albo bitordla |operatora. Za pomocą xor_eqfor ^=można zerować zmienną i xor_eq i, ale ma ona wiele znaków, których nie używałeś.

Obecne g++już domyślnie ignoruje trygrafy, nawet bez -std=gnu++17; musisz użyć, -trigraphsaby je włączyć -std=c++11lub coś w celu ścisłej zgodności ze standardem ISO, który je obejmuje.

23 unikalne bajty:

%: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;
    %>
%>

Wypróbuj online!

Ostateczna wersja używa ' pojedynczego cudzysłowu zamiast hlub "dla separatora spacji. Nie chciałem kopiować char c{}treści, więc je usunąłem. Drukowanie znaku jest bardziej wydajne niż drukowanie łańcucha, więc wykorzystałem to.

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

Separator przestrzeni (wciąż nierozwiązany)

W usuniętej teraz odpowiedzi Johan Du Toit zaproponował zastosowanie specjalnie alternatywnego separatora std::ends. Jest to znak NUL char(0)i drukowany jest jako zero-szerokość na większości terminali. Tak wyglądałoby wyjście1234 , a nie 1 2 3 4. Albo gorzej, oddzielone śmieciami od wszystkiego, co nie cicho się zawali '\0'.

Jeśli możesz użyć dowolnego separatora, kiedy cyfra 0jest łatwa do utworzeniacout << some_zeroed_var . Ale nikt nie chce 10203040, to nawet gorzej niż brak separatora.

Próbowałem wymyślić sposób na utworzenie std::stringgospodarstwa" " bez użycia charlub dosłownego ciągu znaków. Może coś do tego dodać? Może z wykopem dla[] do ustawienia pierwszego bajtu na wartość 32po utworzeniu jednego o długości 1 za pomocą jednego z konstruktorów?

Johan zasugerował również std::iosfunkcję członka fill (), która zwraca bieżący znak wypełnienia. Domyślne ustawienie strumienia jest ustawione na std::basic_ios::init()i ma wartość ' '.

std::cout << i << std::cout.fill();zastępuje, << ' ';ale używa .zamiast' .

Dzięki -, możemy podjąć wskaźnik do couti wykorzystania ->fill()do wywołania funkcji użytkownika:
std::cout << (bitand std::cout)->fill(). Albo nie, my też nie korzystaliśmy b, więc równie dobrze moglibyśmy użyć& zamiast jego odpowiednika leksykalnym bitand.

Wywoływanie funkcji członka bez .lub->

Umieść go w klasie i zdefiniuj 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(); }
}

Następnie ss s{}przed pętlą i std::cout << i << s;wewnątrz pętli. Świetnie, kompiluje się i działa poprawnie, ale musieliśmy użyć pi hdla operator char(), dla straty netto równej 1. Przynajmniej uniknęliśmy btworzenia funkcji członkowskich publicprzez używanie structzamiast class. (I możemy zastąpić dziedziczenie, protectedna wypadek, gdyby to kiedykolwiek pomogło).

Peter Cordes
źródło
@JohanduToit: dobry pomysł z cout.fill()odstd::ios , ale nie byliśmy wcześniej używając . Może moglibyśmy nazwać jakoś biorąc wskaźnik i korzystania ->fill()z funkcji członka? Czy coś zwraca wskaźnik do coutlub inny strumień?
Peter Cordes
Ups, << (bitand std::cout)->fill()kompiluje, ale używa -. (Pomimo nazwy tokena, bitandjest to tylko leksykalny odpowiednik &, a nie operator bitowy i. Działa również jako operator adresu.) Hmm, jest jakiś szablon lub lambda, które mogą uzyskać wskaźnik do funkcji członka że możemy ()bez użycia .lub ->?
Peter Cordes
1
Jedyną inną rzeczą, którą znalazłem, std::ios::leftjest zdefiniowana w gcc jako 32, ale tak naprawdę nie mogłem znaleźć sposobu, aby z tego skorzystać. Myślę, że pozwolę temu odejść i trochę popracować :-)
Johan du Toit
@JohanduToit: Utworzenie int32 nie jest problemem, moja odpowiedź już pokazuje, jak to zrobić, ++zaczynając od int c{};zera. Ale tak, nie schodzę do króliczej nory, szukając lambdas, szablonów lub std::function. Lub std::stringpomysł. Ale nie przyzwyczajamy się gdo tego, że nie możemy faktycznie zadeklarować, std::stringnie tracąc; mój pomysł na użycie gotozamiast fornie wypalił. decltype(something)może dać nam chartyp, ale kosztuje nas y.
Peter Cordes
1
Możesz użyć auto zamiast char dla operatora: struct ss : std::ostream { operator auto () { return fill(); } };ale to niewiele pomaga.
Johan du Toit
7

C ++ (gcc) x86_64 Tylko Linux, 9295 8900 8712 6812 5590 bajtów, 18 unikalnych znaków

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)();}

Wypróbuj online!

Jest to oparte na pomysłach z tej odpowiedzi PPCG . Program w języku maszynowym jest wyrażony jako tablica 32 bitowych liczb całkowitych, z których każdy jest reprezentowany jako suma 1+11+111.... Okazuje się, że kodowanie xjako ytakie może być bardziej efektywne y%(1<<32)==x. Kodowany program języka maszynowego jest następujący

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

... który jest oparty na następującym kodzie C.

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 );
}

Edycja: Teraz akceptuje dane wejściowe stdinzamiastargv[1] . Dzięki tylko dla @ ASCII i @PeterCordes za sugestie!

Edit4: Nieznacznie poprawione kodowanie.

sufitowy
źródło
-wflag pls: P (możesz także zmienić nazwę iina a)
tylko ASCII
Potrzebujesz gcc -zexecstacktego, prawda? Ponieważ int m[]nie jest const. (Ostatnie łańcuchy narzędzi i tak zostały umieszczone .rodatana stronie niewykonywalnej, więc nawet const int m[]nie działa np. W moim systemie Arch Linux z gcc8.2.1 20181127 i ld(GNU Binutils) 2.31.1.) W każdym razie zapomniałeś wspomnieć o tym w swojej odpowiedzi, ale jest w twoim linku TIO.
Peter Cordes
BTW, unikalny algorytm punktacji OP nie uwzględnia przestrzeni i nowego wiersza, więc nie musisz sprawiać, że wszystko jest okropne do czytania, wystarczy tablica: P
Peter Cordes
Możesz zapisać bajty kodu maszynowego, kopiując 1z push %rax/ pop %rdizamiast innego push-instant. Lub prościej, dla wartości, które nie są 64-bitowe, tj. Bez wskaźników, 2-bajtowe mov %eax, %edi. Ponadto Linux syscallnie niszczy rejestrów wejściowych, tylko raxwartością zwracaną i RCX + R11 z zapisanymi RIP i RFLAGS jako część działania syscallinstrukcji. Możesz więc wychodzić rdii rdxustawiać 1różne połączenia oraz używać różnych rejestrów. Ponadto RBX jest zachowywany na wywołaniach, więc nie jest tak naprawdę zapisywany w RBX Clobber main. Zdarza się, że kod startowy CRT nie ma znaczenia.
Peter Cordes
6

21 unikalnych znaków + 1 nieusuwalna nowa linia

%: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))<%%>
%>

Białe spacje nie są wymagane, z wyjątkiem pierwszej nowej linii. Skompilowane wg g ++ 7.3.0.

Użyte znaki: %:include<ostram>()f- .

Ulepszenia innych odpowiedzi:

  1. Usunięto średniki, zmieniając forpętle naif i rekurencję.
  2. Mam postać kosmiczną std::addressof(std::cout)->fill(), aka std::cout.fill().
jimmy23013
źródło
std :: adresof, miło!
Johan du Toit
2

21 20 unikalnych znaków z wyłączeniem białych znaków

Wszystkie białe znaki można zmienić na nowe linie.

%: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;

Wyjścia z segfault. Używane znaki: %:include<ostram>;-h.

Działa w tej konkretnej wersji kompilatora na 64-bitowym systemie Linux:

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

Z parametrem:

-std=c++17

Nawet wtedy nie jestem pewien, czy to zawsze zadziała. Może to również zależeć od wielu innych rzeczy. ciai ciusą przesunięciami pamięci podzielonymi przez 4 między ia iui i. ( intw tej wersji jest 32-bitowy). Może być konieczna zmiana liczb w celu dopasowania do rzeczywistego przesunięcia. Adresy byłyby znacznie bardziej przewidywalne, gdyby wszystkie były zawarte w strukturze. Niestety autow strukturach niedozwolona jest funkcja niestatyczna .

ejest tablicą 0-elementową typu elementu o rozmiarze (2 32 -1) × 2 32 bajty. Jeśli odpowiedni typ wskaźnika ejest zmniejszany, wyższa połowa wskaźnika byłaby zmniejszana o (2 32 -1), co jest równoważne zwiększaniu o jeden. To może zresetować zmniejszony licznik bez użycia znaku równości.

Bardziej rozsądna wersja, która powinna działać bardziej niezawodnie, ale używa jeszcze jednej postaci =:

%: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;

Nawet to nie działa w najnowszej wersji g ++, ponieważ wydaje się, że nie pozwala już na definiowanie mainw dowolnym typie.

Te dwa programy nie używają nawiasów. Ale wtedy średników wydaje się nie do uniknięcia.

jimmy23013
źródło
1

22 Unikalne znaki z wyjątkiem białych znaków. Oddziela liczby znakiem NUL, który wyświetla się poprawnie w systemie 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;
    %>
%>

Wypróbuj 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
źródło
std :: end jest znakiem NUL ( char(0)), a nie spacją ( char(32)w ASCII / UTF-8). en.cppreference.com/w/cpp/io/manip/ends . Wypróbowałem to na pulpicie Linuksa, żeby się upewnić, a wyjście wygląda tak 1234, jakby nie 1 2 3 4. Wygląda tak samo na wyjściu TIO!
Peter Cordes
@PeterCordes, OP nie określa, jak należy rozdzielić liczby ;-)
Johan du Toit
Naprawdę myślisz, że to oni zmarnowany znak na "dla " "jeśli mogliby używany iiiido oddzielania z '0'za 10203040? Myślę, że możesz argumentować, że w wyjściu binarnym programu nadal znajduje się separator, ale wskazanie tej zmiany i opisanie jej w języku angielskim jest ważne dla twojej odpowiedzi, ponieważ nie jest to zamiana zastępcza! Z przyjemnością usunę moją opinię, jeśli rozszerzysz swoją odpowiedź, aby to wyjaśnić i uzasadnić.
Peter Cordes
1
@PeterCordes, Punkt zajęty.
Johan du Toit