Convierta 1 en cualquier entero positivo usando solo las operaciones * 3 y / 2

11

Se puede obtener cualquier número entero positivo comenzando con 1 y aplicando una secuencia de operaciones, cada una de las cuales es "multiplicar por 3" o "dividir por 2, descartando cualquier resto" .

Ejemplos (escribir f para * 3 yg para / 2):

4 = 1 *3 *3 /2 = 1 ffg
6 = 1 ffggf = 1 fffgg
21 = 1 fffgfgfgggf

Escribe un programa con el siguiente comportamiento:

Entrada : cualquier número entero positivo, vía stdin o codificado. (Si está codificado, el número de entrada se excluirá de la longitud del programa).
Salida : una cadena de f y g tal que <input> = 1 <string>(como en los ejemplos). Tal cadena en orden inverso también es aceptable. NB: La salida contiene solo f's y g's, o está vacía.

El ganador es la entrada con la menor cantidad de bytes de programa más salida cuando 41 es la entrada.

res
fuente
1
¿Cómo sabes que esto es cierto?
Marinus
@marinus se cree que esto es cierto (pero aún no se ha probado). buscando alguna prueba.
Fabinout
@marinus, puedes demostrar que es posible por descenso (o equivalente por inducción fuerte). Separación entre mayúsculas y minúsculas en x mod 3: si x=3yconstruye y y luego aplica f; si x=3y+1construye 2y+1y aplica fentonces g; si x=3y+2entonces se complica pero esencialmente es recursivo.
Peter Taylor
En una nota separada, ¿el resultado debe estar en orden de aplicación o el orden de composición también debería ser aceptable?
Peter Taylor
@PeterTaylor De cualquier manera está bien.
res

Respuestas:

3

GolfScript, puntaje 64 (43-2 + 23)

0{)1.$2base:s{{3*}{2/}if}/41=!}do;s{103^}%+

(41 está codificado, por lo tanto, -2 caracteres para la puntuación). La salida es

fffgffggffggffgggffgggg

que tiene 23 caracteres (sin nueva línea). Por construcción, el código garantiza que siempre devuelve (una de) las representaciones más cortas.

Howard
fuente
Citando al usuario Darren Stone en una edición sugerida en esta publicación: "No puedo dejar un comentario aquí, así que dejaré una edición. Esta salida no incluye los dos primeros caracteres" 1 "ni los que se reflejan en la puntuación. Debe ser un solución fácil y sigue siendo una solución increíblemente corta. ¡Salud! " (Rechacé, pero pensé que debía llevar el mensaje)
Pomo de la puerta
@Doorknob El desafío indica que "1 "no se debe incluir en la salida.
Howard
3

Nos estamos ensuciando, amigos!

JAVA 210 207 199 caracteres

public class C{public static void main(String[] a){int i=41;String s="";while(i>1){if(i%3<1){s+="f";i/=3;}else if(i%3<2){s+="g";i+=i+1;}else{s+="g";i+=i+(Math.random()+0.5);}}System.out.println(s);}}

no golfizado:

public class C {

    public static void main(String[] a) {

        int i = 41;
        String s = "";
        while (i > 1) {
            if (i % 3 == 0) {
                s += "f";
                i /= 3;
            } else {
                if (i % 3 == 1) {
                    s += "g";
                    i += i + 1;
                } else {
                    s += "g";
                    i += i + (Math.random() + 0.5);
                }
            }
        }
        System.out.println(s);
    }
}

salida: dependiendo de la fe de los antiguos dioses, la más corta que tuve fue 30. Tenga en cuenta que la salida debe leerse desde la derecha.

234

1 ggfgfgfgfggfggfgffgfggggfgffgfggfgfggggfgffgfggfgfggfgfggfgfgggggfffgfggfgfggfgfgggffgggggfffgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggfgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggggggggggggfgfgfggggfgfgfggfffgfgfggffgfgfggfgfggggffgfgfffff

108

1 gggffgfgfggggggfggggfgffggggfgfgfgfgfgffgggfgggggfggfffggfgfffffgggffggfgfgggffggfgfgggffggggggfgfgffgfgfff

editar 45

1 ggfgfgfgfgggfggfffgfggfgfgggggggffgffgfgfff

puntos : 318 199 + 30 = 229

edit1 (2 * i + 1)% 3 == 0 -> (2 * i)% 3 == 1

Nota Bene si usa Java 6 y no Java 7 mientras juega golf, puede usar

public class NoMain {
    static {
        //some code
        System.exit(1);
    }
}

Estructura de 39 caracteres en lugar de una estructura estándar que tiene 53 caracteres de longitud.

Fabinout
fuente
(2*i+1)%3==0es equivalente ai%3==1
Howard
Sí lo es. gracias
Fabinout
if(X){A}else{if(Y){B}else{C}}es más largo que if(X){A}else if(Y){B}else{C}. También puede reemplazar sus ==condiciones con <condiciones más cortas .
Peter Taylor
@PeterTaylor cierto, mi solución sigue siendo fea. No sé si la parte aleatoria hace que el código sea más corto, pero esto hace que la salida sea más desagradable.
Fabinout
Sus cadenas f / g comienzan con 'g' (que se supone que significa '/ 2'), por lo que convertirán 1 a 0 en lugar de a 41. Cambiar las f's por g's y viceversa, tampoco parece dar 41.
res
3

Python, puntaje 124 (90-2 + ​​36)

x=41;m=f=g=0
while(3**f!=x)*(m!=x):
 f+=1;m=3**f;g=0
 while m>x:m/=2;g+=1
print'f'*f+'g'*g

