11
\$\begingroup\$

Any positive integer can be obtained by starting with 1 and applying a sequence of operations, each of which is either "multiply by 3" or "divide by 2, discarding any remainder".

Examples (writing f for *3 and g for /2):

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

Write a program with the following behavior:

Input: any positive integer, via stdin or hard-coded. (If hard-coded, the input numeral will be excluded from the program length.)
Output: a string of f's and g's such that <input> = 1 <string> (as in the examples). Such a string in reverse order is also acceptable. NB: The output contains only f's and g's, or is empty.

The winner is the entry with the fewest bytes of program-plus-output when 41 is the input.

\$\endgroup\$
  • 1
    \$\begingroup\$ How do you know this is true? \$\endgroup\$ – marinus Nov 7 '13 at 7:00
  • \$\begingroup\$ @marinus this is believed to be true ( but not proven yet). looking for some proof. \$\endgroup\$ – Fabinout Nov 7 '13 at 9:54
  • \$\begingroup\$ @marinus, you can prove that it's possible by descent (or equivalently by strong induction). Case-split on x mod 3: if x=3y construct y and then apply f; if x=3y+1 construct 2y+1 and apply f then g; if x=3y+2 then it gets complicated but essentially is recursive. \$\endgroup\$ – Peter Taylor Nov 7 '13 at 10:04
  • \$\begingroup\$ On a separate note, must the output be in application order or would composition order also be acceptable? \$\endgroup\$ – Peter Taylor Nov 7 '13 at 10:05
  • \$\begingroup\$ @PeterTaylor Either way is OK. \$\endgroup\$ – r.e.s. Nov 7 '13 at 12:54
3
\$\begingroup\$

GolfScript, score 64 (43-2+23)

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

(41 is hardcoded, therefore -2 characters for the score). The output is

fffgffggffggffgggffgggg

which is 23 characters (without newline). By construction the code guarantees that it always returns (one of) the shortest representations.

\$\endgroup\$
  • \$\begingroup\$ Quoting user Darren Stone in a suggested edit on this post: "I am unable to leave a comment here so I will leave an edit. This output does not include the first two characters "1 " nor are those reflected in score. Should be an easy fix and still an incredibly short solution. Cheers!" (I rejected, but thought I should carry the message) \$\endgroup\$ – Doorknob Nov 8 '13 at 1:11
  • \$\begingroup\$ @Doorknob The challenge states that the "1 " should not be included in the output. \$\endgroup\$ – Howard Nov 8 '13 at 6:52
3
\$\begingroup\$

We're getting dirty, friends!

JAVA 210 207 199 characters

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

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

output : depending on the faith of the old gods, the shortest i had was 30. Note that the output must be read from the right.

234

1 ggfgfgfgfggfggfgffgfggggfgffgfggfgfggggfgffgfggfgfggfgfggfgfgggggfffgfggfgfggfgfgggffgggggfffgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggfgfggggfgffgfggfgfggfgfggfgfggfgfggfgfggggggggggggfgfgfggggfgfgfggfffgfgfggffgfgfggfgfggggffgfgfffff

108

1 gggffgfgfggggggfggggfgffggggfgfgfgfgfgffgggfgggggfggfffggfgfffffgggffggfgfgggffggfgfgggffggggggfgfgffgfgfff

edit 45

1 ggfgfgfgfgggfggfffgfggfgfgggggggffgffgfgfff

points : 318 199+30 = 229

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

Nota Bene if you use Java 6 and not Java 7 while golfing, you can use

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

39 characters structure instead of a standard structure which is 53 characters long.

\$\endgroup\$
  • \$\begingroup\$ (2*i+1)%3==0 is equivalent to i%3==1 \$\endgroup\$ – Howard Nov 7 '13 at 10:42
  • \$\begingroup\$ Yes it is. thanks \$\endgroup\$ – Fabinout Nov 7 '13 at 10:43
  • \$\begingroup\$ if(X){A}else{if(Y){B}else{C}} is longer than if(X){A}else if(Y){B}else{C}. Also you can replace your == conditions with shorter < conditions. \$\endgroup\$ – Peter Taylor Nov 7 '13 at 11:27
  • \$\begingroup\$ @PeterTaylor true, my solution still is ugly. I don't know if the random part makes the code shorter, but it sures makes the output crappier. \$\endgroup\$ – Fabinout Nov 7 '13 at 12:32
  • \$\begingroup\$ Your f/g strings begin with 'g' (which is supposed to stand for '/2'), so they will convert 1 to 0 instead of to 41. Changing the f's to g's and vice versa, also doesn't seem to give 41. \$\endgroup\$ – r.e.s. Nov 7 '13 at 13:53
