[10/12/15] Powers of Two

Discussion in 'Programming' started by BlizzardFyre, Oct 12, 2015.

Thread Status:
Not open for further replies.
  1. Hello World!

    This is week two of the programming challenge of the week.

    This weeks challenge: Write a method that will print any number as a power of two. Your method must have the prototype: "private String pow2(int n)" and contain a return statement.

    Example:

    pow2(12); returns "8 4"
    pow2(13); returns "8 4 1"
    pow2(15); returns "8 4 2 1"

    The rules are posted here.

    You can use any method you want. I got this challenge idea from a TA in a class I took last year. It is very entertaining, and I hope you all enjoy it as well. I have found this challenge online with C or C++, so trust me the solution in Java is not out there.

    Submissions close 10/19/2015

    Happy Golfing!
     
  2. samczsun

    Supporter

    Code (Text):

    private native String pow2(int n);
     
    34 chars

    EDIT:
    Look down for my latest entry
     
    #2 samczsun, Oct 12, 2015
    Last edited: Oct 13, 2015
    • Funny Funny x 1
    • Winner Winner x 1
  3. Actually doing the challenge (unlike @samczsun ) i came up with this:

    Code (Text):
     
        private static String pow2(int n) {
            String result = Integer.toBinaryString(n);
            int s = result.length();
            for (int i = result.length(); i > 0; i--) {
                result += result.charAt(i - 1) == '1' ? " " + (int) Math.pow(2, s - i) : "";
            }
            return result.substring(s + 1);
        }
     
    Compressed version (182 bytes):
    Code (Text):

        private String pow2(int n){String r=Integer.toBinaryString(n);int s=r.length();for(int i=r.length();i>0;i--)r+=r.charAt(i-1)=='1'?" "+(int)Math.pow(2,s-i):"";return r.substring(s+1)}
     
     
    #3 kmecpp, Oct 12, 2015
    Last edited: Oct 12, 2015
  4. samczsun

    Supporter

    @kmecpp
    Oi m8 mai s0lutin is sh0rter than urs
     
  5. Although I can understand English pretty well, this questions is difficult to understand for me.

    Do you mind adding some extra explanation ?
     
  6. Didn't see the spoiler :\
     
  7. Screw you people, 106 characters
    Code (Java):
    private String pow2(int n){
    String s="";
    for(int i=1;i<n;i*=2)if((n&i)==i)s+=i+" ";
    return s.trim();
    }
    Still need to reverse the output, I'm getting '4 8' on 12 xD

    [EDIT] 99100 characters
    Code (Java):
    private String pow2(int n){String s="";for(int i=1;i<=n;i*=2)if((n&i)==i)s=i+" "+s;return s.trim();}
    [EDIT #2] @samczsun pointed out that it doesn't work for pow2 numbers (1, 2, 4, 8, etc) so I had to add another char: < has to be <= (in the for loop)

    [EDIT #3] While still trying to compress, I found a recursive solution which leads to a result with one space character too many and 99 chars used. Still a nice find imo.
    Code (Java):
    private String pow2(int n){int i=Integer.highestOneBit(n);if(i>0)return i+" "+pow2(n-i);return "";}
    [EDIT #4] @CrypticStorm Mentioned I missed a ternary replacement, and @samczsun remembered me of the \b character to fix the leftover whitespace in the recursive solution (which is a cheat, but apparently works on most consoles), which brings us to 91 characters
    Code (Java):
    private String pow2(int n){int i=Integer.highestOneBit(n);return i>0?i+" "+pow2(n-i):"\b";}
     
    #7 DarkSeraphim, Oct 12, 2015
    Last edited: Oct 12, 2015
    • Winner Winner x 2
  8. Code (Text):

        private String pow2(int n) {
            StringBuffer b = new StringBuffer();
            int pow2;
            while (n > 0) {
                pow2 = 1;
                while (pow2 <= n) pow2 <<= 1;
                n -= (pow2 >>= 1);
                b.append(pow2).append(' ');
            }
            return b.toString();
        }
     
    Compressed
    Code (Text):

    private String pow2(int n){StringBuffer b=new StringBuffer();int pow2;while(n>0){pow2=1;while(pow2<=n)pow2<<=1;n-=(pow2>>=1);b.append(pow2).append(' ');}
    return b.toString();}
     
     
  9. 1) edit javac
    2) change symbol table for ++ operator
    3) 3 char solution
    4) ????
    5) profit
     
  10. Welp i misread the header that stated the solution needed to be in Java, but I got down to 80 characters in python.
    Code (Text):
    def pow2(x):return p(x)[1:]
    def p(x):d=x&~-x;return p(d)+" "+str(x-d)if(x)else""
    The magic comes from the beginning of p(x) which defined d in simpler terms as x&x-1 which if you do the logic is x with it's last 1 removed. By taking x-d i can get the value to print, and d is the number to continue with and get it's last 1 until the number reaches zero.

    Maybe I'll try this in Java, but I don't like golfing Java, so have fun with this solution. :D

    EDIT: Never mind, I translated my solution to Java. 82 characters
    Code (Text):
    private String pow2(int n) {int d=n&n-1;return n>0?(pow2(d)+" "+(n-d)).trim():"";}
    EDIT: Oops forgot a space, 81. Thanks @samczsun
    Code (Text):
    private String pow2(int n){int d=n&n-1;return n>0?(pow2(d)+" "+(n-d)).trim():"";}
    EDIT: Don't even bother defining d, it takes too many chars. 79
    Code (Text):
    private String pow2(int n){return n>0?(pow2(n&n-1)+" "+(n-(n&n-1))).trim():"";}
    EDIT: Use -= assignment to add 1 char remove extra parentheses set, 78
    Code (Text):
    private String pow2(int n){return n>0?(pow2(n&n-1)+" "+(n-=n&n-1)).trim():"";}
    EDIT: Move .trim() to the outside of the ternary, allowing the new parentheses to replace the space after return. 77
    Code (Text):
    private String pow2(int n){return(n>0?pow2(n&~-n)+" "+(n-=n&~-n):"").trim();}
    EDIT: Went back to my python solution after these optimizations. Python down to 67
    Code (Text):
    def pow2(x):d=x&~-x;return(pow2(d)+" "+str(x-d)if(x)else"").strip()
     
    #10 CrypticStorm, Oct 12, 2015
    Last edited: Oct 12, 2015
    • Winner Winner x 7
  11. samczsun

    Supporter

    @CrypticStorm

    Code (Text):
    private String pow2(int n){return(n>0?pow2(n-(n-=n&~-n))+" "+n:"").trim();}
    75

    If you don't mind the leading space:
    Code (Text):
    private String pow2(int n){return n>0?pow2(n-(n-=n&~-n))+" "+n:"";}
    67

    If you got rid of the silly method name
    Code (Text):
    private String a(int n){return n>0?a(n-(n-=n&~-n))+" "+n:"";}
    61

    If you just don't care
    Code (Text):
    private native String a(int n);
    31
     
    #11 samczsun, Oct 13, 2015
    Last edited: Oct 14, 2015
    • Winner Winner x 3
  12. This can be reduced to: (if my java has an error, then the semantics are fine, I just didn't do this in an ide)
    Code (Java):
    private String pow2(int n){int i=Integer.highestOneBit(n);return i>0?i+" "+pow2(n-i):"";}
     
  13. Already got that ages ago xD.
     
    • Useful Useful x 1
  14. Dank memes.
     
  15. And we have a winner! Congratulations to @samczsun,

    Honorable mention to @CrypticStorm who was two bytes off.

    Stay tuned for the next challenge, it will be posted momentarily.
     
  16. Cldfire

    Cldfire Retired Moderator
    Retired

Thread Status:
Not open for further replies.