Je suis nouveau dans le sport du golf de code. J'essaie de générer une échelle d'entiers en utilisant le moins de caractères uniques en C ++.
Disons que l'on nous donne un entier 4.
Nous générerons l'échelle suivante:
1
1 2
1 2 3
1 2 3 4
En bref, mon programme lira un entier positif depuis stdin et imprimera cette échelle dans la sortie. J'essaie de le faire avec le moins de caractères uniques possible.
Mon programme est le suivant:
#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;
}
}
Voici le vérificateur que j'ai utilisé pour vérifier le nombre de caractères uniques dans mon programme:
#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;
}
De préférence, je souhaite utiliser moins de 25 caractères uniques pour terminer ce programme (à l'exclusion des caractères de nouvelle ligne, mais y compris les espaces). Actuellement, mon programme utilise 27. Je ne sais pas comment l'optimiser davantage.
Quelqu'un pourrait-il me conseiller sur la façon de l'optimiser davantage (en termes de nombre de caractères uniques utilisés)? Veuillez noter que seul C ++ peut être utilisé.
la source
Réponses:
Je crois que j'ai réussi à supprimer le caractère = de votre code, bien qu'il soit maintenant beaucoup plus lent
Ce n'est pas joli, mais en abusant du débordement d'entier, nous pouvons revenir à 0 sans utiliser =
Nous avons également dû changer un peu les gardes. Malheureusement, à cause de l'inclusion, je ne pouvais pas me débarrasser de tous les nouveaux personnages de ligne (bien que ce soit proche), ce qui pourrait être la prochaine piste d'enquête.
Edit: manque de temps pour l'instant, mais si vous incluez et utilisez strstream et diverses autres bibliothèques, je pense que vous pourrez peut-être aussi supprimer le caractère ", en utilisant à nouveau des entiers pour arriver au caractère correct pour l'espace et en le passant dans le strstream
la source
#include<std>et éliminer tous les:art. Ce n'est pas une excellente pratique de codage, mais ce n'est pas la question.using namespace std;ce qui utiliserait un p supplémentaire pour le: donc un net 0gperte nette, donc je suppose. S'il s'agissait de code or, nous pourrions réduire le nombre d'octets en renommantii,iiiet eniiiid'autres noms de lettre unique (choisissez toutes les autres lettres déjà utilisées), mais ce n'est pas le but de ce défi, donc je suppose que non. Je me demande s'il y aurait des gains à utilisergetcetputcau lieu decin/cout, je devrais l'essayer.signed char. Si vous compilez avec l'optimisation activée, ce code peut rompre avec les compilateurs modernes, à moins que vous n'utilisiezgcc -fwrapvpour rendre le débordement signé bien défini comme bouclage du complément à 2. clang prend également en charge-fwrapv. (unsignedles types entiers, notamment,unsigned charont un comportement bien défini (bouclage) dans ISO C ++). Cela dépend de l'ABI, que cecharsoitsigned charou nonunsigned char, celacharpeut donc être ok.J'ai finalement obtenu 24 caractères uniques en combinant les réponses de @ExpiredData et @someone. En outre, l'utilisation du type de données court au lieu de int a aidé à accélérer mon programme car il prend plus de temps pour déborder un type de données court.
Mon code est le suivant.
la source
char iiiii;, la dernière des initialisations de variables.23 caractères uniques à l'aide de Digraphs. (25 sans). Pas d'UB.
Utilisez la syntaxe d'initialisation renforcée C ++ 11 pour lister-initialiser un entier à zéro en
int var{};évitant=et0. (Ou dans votre cas, en évitant globaliiii). Cela vous donne une source de zéros autres que les variables globales (qui sont initialisées statiquement à zéro, contrairement aux locaux).Les compilateurs actuels acceptent cette syntaxe par défaut, sans avoir à activer d'options spéciales.
(L'astuce de bouclage entier est amusante, et ok pour le golf avec l'optimisation désactivée, mais le débordement signé est un comportement indéfini dans ISO C ++. L'activation de l'optimisation transformera ces boucles enveloppantes en boucles infinies, sauf si vous compilez avec gcc / clang
-fwrapvpour donner un puits de débordement d'entier signé bien - comportement défini: enveloppement du complément à 2.Fait amusant: ISO C ++
std::atomic<int>a un complément de 2 bien défini!int32_tdoit être le complément de 2 s'il est défini, mais le comportement de débordement n'est pas défini, il peut donc toujours être un typedef pourintoulongsur n'importe quelle machine où l'un de ces types est de 32 bits, sans remplissage et complément de 2.)Inutile pour ce cas spécifique:
Vous pouvez également initialiser une nouvelle variable en tant que copie d'une variable existante, avec des accolades ou (avec un initialiseur non vide), des parens pour l'initialisation directe .
int a(b)ouint a{b}équivalent àint a = b;Mais
int b();déclare une fonction au lieu d'une variable initialisée à zéro.En outre, vous pouvez obtenir un zéro avec
int()ouchar(), c'est -à- dire l' initialisation zéro d'un objet anonyme.Nous pouvons remplacer vos
<=comparaisons par des<comparaisons par une simple transformation logique : effectuez l'incrémentation du compteur de boucles juste après la comparaison, plutôt qu'en bas de la boucle. L'OMI est plus simple que les alternatives proposées par les gens, comme utiliser++dans la première partie de afor()pour transformer un 0 en un 1.Nous pourrions jouer au golf,
for(int r{}; r++ < n;)mais l'OMI est moins facile à lire pour les humains. Nous n'optimisons pas le nombre total d'octets.Si nous utilisions déjà
h, nous pourrions enregistrer le'ou"pour un espace.En supposant un environnement ASCII ou UTF-8, l'espace est un
charavec une valeur 32. Nous pouvons créer cela dans une variable assez facilement, puiscout << c;Et d'autres valeurs peuvent évidemment être créées à partir d'une séquence
++et d'un doublement, en fonction des bits de leur représentation binaire. Décaler efficacement un 0 (rien) ou 1 (++) dans le LSB avant de doubler dans une nouvelle variable.Cette version utilise à la
hplace de'ou".Il est beaucoup plus rapide que l'une des versions existantes (ne s'appuyant pas sur une longue boucle) et est exempt de comportement indéfini . Il se compile sans avertissement avec
g++ -O3 -Wall -Wextra -Wpedanticet avecclang++.-std=c++11est facultatif. Il est légal et portable ISO C ++ 11 :)Il ne dépend pas non plus des variables globales. Et je l'ai rendu plus lisible par l'homme avec des noms de variables qui ont un sens.
Nombre d'octets uniques: 25 , à l' exclusion des commentaires avec lesquels j'ai supprimé
g++ -E. Et à l'exclusion de l'espace et de la nouvelle ligne comme votre comptoir. J'ai utilisé àsed 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -icpartir de cet askubuntu pour compter les occurrences de chaque personnage, etwcje l'ai canalisé pour compter le nombre de caractères uniques que j'avais.Les 2 seuls
fcaractères sont defor. Nous pourrions utiliser deswhileboucles à la place si nous en avions une utilisationw.Nous pourrions éventuellement réécrire les boucles dans un style en langage assembleur
i < r || goto some_label;pour écrire un saut conditionnel au bas de la boucle, ou autre chose. (Mais en utilisantorau lieu de||). Non, ça ne marche pas.gotoest une instruction commeifet ne peut pas être un sous-composant d'une expression comme il le peut en Perl. Sinon, nous aurions pu l'utiliser pour supprimer les caractères(et).Nous pourrions échanger
fpourgavecif(stuff) goto label;au lieu defor, et les deux boucles exécutent toujours au moins 1 itération, nous n'aurions donc besoin que d'une seule branche de boucle en bas, comme unedo{}whilestructure de boucle asm normale . En supposant que l'utilisateur entre un entier> 0 ...Digraphes et trigraphes
Heureusement, les trigraphes ont été supprimés à partir d'ISO C ++ 17 , nous n'avons donc pas à utiliser à la
??>place de}si nous sommes uniques pour la révision C ++ la plus récente.Mais uniquement les trigraphes: ISO C ++ 17 a toujours des digraphes comme
:>pour]et%>pour}. Ainsi , au coût d'utilisation%, nous pouvons éviter à la fois{et}, et utiliser%:pour#une économie nette de 2 moins de caractères uniques.Et C ++ a des mots-clés d'opérateur comme
notpour l'!opérateur, oubitorpour l'|opérateur. Avecxor_eqfor^=, vous pouvez mettre à zéro une variable aveci xor_eq i, mais elle contient plusieurs caractères que vous n'utilisiez pas.Le courant
g++ignore déjà les trigraphes par défaut même sans-std=gnu++17; vous devez utiliser-trigraphspour les activer, ou-std=c++11quelque chose pour une stricte conformité à une norme ISO qui les inclut.23 octets uniques:
Essayez-le en ligne!
La version finale utilise un
'guillemet simple au lieu dehou"pour le séparateur d'espace. Je ne voulais pas digraphier lechar c{}truc alors je l'ai supprimé. L'impression d'un caractère est plus efficace que l'impression d'une chaîne, donc je l'ai utilisé.Histogramme:
Le séparateur d'espace (toujours non résolu)
Dans une réponse maintenant supprimée, Johan Du Toit a proposé d'utiliser un séparateur alternatif, en particulier
std::ends. C'est un caractère NULchar(0), et s'imprime en largeur nulle sur la plupart des terminaux. Ainsi, la sortie ressemblerait1234, non1 2 3 4. Ou pire, séparés par des ordures sur tout ce qui ne s'est pas effondré en silence'\0'.Si vous pouvez utiliser un séparateur arbitraire, lorsque le chiffre
0est facile à créer aveccout << some_zeroed_var. Mais personne ne veut10203040, c'est encore pire que pas de séparateur.J'essayais de penser à un moyen de créer un
std::stringholding a" "sans utilisercharou un string littéral. Peut-être y ajouter quelque chose? Peut-être avec un digraphe pour[]définir le premier octet sur une valeur de32, après en avoir créé un de longueur 1 via l'un des constructeurs?Johan a également suggéré la
std::iosfonction membre fill () qui renvoie le caractère de remplissage actuel. La valeur par défaut pour un flux est définie parstd::basic_ios::init()et est' '.std::cout << i << std::cout.fill();remplace<< ' ';mais utilise à la.place de'.Avec
-, nous pouvons prendre un pointeur verscoutet à utiliser->fill()pour appeler la fonction de membre:std::cout << (bitand std::cout)->fill(). Ou pas, nous n'utilisions pasbnon plus, donc nous pourrions aussi bien avons utilisé au&lieu de son équivalent lexical,bitand.Appel d'une fonction membre sans
.ou->Mettez-le dans une classe et définissez
operator char() { fill(); }Puis
ss s{}avant la boucle, etstd::cout << i << s;à l'intérieur de la boucle. Génial, il compile et fonctionne correctement, mais nous avons dû utiliserpethpouroperator char(), pour une perte nette de 1. Au moins, nous avons évitébde créer des fonctions membrespublicen utilisantstructau lieu declass. (Et nous pourrions remplacer l'héritageprotectedau cas où cela aiderait).la source
cout.fill()fromstd::ios, mais nous n'utilisions pas auparavant.Peut-être pouvons-nous l'appeler d'une manière ou d'une autre en prenant un pointeur et en utilisant->fill()une fonction membre? Est-ce que quelque chose renvoie un pointeur verscoutou tout autre flux?<< (bitand std::cout)->fill()compile, mais utilise-. (Malgré le nom du jeton,bitandest juste un équivalent lexical&, pas spécifiquement l'opérateur au niveau du bit et. Il fonctionne également comme l'opérateur de l'adresse.) Hmm, existe-t-il des modèles ou des éléments lambda qui peuvent obtenir un pointeur vers une fonction membre que nous pouvons()sans utiliser.ou->?std::ios::leftdéfinie comme 32, dans gcc, mais je ne pouvais pas vraiment trouver un moyen d'en tirer parti. Je pense que je vais laisser tomber celui-ci et faire un travail réel :-)int32 n'est pas un problème, ma réponse montre déjà comment faire cela en++partant d'unint c{};zéro. Mais ouais, je ne vais pas dans le trou du lapin pour chercher des lambdas, des modèles oustd::function. Ou l'std::stringidée. Mais nous ne l'utilisonsgpas, nous ne pouvons pas déclarer unstd::stringsans perdre; mon idée d'utilisergotoau lieu deforn'a pas fonctionné.decltype(something)pourrait nous donner unchartype, mais nous coûte uny.struct ss : std::ostream { operator auto () { return fill(); } };mais cela n'aide pas beaucoup.C ++ (gcc) x86_64 Linux uniquement,
9295 8900 8712 68125590 octets, 18 caractères uniquesEssayez-le en ligne!
Ceci est basé sur les idées de cette réponse PPCG . Un programme en langage machine est exprimé sous la forme d'un tableau de 32 bits, chacun étant représenté par une somme de
1+11+111.... Il s'avère qu'il peut être plus efficace de coderxcommeytely%(1<<32)==x. Le programme en langage machine codé est le suivant... qui est basé sur le code C suivant.
Modifier: accepte désormais les entrées de
stdinau lieu deargv[1]. Merci à @ ASCII et @PeterCordes pour leurs suggestions!Edit4: encodage
légèrementamélioré.la source
-wdrapeau pls: P (vous pouvez également renommeriiàa)gcc -zexecstack, non? Parce queint m[]nonconst. (Et les chaînes d'outils récentes placées.rodatadans une page non exécutable de toute façon, donc mêmeconst int m[]ne fonctionne pas, par exemple, sur mon système Arch Linux avecgcc8.2.1 20181127 etld(GNU Binutils) 2.31.1.) Quoi qu'il en soit, vous avez oublié de le mentionner dans votre réponse, mais c'est dans votre lien TIO.1avecpush %rax/pop %rdiau lieu d'un autre push-immediate. Ou plus simplement, pour les valeurs qui ne sont pas 64 bits, c'est-à-dire non pointeurs, 2 octetsmov %eax, %edi. En outre, Linuxsyscallne détruit pas ses registres d'entrée, uniquementraxavec la valeur de retour et RCX + R11 avec RIP et RFLAGS enregistrés dans le cadre du fonctionnement de l'syscallinstruction. Ainsi, vous pouvez quitterrdietrdxdéfinir plusieurs1appels, et utiliser différentes regs. De plus, RBX est préservé des appels, il n'est donc pas vraiment enregistré dans le RBX de clobber main. Il se trouve que cela fonctionne parce que le code de démarrage CRT s'en fiche.21 caractères uniques + 1 nouvelle ligne inamovible
Les espaces blancs ne sont pas requis, sauf pour la première nouvelle ligne. Compilé dans g ++ 7.3.0.
Les caractères utilisés:
%:include<ostram>()f-.Améliorations apportées à d'autres réponses:
forbouclesifet la récursivité.std::addressof(std::cout)->fill(), aliasstd::cout.fill().la source
2120 personnages uniques hors espaces blancsTous les espaces blancs peuvent être modifiés en nouvelles lignes.
Quitte avec segfault. Les caractères utilisés:
%:include<ostram>;-h.Il fonctionne dans cette version de compilateur spécifique sur un Linux 64 bits:
Avec le paramètre:
Même alors, je ne suis pas sûr que cela fonctionnerait toujours. Cela peut aussi dépendre de beaucoup d'autres choses.
ciaetciusont les décalages de mémoire divisés par 4 entreiaiueti. (int32 bits dans cette version.) Il se peut que vous deviez modifier les nombres pour qu'ils correspondent au décalage réel. Les adresses seraient beaucoup plus prévisibles si elles sont toutes contenues dans une structure. Malheureusement non statiqueauton'est pas autorisé dans une structure.eest un tableau à 0 éléments d'un type d'élément avec une taille de (2 32 -1) × 2 32 octets. Si le type de pointeur correspondant deeest décrémenté, la moitié supérieure du pointeur serait décrémentée de (2 32 -1), ce qui équivaut à une incrémentation de un. Cela pourrait réinitialiser le compteur décrémenté sans utiliser le signe d'égalité.Une version plus raisonnable qui devrait fonctionner de manière plus fiable, mais utilise un caractère de plus
=:Même cela ne fonctionne pas dans la dernière version de g ++ car il ne semble plus permettre de définir
maindans un type arbitraire.Ces deux programmes n'utilisent pas de parenthèses. Mais les points-virgules ne semblent pas évitables.
la source
22 Personnages uniques hors espaces blancs. Sépare les nombres par un caractère NUL qui s'affiche correctement sous Windows.
Essayez-le en ligne
Histogramme:
la source
char(0)), pas un espace (char(32)en ASCII / UTF-8). en.cppreference.com/w/cpp/io/manip/ends . Je l'ai essayé sur mon bureau Linux juste pour m'assurer, et la sortie ressemble1234, non1 2 3 4. Il en va de même sur votre sortie TIO!"pour" "s'ils auraient puiiiise séparer de'0'pour10203040? Je suppose que vous pouvez démontrer qu'il y a toujours un séparateur dans la sortie binaire du programme, mais souligner ce changement et le décrire en anglais est important pour votre réponse, car ce n'est pas un remplacement direct! Je serais heureux de supprimer mon downvote si vous développez votre réponse pour expliquer et justifier cela.