Puzzles/Gray Code
< Puzzles
Jump to navigation
Jump to search
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.
- 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.
- 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.
- 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.
- Among sentences that satisfy the preceding constraints equally, those with the smallest number of words are preferred. That is, minimize #@:;:.
- Among sentences that satisfy the preceding constraint equally, those the smallest number of total necessary characters are preferred. That is, minimize #.
- Among sentences that satisfy the constraints 1 2 3 equally, the fastest are preferred. That, is, minimize 6!:2.
- Among sentences that satisfy the preceding constraint within a factor of two, the leanest are preferred. That, is, minimize 7!:2.
Spoiler Alert!
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 Roger Hui 1 ~:/\^:_1"1@:#:@i.@(2&^)
15 22 0.0391 1313216 From Essay, and then independently by Raul in the Forums. See further notes Roger Hui, 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(,:&:$: |.)/
.-- Dan Bron <<DateTime(2006-12-04T21:09:14Z)>> 3 (, ,:;.0 + */@:$)^:(]`0:)
18 22 0.0020 1055680 Bottom up (iterative). Could be shortened. -- Dan Bron <<DateTime(2006-12-04T21:09:14Z)>> 4 2 ~:/\"1 0: ,. [: #:@:i. 2 ^ ]
15 21 0.0600 6816576 See discussion section for alternate formulations -- Dan Bron <<DateTime(2006-12-04T23:32:23Z)>> 5 0 _1 (] ~: |.!.0) [: #:@:i. 2 ^ ]
15 25 0.0068 2099328 Not sure if this counts as another formulation of #4. -- Dan Bron <<DateTime(2006-12-04T23:32:23Z)>> 6 (22 b. _1: 33 b. ])@:(2 i.@:^ ])
16 28 0.0007 787264 Bitwise version of #5. See notes on this solution. -- Dan Bron 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 Again due to R.E. Boss in the Forums. Discussion of this solution. 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