Qualquer número inteiro positivo pode ser obtido começando com 1 e aplicando uma sequência de operações, cada uma das quais é "multiplicada por 3" ou "dividida por 2, descartando qualquer restante" .

Exemplos (escrevendo f para * 3 eg para / 2):

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

Escreva um programa com o seguinte comportamento:

Entrada : qualquer número inteiro positivo, via stdin ou codificado. (Se codificado, o número de entrada será excluído do comprimento do programa.)
Saída : uma sequência de f e g tais que <input> = 1 <string>(como nos exemplos). Essa string na ordem inversa também é aceitável. NB: A saída contém apenas f e eg, ou está vazia.

O vencedor é a entrada com o menor número de bytes de programa com saída quando 41 é a entrada.

GolfScript, pontuação 64 (43-2 + 23)

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

(41 é codificado permanentemente, portanto, -2 caracteres para a pontuação). A saída é

fffgffggffggffgggffgggg

que tem 23 caracteres (sem nova linha). Por construção, o código garante que sempre retorne (uma) as representações mais curtas.

Estamos ficando sujos, 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);}}

sem golfe:

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);
    }
}

saída: dependendo da fé dos deuses antigos, o menor que eu tinha era 30. Observe que a saída deve ser lida da direita.

234

1 ggfgfgfgfggfggfgffgfggggfgffgfggfgfggggfgffgfggfgfggfgfggfgfgggggfffgfggfgfggfgfgggffgggggfffgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggfgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggggggggggggfgfgfggggfgfgfggfffgfgfggffgfgfggfgfggggffgfgfffff

108

1 gggffgfgfggggggfggggfgffggggfgfgfgfgfgffgggfgggggfggfffggfgfffffgggffggfgfgggffggfgfgggffggggggfgfgffgfgfff

editar 45

1 ggfgfgfgfgggfggfffgfggfgfgggggggffgffgfgfff

pontos : 318 199 + 30 = 229

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

Nota Bem, se você usa Java 6 e não Java 7 enquanto joga golfe, pode usar

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

Estrutura de 39 caracteres em vez de uma estrutura padrão com 53 caracteres.

Python, pontuação 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 (novas linhas como 1 cada) - 2 para número de entrada codificado + 36 caracteres de saída

Resultado:

ffffffffffffffffgggggggggggggggggggg

Python, pontuação 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'

Perl, pontuação 89 (63-2 + 28)

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

Conjetura: Se a abordagem ingênua descrita em minha solução original abaixo atingir um ciclo, esse ciclo será [21, 7, 15, 5, 10, 21, ...] . Como não há contra-exemplos para 1 ≤ n ≤ 10 ⁶ , isso parece provável que seja verdade. Para provar isso, basta mostrar que esse é o único ciclo que pode existir, o que eu posso ou não fazer em um momento posterior.

A solução acima evita o ciclo imediatamente, em vez de adivinhar (erradamente) e evita-o na segunda vez.

Saída (28 bytes):

ggfgfgfgfggfggfgfgfggfgfgfff

Perl, marca 100 (69-2 + 33)

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

Usando uma abordagem de adivinhação e verificação. A cadeia é construída usando operações inversas (convertendo o valor para 1 , e não o contrário), e a cadeia é espelhada de acordo, o que é permitido pela especificação do problema.

Sempre que um não múltiplo de três for encontrado, ele será multiplicado por dois, adicionando um se o resultado for um múltiplo de três. Quando um múltiplo de três for encontrado, ele será dividido por três ... a menos que esse valor tenha sido encontrado anteriormente, indicando um ciclo, portanto, adivinhe e verifique.

Saída (33 bytes):

ggfgfgfgfggfggfgffgfgggfggfgfgfff

J, escore 103 (82-2 + 23)

* Nota: Eu nomeei meus verbos fe g, para não ser confundido com as strings de saída fe g.

Codificado:

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

Funções gerais:

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

Acabou com a operação em blocos de números binários, que foi a mudança mais importante na compactação g. Renomeiei as variáveis ​​e removi alguns espaços em branco, mas tudo continua funcional do mesmo jeito. (Uso: g 41)

J, pontuação 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
)

Resultado: ffffffffggggggggfgffggg

fconverte uma lista de booleanos em número, usando 0s como *3e 1s como /2(e floor). #:i.2^icria uma matriz de classificação 2 contendo todas as matrizes booleanas de classificação 1 i.