90 caracteres de código (líneas nuevas como 1 cada uno) - 2 para el número de entrada codificado + 36 caracteres de salida

Salida:

ffffffffffffffffgggggggggggggggggggg
Piedra de Darren
fuente
1
Si lo hace m=f=0, puede hacer el bucle externo while(n!=x)*(m!=x)y eliminar los descansos. Lo lleva a 95 caracteres de código.
Daniel Lubarov el
@Daniel: Usted, señor, es un caballero y un erudito. ¡Gracias! Su presentación todavía está segura 10 caracteres por delante de mí. :)
Darren Stone
1
Puede ahorrar un poco más si reemplaza todo npor 3**f.
Howard
1
Para input = 1, su programa genera un error ("nombre 'g' no está definido", debido a que no ingresa el bucle while externo).
Res
1
Podría cortar otro personaje escribiendo print'f'*f+'g'*g, lo que daría un puntaje de 90-2 + ​​36 = 124.
res
3

Python, puntaje 121 (87 - 2 + 36)

t=bin(41)
l,n,f=len(t),1,0
while bin(n)[:l]!=t:f+=1;n*=3
print(len(bin(n))-l)*'g'+f*'f'
Daniel Lubarov
fuente
@ Darren, no estaba seguro de cómo interpretar la descripción de salida, pero probablemente tengas razón. Agregué el '1'. ¡Gracias!
Daniel Lubarov
1
Puede soltar el '1' (¡de nuevo!) Su interpretación original de la descripción de salida fue correcta. ¡Disfruta de la ventaja de Python, de nuevo! :-)
Darren Stone
1
Si combinara sus líneas 2da, 3ra y 4ta l,n,f=len(t),1,0y eliminara la '1',declaración impresa, su puntaje sería 87-2 + 36 = 121.
res
Gracias chicos, dejé caer el 1,. l,n,f=len(t),1,0da la misma cantidad de caracteres, ¿verdad? (Para cada variable, una =y una nueva línea se reemplaza con dos ,s.)
Daniel Lubarov
Si cada nueva línea tiene un carácter (p. Ej., LF de estilo UNIX), las versiones de una y tres líneas tienen la misma longitud. Si cada nueva línea tiene dos caracteres (p. Ej., CR + LF de estilo MS Windows), la versión de una línea es dos caracteres más corta que la versión de tres líneas. La puntuación de 121 supone nuevas líneas de un personaje.
res
1

Perl, puntaje 89 (63 - 2 + 28)

$_=41;$_=${$g=$_%3||$_==21?g:f}?$_*2+$_%3%2:$_/3while$_>print$g

Conjetura: si el enfoque ingenuo descrito en mi solución original a continuación llega a un ciclo, ese ciclo será [21, 7, 15, 5, 10, 21, ...] . Como no hay contraejemplos para 1 ≤ n ≤ 10 6 , parece probable que esto sea cierto. Para probar esto, sería suficiente demostrar que este es el único ciclo que puede existir, lo que puedo hacer o no en un momento posterior.

La solución anterior evita el ciclo inmediatamente, en lugar de adivinar (erróneamente) y evitarlo la segunda vez.

Salida (28 bytes):

ggfgfgfgfggfggfgfgfggfgfgfff

Perl, puntaje 100 (69 - 2 + 33)

$_=41;1while$_>print$s{$_=$$g?$_*2+$_%3%2:$_/3}=$g=$_%3||$s{$_/3}?g:f

Usando un enfoque de adivinar y verificar. La cadena se construye utilizando operaciones inversas (convirtiendo el valor a 1 , en lugar de al revés), y la cadena se refleja en consecuencia, lo que está permitido por la especificación del problema.

Siempre que se encuentre un no múltiplo de tres, se multiplicará por dos, agregando uno si el resultado sería un múltiplo de tres. Cuando se encuentra un múltiplo de tres, se dividirá entre tres ... a menos que este valor se haya encontrado previamente, lo que indica un ciclo, por lo tanto, adivina y verifica.

Salida (33 bytes):

ggfgfgfgfggfggfgffgfgggfggfgfgfff
primo
fuente
1

J, puntaje 103 (82-2 + 23)

* Nota: nombré mis verbos fy g, para no confundirme con cadenas de salida fy g.

Codificado duro:

f=:3 :'s=.1 for_a.y do.s=.((<.&-:)`(*&3)@.a)s end.'
'gf'{~#:(>:^:(41&~:@f@#:)^:_)1

Funciones generales:

f=:3 :'s=.1 for_a.y do.s=.((<.&-:)`(*&3)@.a)s end.'
g=:3 :'''gf''{~#:(>:^:(y&~:@f@#:)^:_)1'

Eliminó la operación en bloques de números binarios, que fue el cambio más importante en cuanto a la compactación g. Cambié el nombre de las variables y eliminé algunos espacios en blanco por el gusto de hacerlo, pero todo sigue siendo funcionalmente igual. (Uso: g 41)

J, puntaje 197 (174 + 23)

f =: 3 : 0
acc =. 1
for_a. y do. acc =. ((*&3)`(<.&-:)@.a) acc end.
)

g =: 3 : 0
f2 =: f"1 f.
l =. 0$0
i =. 1
while. 0=$(l=.(#~(y&=@:f2))#:i.2^i) do. i=.>:i end.
'fg'{~{.l
)

Salida: ffffffffggggggggfgffggg

fconvierte una lista de booleanos en números, usando 0s como *3y 1s como /2(y floor). #:i.2^icrea una matriz de rango 2 que contiene todas las matrices booleanas de rango 1 de longitud i.

racionalis
fuente