3
\$\begingroup\$

Python, score 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 chars of code (newlines as 1 each) - 2 for hard-coded input numeral + 36 chars of output

Output:

ffffffffffffffffgggggggggggggggggggg
\$\endgroup\$
  • 1
    \$\begingroup\$ If you do m=f=0 you can make the outer loop while(n!=x)*(m!=x) and remove the breaks. Brings it to 95 chars of code. \$\endgroup\$ – Daniel Lubarov Nov 8 '13 at 3:49
  • \$\begingroup\$ @Daniel: You, sir, are a gentleman and a scholar. Thanks! Your submission is still safely 10 chars ahead of me. :) \$\endgroup\$ – Darren Stone Nov 8 '13 at 5:46
  • 1
    \$\begingroup\$ You can further save a bit if you replace all n by3**f. \$\endgroup\$ – Howard Nov 8 '13 at 7:56
  • 1
    \$\begingroup\$ For input = 1, your program generates an error ("name 'g' is not defined", due to not entering the outer while-loop). \$\endgroup\$ – r.e.s. Nov 8 '13 at 15:19
  • 1
    \$\begingroup\$ You could cut out another character by writing print'f'*f+'g'*g, which would give a score of 90-2+36 = 124. \$\endgroup\$ – r.e.s. Nov 9 '13 at 0:44
3
\$\begingroup\$

Python, score 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'
\$\endgroup\$
  • \$\begingroup\$ @Darren, I wasn't sure how to interpret the output description, but you're probably right. I added the '1'. Thanks! \$\endgroup\$ – Daniel Lubarov Nov 8 '13 at 7:02
  • 1
    \$\begingroup\$ You can drop the '1' (again!) Your original interpretation of output description was correct. Enjoy the Python lead, again! :-) \$\endgroup\$ – Darren Stone Nov 8 '13 at 16:47
  • 1
    \$\begingroup\$ If you combined your 2nd, 3rd, and 4th lines into l,n,f=len(t),1,0, and removed the '1', from the print statement, your score would be 87-2+36 = 121. \$\endgroup\$ – r.e.s. Nov 9 '13 at 0:37
  • \$\begingroup\$ Thanks guys - I dropped the 1,. l,n,f=len(t),1,0 gives the same number of characters, right? (For each variable, an = and a newline is replaced with two ,s.) \$\endgroup\$ – Daniel Lubarov Nov 9 '13 at 4:07
  • \$\begingroup\$ If each newline is one character (e.g. UNIX-style LF), then the one-line and three-line versions have the same length. If each newline is two characters (e.g. MS Windows-style CR+LF), then the one-line version is two characters shorter than the three-line version. The score of 121 assumes one-character newlines. \$\endgroup\$ – r.e.s. Nov 9 '13 at 5:21
1
\$\begingroup\$

Perl, score 89 (63 - 2 + 28)

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

Conjecture: If the naive approach described in my original solution below ever reaches a cycle, that cycle will be [21, 7, 15, 5, 10, 21, ...]. As there are no counter-examples for 1 ≤ n ≤ 106, this seems likely to be true. To prove this, it would suffice to show that this is the only cycle which can exist, which I may or may not do at a later point in time.

The above solution avoids the cycle immediately, instead of guessing (wrongly), and avoiding it the second time through.

Output (28 bytes):

ggfgfgfgfggfggfgfgfggfgfgfff

Perl, score 100 (69 - 2 + 33)

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

Using a guess-and-check approach. The string is constructed using inverse operations (converting the value to 1, instead of the other way around), and the string becomes mirrored accordingly, which is allowed by the problem specification.

Whenever a non-multiple of three is encountered, it will be multiplied by two, adding one if the result would then be a multiple of three. When a multiple of three is encountered, it will be divided by three... unless this value has previously been encountered, indicating a cycle, hence guess-and-check.

Output (33 bytes):

ggfgfgfgfggfggfgffgfgggfggfgfgfff
\$\endgroup\$
1
\$\begingroup\$

J, score 103 (82-2+23)

*Note: I named my verbs f and g, not to be confused with output strings f and g.

Hard-coded:

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

General functions:

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

Did away with operating on blocks of binary numbers, which was the most important change as far as compacting g. Renamed variables and removed some whitespace for the heck of it, but everything's still functionally the same. (Usage: g 41)

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

Output: ffffffffggggggggfgffggg

f converts a list of booleans into number, using 0s as *3 and 1s as /2 (and floor). #:i.2^i creates a rank 2 array containing all the rank 1 boolean arrays of length i.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.