6
\$\begingroup\$

Write a program or function that takes a base n and a number x, and returns or outputs the n-ary Gray code of x.

Rules

  • n is an integer in the range 2 <= n <= 16.
  • x is an integer in the range 0 <= n < 2**32.
  • The inputted numbers can either be two integer arguments if you write a function, or two arguments to ARGV or a space separated pair to STDIN if you write a program.
  • The output should be a string, either returned or printed to STDOUT.
  • If n is 10 or more, use hex digits to represent digits with a value greater than 9. The case of the digits does not matter.
  • If the n-ary Gray code of x is zero, '0' must be printed or returned.
  • Code length is in bytes, and standard loopholes are not permitted.
  • You do not need to use the same algorithm as below, but if you use a different one, make sure it produces valid Gray codes.

Example

Example code adapted from Wikipedia:

>>> import string
>>> 
>>> def nary_gray_code(base, num):
...     base_num = []
...     # Convert to num to base base
...     while num:
...         base_num.append(num % base)
...         num = num // base
...     # Convert base base number to base-ary Gray code
...     shift = 0
...     gray = []
...     for b in reversed(base_num):
...         gray.insert(0, (b + shift) % base)
...         shift += base - gray[0]
...     return "".join(string.hexdigits[i] for i in reversed(gray)) or "0"
... 
>>> nary_gray_code(2, 100)
'1010110'
>>> nary_gray_code(2, 1)
'1'
>>> nary_gray_code(2, 0)
'0'
>>> nary_gray_code(10, 23)
'21'
>>> nary_gray_code(10, 100)
'190'
>>> nary_gray_code(3, 26)
'200'
>>> nary_gray_code(3, 27)
'1200'
>>> for i in range(2, 17):
...     print(i, nary_gray_code(i, 2**32 - 1))
... 
2 10000000000000000000000000000000
3 122102120011102000122
4 3000000000000000
5 34020102231331
6 1401154214013
7 260241350125
8 34000000000
9 11762782617
10 4875571576
11 1824007509
12 92b627446
13 5b25a2c00
14 2ac96ab2b
15 197dde1a7
16 f0000000
>>>
\$\endgroup\$
  • \$\begingroup\$ Keep in mind that there are many different gray codes, so you can't test through equality with some test set. \$\endgroup\$ – orlp Apr 15 '15 at 21:15
2
\$\begingroup\$

Pyth, 20 bytes

Msme.H%dGu+G-HsGjHGY

This defines a function g which takes two integers as parameters. Take a look at this online demonstration: Pyth Compiler/Executor.

Explanation:

Msme.H%dGu+G-HsGjHGY  
M                     def g(G, H): return _
                jHG      convert H to base G
         u      jHGY     reduce(lambda G, H: _, jHG, [])
          +G-HsG            G + [H - sum(G)]
  m                      map each number d to:
   e.H%dG                   hex-representation(d % G)[-1]
 s                       sum (join all digits)

This code is a little bit confusing. There are 4 function parameters in this code: two of them are called G and two of them are called H. The G in +G-HsG is different from the G in jHG or %dG.

\$\endgroup\$
  • \$\begingroup\$ I don't think the problem description allows newline as a separator. \$\endgroup\$ – isaacg Apr 15 '15 at 10:23
  • 1
    \$\begingroup\$ @isaacg Your right. Changed it into a function, still 20 bytes. \$\endgroup\$ – Jakube Apr 15 '15 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.