Puzzles/Gray Code

Problem

Given positive integer n, generate the first 2^n gray codes.

Constraints

This problem is amenable to J solutions. Though explicit constraints are given below, they can not measure the most important qualities of a superior solution: novelty, elegance, and innovative use of the language. Don't expend too much effort trying to shorten, speed up, or trim down solutions. What's interesting here is a variety of solutions, not large sets of differently-worded identical algorithms.

0. Sentence must produce the first 2^n gray codes. That is, satisfy (-: G) or (#.@:, -: G) where G is the solution given by Roger. This constraint is absolute.

1. The result must be guarunteed (predicted, fully supported) by the Dictionary. To put it another way, you may not leverage bugs in the implementation (but you may leverage bugs in the documentation). This constraint is absolute.

2. Assume you're running under jconsole -jprofile: that is, you may not depend on any sentence having been executed before your own. Put another way, do not rely on the names normally defined by the J standard library. This constraint is absolute.

3. Among sentences that satisfy the preceding constraints equally, those with the smallest number of words are preferred. That is, minimize #@:;:.

4. Among sentences that satisfy the preceding constraint equally, those the smallest number of total necessary characters are preferred. That is, minimize #.

5. Among sentences that satisfy the constraints 0 1 2 equally, the fastest are preferred. That, is, minimize 6!:2.

6. Among sentences that satisfy the preceding constraint within a factor of two, the leanest are preferred. That, is, minimize 7!:2.

Spoiler Alert!

Solutions

Discussion

• Regarding solution 1: The elegant phrase ~:/\^:_1"1 may encapsulate the all the ~:/\-style solutions (4-6). Compare its definition to solution 5:

     ~:/\ b. _1
  (~: |.!.0) :.(~:/\)

  However, since this is "hidden information", it is better to treat ~:/\^:_1"1 as a different algorithm, and let the others stand. (Though it does lead to the idea ~:/\^:_1&.|:@:#:@i.@(2&^))

• Regarding solution 4, there is a large variation in performance among the several obvious ways to code this algorithm:

  NB. Formulations:
  
     j =:  2  ~:/\"1(_ , -@:>:)      {. [: #:@:i. 2 ^ ]   
     k =:  2  ~:/\         "(1)  0   ,. [: #:@:i. 2 ^ ]
     l =:  2  ~:/\         " 1   0:  ,. [: #:@:i. 2 ^ ]
     m =:  2  ~:/\         &.|   0:  ,. [: #:@:i. 2 ^ ]
     n =:  2  ~:/\         &.|:  0   ,. [: #:@:i. 2 ^ ]
     o =:  2 (~:/\ 0:  , ])&.|:         [: #:@:i. 2 ^ ]
     p =:  2 (~:/\ 0   , ])&.|:         [: #:@:i. 2 ^ ]
     q =:  2 (~:/\ -@:>:@:# {. ])&.|:   [: #:@:i. 2 ^ ]
  
     NB.  Compared
  
   set   alg time space 
  ------  -  ---- -----
                        
          j  6.26 1.00  
          k  6.36 1.00  
          l  4.76 4.33  
   n=15   m  2.67 5.66  
          n  1.35 2.00  
          o  1.47 4.66  
          p  1.05 2.00  
          q  1.00 2.00  

• Regarding solution 6: the algorithm is the same as solution 5, but the operations are bitwise. This is probably the way a C or assembler programmer would solve this puzzle. The verb can generate solutions all the way up to n=25 before running out of memory (and in less than a second, at that!).

• Regarding solution 8: This solution is verbose but blazingly fast (isn't there always a tradeoff?). I bet it retains its crown. Kudos, RE Boss.