15
\$\begingroup\$

Introduction

A pointer array is an array L of nonzero integers where 0 ≤ L[i]+i < len(L) holds for all indices i (assuming 0-based indexing). We say that the index i points to the index L[i]+i. A pointer array is a loop if the indices form a single cycle of length len(L). Here are some examples:

  • [1,2,-1,3] is not a pointer array, because the 3 does not point to an index.
  • [1,2,-1,-3] is a pointer array, but not a loop, because no index points to the -1.
  • [2,2,-2,-2] is a pointer array, but not a loop, because the indices form two cycles.
  • [2,2,-1,-3] is a loop.

Input

Your input is a non-empty list of nonzero integers, in any reasonable format. It may be unsorted and/or contain duplicates.

Output

Your output shall be a loop that contains all the integers in the input list (and possibly other integers too), counting multiplicities. They need not occur in the same order as in the input, and the output need not be minimal in any sense.

Example

For the input [2,-4,2], an acceptable output would be [2,2,-1,1,-4].

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Including a couple of example inputs and outputs in your answer is appreciated.

Test cases

These are given in the format input -> some possible output(s).

[1] -> [1,-1] or [1,1,1,-3]
[2] -> [2,-1,-1] or [1,2,-2,-1]
[-2] -> [1,1,-2] or [3,1,2,-2,-4]
[2,-2] -> [2,-1,1,-2] or [2,-1,2,-2,-1]
[2,2,2] -> [2,-1,2,-2,2,-2,-1] or [2,2,2,2,-3,-5]
[2,-4,2] -> [2,2,-1,1,-4] or [2,5,1,1,1,-4,2,-7,-1]
[3,-1,2,-2,-1,-5] -> [2,3,-1,2,-1,-5] or [3,3,-1,-1,2,2,-1,6,1,1,1,1,-12,-5]
[-2,-2,10,-2,-2,-2] -> [10,-1,1,-2,-2,1,-2,-2,1,-2,-2]
[-15,15,-15] -> [15,-1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,-15,-15]
[1,2,3,4,5] -> [1,2,3,-1,4,-1,5,-1,-1,-9,-1,-1]
\$\endgroup\$
11
\$\begingroup\$

Jelly, 12 bytes

ż~Ṣ€FxA$;L$U

Try it online!

Background

Consider the pair of integers n, ~n, where n ≥ 0 and ~ denotes bitwise NOT, i.e., ~n = -(n + 1).

By placing n copies of n to the left of n + 1 copies of ~n, if we start traversing the pointer array from the rightmost ~n, we'll traverse all 2n + 1 elements and find ourselves at the left of the leftmost n.

For example, if n = 4:

X  4  4  4  4  -5 -5 -5 -5 -5
                            ^
            ^
                         ^
         ^
                      ^
      ^
                   ^
   ^
                ^
^

For the special case n = 0, the element n itself is repeated 0 times, leaving this:

X -1
   ^
^

For each integer k in the input, we can form a pair n, ~n that contains k by setting n = k if k > 0 and n = ~k if k < 0. This works because ~ is an involution, i.e., ~~k = k.

All that's left to do is chain the generated tuples and prepend their combined lengths, so the leftmost element takes us back to the rightmost one.

Examples

[1] -> [3, 1, -2, -2]
[2] -> [5, 2, 2, -3, -3, -3]
[-2] -> [3, 1, -2, -2]
[2, -2] -> [8, 1, -2, -2, 2, 2, -3, -3, -3]
[2, 2, 2] -> [15, 2, 2, -3, -3, -3, 2, 2, -3, -3, -3, 2, 2, -3, -3, -3]
[2, -4, 2] -> [17, 2, 2, -3, -3, -3, 3, 3, 3, -4, -4, -4, -4, 2, 2, -3, -3, -3]
[3, -1, 2, -2, -1, -5] -> [26, 4, 4, 4, 4, -5, -5, -5, -5, -5, -1, 1, -2, -2, 2, 2, -3, -3, -3, -1, 3, 3, 3, -4, -4, -4, -4]
[-2, -2, 10, -2, -2, -2] -> [36, 1, -2, -2, 1, -2, -2, 1, -2, -2, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, 1, -2, -2, 1, -2, -2]
[-15, 15, -15] -> [89, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15]
[1, 2, 3, 4, 5] -> [35, 5, 5, 5, 5, 5, -6, -6, -6, -6, -6, -6, 4, 4, 4, 4, -5, -5, -5, -5, -5, 3, 3, 3, -4, -4, -4, -4, 2, 2, -3, -3, -3, 1, -2, -2]

How it works

ż~Ṣ€FxA$;L$U  Main link. Argument: A (list of integers)

 ~            Yield the bitwise not of each k in A.
ż             Zipwith; pair each k in A with ~k.
  Ṣ€          Sort each pair, yielding [~n, n] with n ≥ 0.
    F         Flatten the list of pairs.
       $      Combine the previous two links into a monadic chain:
      A         Yield the absolute values of all integers in the list.
                |n| = n and |~n| = |-(n + 1)| = n + 1
     x          Repeat each integer m a total of |m| times.
          $   Combine the previous two links into a monadic chain:
         L      Yield the length of the generated list.
        ;       Append the length to the list.
           U  Upend; reverse the generated list.
\$\endgroup\$
  • \$\begingroup\$ You don't need to handle the special case n = 0, because the spec says "nonzero integers". \$\endgroup\$ – Peter Taylor Apr 6 '16 at 19:49
  • \$\begingroup\$ While 0 will never occur in the input, I still need the pair 0, -1 if -1 does. \$\endgroup\$ – Dennis Apr 6 '16 at 20:17

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.