Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

mini-golf: convert integer into list of powers of two

by xyzzy (Pilgrim)
on May 23, 2012 at 20:24 UTC ( #972098=perlmeditation: print w/replies, xml ) Need Help??

I want(ed) to write a function that would expand a bit field (unsigned integer) into a list of powers of two, so f(0) = (), f(4) = (4), f(13) = (1,4,8), f(31) = (1,2,4,8,16)... I thought storing options in a single field and then having a separate table for definitions was a good idea. I have since realized that I should use object-oriented relational databases the way they are designed to be used, but I still think it's an interesting exerc ise. Anyway, I came up with a 5-minute-one-liner solution and was going to post a SoPW, but after I realized I wasn't going to use it anyway and since it was a one-liner I decided to turn it into a golf meditation. I'm a pretty lousy golfer and I never came up with challenges before but I'm curious how short someone else can make this. I originally wrote it as an anonymous function, so a valid solution should start with sub{ and end with } and return a list.

My original 5-minute solution


$,=qq.\n.;print q.\/\/____\/.,q./\ \ / / \\.,q.    /_/__.,q..
Happy, sober, smart: pick two.

Replies are listed 'Best First'.
Re: mini-golf: convert integer into list of powers of two
by tobyink (Canon) on May 23, 2012 at 22:19 UTC

    Riding on BrowserUK's coat tails, I'm down to 31 characters...

    sub{grep$_[0]&($_=2**$_),0..31}
    perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'

      Very, very nice++

      It'd never occurred to me to assign to $_ in grep, but it deals perfectly with the duplication in my attempt. I can see me using that in the future.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

      The start of some sanity?

Re: mini-golf: convert integer into list of powers of two
by moritz (Cardinal) on May 24, 2012 at 08:13 UTC

    This is not a solution, but a tale of a solution that didn't work out.

    I thought: hey, why not solve it with regexes?

    First, convert the number $n to a string of length $n,  1 x $n. Then write a regex that matches only strings of lengths that are powers of two. then do (1 x $n) =~ /^(?:($that_regex)(?{ say length $1}))*

    and be happy.

    You can recursively define powers of two as

    n_0 = 1 n_i = n_(i-1) + n_(i-1)

    That should be straight forward to mold into a regex, no? After all, our regexes are recursive:

    say (1 x 5) =~ /^(1|((?1))\2)*$/

    Unfortunately Perl 5 does not agree: Infinite recursion in regex

    The problem is that as soon as all the 1s are exhausted, the regex engine endlessly recurses (the (?1) branch) while not consuming any characters.

    So, if only the end is the problem, maybe we can just stop recursing when we're at the end of the string? Look-aheads to the rescue:

    (1 x 5) =~ /^(?:(1|((?=1)(?1))\2)(?{ say length $1 }))*$/

    And indeed, it matches. But it only ever matches chunks of length 1, because the left alternative is tried first. So the |1 would need to go at the end, but then it's still infinite recursion, because the recursion occurs before consuming any characters.

    I know this isn't what regexes are meant for, but I'd still like it to work. Unfortunately I've run out of ideas for now. Does anybody know how to fix it?

Re: mini-golf: convert integer into list of powers of two
by Jenda (Abbot) on May 24, 2012 at 09:19 UTC

    31

    (on a 32 bit perl only the first 31 bits may be used, on a 64 bit one, it's the first 63. I can't tell perl the number is unsigned.

    Jenda
    Enoch was right!
    Enjoy the last years of Rome.

      That's 32 by my reckoning...

      Using the assign-within-grep trick I applied to BrowserUK's solution, it is possible to take it down to 31 though:

      0 1 2 3 1234567890123456789012345678901 sub{grep$_[0]&($_=1<<$_),0..31}
      perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
Re: mini-golf: convert integer into list of powers of two
by BrowserUk (Pope) on May 23, 2012 at 20:44 UTC

    34


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

    The start of some sanity?

      Nice, but breaks on 32-bit Perl.

      perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
Re: mini-golf: convert integer into list of powers of two
by moritz (Cardinal) on May 24, 2012 at 07:29 UTC
Re: mini-golf: convert integer into list of powers of two
by toolic (Bishop) on May 23, 2012 at 21:21 UTC

      f(7) is (1,2,4) because 7 is 1+2+4.

      perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://972098]
Approved by BrowserUk
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (5)
As of 2021-06-20 22:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What does the "s" stand for in "perls"? (Whence perls)












    Results (96 votes). Check out past polls.

    Notices?