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
1 2 3 4 5 6 7
+ 8
1234567890123456789012345678901234567890123456789012345678901234567890
+1234567890
sub{$m=sprintf('%b',shift);$n=1;for(reverse split//,$m){$_&&push@v,$n;
+$n*=2}@v}
After I decided to golf it, I got rid of $m and figured out that iterating $n = 0,1,2,... instead of $n = 1,2,4,8... would shave off three chars for an even 70 1 2 3 4 5 6 7
+ 8
1234567890123456789012345678901234567890123456789012345678901234567890
+1234567890
sub{for(reverse split//,sprintf('%b',shift)){$_&&push@v,2**$n;$n++}@v}
$,=qq.\n.;print q.\/\/____\/.,q./\ \ / / \\.,q. /_/__.,q..
Happy, sober, smart: pick two.
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...
perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
| [reply] [d/l] |
|
| [reply] |
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?
| [reply] [d/l] [select] |
Re: mini-golf: convert integer into list of powers of two
by BrowserUk (Patriarch) 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".
| [reply] [d/l] |
|
| [reply] |
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.
| [reply] [d/l] |
|
That's 32 by my reckoning...
0 1 2 3
12345678901234567890123456789012
sub{grep$_,map$_[0]&1<<$_,0..31}
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'
| [reply] [d/l] [select] |
Re: mini-golf: convert integer into list of powers of two
by moritz (Cardinal) on May 24, 2012 at 07:29 UTC
|
Here is a Perl 6 solution, not golfed very hard:
| [reply] [d/l] |
Re: mini-golf: convert integer into list of powers of two
by toolic (Bishop) on May 23, 2012 at 21:21 UTC
|
score = 56, although I don't really understand your spec. Why doesn't f(4) = 1,2,4?
# 1 2 3 4 5
# 12345678901234567890123456789012345678901234567890123456789
perl -E'$n=pop;while(2**$i<=$n){$_.=2**$i.",";$i++}chop;say'
+ 31
1,2,4,8,16
| [reply] [d/l] [select] |
|
| [reply] |
|
|