Talk:Puzzles/Gray Code

From J Wiki
Jump to: navigation, search

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.