Soy nuevo en el deporte del código golf. Estoy tratando de generar una escalera de enteros utilizando el menor número de caracteres únicos en C ++.
Digamos que se nos da un número entero 4.
Generaremos la siguiente escalera:
1
1 2
1 2 3
1 2 3 4
En resumen, mi programa leerá un entero positivo de stdin e imprimirá esta escalera en la salida. Estoy tratando de hacerlo con la menor cantidad de caracteres únicos posibles.
Mi programa es el siguiente:
#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;
}
}
Aquí está el corrector que usé para verificar la cantidad de caracteres únicos en mi 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;
}
Preferiblemente deseo usar menos de 25 caracteres únicos para completar este programa (excluyendo caracteres de nueva línea pero incluyendo espacios en blanco). Actualmente, mi programa usa 27. No estoy seguro de cómo optimizarlo aún más.
¿Podría alguien aconsejarme sobre cómo optimizarlo aún más (en términos de la cantidad de caracteres únicos utilizados)? Tenga en cuenta que solo se puede usar C ++.
fuente
Respuestas:
Creo que logré eliminar el carácter = de su código, aunque ahora es significativamente más lento
No es bonito, pero al abusar del desbordamiento de enteros podemos volver a 0 sin usar =
También tuvimos que cambiar un poco a los guardias. Desafortunadamente, debido a la inclusión, no pude deshacerme de todos los nuevos caracteres de línea (aunque está cerca), por lo que puede ser la próxima vía de investigación.
Editar: Sin tiempo por ahora, pero si incluye y usa strstream y varias otras bibliotecas, creo que también puede eliminar el "carácter", nuevamente usando números enteros para llegar al carácter correcto para el espacio y pasarlo al Strstream
fuente
#include<std>y eliminar todos los:s. No es una buena práctica de codificación, pero eso no viene al caso.using namespace std;lo que usaría una p adicional para: entonces un 0 netog, así que la pérdida neta, supongo. Si este fuera el código dorado, podríamos reducir el recuento de bytes cambiando el nombreii,iiiyiiiia otros nombres de letras individuales (elija cualquier otra letra ya utilizada), pero de eso no se trata este desafío, así que supongo que no. Me pregunto si habría algún beneficio al usarlogetcy, enputclugar decin/cout, tendría que intentarlo.signed char. Si compila con la optimización habilitada, este código puede romperse con los compiladores modernos, a menos que lo usegcc -fwrapvpara hacer que el desbordamiento firmado esté bien definido como un complemento del complemento 2. el sonido metálico-fwrapvtambién. (losunsignedtipos enteros incluidosunsigned chartienen un comportamiento bien definido (envolvente) en ISO C ++). Depende de la ABI sicharessigned charounsigned char, por lo quecharpuede estar bien.Finalmente obtuve 24 caracteres únicos al combinar las respuestas de @ExpiredData y @someone. Además, usar el tipo de datos cortos en lugar de int ayudó a acelerar mi programa porque toma más tiempo desbordar un tipo de datos corto.
Mi código es el siguiente.
fuente
char iiiii;, la última de las inicializaciones variables.23 personajes únicos que usan dígrafos. (25 sin). No UB
Utilice la sintaxis de inicializador con soporte de C ++ 11 para inicializar en una lista un entero a cero
int var{};evitando=y0. (O en su caso, evitando globaliiii). Esto le proporciona una fuente de ceros distintos de las variables globales (que se inicializan estáticamente a cero, a diferencia de los locales).Los compiladores actuales aceptan esta sintaxis de manera predeterminada, sin tener que habilitar ninguna opción especial.
(El truco de wraparound entero es divertido, y está bien para jugar al golf con la optimización deshabilitada, pero el desbordamiento firmado es un comportamiento indefinido en ISO C ++. Habilitar la optimización convertirá esos bucles envolventes en bucles infinitos, a menos que compile con gcc / clang
-fwrapvpara proporcionar un desbordamiento entero firmado -definido comportamiento: complemento de 2 envolvente.Dato curioso: ¡ISO C ++
std::atomic<int>tiene un complemento de 2 bien definido!int32_tse requiere que sea el complemento de 2 si está definido, pero el comportamiento de desbordamiento no está definido, por lo que aún puede ser un typedef paraintolongen cualquier máquina donde uno de esos tipos sea de 32 bits, sin relleno, y el complemento de 2).No es útil para este caso específico:
También puede inicializar una nueva variable como una copia de una existente, con llaves o (con un inicializador no vacío), parens para la inicialización directa .
int a(b)oint a{b}son equivalentes aint a = b;Pero
int b();declara una función en lugar de una variable inicializada a cero.Además, puede obtener un cero con
int()ochar(), es decir , inicialización cero de un objeto anónimo.Podemos reemplazar sus
<=comparaciones con<comparaciones por una simple transformación lógica : haga el incremento del contador de bucle justo después de la comparación, en lugar de en la parte inferior del bucle. En mi opinión, esto es más simple que las alternativas que la gente ha propuesto, como usar++en la primera parte de afor()para hacer un 0 en un 1.Podríamos reducir eso a golf,
for(int r{}; r++ < n;)pero la OMI es menos fácil de leer para los humanos. No estamos optimizando para el recuento total de bytes.Si ya estuviéramos usando
h, podríamos guardar el'o"para un espacio.Suponiendo un entorno ASCII o UTF-8, el espacio tiene un
charvalor 32. Podemos crearlo en una variable con bastante facilidad, luegocout << c;Y, obviamente, se pueden crear otros valores a partir de una secuencia
++y duplicación, en función de los bits de su representación binaria. Cambiando efectivamente un 0 (nada) o 1 (++) en el LSB antes de duplicar en una nueva variable.Esta versión usa en
hlugar de'o".Es mucho más rápido que cualquiera de las versiones existentes (sin depender de un bucle largo), y está libre de Comportamiento indefinido . Se compila sin advertencias con
g++ -O3 -Wall -Wextra -Wpedanticy conclang++.-std=c++11es opcional. Es legal y portátil ISO C ++ 11 :)Tampoco se basa en variables globales. Y lo hice más legible para los humanos con nombres de variables que tienen un significado.
Recuento de bytes únicos: 25 , excluyendo los comentarios que eliminé
g++ -E. Y excluyendo el espacio y la nueva línea como su mostrador. Utilicésed 's/\(.\)/\1\n/g' ladder-nocomments.cpp | sort | uniq -iceste askubuntu para contar las ocurrencias de cada personaje, y lo canalicéwcpara contar cuántos caracteres únicos tenía.Los únicos 2
fcaracteres son defor. Podríamos usarwhilebucles en su lugar si tuviéramos un usow.Posiblemente podríamos reescribir los bucles en un estilo de lenguaje ensamblador
i < r || goto some_label;para escribir un salto condicional en la parte inferior del bucle, o lo que sea. (Pero usando enorlugar de||). No, eso no funciona.gotoes una declaración comoify no puede ser un subcomponente de una expresión como puede en Perl. De lo contrario, podríamos haberlo usado para eliminar los caracteres(y).Podríamos operar
fparagconif(stuff) goto label;en lugar defor, y ambos bucles siempre se ejecutan al menos 1 iteración por lo que sólo necesitaríamos un bucle-rama en la parte inferior, al igual que una normal de asmdo{}whileestructura de bucle. Suponiendo que el usuario ingresa un número entero> 0 ...Dígrafos y Trígrafos
Afortunadamente, los trigrafos se han eliminado a partir de ISO C ++ 17, por lo que no tenemos que usarlos en
??>lugar de}si estamos jugando al golf exclusivo para la revisión más reciente de C ++.Pero solo trigrafos específicamente: ISO C ++ 17 todavía tiene digrafos como
:>por]y%>para}. Así que en el costo de usar%, podemos evitar tanto{y}, y el uso%:de#un ahorro neto de 2 menos caracteres únicos.Y C ++ tiene palabras clave de operador como
notpara el!operador obitorpara el|operador. Conxor_eqfor^=, puede poner a cero una variable coni xor_eq i, pero tiene varios caracteres que no estaba usando.Current
g++ya ignora los trigraphs por defecto incluso sin-std=gnu++17; tiene que usar-trigraphspara habilitarlos, o-std=c++11algo por el estricto cumplimiento de un estándar ISO que los incluye.23 bytes únicos:
Pruébalo en línea!
La versión final utiliza una
'comilla simple en lugar deho"para el separador de espacio. No quería dibujar laschar c{}cosas, así que lo eliminé. Imprimir un char es más eficiente que imprimir una cadena, así que lo usé.Histograma:
El separador de espacios (aún sin resolver)
En una respuesta ahora eliminada, Johan Du Toit propuso usar un separador alternativo, específicamente
std::ends. Ese es un carácter NULchar(0), y se imprime como ancho cero en la mayoría de los terminales. Entonces la salida se vería así1234, no1 2 3 4. O peor, separados por basura en cualquier cosa que no colapsó en silencio'\0'.Si puede usar un separador arbitrario, cuando el dígito
0es fácil de crearcout << some_zeroed_var. Pero nadie quiere10203040, eso es peor que ningún separador.Estaba tratando de pensar en una forma de crear una
std::stringretención" "sin usarcharo un literal de cadena. ¿Quizás agregarle algo? ¿Quizás con un dígrafo para[]establecer el primer byte en un valor de32, después de crear uno con longitud 1 a través de uno de los constructores?Johan también sugirió la
std::iosfunción miembro fill () que devuelve el carácter de relleno actual. El valor predeterminado para una secuencia lo establecestd::basic_ios::init()y es' '.std::cout << i << std::cout.fill();reemplaza<< ' ';pero usa en.lugar de'.Con
-, podemos tomar un puntero acouty el uso->fill()de llamar a la función miembro:std::cout << (bitand std::cout)->fill(). O no, no estábamos usandobya sea por lo que bien podría haber utilizado&en lugar de su equivalente léxico,bitand.Llamar a una función miembro sin
.o->Ponlo dentro de una clase y define
operator char() { fill(); }Luego
ss s{}antes del bucle, ystd::cout << i << s;dentro del bucle. Genial, se compila y funciona correctamente, pero tuvimos que usarpyhparaoperator char(), para una pérdida neta de 1. Al menos evitamosbhacer funciones miembropublicusando enstructlugar declass. (Y podríamos anular la herenciaprotecteden caso de que alguna vez ayude).fuente
cout.fill()fromstd::ios, pero no estábamos usando anteriormente ¿.Tal vez podamos llamarlo de alguna manera tomando un puntero y usando->fill()una función miembro? ¿Algo devuelve un punterocouto cualquier otra secuencia?<< (bitand std::cout)->fill()compila, pero usa-. (A pesar del nombre del token,bitandes solo un equivalente léxico&, no específicamente el operador bit a bit. También funciona como la dirección del operador). Hmm, ¿hay alguna plantilla o material lambda que pueda obtener un puntero a una función miembro? que podemos()sin usar.o->?std::ios::leftse define como 32, en gcc, pero realmente no pude encontrar una manera de aprovechar eso. Creo que voy a dejar ir este y hacer un trabajo real :-)int32 no es un problema, mi respuesta ya muestra cómo hacerlo++comenzando desde unint c{};cero. Pero sí, no voy por el agujero del conejo de mirar lambdas, plantillas ostd::function. O lastd::stringidea Pero no estamos acostumbradosga que en realidad no podamos declarar unstd::stringsin perder; mi idea de usar engotolugar deforno funcionó.decltype(something)podría darnos unchartipo, pero nos cuesta ay.struct ss : std::ostream { operator auto () { return fill(); } };pero no ayuda mucho.C ++ (gcc) x86_64 solo Linux,
9295 8900 8712 68125590 bytes, 18 caracteres únicosPruébalo en línea!
Esto se basa en ideas de esta respuesta PPCG . Un programa de lenguaje de máquina se expresa como una matriz de entradas de 32 bits, cada una de las cuales se representa como una suma de
1+11+111.... Resulta que puede ser más eficiente codificarxcomoytal quey%(1<<32)==x. El programa de lenguaje de máquina codificado es el siguiente... que se basa en el siguiente código C.
Editar: ahora acepta entradas de en
stdinlugar deargv[1]. ¡Gracias a @ ASCII-only y @PeterCordes por sus sugerencias!Edit4:
codificaciónligeramentemejorada significativamente.fuente
-wpls (bandera también: P puede cambiar el nombreiiaa)gcc -zexecstackesto, ¿verdad? Porqueint m[]no lo esconst. (Y las cadenas de herramientas recientes ponen.rodataen una página no ejecutable de todos modos, por lo que inclusoconst int m[]no funciona en, por ejemplo, mi sistema Arch Linux congcc8.2.1 20181127 yld(GNU Binutils) 2.31.1.) De todos modos, olvidó mencionar eso en su respuesta, pero está en tu enlace TIO.1conpush %rax/ enpop %rdilugar de otro envío inmediato. O más simplemente, para valores que no son de 64 bits, es decir, no punteros, de 2 bytesmov %eax, %edi. Además, Linuxsyscallno destruye sus registros de entrada, soloraxcon el valor de retorno y RCX + R11 con RIP y RFLAGS guardados como parte de cómo funciona lasyscallinstrucción. Por lo tanto, puede salirrdiyrdxestablecer1llamadas cruzadas, y usar diferentes registros. Además, RBX tiene llamadas preservadas, por lo que en realidad no se guarda en RBX de clobber main. Sucede que funciona porque el código de inicio CRT no le importa.21 personajes únicos + 1 nueva línea inamovible
No se requieren espacios en blanco excepto la primera línea nueva. Compilado en g ++ 7.3.0.
Caracteres usados:
%:include<ostram>()f-.Mejoras a otras respuestas:
forbuclesify recursividad.std::addressof(std::cout)->fill(), aliasstd::cout.fill().fuente
2120 caracteres únicos excluyendo espacios en blancoTodos los espacios en blanco podrían cambiarse a nuevas líneas.
Salidas con segfault. Los caracteres utilizados:
%:include<ostram>;-h.Funciona en esta versión específica del compilador en un Linux de 64 bits:
Con el parámetro:
Incluso entonces, no estoy seguro de que siempre funcione. También puede depender de muchas otras cosas.
ciayciuson las compensaciones de memoria divididas por 4 entreiaiuyi. (intes de 32 bits en esta versión). Puede que tenga que cambiar los números para que coincidan con el desplazamiento real. Las direcciones serían mucho más predecibles si están todas contenidas en una estructura. Lamentablemente, no estáticoautono está permitido en una estructura.ees una matriz de 0 elementos de un tipo de elemento con un tamaño de (2 32 -1) × 2 32 bytes. Siese disminuye el tipo de puntero correspondiente , la mitad superior del puntero se disminuiría en (2 32 -1), lo que equivale a incrementar en uno. Esto podría restablecer el contador decrementado sin usar el signo de igualdad.Una versión más razonable que debería funcionar de manera más confiable, pero utiliza un personaje más
=:Incluso esto no funciona en la última versión de g ++ porque ya no parece permitir la definición
mainen un tipo arbitrario.Estos dos programas no usan paréntesis. Pero los puntos y comas no parecen ser evitables.
fuente
22 caracteres únicos, excluyendo espacios en blanco. Separa los números con un carácter NUL que se muestra correctamente en Windows.
Pruébalo en línea
Histograma:
fuente
char(0)), no un espacio (char(32)en ASCII / UTF-8). en.cppreference.com/w/cpp/io/manip/ends . Lo probé en mi escritorio de Linux solo para asegurarme, y la salida se ve así1234, no1 2 3 4. ¡Se ve de la misma manera en su salida TIO!"por" "si podían haber utilizadoiiiipara separar con'0'a10203040? Supongo que puede argumentar que todavía hay un separador en la salida binaria del programa, pero señalar este cambio y describirlo en inglés es importante para su respuesta, ¡porque este no es un reemplazo directo! Estaré encantado de eliminar mi voto negativo si expande su respuesta para explicar y justificar eso.