10
\$\begingroup\$

Given the functions

L: (x, y) => (2x - y, y)
R: (x, y) => (x, 2y - x)

and a number N generate a minimal sequence of function applications which take the initial pair (0, 1) to a pair which contains N (i.e. either (x, N) or (N, y)).

Example: N = 21. The minimal sequence is of length 5, and one such sequence is

          (  0,  1)
1. L ---> ( -1,  1)
2. L ---> ( -3,  1)
3. R ---> ( -3,  5)
4. L ---> (-11,  5)
5. R ---> (-11, 21)

Write the shortest function or program you can which generates a minimal sequence in O(lg N) time and O(1) space. You may output / return a string in either application order (LLRLR) or composition order (RLRLL), but document which.

\$\endgroup\$

3 Answers 3

2
\$\begingroup\$

Perl, 82 81 Characters (complete program)

$n=<>;@_=(R,L);if($n<0){$n=1-$n;$a--}while($n>1){print$_[$n%2+$a];$n+=$n%2;$n/=2}

It takes one number as input, and it outputs the sequence in application order.

Edit: Instead of redefining the array in the if statement, set a number to negative one and add it to the index when the array is referenced. It achieves the same effect.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 55 or 39 characters

f=->n{(n>0?n-1:-n).to_s(2).tr'01',n>1?'LR':n<0?'RL':''}

The function returns the function sequence in composition order.

Usage:

puts f[21]     # RLRLL
puts f[-6]     # LLR

Edit: If we allow recursion (which violates the O(1) memory constraint but such does any function since the return value itself is O(lg n)) we can shrink the code to 39 characters.

f=->n{n<n*n ?f[(n-1)/2+1]+'RL'[n%2]:''}
\$\endgroup\$
0
\$\begingroup\$

Jelly, 15 bytes

“”HĊß;ị⁾LR$ƲḂƑ?

Try it online!

This uses the same allowance in Howard's answer, in that we can use recursion, despite it violating the \$O(1)\$ memory requirement. If this isn't allowed, then the following 20 byte solution works instead:

ḶȯAṀ©Bị⁾LRUAƑ}¡$®aḟ0

Try it online!

Both output the composition order

How they work

“”HĊß;ị⁾LR$ƲḂƑ? - Main link f(N). Takes N on the left
              ? - If statement:
             Ƒ  -   If: Invariant under:
            Ḃ   -     Bit; Yields 1 for 0/1, else 0
“”              -   Then: Return the empty string
           Ʋ    -   Else:
  H             -     N÷2
   Ċ            -     Ceiling
    ß           -     f(⌈N÷2⌉)
          $     -     Group the previous 2 links together as a monad g(N):
       ⁾LR      -       "LR"
      ị         -       Modular index N into "LR"
     ;          -     Append to f(⌈N÷2⌉)

The 20 byte version (+6 bytes to handle \$N = 0, 1\$):

ḶȯAṀ©Bị⁾LRUAƑ}¡$®aḟ0 - Main link. Takes N on the left
Ḷ                    - [0, 1, ..., N-1] for N > 0 else []
  A                  - abs(N)
 ȯ                   - Replace [] with abs(N)
   Ṁ                 - Max; N-1 if N > 0 else abs(N)
    ©                - Save this to the register R
     B               - Convert R to binary
               $     - Group the previous 2 links into a monad f(N):
       ⁾LR           -   "LR"
             }       -   To N:
            Ƒ        -     Invariant under:
           A         -       Absolute value; 1 if N ≥ 0 else 0
              ¡      -   Do the following that many times:
          U          -     Reverse "LR"
                         This yields "RL" if N ≥ 0 else "LR" 
      ị              - For each bit in R, index into "RL" or "LR",
                       yielding a list of Rs and Ls, S
                ®    - Yield R
                 a   - Replace all but R = 0 with S
                  ḟ0 - Change R = 0 to []
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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