For those that don't know, a grey coded list of numbers has all numbers with a given number of bits, ordered such that there is exactly one bit changed from each item to the next, including from the first to the last item. For example, the cannonical 2 bit grey code is

00
01
11
10

The goal is to return a list ref to a list of strings comprising a grey code list for a given number of bits. Note that by strings I mean a series of ascii 1's and 0's, not the actual binay data.

My solution comes in at 101 chars: 
sub grey
{
$b=shift;
for $c (0..2**$b-1){for(-$b..-1){
$l[$c].=($c&1<<-$_-1)>>-$_-1^($c&1<<-$_)>>-$_;}}
return \@l;
}

[download]


'The fickle fascination of and Everlasting God' - Billy Corgan, The Smashing Pumpkins

Replies are listed 'Best First'.
Re: (Golf) Grey code
by no_slogan (Deacon) on Jul 28, 2001 at 04:21 UTC
    51 characters: 
    @;="";$x=0,@;=map{$_.$x,$_.($x^=1)}@;for 1..pop;\@;

    [download]
    Am I going to get myself in trouble using random punctuation mark variables like @;? It saved me one space character...

    Update: Down to 45, even passes strict and warnings! 

    [map{sprintf"%0$_[0]b",$_^$_/2}0..2**$_[0]-1]

    [download]
[reply]
[d/l]
[select]
Re: (Golf) Grey code
by abstracts (Hermit) on Jul 28, 2001 at 04:11 UTC
    Here is my go at 72: 
    sub grey{
   my($b)=@_;my$l=$b<2?['']:grey($b-1);
   [map("0$_",@$l),map"1$_",reverse@$l]
}

    [download]
    Aziz,,,
[reply]
[d/l]
      something about the fact that your recursion is considderably faster than my loops scares me...
      update: ahh... now i get it, O(n) vs O(n*log n)

      'The fickle fascination of and Everlasting God' - Billy Corgan, The Smashing Pumpkins
[reply]
(MeowChow) Re: (Golf) Grey code
by MeowChow (Vicar) on Jul 28, 2001 at 04:15 UTC
    59 chars:
      
    sub g {
  ($n=pop)--?[map("0$_",@l=@{g($n)}),map"1$_",reverse@l]:['']
}

    [download]
       MeowChow                                   
               s aamecha.s a..a\u$&owag.print
[reply]
[d/l]

Back to Meditations