8
\$\begingroup\$

This challenge posed an algorithm for encoding an integer n as another integer r. What follows is a succinct explanation of that algorithm, using n=60 as an example.

The original algorithm

  • First, we encode the number as a string of brackets.

    • If n = 1, return an empty string.
    • Otherwise, we take n's prime decomposition sorted ascending and replace each element with its prime index (1-indexed) in brackets. 60 = 2*2*3*5 => [1][1][2][3]
    • Do this recursively until all we have are brackets. [1][1][2][3] => [][][[1]][[2]] => [][][[]][[[1]]] => [][][[]][[[]]]
  • Once we have our string of brackets, we convert that into an integer with the following process.

    • Convert each opening bracket to a 1 and each closing bracket to a 0. [][][[]][[[]]] => 10101100111000
    • Remove all trailing 0s and the final 1. 10101100111000 => 1010110011
    • Convert the final string of 0s and 1s from binary to an integer. 1010110011 => 691

Decoding this encoding

An interesting property of this algorithm is that it is not surjective. Not every integer can be the result of this encoding.

  • Firstly, the binary representation of the result r, must be balance-able in that the number of 0s must never exceed the number of 1s. A short falsey test case is 4, which is 100 in binary.
  • Secondly, the brackets in the binary representation must be sorted ascending when the final 1 and trailing 0s are appended once more. A short falsey test case is 12 <= 1100 <= 110010 <= (())().

However, just determining if a number is decode-able in this way would make for a short challenge. Instead, the challenge is to repeatedly decode a given input until either an un-decode-able number or a cycle is reached, and returning the resulting sequence of numbers.

The challenge

  • Given a number 1 <= r <= 2**20 = 1048576, return the sequence of numbers that r successively decodes into, starting with r itself and ending with an un-decode-able number or a cycle.
  • If an un-decode-able number is given as input, such as 4 or 12, will return a list containing only the input.
  • A sequence ending in a cycle should be indicated in some way, either by appending or prepending a marker (pick any non-positive integer, string, list, etc. as a marker, but keep it consistent), or by repeating the cycle in some way (repeating the first element, repeating the whole cycle, repeating infinitely, etc.).
  • On the off chance that any of the sequences are infinite (by increasing forever, for example), consider it undefined behavior.
  • This is code golf. Smallest number of bytes wins.

A worked example of decoding

   1 -> 1 -> 1100 -> [[]] -> [2] -> 3
-> 3 -> 11 -> 111000 -> [[[]]] -> [[2]] -> [3] -> 5
-> 5 -> 101 -> 101100 -> [][[]] -> 2*[2] -> 2*3 -> 6
-> 6 -> 110 -> 110100 -> [[][]] -> [2*2] -> [4] -> 7
-> 7 -> 111 -> 11110000 -> [[[[]]]] -> [[[2]]] -> [[3]] -> [5] -> 11
-> 11 -> 1011 -> 10111000 -> [][[[]]] -> 2*[[2]] -> 2*[3] -> 2*5 -> 10
-> 10 -> 1010 -> 101010 -> [][][] -> 2*2*2 -> 8
-> 8 -> 1000  ERROR: Unbalanced string

Test cases

4 -> [4]
12 -> [12]
1 -> [1, 3, 5, 6, 7, 11, 10, 8]
2 -> [2, 4]
13 -> [13, 13]    # cycle is repeated once
23 -> [23, 22, 14, 17]
51 -> [51, 15, 31, 127, 5381]
691 -> [691, 60]
126 -> [126, 1787, 90907]
1019 -> [1019, 506683, 359087867, 560390368728]

Suggestions and feedback for this challenge are most welcome. Good luck and good golfing!

\$\endgroup\$
  • \$\begingroup\$ Sandbox. \$\endgroup\$ – user202729 Dec 14 '17 at 6:52
  • \$\begingroup\$ How does 1 give 3? \$\endgroup\$ – Leaky Nun Dec 14 '17 at 12:15
  • \$\begingroup\$ @LeakyNun 1 --(append an 1 and trailing zeros)--> 1100 --> [[]] --> [[1]] --> [2] --> 3 \$\endgroup\$ – Colera Su Dec 14 '17 at 12:58
  • \$\begingroup\$ 6->110->110100 which isn't valid, right? So should input 1 give [1,3,5,6]? \$\endgroup\$ – dylnan Dec 15 '17 at 4:55
  • \$\begingroup\$ And for 7: 7->111->11110000->[[[[]]]]->4th prime = 7? Maybe I don't understand the algorithm \$\endgroup\$ – dylnan Dec 15 '17 at 5:00
4
\$\begingroup\$

Python 3, 379 358 339 337 327 310 304 bytes

Conjecture: Is 13 the only number that will lead to a cycle? (There are no exceptions smaller than 106.)

Fixed a bug and -7 bytes thanks to Sherlock9.
-3 byte thanks to Jonathan Frech.
-16 bytes thanks to ovs.
-6 bytes thanks to Mr. Xcoder.

If there is a cycle, it will repeat the whole cycle.

def p(a,x=0,n=1):
 while a:x+=1;a-=n%x;n*=x*x
 return x
def g(a):
 c=i=0
 for v in a:
  c+=int(v)*2-1
  if c<0:return 0,0
  if c<1:break
  i+=1
 if a:x=p(g(a[1:i])[0]);b,c=g(a[i+1:]);return(x>c>0)*(0,0)or(x*b,x)
 return 1,0
def f(a):
 x=a,
 while(x.count(a)<3)*a:a,t=g(bin(a-~a)[2:]);x+=a,
 return x[:-1]

Try it online!

Explanation:

def p(a,x=0,n=1):     # return the a-th prime
 while a:             # magical way to enumerate primes
  x+=1
  a-=n%x
  n*=x*x
 return x

def g(a):             # decode a 0/1 string
 c=i=0
 for v in a:
  c+=int(v)*2-1       # +1 if 1, -1 if 0
  if c<0: return(0,0) # c<0: unbalanced parentheses
  if c<1: break       # first outermost parentheses
  i+=1
 if a:
   x=p(g(a[1:i])[0])  # recursive solve those inside the parentheses ...
   b,c=g(a[i+1:])     # and the remaining
   if x>c and c:      # if not ascending
    return (0,0)
   return (x*b,x)     # return (result, value of first closed parentheses)
 return (1,0)         # empty string

def f(a):
 x=a,
 while a and x.count(a)<3: # detect non-decodable or cycle
  a,t=g(bin(a-~a)[2:])     # a-~a is a*2+1
  x+=a,
 return x[:-1]
\$\endgroup\$
1
\$\begingroup\$

Pyth, 62 bytes

L?b**FKme.fP_Zyd)bSIK1fTseB.u.xyvs@L,"],"\[++JjN2 1m0h-/J1/J00

Test suite

Indicates a cycle by repeating the final number.

L?b**FKme.fP_Zyd)bSIK1    Define y to decode from list format. 0 if invalid.

fTseB.u.xyvs@L,"],"\[++JjN2 1m0h-/J1/J00
     .u                                     Repeat the following until it cycles
                                            Collecting the values in a list.
                     ++JjN2 1m0h-/J1/J0     Convert the number to expanded binary
            @L,"],"\[                       Map 0 to "],", 1 to "["
           s                                Flatten to a string.
          v                                 Evaluate as a Python object.
       .x                              0    If evaluation fails, return 0.
         y                                  Otherwise decode.
  seB                                       Duplicate the final number
fT                                          Remove all 0s.
\$\endgroup\$

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.