Ich bin neu im Code-Golfsport. Ich versuche, eine Rangliste von Ganzzahlen mit der geringsten Anzahl von eindeutigen Zeichen in C ++ zu generieren.
Nehmen wir an, wir bekommen eine ganze Zahl 4.
Wir werden die folgende Leiter generieren:
1
1 2
1 2 3
1 2 3 4
Kurz gesagt, mein Programm liest eine positive Ganzzahl von stdin und druckt diese Leiter zur Ausgabe. Ich versuche dies mit der geringstmöglichen Anzahl von eindeutigen Zeichen zu tun .
Mein Programm ist wie folgt:
#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;
}
}
Hier ist der Checker, mit dem ich die Anzahl der eindeutigen Zeichen in meinem Programm überprüft habe:
#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;
}
Vorzugsweise möchte ich weniger als 25 eindeutige Zeichen verwenden, um dieses Programm zu vervollständigen (ausgenommen Zeilenumbrüche, aber einschließlich Leerzeichen). Derzeit verwendet mein Programm 27. Ich bin nicht sicher, wie ich es weiter optimieren soll.
Könnte mich bitte jemand beraten, wie ich es weiter optimieren kann (in Bezug auf die Anzahl der verwendeten eindeutigen Zeichen)? Bitte beachten Sie, dass nur C ++ verwendet werden kann.
quelle
Antworten:
Ich glaube, ich habe es geschafft, das Zeichen = aus Ihrem Code zu entfernen, obwohl es jetzt erheblich langsamer ist
Es ist nicht schön, aber durch den Missbrauch eines Integer-Überlaufs können wir ohne Verwendung von = auf 0 zurückkehren
Auch mussten wir die Wachen ein wenig wechseln. Leider konnte ich wegen des Includes nicht alle neuen Zeilenzeichen entfernen (obwohl es in der Nähe ist), so dass dies möglicherweise die nächste Möglichkeit zur Untersuchung ist.
Bearbeiten: Die Zeit wird knapp, aber wenn Sie strstream und verschiedene andere Bibliotheken einbinden und verwenden, können Sie möglicherweise auch das Zeichen "wieder entfernen, indem Sie Ganzzahlen verwenden, um das richtige Zeichen für den Raum zu finden und es in das zu übergeben strstream
quelle
#include<std>und alle:s beseitigen . Keine großartige Codierungspraxis, aber das ist nebensächlich.using namespace std;was ein zusätzliches p für das: also net 0 verwenden würdeg, also netto Verlust, denke ich. Wenn dieser Code Gold waren, konnten wir die Bytezahl durch die Umbenennung reduzierenii,iiiundiiiizu anderen einzelnen Buchstaben - Namen (Pick alle anderen bereits verwendeten Buchstaben), aber das ist nicht das, was diese Herausforderung zu, so dass ich nicht erraten. Ich frage mich, ob es irgendwelche Vorteile bei der Verwendung gibtgetcund ob ich esputcanstelle voncin/coutversuchen müsste.signed char. Wenn Sie mit aktivierter Optimierung kompilieren, funktioniert dieser Code möglicherweise nicht mehr mit modernen Compilern, es sei denn, Siegcc -fwrapvdefinieren einen signierten Überlauf als Komplementumlauf von 2. Clang unterstützt-fwrapvauch. (unsignedInteger-Typen einschließlichunsigned charhaben in ISO C ++ ein genau definiertes Verhalten (Wrap-Around)). Es hängt von dem ABI , obcharistsigned charoderunsigned char, socharkann in Ordnung sein.Ich habe endlich 24 einzigartige Charaktere erhalten, indem ich die Antworten von @ExpiredData und @someone kombiniert habe. Außerdem hat die Verwendung des Datentyps short anstelle von int dazu beigetragen, mein Programm zu beschleunigen, da das Überlaufen eines kurzen Datentyps kürzer ist.
Mein Code ist wie folgt.
quelle
char iiiii;der letzten Variableninitialisierung.23 einzigartige Charaktere mit Digraphen. (25 ohne). Nein UB.
Verwenden Sie die geschweifte C ++ 11 -Initialisierungssyntax, um eine Ganzzahl unter
int var{};Vermeidung von=und auf Null zu setzen0. (Oder in Ihrem Fall global vermeideniiii). Dies gibt Ihnen eine Quelle für andere Nullen als globale Variablen (die im Gegensatz zu lokalen Variablen statisch auf Null initialisiert sind).Aktuelle Compiler akzeptieren diese Syntax standardmäßig, ohne dass spezielle Optionen aktiviert werden müssen.
(Der Integer-Wraparound-Trick macht Spaß und ist für Golfer mit deaktivierter Optimierung in Ordnung, aber signierter Überlauf ist undefiniertes Verhalten in ISO C ++. Durch Aktivieren der Optimierung werden diese Wraparound-Schleifen in Endlosschleifen umgewandelt, es sei denn, Sie kompilieren mit gcc / clang
-fwrapv, um einen signierten Integer-Überlauf zu erzielen -definiertes Verhalten: Komplementumlauf von 2.Unterhaltsame Tatsache: ISO C ++
std::atomic<int>hat einen gut definierten 2er-Komplement-Wrap-Around!int32_tEs muss das Zweierkomplement sein, wenn es überhaupt definiert ist, aber das Überlaufverhalten ist undefiniert, sodass es weiterhin ein typedef fürintoderlongauf jedem Computer sein kann, auf dem einer dieser Typen 32 Bit, kein Auffüllen und das Zweierkomplement ist.)Für diesen speziellen Fall nicht nützlich:
Sie können eine neue Variable auch mit geschweiften Klammern oder (mit einem nicht leeren Initialisierer) mit Parens für die direkte Initialisierung als Kopie einer vorhandenen Variablen initialisieren .
int a(b)oderint a{b}sind äquivalent zuint a = b;Aber
int b();deklariert eine Funktion statt einer Variable auf Null initialisiert.Sie können auch eine Null mit
int()oder erhaltenchar(), dh eine Null-Initialisierung eines anonymen Objekts.Wir können Ihre
<=Vergleiche durch<Vergleiche durch eine einfache logische Transformation ersetzen : Führen Sie das Inkrement des Schleifenzählers direkt nach dem Vergleich durch, anstatt am Ende der Schleife. IMO ist dies einfacher als die Alternativen, die die Leute vorgeschlagen haben, wie++im ersten Teil von afor(), um aus einer 0 eine 1 zu machen.Wir könnten Golf spielen,
for(int r{}; r++ < n;)aber IMO ist das für Menschen weniger einfach zu lesen. Wir optimieren nicht für die Gesamtanzahl der Bytes.Wenn wir bereits verwenden
h, könnten wir das'oder"für ein Leerzeichen speichern .Angenommen, eine ASCII- oder UTF-8-Umgebung hat das Leerzeichen den
charWert 32. Das können wir dann leicht in einer Variablen erstellencout << c;Und andere Werte können offensichtlich aus einer Folge von
++und Verdopplung erzeugt werden, basierend auf den Bits ihrer Binärdarstellung. Verschieben Sie effektiv eine 0 (nichts) oder 1 (++) in das LSB, bevor Sie es in eine neue Variable verdoppeln.Diese Version verwendet
hanstelle von'oder".Es ist viel schneller als jede der vorhandenen Versionen (ohne auf eine lange Schleife angewiesen zu sein) und es ist frei von undefiniertem Verhalten . Es kompiliert ohne Warnungen mit
g++ -O3 -Wall -Wextra -Wpedanticund mitclang++.-std=c++11es ist optional. Es ist legal und portabel ISO C ++ 11 :)Es ist auch nicht auf globale Variablen angewiesen. Und ich habe es mit Variablennamen, die eine Bedeutung haben, lesbarer gemacht.
Anzahl der eindeutigen Bytes: 25 , ohne die Kommentare, die ich entfernt habe
g++ -E. Und ohne Leerzeichen und Zeilenvorschub wie bei Ihrem Counter. Ich habesed 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -icdieses Askubuntu verwendet, um die Vorkommen der einzelnen Charaktere zu zählen, und habe es weitergeleitet, umwczu zählen, wie viele eindeutige Charaktere ich hatte.Die einzigen 2
fZeichen sind vonfor. Wir könntenwhilestattdessen Schleifen verwenden, wenn wir eine Verwendung für hattenw.Wir könnten die Schleifen möglicherweise in einen Assembler-Stil umschreiben
i < r || goto some_label;, um einen bedingten Sprung am Ende der Schleife zu schreiben, oder was auch immer. (Aber mitorstatt||). Nein, das geht nicht.gotoist eine Anweisung wieifin Perl und kann keine Unterkomponente eines Ausdrucks sein. Andernfalls hätten wir es verwenden können, um die Zeichen(und zu entfernen).Wir konnten den Handel
ffürgmitif(stuff) goto label;stattfor, und beide Schleifen immer mindestens 1 Iteration laufen , so dass wir nur an der Unterseite eine Schleife-Zweig benötigen würde, wie eine normale asmdo{}whileSchleifenstruktur. Angenommen, der Benutzer gibt eine Ganzzahl> 0 ein ...Digraphen und Trigraphen
Glücklicherweise wurden Trigraphen ab ISO C ++ 17 entfernt, sodass wir sie nicht mehr verwenden müssen,
??>anstatt}für die letzte C ++ - Revision ausschließlich Golf zu spielen.Aber nur Trigraphen im Speziellen: ISO C ++ 17 hat immer noch Digraphen wie
:>für]und%>für}. Also auf Kosten der Verwendung%, können wir beide vermeiden{und}, und verwenden Sie%:für#eine Netto-Einsparung von 2 weniger eindeutigen Zeichen.Und C ++ hat Operator-Schlüsselwörter wie
notfür den!Operator oderbitorfür den|Operator. Mitxor_eqfor^=können Sie eine Variable auf Null setzeni xor_eq i, sie enthält jedoch mehrere Zeichen, die Sie nicht verwendet haben.Current
g++ignoriert Trigraphen bereits standardmäßig, auch ohne-std=gnu++17; Sie müssen verwenden-trigraphs, um sie zu aktivieren, oder-std=c++11etwas, um einer ISO-Norm, die sie enthält, strikt zu entsprechen.23 eindeutige Bytes:
Probieren Sie es online!
In der endgültigen Version wird
'anstelle vonhoder"für das Leerzeichen ein einfaches Anführungszeichen verwendet. Ich wollte daschar c{}Zeug nicht digraphen, also habe ich es gelöscht. Das Drucken eines Zeichens ist effizienter als das Drucken einer Zeichenfolge, also habe ich das verwendet.Histogramm:
Das Leerzeichen (noch ungelöst)
In einer jetzt gelöschten Antwort schlug Johan Du Toit die Verwendung eines alternativen Trennzeichens vor
std::ends. Das ist ein NUL-Zeichenchar(0)und wird auf den meisten Terminals als Breite Null gedruckt. So würde die Ausgabe aussieht1234, nicht1 2 3 4. Oder schlimmer noch, getrennt durch Müll an irgendetwas, das nicht lautlos zusammenbrach'\0'.Wenn Sie ein beliebiges Trennzeichen verwenden können, können Sie die Ziffer
0einfach mit erstellencout << some_zeroed_var. Aber niemand will10203040, das ist noch schlimmer als kein Trennzeichen.Ich habe versucht, einen Weg zu finden, um eine
std::stringHolding" "ohne Verwendungchareines String-Literal zu erstellen . Vielleicht etwas anhängen? Vielleicht mit einem Digraphen[], um das erste Byte auf einen Wert von zu setzen32, nachdem über einen der Konstruktoren eines mit der Länge 1 erstellt wurde?Johan schlug auch die
std::iosMitgliedsfunktion fill () vor, die das aktuelle Füllzeichen zurückgibt. Die Standardeinstellung für einen Stream iststd::basic_ios::init()und' '.std::cout << i << std::cout.fill();ersetzt<< ' ';aber verwendet.statt'.Mit
-, können wir einen Zeiger nehmencoutund die Verwendung->fill()der Memberfunktion aufzurufen:std::cout << (bitand std::cout)->fill(). Oder auch nicht, wir wurden mit nichtbentweder so können wir auch genutzt haben&statt dessen lexikalische Äquivalentbitand.Aufrufen einer Mitgliedsfunktion ohne
.oder->Setzen Sie es in eine Klasse und definieren Sie
operator char() { fill(); }Dann
ss s{}vor der Schleife undstd::cout << i << s;innerhalb der Schleife. Großartig, es kompiliert und funktioniert einwandfrei , aber wir mussten Gebrauchpundhfüroperator char(), für einen Nettoverlust von 1. Mindestens wir vermiedenbMitgliederfunktionen zu machen ,publicindem Siestructstattclass. (Und wir könnten die Vererbung mit überschreiben,protectedfalls das jemals hilft).quelle
cout.fill()fromstd::ios, aber wir haben es vorher nicht benutzt.Vielleicht können wir es irgendwie aufrufen, indem wir einen Zeiger nehmen und->fill()auf eine Mitgliedsfunktion verweisen? Gibt irgendetwas einen Zeiger aufcouteinen anderen Stream zurück?<< (bitand std::cout)->fill()kompiliert, aber verwendet-. (Ist trotz des Tokennamensbitandnur ein lexikalisches Äquivalent zu&, nicht speziell zum bitweisen Operator und zum Operator. Sie fungiert auch als Operatoradresse.) Hmm, gibt es Template- oder Lambda-Informationen, die einen Zeiger auf eine Member-Funktion abrufen können? das können wir()ohne.oder->?std::ios::leftes in gcc als 32 definiert ist, aber ich konnte nicht wirklich einen Weg finden, dies auszunutzen. Ich glaube, ich lasse diesen los und erledige ein paar aktuelle Arbeiten :-)int32 zu erstellen ist kein Problem, meine Antwort zeigt bereits, wie man das mit++einerint c{};Null anfängt . Aber ja, ich gehe nicht das Kaninchenloch hinunter, um Lambdas, Vorlagen oder ähnliches zu untersuchenstd::function. Oder diestd::stringIdee. Aber wir sind nicht daran gewöhntg, dass wir tatsächlich eine deklarieren können,std::stringohne zu verlieren. Meine Idee,gotoanstatt zu verwenden, istfornicht aufgegangen.decltype(something)könnte uns einenchartyp geben, kostet uns aber eineny.struct ss : std::ostream { operator auto () { return fill(); } };aber es hilft nicht viel.Nur C ++ (gcc) x86_64 Linux,
9295 8900 8712 68125590 Bytes, 18 eindeutige ZeichenProbieren Sie es online!
Dies basiert auf Ideen aus dieser PPCG-Antwort . Ein Maschinensprachenprogramm wird als Array von 32-Bit-Ints ausgedrückt, von denen jedes als Summe von dargestellt wird
1+11+111.... Es stellt sich heraus, dass es möglicherweise effizienter ist, dasxalsysolches zu codiereny%(1<<32)==x. Das codierte Maschinensprachenprogramm ist das folgende... der auf dem folgenden C-Code basiert.
Bearbeiten: Akzeptiert jetzt Eingaben von
stdinanstelle vonargv[1]. Vielen Dank an @ ASCII-only und @PeterCordes für ihre Vorschläge!Edit4:
Etwasdeutlich verbesserte Kodierung.quelle
-wpls Flagge: P (auch können Sie umbenenneniizua)gcc -zexecstackdafür, oder? Daint m[]geht es nichtconst. (Und die neuesten Toolchains haben.rodatasowieso eine nicht ausführbare Seite hinzugefügt, so dass sie zBconst int m[]auf meinem Arch Linux-System mitgcc8.2.1 20181127 undld(GNU Binutils) 2.31.1 nicht funktionieren.) Wie auch immer, Sie haben vergessen, dies in Ihrer Antwort zu erwähnen. aber es ist in Ihrem TIO-Link.1mitpush %rax/pop %rdianstelle eines anderen Push-Direkt kopieren . Oder einfacher gesagt, für Werte, die nicht 64-Bit sind, dh Nicht-Zeiger, 2 Bytemov %eax, %edi. Außerdem zerstört Linuxsyscallseine Eingaberegister nicht, nurraxmit dem Rückgabewert und RCX + R11 mit gespeichertem RIP und RFLAGS als Teil der Funktionsweise dessyscallBefehls. So verlassen Sie könnenrdiundrdxsetzen1über Anrufe und verschiedene regs verwenden. RBX bleibt auch bei Anrufen erhalten, so dass es nicht wirklich sicher ist, die RBX des Hauptgeräts zu löschen. Es funktioniert, weil es den CRT-Startcode nicht interessiert.21 eindeutige Zeichen + 1 nicht entfernbarer Zeilenvorschub
Leerzeichen sind bis auf die erste Zeile nicht erforderlich. Kompiliert in g ++ 7.3.0.
Verwendete Zeichen:
%:include<ostram>()f-.Verbesserungen bei anderen Antworten:
forSchleifen in geändert wurdenifund die Rekursion geändert wurden.std::addressof(std::cout)->fill(), akastd::cout.fill().quelle
2120 eindeutige Zeichen ohne LeerzeichenAlle Leerzeichen können in Zeilenumbrüche umgewandelt werden.
Beendet mit Segfault. Verwendete Zeichen:
%:include<ostram>;-h.Es funktioniert in dieser speziellen Compiler-Version auf einem 64-Bit-Linux:
Mit dem Parameter:
Selbst dann bin ich mir nicht sicher, ob es immer funktionieren würde. Es kann auch von vielen anderen Dingen abhängen.
ciaundciusind die Speicheroffsets geteilt durch 4 zwischeniaiuundi. (intIn dieser Version sind es 32 Bit.) Möglicherweise müssen Sie die Zahlen ändern, um sie an den tatsächlichen Versatz anzupassen. Die Adressen wären viel vorhersehbarer, wenn sie alle in einer Struktur enthalten wären. Leiderautoist in einer Struktur nicht statisch erlaubt.eist ein 0-Elemente-Array eines Elementtyps mit einer Größe von (2 32 -1) × 2 32 Bytes. Wenn der entsprechende Zeigertyp vonedekrementiert wird, wird die höhere Hälfte des Zeigers um (2 32) dekrementiert -1) , was einer Inkrementierung um eins entspricht. Dies könnte den dekrementierten Zähler ohne Verwendung des Gleichheitszeichens zurücksetzen.Eine vernünftigere Version, die zuverlässiger funktionieren sollte, aber ein Zeichen mehr verwendet
=:Auch dies funktioniert in der neuesten Version von g ++ nicht, da es nicht mehr möglich zu sein scheint,
maineinen beliebigen Typ zu definieren.Diese beiden Programme verwenden keine Klammern. Aber dann scheinen Semikolons nicht vermeidbar zu sein.
quelle
22 Eindeutige Zeichen ohne Leerzeichen. Trennt die Zahlen durch ein NUL-Zeichen, das unter Windows korrekt angezeigt wird.
Probieren Sie es online aus
Histogramm:
quelle
char(0)), kein Leerzeichen (char(32)in ASCII / UTF-8). de.cppreference.com/w/cpp/io/manip/ends . Ich habe es auf meinem Linux-Desktop versucht, um sicherzugehen, und die Ausgabe sieht1234nicht so aus1 2 3 4. Auf Ihrem TIO-Ausgang sieht es genauso aus!"für verschwendet," "wenn sie sich früheriiiimit'0'für hätten trennen können10203040? Ich vermute, Sie können ein Argument dafür anführen, dass sich noch ein Trennzeichen in der Binärausgabe des Programms befindet, aber es ist wichtig, dass Sie auf diese Änderung hinweisen und sie auf Englisch beschreiben, da dies kein Ersatz ist! Ich würde gerne meine Ablehnung entfernen, wenn Sie Ihre Antwort erweitern, um dies zu erklären und zu rechtfertigen.