Eu sou novo no esporte do código de golfe. Eu estou tentando gerar uma escada de números inteiros usando o menor número de caracteres exclusivos em C ++.
Digamos que recebemos um número inteiro 4.
Vamos gerar a seguinte escada:
1
1 2
1 2 3
1 2 3 4
Em resumo, meu programa lerá um número inteiro positivo de stdin e imprimirá essa escada na saída. Estou tentando fazer isso com o menor número possível de caracteres únicos .
Meu programa é o seguinte:
#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;
}
}
Aqui está o verificador que eu usei para verificar o número de caracteres únicos no meu programa:
#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 preferência, desejo usar menos de 25 caracteres únicos para concluir este programa (excluindo caracteres de nova linha, mas incluindo espaço em branco). Atualmente, meu programa usa 27. Não sei como otimizá-lo ainda mais.
Alguém poderia me aconselhar sobre como otimizá-lo ainda mais (em termos do número de caracteres únicos usados)? Observe que apenas C ++ pode ser usado.
fonte
Respostas:
Acredito que consegui remover o caractere = do seu código, embora agora seja significativamente mais lento
Não é bonito, mas ao abusar do excesso de números inteiros, podemos voltar a 0 sem usar =
Também tivemos que mudar um pouco os guardas. Infelizmente, por causa da inclusão, não consegui me livrar de todos os novos caracteres de linha (embora estejam próximos), para que possa ser o próximo caminho para investigação.
Edit: Sem tempo, por enquanto, mas se você incluir e usar strstream e várias outras bibliotecas, acho que também poderá remover o caractere ", novamente usando números inteiros para chegar ao caractere correto por espaço e passá-lo para o corrente
fonte
#include<std>e eliminar todos os:s. Não é uma boa prática de codificação, mas isso não vem ao caso.using namespace std;o que usar um p adicional para o: assim uma rede 0gperda tão líquida, eu acho. Se fosse um código de ouro, poderíamos reduzir a contagem de bytes renomeandoii,iiieiiiipara outros nomes de letras únicas (escolha outras letras já usadas), mas não é esse o objetivo deste desafio, então acho que não. Eu estou querendo saber se haveria algum ganho para usargetce, emputcvez decin/cout, teria que tentar.signed char. Se você compilar com a otimização ativada, esse código poderá ser rompido com os compiladores modernos, a menos que você usegcc -fwrapvpara tornar o estouro assinado bem definido como o complemento do 2. clang suporta-fwrapvtambém. (unsignedtipos inteiros, incluindounsigned charum comportamento bem definido (wrap-around) no ISO C ++). Depende da ABI secharésigned charouunsigned char, entãocharpode ser ok.Finalmente consegui 24 caracteres únicos, combinando as respostas de @ExpiredData e @someone. Além disso, o uso do tipo de dados curto em vez de int ajudou a acelerar o meu programa, pois leva um tempo menor para estourar um tipo de dados curto.
Meu código é o seguinte.
fonte
char iiiii;, a última das inicializações de variáveis.23 caracteres únicos usando Digraphs. (25 sem). Sem UB.
Use a sintaxe do inicializador em C ++ 11 para inicializar em lista um número inteiro para zero,
int var{};evitando=e0. (Ou no seu caso, evitando globaliiii). Isso fornece uma fonte de zeros diferentes de variáveis globais (que são inicializadas estaticamente para zero, diferentemente dos locais).Os compiladores atuais aceitam essa sintaxe por padrão, sem precisar habilitar nenhuma opção especial.
(O truque envolvente de número inteiro é divertido e aceitável para jogar golfe com a otimização desativada, mas o estouro assinado é um comportamento indefinido no ISO C ++. A ativação da otimização transformará esses loops em envolventes em loops infinitos, a menos que você compile com gcc / clang
-fwrapvpara fornecer um estouro inteiro assinado comportamento definido: complemento do 2 envolvente.Curiosidade: o ISO C ++
std::atomic<int>possui um complemento bem definido do 2!int32_té necessário que seja o complemento de 2, se definido, mas o comportamento de estouro é indefinido, portanto ainda pode ser um typedef paraintoulongem qualquer máquina em que um desses tipos seja de 32 bits, sem preenchimento e o complemento de 2).Não é útil para este caso específico:
Você também pode inicializar uma nova variável como uma cópia de uma existente, com chaves ou (com um inicializador não vazio), parens para inicialização direta .
int a(b)ouint a{b}são equivalentes aint a = b;Mas
int b();declara uma função em vez de uma variável inicializada como zero.Além disso, você pode obter um zero com
int()ouchar(), ou seja, com a inicialização zero de um objeto anônimo.Podemos substituir suas
<=comparações por<comparadas por uma transformação lógica simples : faça o incremento do contador de loop logo após a comparação, em vez de na parte inferior do loop. Na IMO, isso é mais simples do que as alternativas que as pessoas propuseram, como usar++na primeira parte de afor()para transformar 0 em 1.Poderíamos jogar isso até a
for(int r{}; r++ < n;)IMO, mas é menos fácil para os humanos lerem. Não estamos otimizando a contagem total de bytes.Se já estivéssemos usando
h, poderíamos salvar o espaço'ou"um espaço.Assumindo um ambiente ASCII ou UTF-8, o espaço é um
charcom valor 32. Podemos criar isso em uma variável com bastante facilidade e, em seguida,cout << c;E outros valores podem obviamente ser criados a partir de uma sequência
++e duplicação, com base nos bits de sua representação binária. Mudando efetivamente um 0 (nada) ou 1 (++) para o LSB antes de dobrar para uma nova variável.Esta versão usa em
hvez de'ou".É muito mais rápido que qualquer uma das versões existentes (sem depender de um loop longo) e está livre de comportamento indefinido . Ele compila sem advertências com
g++ -O3 -Wall -Wextra -Wpedantice comclang++.-std=c++11é opcional. É ISO C ++ 11 legal e portátil :)Também não depende de variáveis globais. E tornei mais legível para humanos com nomes de variáveis que têm um significado.
Contagem de bytes únicos: 25 , excluindo os comentários com os quais eu removi
g++ -E. E excluindo espaço e nova linha como seu contador. Eu useised 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -icneste askubuntu para contar ocorrências de cada caractere e canalizei issowcpara contar quantos caracteres únicos eu tinha.Os únicos 2
fcaracteres são defor. Emwhilevez disso, poderíamos usar loops se tivéssemos um usow.Poderíamos reescrever os loops em um estilo de linguagem assembly
i < r || goto some_label;para escrever um salto condicional na parte inferior do loop, ou o que seja. (Mas usando emorvez de||). Não, isso não funciona.gotoé uma declaração comoife não pode ser um subcomponente de uma expressão como no Perl. Caso contrário, poderíamos usá-lo para remover os caracteres(e).Poderíamos negociar
fparagcomif(stuff) goto label;em vez defor, e ambos os loops sempre executar pelo menos 1 iteração de modo que só iria precisar de um loop-filial na parte inferior, como uma normal, asmdo{}whileestrutura de loop. Supondo que o usuário insira um número inteiro> 0 ...Digraphs e Trigraphs
Felizmente, os trigrafos foram removidos a partir da ISO C ++ 17, portanto, não precisamos usá-lo em
??>vez de}jogar golfe exclusivo para a revisão mais recente do C ++.Mas apenas trigramas especificamente: a ISO C ++ 17 ainda possui dígrafos como
:>para]e%>para}. Portanto, com o custo de uso%, podemos evitar ambos{e}, e usá-%:los#para uma economia líquida de menos 2 caracteres únicos.E o C ++ possui palavras-chave
notdo!operador, como para o operador oubitorpara o|operador. Comxor_eqfor^=, você pode zerar uma variável comi xor_eq i, mas ela possui vários caracteres que não estava usando.A corrente
g++já ignora trigramas por padrão, mesmo sem-std=gnu++17; você precisa usá-trigraphs-los para habilitá-los, ou-std=c++11algo para uma estrita conformidade com um padrão ISO que os inclui.23 bytes únicos:
Experimente online!
A versão final usa
'aspas simples em vez dehou"para o separador de espaço. Eu não queria digrafar aschar c{}coisas, então as apaguei. Imprimir um char é mais eficiente do que imprimir uma string, então usei isso.Histograma:
O separador de espaço (ainda não resolvido)
Em uma resposta agora excluída, Johan Du Toit propôs o uso de um separador alternativo, especificamente
std::ends. Esse é um caractere NULchar(0), e é impresso como largura zero na maioria dos terminais. Portanto, a saída seria semelhante1234, não1 2 3 4. Ou pior, separados por lixo em qualquer coisa que não entrou em colapso silenciosamente'\0'.Se você pode usar um separador arbitrário, quando
0é fácil criar o dígitocout << some_zeroed_var. Mas ninguém quer10203040, isso é ainda pior do que nenhum separador.Eu estava tentando pensar em uma maneira de criar um
std::stringholding a" "sem usarcharou uma string literal. Talvez acrescentando algo a isso? Talvez com um dígrafo para[]definir o primeiro byte como um valor de32, depois de criar um com comprimento 1 por meio de um dos construtores?Johan também sugeriu a
std::iosfunção de membro fill () que retorna o caractere de preenchimento atual. O padrão para um fluxo é definido porstd::basic_ios::init()e é' '.std::cout << i << std::cout.fill();substitui<< ' ';mas usa em.vez de'.Com
-, podemos tomar um ponteiro paracoute uso->fill()para chamar a função de membro:std::cout << (bitand std::cout)->fill(). Ou não, nós também não estávamos usandob, então poderíamos ter usado em&vez de seu equivalente lexicalbitand.Chamar uma função de membro sem
.ou->Coloque-o dentro de uma classe e defina
operator char() { fill(); }Depois,
ss s{}antes do loop, estd::cout << i << s;dentro do loop. Ótimo, ele compila e funciona corretamente, mas tivemos que usarpehparaoperator char(), com uma perda líquida de 1. Pelo menos, evitamosbcriar funções de membropublicusando emstructvez declass. (E podemos substituir a herançaprotectedcaso isso ajude).fonte
cout.fill()fromstd::ios, mas não estávamos usando anteriormente..Talvez possamos chamá-lo de alguma forma pegando um ponteiro e usando->fill()uma função de membro? Alguma coisa retorna um ponteiro paracoutou para qualquer outro fluxo?<< (bitand std::cout)->fill()compila, mas usa-. (Apesar do nome do token,bitandé apenas um equivalente lexical&, e não especificamente o operador bit a bit. Também funciona como o endereço do operador.) Hmm, há algum modelo ou material lambda que pode direcionar uma função de membro que podemos()sem usar.ou->?std::ios::leftdefinida como 32, no gcc, mas não consegui descobrir uma maneira de tirar proveito disso. Eu acho que eu vou deixar isso ir e obter algum trabalho real feito :-)int32 não é um problema, minha resposta já mostra como fazer isso++partindo doint c{};zero. Mas sim, eu não vou descer pela toca do coelho olhando para lambdas, modelos oustd::function. Ou astd::stringideia. Mas não estamos acostumadosga, na verdade, não podemos declarar umstd::stringsem perder; minha ideia de usar emgotovez defornão deu certo.decltype(something)poderia nos dar umchartipo, mas nos custa ay.struct ss : std::ostream { operator auto () { return fill(); } };mas isso não ajuda muito.C ++ (gcc) x86_64 somente Linux,
9295 8900 8712 68125590 bytes, 18 caracteres exclusivosExperimente online!
Isso é baseado nas idéias desta resposta do PPCG . Um programa de linguagem de máquina é expresso como uma matriz de 32 bits de ints, cada um dos quais é representado como uma soma de
1+11+111.... Acontece que pode ser mais eficiente codificarxcomoytaly%(1<<32)==x. O programa de linguagem de máquina codificado é o seguinte... que se baseia no seguinte código C.
Editar: agora aceita entrada de em
stdinvez deargv[1]. Obrigado a @ ASCII-only e @PeterCordes por suas sugestões!Edit4: Codificação
ligeiramentemelhorada significativamente.fonte
-wflag pls: P (também é possível renomeariiparaa)gcc -zexecstackdisso, certo? Porqueint m[]não éconst. (E cadeias de ferramentas recentes colocadas.rodataem uma página não executável de qualquer maneira, mesmoconst int m[]assim não funcionam, por exemplo, no meu sistema Arch Linux comgcc8.2.1 20181127 eld(GNU Binutils) 2.31.1.) De qualquer forma, você esqueceu de mencionar isso em sua resposta, mas está no seu link do TIO.1compush %rax/ empop %rdivez de outro push-imediato. Ou, mais simplesmente, para valores que não são de 64 bits, ou seja, não ponteiros, 2 bytesmov %eax, %edi. Além disso, o Linuxsyscallnão destrói seus registros de entrada, apenasraxcom o valor de retorno e RCX + R11 com RIP e RFLAGS salvos como parte de como assyscallinstruções funcionam. Assim, você pode sairrdierdxdefinir1entre chamadas e usar diferentes regs. Além disso, o RBX é preservado por chamada, portanto, não é realmente possível salvar o RBX do main. Acontece que funciona porque o código inicial do CRT não se importa.21 caracteres únicos + 1 nova linha irremovível
Espaços em branco não são necessários, exceto para a primeira nova linha. Compilado em g ++ 7.3.0.
Caracteres utilizados:
%:include<ostram>()f-.Melhorias em outras respostas:
forloops paraife recursão.std::addressof(std::cout)->fill(), akastd::cout.fill().fonte
2120 caracteres únicos, excluindo espaços em brancoTodos os espaços em branco podem ser alterados para novas linhas.
Sai com segfault. Caracteres usados:
%:include<ostram>;-h.Ele funciona nesta versão específica do compilador em um Linux de 64 bits:
Com o parâmetro:
Mesmo assim, não tenho certeza de que sempre funcionaria. Também pode depender de muitas outras coisas.
ciaeciusão os deslocamentos da memória divididos por 4 entreiaiuei. (inté de 32 bits nesta versão.) Pode ser necessário alterar os números para corresponder ao deslocamento real. Os endereços seriam muito mais previsíveis se todos estiverem contidos em uma estrutura. Infelizmente não estáticoautonão é permitido em uma estrutura.eé uma matriz de 0 elementos de um tipo de elemento com um tamanho de (2 32 -1) × 2 32 bytes. Se o tipo de ponteiro correspondenteefor decrementado, a metade superior do ponteiro será decrementada por (2 32 -1), o que equivale a incrementar um. Isso poderia redefinir o contador decrementado sem usar o sinal de igualdade.Uma versão mais razoável que deve funcionar de maneira mais confiável, mas usa mais um caractere
=:Mesmo isso não funciona na versão mais recente do g ++, porque parece não permitir definir
mainum tipo arbitrário.Esses dois programas não usam parênteses. Mas então ponto e vírgula não parece ser evitável.
fonte
22 Caracteres exclusivos, excluindo espaços em branco. Separa os números com um caractere NUL que é exibido corretamente no Windows.
Experimente online
Histograma:
fonte
char(0)), não um espaço (char(32)em ASCII / UTF-8). pt.cppreference.com/w/cpp/io/manip/ends . Eu tentei no meu desktop Linux apenas para ter certeza, e a saída parece1234, não1 2 3 4. Parece o mesmo na sua saída TIO!"para" "se eles poderiam ter usadoiiiipara separar com'0'a10203040? Eu acho que você pode argumentar que ainda existe um separador na saída binária do programa, mas apontar essa alteração e descrevê-la em inglês é importante para sua resposta, porque essa não é uma substituição imediata! Ficaria feliz em remover meu voto negativo se você expandir sua resposta para explicar e justificar isso.