## 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.

1. 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.

2. 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.

3. 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.

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

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

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

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

## Solutions

 No. Verb #@;: # 100 (6!:2) ,&'(15)' [: (7!:2) ,&'(15)' Notes Author/Sig 0 3 : '(0&,. , 1&,.@|.)^:y i.1 0' 18 29 0.0083 1311680 From Essay RogerHui 1 ~:/\^:_1"1@:#:@i.@(2&^) 15 22 0.0391 1313216 From Essay, and then independently by Raul in the Forums. See further notes 2 3 : '(,:&:\$: |.)/ i. y # 2' 14 27 0.1480 1444416 Top-down (doubly recursive). Dog slow. And I can't figure out a way to make it tacit, because I need the scope of \$: to be (,:&:\$: |.)/. -- DanBron 2006-12-04 21:09:14 3 (, ,:;.0 + */@:\$)^:(]`0:) 18 22 0.0020 1055680 Bottom up (iterative). Could be shortened. -- DanBron 2006-12-04 21:09:14 4 2 ~:/\"1 0: ,. [: #:@:i. 2 ^ ] 15 21 0.0600 6816576 See discussion section for alternate formulations -- DanBron 2006-12-04 23:32:23 5 0 _1 (] ~: |.!.0) [: #:@:i. 2 ^ ] 15 25 0.0068 2099328 Not sure if this counts as another formulation of #4. -- DanBron 2006-12-04 23:32:23 6 (22 b. _1: 33 b. ])@:(2 i.@:^ ]) 16 28 0.0007 787264 Bitwise version of #5. See notes on this solution. -- DanBron programming/2006-December/004300 7 [: +/\ 0: , (, >:@# , -@|.)^:(]`(\$@0:)) 26 32 0.0010 525312 This solution with the impressively small memory footprint is due to R.E. Boss in the Forums RE Boss 8 [:>[:(({. * #@]) ,@:+  (\$ (,: |.)))&.>/ (<0 1) ,~ 2: <@^ ] (((\$~ *)@- +:@{:) , |.@]) i.@<.&.(2&^.) 63 80 0.0002 790976 RE Boss 9 [: ({: (({. * #@]) ,@:+ (\$ (,: |.))) ((* #) ,@:+ # \$ (,: |.))^:({.`(0: , 1:)))  ] (] , 2: ^ (- 2&^)) <.@(2&^.)@<: 70 87 0.0002 791040 Another RE Boss solution, similar to his solution 7, but without the boxing. RE Boss 10 [:#: [: ({: (({. * #@]) ,@:+ (\$ (,: |.))) ((* #) ,@:+ # \$ (,: |.))^:({.`(0: , 1:)))  ] (] , 2: ^ (- 2&^)) <.@(2&^.)@<: 70 87 0.0026 791040 Equal to number 9 but binary output. RE Boss

### 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.

Puzzles/Gray Code (last edited 2008-12-08 10:45:34 by anonymous)