Любое положительное целое число можно получить, начиная с 1 и применяя последовательность операций, каждая из которых либо «умножить на 3», либо «разделить на 2, отбрасывая любой остаток» .

Примеры (пишем f для * 3 и g для / 2):

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

Напишите программу со следующим поведением:

Ввод : любое положительное целое число, через стандартный или жестко запрограммированный. (При жестком кодировании входная цифра будет исключена из длины программы.)
Вывод : строка f и g такая, что <input> = 1 <string>(как в примерах). Такая строка в обратном порядке также приемлема. NB. Выходные данные содержат только f и g или являются пустыми.

Победителем является запись с наименьшим количеством байтов программы плюс-вывод, когда 41 является входом.

GolfScript, оценка 64 (43-2 + 23)

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

(41 жестко запрограммирован, поэтому -2 балла за счет). Выход

fffgffggffggffgggffgggg

что составляет 23 символа (без перевода строки). По построению код гарантирует, что он всегда возвращает (одно из) кратчайших представлений.

Мы пачкаемся, друзья!

ЯВА 210 207 199 символов

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

без golfed:

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

Вывод: в зависимости от веры старых богов, самое короткое, что у меня было, - 30. Обратите внимание, что вывод должен быть прочитан справа.

234

1 ggfgfgfgfggfggfgffgfggggfgffgfggfgfggggfgffgfggfgfggfgfggfgfgggggfffgfggfgfggfgfgggffgggggfffgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggfgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggggggggggggfgfgfggggfgfgfggfffgfgfggffgfgfggfgfggggffgfgfffff

108

1 gggffgfgfggggggfggggfgffggggfgfgfgfgfgffgggfgggggfggfffggfgfffffgggffggfgfgggffggfgfgggffggggggfgfgffgfgfff

редактировать 45

1 ggfgfgfgfgggfggfffgfggfgfgggggggffgffgfgfff

точки : 318 199 + 30 = 229

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

Nota Bene, если вы используете Java 6, а не Java 7 во время игры в гольф, вы можете использовать

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

Структура из 39 символов вместо стандартной структуры длиной 53 символа.

Питон, оценка 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 символов кода (новые строки как 1 каждый) - 2 для жестко закодированной входной цифры + 36 символов для вывода

Выход:

ffffffffffffffffgggggggggggggggggggg

Питон, оценка 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, оценка 89 (63 - 2 + 28)

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

Предположение: если наивный подход, описанный в моем первоначальном решении ниже, когда-либо достигнет цикла, этот цикл будет [21, 7, 15, 5, 10, 21, ...] . Поскольку нет контрпримеров для 1 ≤ n ≤ 10 ⁶ , похоже, что это правда. Чтобы доказать это, достаточно показать, что это единственный цикл, который может существовать, что я могу или не могу сделать в более поздний момент времени.

Вышеупомянутое решение избегает цикла немедленно, вместо того, чтобы угадывать (неправильно), и избегать его во второй раз.

Выход (28 байт):

ggfgfgfgfggfggfgfgfggfgfgfff

Perl, оценка 100 (69 - 2 + 33)

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

Использование метода угадывания и проверки. Строка строится с использованием обратных операций (преобразование значения в 1 , а не наоборот), и строка соответствующим образом зеркально отражается, что разрешено в спецификации задачи.

Всякий раз, когда встречается не кратное трем, оно умножается на два, добавляя единицу, если результат будет кратным трем. Когда встречается число, кратное трем, оно будет разделено на три ..., если только это значение не встречалось ранее, что указывает на цикл, а значит, на угадывание и проверку.

Выход (33 байта):

ggfgfgfgfggfggfgffgfgggfggfgfgfff

J, оценка 103 (82-2 + 23)

* Примечание: я назвал свои глаголы fи g, чтобы не путать с выходными строками fи g.

Hard кодировки:

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

Общие функции:

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

Избавился от работы с блоками двоичных чисел, что было самым важным изменением в сжатии g. Переименовал переменные и удалил некоторые пробелы, но все по-прежнему функционально. (Использование: g 41)

J, оценка 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
)

Выход: ffffffffggggggggfgffggg

fпреобразует список логических чисел в число, используя 0s как *3и 1s как /2(и floor). #:i.2^iсоздает массив ранга 2, содержащий все логические массивы ранга 1 длины i.