Hi Everybody - I was recently thinking of a possible use for Gray codes that work in a base greater than 2. Searching my mail on this, I was led back to a discussion from 2006 that Dan Bron had kicked off by offering the generation and conversion of Gray codes as a puzzle.
R. E. Boss, among others, took this and ran with it, resulting in this set of solutions: http://www.jsoftware.com/jwiki/RE%20Boss/Performance%20Records/Gray%20code . Alas, these were all for binary Gray codes but I want one that works in base 3, so I looked at the 0th-place entry on Mr. Boss's list (wrapped line) : ([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<0 1) ,~ 2: <@^ ] ((($~ *)@- +:@{:) , |.@]) i.@<.&.(2&^.)) And thought, do I really have to fully understand this to convert it from base 2 to base 3? It turns out, I don't. Simply by replacing the 2s with 3s (and the "0 1", which appeared to be "i.2", with "0 1 2"), I came up with this: ([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<0 1 2) ,~ 3: <@^ ] ((($~ *)@- +:@{:) , |.@]) i.@<.&.(3&^.)) Applying this to an argument to see what I get: ([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<0 1 2) ,~ 3: <@^ ] ((($~ *)@- +:@{:) , |.@]) i.@<.&.(3&^.)) 3 0 1 2 5 4 3 6 7 8 17 16 15 12 13 14 11 10 9 18 19 20 23 22 21 24 25 26 I get a promising result as it appears to be a permutation of i.3^3; this is the solution in "decimal" form. Converting this to base 3 confirms my suspicion that this actually worked: 3 3 3#:([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<0 1 2) ,~ 3: <@^ ] ((($~ *)@- +:@{:) , |.@]) i.@<.&.(3&^.)) 3 0 0 0 0 0 1 0 0 2 0 1 2 0 1 1 0 1 0 0 2 0 0 2 1 0 2 2 1 2 2 1 2 1 1 2 0 1 1 0 1 1 1 1 1 2 1 0 2 1 0 1 1 0 0 2 0 0 2 0 1 2 0 2 2 1 2 2 1 1 2 1 0 2 2 0 2 2 1 2 2 2 Rather amazing, don't you think? However, in addition to my refusal to understand the code before I modified it, I'm faced with my inability to grasp why I can't simply generalize this into a dyadic verb. I know enough to be suspicious that the "2:" or "3:" is problematic, and when I try my usual crutch of "13 :", it confirms that there is some kind of bump in the road from explicit to tacit: 13 : '([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<i.x) ,~ x <@^ ] ((($~ *)@- +:@{:) , |.@]) i.@<.&.(x&^.)) y' 4 : '([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<i.x) ,~ x <@^ ] ((($~ *)@- +:@{:) , |.@]) i.@<.&.(x&^.)) y' Though this answer is functionally correct, it's not tacit: 3 (4 : '([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<i.x) ,~ x <@^ ] ((($~ *)@- +:@{:) , |.@]) i.@<.&.(x&^.)) y') 3 0 1 2 5 4 3 6 7 8 17 16 15 12 13 14 11 10 9 18 19 20 23 22 21 24 25 26 Can anyone explain to me why "13 :" fails, or how one might retain the tacit structure with the conversion to the dyadic version? Also, there's actually a flaw in my working solution above as a better sequence would wrap from the last to the first as a Gray code too. Though this is an additional constraint not in the original puzzle, it is a useful one. For example, a good sequence for two base-3 digits would be this: 00 01 02 22 20 21 11 12 10 In this case, the last "10" Gray-codes to "00", the initial one. Any ideas on any of these questions? Thanks, Devon -- Devon McCormick, CFA ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
