Dowolną dodatnią liczbę całkowitą można uzyskać, rozpoczynając od 1 i stosując sekwencję operacji, z których każda albo „pomnóż przez 3”, albo „podziel przez 2, odrzucając resztę” .

Przykłady (pisanie f dla * 3 ig dla / 2):

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

Napisz program o następującym działaniu:

Dane wejściowe : dowolna dodatnia liczba całkowita, poprzez stdin lub na stałe. (W przypadku zakodowania na stałe, numer wejściowy zostanie wykluczony z długości programu.)
Wyjście : ciąg znaków f i g taki, że <input> = 1 <string>(jak w przykładach). Taki ciąg w odwrotnej kolejności jest również dopuszczalny. NB: Dane wyjściowe zawierają tylko f i g lub są puste.

Zwycięzcą jest pozycja z najmniejszą liczbą bajtów programu plus wyjście, gdy 41 to wejście.

GolfScript, wynik 64 (43-2 + 23)

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

(41 jest zakodowane, więc -2 znaki dla wyniku). Dane wyjściowe to

fffgffggffggffgggffgggg

który ma 23 znaki (bez nowej linii). Dzięki konstrukcji kod gwarantuje, że zawsze zwraca (jedną z) najkrótszych reprezentacji.

Brudzimy się, przyjaciele!

JAWA 210 207 199 znaków

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

nie golfa:

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

wyjście: w zależności od wiary starych bogów, najkrótszy miałem 30. Zauważ, że wynik musi być odczytany z prawej strony.

234

1 ggfgfgfgfggfggfgffgfggggfgffgfggfgfggggfgffgfggfgfggfgfggfgfgggggfffgfggfgfggfgfgggffgggggfffgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggfgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggggggggggggfgfgfggggfgfgfggfffgfgfggffgfgfggfgfggggffgfgfffff

108

1 gggffgfgfggggggfggggfgffggggfgfgfgfgfgffgggfgggggfggfffggfgfffffgggffggfgfgggffggfgfgggffggggggfgfgffgfgfff

edycja 45

1 ggfgfgfgfgggfggfffgfggfgfgggggggffgffgfgfff

punkty: 318 199 + 30 = 229

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

Nota Bene, jeśli używasz Java 6, a nie Java 7 podczas gry w golfa, możesz użyć

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

Struktura 39 znaków zamiast standardowej struktury o długości 53 znaków.

Python, wynik 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 znaków kodu (nowe wiersze jako 1 każdy) - 2 dla zakodowanych cyfr wejściowych + 36 znaków wyjściowych

Wynik:

ffffffffffffffffgggggggggggggggggggg

Python, wynik 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, wynik 89 (63-2 + 28)

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

Przypuszczenie: jeśli naiwne podejście opisane w moim oryginalnym rozwiązaniu poniżej osiągnie cykl, cykl ten wyniesie [21, 7, 15, 5, 10, 21, ...] . Ponieważ nie ma kontrprzykładów dla 1 ≤ n ≤ 10 ⁶ , wydaje się to prawdopodobne. Aby to udowodnić, wystarczyłoby wykazanie, że jest to jedyny cykl, który może istnieć, co mogę, ale nie muszę, zrobić w późniejszym czasie.

Powyższe rozwiązanie pozwala uniknąć cyklu natychmiast, zamiast zgadywania (błędnie) i unikania go za drugim razem.

Wyjście (28 bajtów):

ggfgfgfgfggfggfgfgfggfgfgfff

Perl, wynik 100 (69-2 + 33)

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

Korzystanie z metody zgadywania i sprawdzania. Łańcuch jest konstruowany przy użyciu operacji odwrotnych (konwersja wartości na 1 zamiast na odwrót), a łańcuch zostaje odpowiednio dublowany, co jest dozwolone w specyfikacji problemu.

Za każdym razem, gdy napotkamy nie wielokrotność trzech, zostanie ona pomnożona przez dwa, dodając jeden, jeśli wynik będzie wielokrotnością trzech. Kiedy napotkamy wielokrotność trzech, zostanie ona podzielona przez trzy ... chyba że wcześniej ta wartość została napotkana, co wskazuje na cykl, a więc zgadnij i sprawdź.

Wyjście (33 bajty):

ggfgfgfgfggfggfgffgfgggfggfgfgfff

J, wynik 103 (82–2 + 23)

* Uwaga: Nazwałem swoje czasowniki fi g, nie należy mylić ich z ciągami wyjściowymi fi g.

Mocno zakodowane:

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

Funkcje ogólne:

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

Zrezygnowałem z operowania na blokach liczb binarnych, co było najważniejszą zmianą w zakresie kompaktowania g. Zmieniłem nazwy zmiennych i usunąłem trochę białych znaków, ale wszystko funkcjonalnie jest takie samo. (Zastosowanie: g 41)

J, wynik 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
)

Wynik: ffffffffggggggggfgffggg

fkonwertuje listę wartości logicznych na liczbę, używając 0 jako *3i 1 jako /2(i floor). #:i.2^itworzy tablicę rangi 2 zawierającą wszystkie tablice boolowskie rangi 1 o długości i.