Differences between revisions 37 and 38
 ⇤ ← Revision 37 as of 2007-09-06 19:26:21 → Size: 6830 Editor: RE Boss Comment: ← Revision 38 as of 2008-12-08 10:45:34 → ⇥ Size: 6828 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 3: Line 3: Given positive integer `n`, generate the first `2^n` [http://en.wikipedia.org/wiki/Gray_code gray codes]. Given positive integer `n`, generate the first `2^n` [[WikiPedia:Gray_code|gray codes]]. Line 10: Line 10: 1.#0 Sentence must produce the first `2^n` gray codes. That is, satisfy `(-: G)` ''or'' `(#.@:, -: G)` where `G` is [:Essays/Gray_Code:the solution given by Roger]. This constraint is absolute. 1.#0 Sentence must produce the first `2^n` gray codes. That is, satisfy `(-: G)` ''or'' `(#.@:, -: G)` where `G` is [[Essays/Gray Code|the solution given by Roger]]. This constraint is absolute. Line 12: Line 12: 1. The result must be guarunteed (predicted, fully supported) by the [wiki:JDic:contents 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. 1. The result must be guarunteed (predicted, fully supported) by the [[JDic:contents|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. Line 24: Line 24: [[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]] <
><
><
><
><
><
><
><
> Line 26: Line 26: [[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]][[BR]] <
><
><
><
><
><
><
><
><
><
><
><
><
><
><
><
><
><
><
><
><
><
><
><
> Line 30: Line 30: ||'''No.'''||'''Verb'''||'''`#@;:`'''||'''`#`'''||'''`100 (6!:2)`[[BR]]`,&'(15)'`'''||'''`[: (7!:2)`[[BR]]`,&'(15)'`'''||'''Notes'''||'''Author/Sig'''||||<)>0||`3 : '(0&,. , 1&,.@|.)^:y i.1 0'`||<)>18||<)>29||<)>0.0083||<)>1311680||From [:Essays/Gray_Code:Essay]||RogerHui||||<)>1[[Anchor(soln1)]]||`~:/\^:_1"1@:#:@i.@(2&^)`||<)>15||<)>22||<)>0.0391||<)>1313216||From [:Essays/Gray_Code:Essay], and then independently by [wiki:JForum:programming/2006-December/004270 Raul in the Forums]. See [#soln1notes further notes]||RogerHui, [wiki:Self:Raul_Miller RaulMiller]||||<)>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 [[DateTime(2006-12-04T21:09:14Z)]]||||<)>3||{{{(, ,:;.0 + */@:\$)^:(]`0:)}}}||<)>18||<)>22||<)>0.0020||<)>1055680||Bottom up (iterative). Could be shortened.||-- DanBron [[DateTime(2006-12-04T21:09:14Z)]]||||<)>4[[Anchor(soln4)]]||`2 ~:/\"1 0: ,. [: #:@:i. 2 ^ ]`||<)>15||<)>21||<)>0.0600||<)>6816576|| See discussion section for [#soln4alts alternate formulations]||-- DanBron [[DateTime(2006-12-04T23:32:23Z)]]||||<)>5[[Anchor(soln5)]]||`0 _1 (] ~: |.!.0) [: #:@:i. 2 ^ ]`||<)>15||<)>25||<)>0.0068||<)>2099328|| Not sure if this counts as another formulation of [#soln4 #4].||-- DanBron [[DateTime(2006-12-04T23:32:23Z)]]||||<)>6[[Anchor(soln6)]]||`(22 b. _1: 33 b. ])@:(2 i.@:^ ])`||<)>16||<)>28||<)>0.0007||<)>787264||Bitwise version of [#soln5 #5]. See [#soln6notes notes on this solution].||-- DanBron programming/2006-December/004300||||<)>7[[Anchor(soln7)]]||{{{[: +/\ 0: , (, >:@# , -@|.)^:(]`(\$@0:))}}}||<)>26||<)>32||<)>0.0010||<)>525312||This solution with the impressively small memory footprint is [wiki:JForum:programming/2006-December/004300 due to R.E. Boss in the Forums]||[:RE Boss]||||<)>8[[Anchor(soln8)]]||{{{[:>[:(({. * #@]) ,@:+ }}}[[BR]]{{{(\$ (,: |.)))&.>/ (<0 1) ,~ 2: <@^ ]}}}[[BR]]{{{(((\$~ *)@- +:@{:) , |.@]) i.@<.&.(2&^.)}}}||<)>63||<)>80||<)>0.0002||<)>790976||[wiki:JForum:programming/2006-December/004324 Again due to R.E. Boss in the Forums]. [#soln8notes Discussion of this solution.] ||[:RE Boss]||||<)>9[[Anchor(soln9)]]||`[: ({: (({. * #@]) ,@:+ (\$ (,: |.)))`[[BR]]{{{((* #) ,@:+ # \$ (,: |.))^:({.`(0: , 1:)))}}}[[BR]]` ] (] , 2: ^ (- 2&^)) <.@(2&^.)@<:`||<)>70||<)>87||<)>0.0002||<)>791040||Another [:RE Boss] solution, similar to his [#soln7 solution 7], but without the boxing.||[:RE Boss]||||<)>10||`[:#: [: ({: (({. * #@]) ,@:+ (\$ (,: |.)))`[[BR]]{{{((* #) ,@:+ # \$ (,: |.))^:({.`(0: , 1:)))}}}[[BR]]` ] (] , 2: ^ (- 2&^)) <.@(2&^.)@<:`||<)>70||<)>87||<)>0.0026||<)>791040||Equal to number 9 but binary output.||[:RE Boss]|| ||'''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 [[Essays/Gray Code|Essay]]||RogerHui||||<)>1<>||`~:/\^:_1"1@:#:@i.@(2&^)`||<)>15||<)>22||<)>0.0391||<)>1313216||From [[Essays/Gray Code|Essay]], and then independently by [[JForum:programming/2006-December/004270|Raul in the Forums]]. See [[#soln1notes|further notes]]||RogerHui, [[Raul Miller|RaulMiller]]||||<)>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 <>||||<)>3||{{{(, ,:;.0 + */@:\$)^:(]`0:)}}}||<)>18||<)>22||<)>0.0020||<)>1055680||Bottom up (iterative). Could be shortened.||-- DanBron <>||||<)>4<>||`2 ~:/\"1 0: ,. [: #:@:i. 2 ^ ]`||<)>15||<)>21||<)>0.0600||<)>6816576|| See discussion section for [[#soln4alts|alternate formulations]]||-- DanBron <>||||<)>5<>||`0 _1 (] ~: |.!.0) [: #:@:i. 2 ^ ]`||<)>15||<)>25||<)>0.0068||<)>2099328|| Not sure if this counts as another formulation of [[#soln4|#4]].||-- DanBron <>||||<)>6<>||`(22 b. _1: 33 b. ])@:(2 i.@:^ ])`||<)>16||<)>28||<)>0.0007||<)>787264||Bitwise version of [[#soln5|#5]]. See [[#soln6notes|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 [[JForum:programming/2006-December/004300|due to R.E. Boss in the Forums]]||[[RE Boss]]||||<)>8<>||{{{[:>[:(({. * #@]) ,@:+ }}}<
>{{{(\$ (,: |.)))&.>/ (<0 1) ,~ 2: <@^ ]}}}<
>{{{(((\$~ *)@- +:@{:) , |.@]) i.@<.&.(2&^.)}}}||<)>63||<)>80||<)>0.0002||<)>790976||[[JForum:programming/2006-December/004324|Again due to R.E. Boss in the Forums]]. [[#soln8notes|Discussion of this solution.]] ||[[RE Boss]]||||<)>9<>||`[: ({: (({. * #@]) ,@:+ (\$ (,: |.)))`<
>{{{((* #) ,@:+ # \$ (,: |.))^:({.`(0: , 1:)))}}}<
>` ] (] , 2: ^ (- 2&^)) <.@(2&^.)@<:`||<)>70||<)>87||<)>0.0002||<)>791040||Another [[RE Boss]] solution, similar to his [[#soln7|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]]|| Line 45: Line 45: * [[Anchor(soln1notes)]] Regarding [#soln1 solution 1]: The elegant phrase `~:/\^:_1"1` may encapsulate the all the `~:/\`-style solutions (4-6). Compare its definition to [#soln5 solution 5]: {{{ * <> Regarding [[#soln1|solution 1]]: The elegant phrase `~:/\^:_1"1` may encapsulate the all the `~:/\`-style solutions (4-6). Compare its definition to [[#soln5|solution 5]]: {{{ Line 48: Line 48: * [[Anchor(soln4alts)]] Regarding [#soln4 solution 4], there is a large variation in performance among the several obvious ways to code this algorithm: {{{ * <> Regarding [[#soln4|solution 4]], there is a large variation in performance among the several obvious ways to code this algorithm: {{{ Line 76: Line 76: * [[Anchor(soln6notes)]] Regarding [#soln6 solution 6]: the algorithm is the same as [#soln5 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 [[#soln6|solution 6]]: the algorithm is the same as [[#soln5|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!). Line 78: Line 78: * [[Anchor(soln8notes)]] Regarding [#soln8 solution 8]: This solution is verbose but blazingly fast (isn't there ''always'' a tradeoff?). I bet it retains its crown. Kudos, [:RE Boss]. * <> Regarding [[#soln8|solution 8]]: This solution is verbose but blazingly fast (isn't there ''always'' a tradeoff?). I bet it retains its crown. Kudos, [[RE Boss]].

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