12
\$\begingroup\$

Lets define a pointer sequence to be any sequence such that a(n) = a((n-1)-(a(n-1))) forall n greater than some finite number. For example if our sequence begun with

3 2 1 

Our next term would be 2, because a(n-1) = 1, (n-1)-1 = 1, a(1) = 2 (this example is zero index however it does not matter what index you use the calculation will always be the same.). If we repeat the process we get the infinite sequence

3 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2

Task

Given some initial array of positive integers output the pointer sequence starting with that array.

Output types

Output is intended to be flexible, if you choose to write a function as your program it can return, either an infinite list of integers or a function that indexes the sequence. If you choose to write a full program you may output terms of the sequence indefinitely.

You may also choose to take two inputs, the starting array and an index. If you choose to do this you need only output the term of the sequence at that index.


You will never be given a sequence that requires indexing before the beginning of the sequence. For example 3 is not a valid input because you would need terms before the 3 to resolve the next term.

This is so your score will be the number of bytes in your program with a lower score being better.

Test Cases

test cases are truncated for simplicity

2 1   -> 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 ...
2 3 1 -> 2 3 1 3 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 ...
3 3 1 -> 3 3 1 3 3 3 1 3 3 3 1 3 3 3 1 3 3 3 1 3 3 3 1 3 3 3 1 3 ...
4 3 1 -> 4 3 1 3 4 4 3 3 4 4 4 3 4 4 4 4 3 4 4 4 4 3 4 4 4 4 3 4 ...
\$\endgroup\$
  • \$\begingroup\$ Is it allowed to output n extra terms in addition to the input array? Or the n-th term starting after those provided as input? \$\endgroup\$ – Luis Mendo Oct 11 '17 at 19:34
  • \$\begingroup\$ @LuisMendo Sure any indexing is fine. \$\endgroup\$ – Sriotchilism O'Zaic Oct 11 '17 at 20:41

15 Answers 15

8
\$\begingroup\$

JavaScript (ES6), 25 bytes

a=>f=n=>a[n]||f(--n-f(n))

An anonymous function that, when called, creates a function f that gives the item at a given index in the sequence.

Please let me know if I misunderstood anything...

\$\endgroup\$
  • \$\begingroup\$ You call f(n) from in f(n). I don't think that will ever terminate, but I don't know JS. \$\endgroup\$ – Sriotchilism O'Zaic Oct 11 '17 at 15:20
  • \$\begingroup\$ @FunkyComputerMan When n gets low enough the a[n] will return a truthy value, so the || will short-circuit and prevent it from infinitely recursing. \$\endgroup\$ – ETHproductions Oct 11 '17 at 15:21
  • \$\begingroup\$ Yeah I got that but n doesn't get any lower with each call. I'm pretty sure if n is greater than the length of a you will never halt. \$\endgroup\$ – Sriotchilism O'Zaic Oct 11 '17 at 15:22
  • 2
    \$\begingroup\$ @FunkyComputerMan It goes get lower with each call, --n assign n to n-1 so the next reference to it will refer to the decremented n. \$\endgroup\$ – Erik the Outgolfer Oct 11 '17 at 15:23
  • 2
    \$\begingroup\$ @FunkyComputerMan --n decrements n, which means that f(--n-f(n)) is the same as f((n-1)-f(n-1)) \$\endgroup\$ – ETHproductions Oct 11 '17 at 15:23
5
\$\begingroup\$

Husk, 7 6 bytes

¡S!o_L

Returns an infinite list. Try it online! Note that it takes a while for TIO to truncate and print the result.

Explanation

The operator ¡ has several meanings. Here I'm using "construct infinite list by iterating a function that computes a new element from the list of existing ones". Given a list of length N, the new element will have 1-based index N+1. All we need to do is negate the last element of the list (which is the previous value) and index into the list using the result.

¡S!o_L  Implicit input.
¡       Construct infinite list by iterating this function on input:
 S!      Element at index
    →    last element
  o_     negated.
\$\endgroup\$
4
\$\begingroup\$

Haskell, 36 bytes

Takes a list and returns a function that indexes the sequence

l!n|n<length l=l!!n|e<-n-1=l!(e-l!e)

Try it online!

Explanation

Here we are defining a function ! that takes a list l and a index n. If n is less than the length of l we index l by n, otherwise we return l!((n-1)-l!(n-1)). This follows the recursive definition of the function I gave in the question.

Here is the same program ungolfed.

a l n
 |n<length l = l!!n
 |otherwise = (a l) ((n-1) - (a l) (n-1))

I use e<-n-1 instead of otherwise to save bytes while assigning n-1 to e so it can be used later.

\$\endgroup\$
4
\$\begingroup\$

MATL, 13 9 bytes

:"tt0)_)h

Outputs the initial terms followed by n additional terms (allowed by the challenge), where n is a positive integer taken as input.

Try it online!

Explanation

:"      % Implicitly input n. Do the following n times
  tt    %    Duplicate the sequence so far, twice. In the first iteration this
        %    implicitly inputs the array of initial terms
  0)    %    Get value of the last entry, say m
  _)    %    Get value of the entry which is m positions back from the last
  h     %    Append. This extends the array with the new entry
        % Implicit end. Implicitly display
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 63 bytes

takes two inputs

(Clear@a;(a@#2[[1]]=#)&~MapIndexed~#;a@n_:=a[n-1-a[n-1]];a@#2)&  

Try it online!

-3 bytes from Martin Ender

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

R, 55 bytes

f=function(a,n)"if"(n<=sum(a|1),a[n],f(a,n-1-f(a,n-1)))

Try it online!

Takes two inputs.

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

Standard ML (MLton), 58 bytes

fun a$n=if n<length$then List.nth($,n)else a$(n-1-a$(n-1))

Try it online! The function a takes the initial list and an index and returns the sequence element at that index. Example usage: a [4,3,1] 5 yields 4.

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

Jelly, 6 bytes

NṪịṭµ¡

Takes a sequence S and an integer k, and adds k terms to S.

Try it online!

How it works

NṪịṭµ¡  Main link. Left argument: S (sequence). Right argument: k (integer)

    µ¡  Combine the links to the left into a (variadic) chain and call it k times.
        The new chain started by µ is monadic, so the chain to the left will be
        called monadically.
N           Negate; multiply all elements in S by -1.
 Ṫ          Tail; retrieve the last element, i.e., -a(n-1).
  ị         At-index; retrieve the element of S at index -a(n-1).
            Since indexing is modular and the last element has indices n-1 and 0,
            this computes a( (n-1) - a(n-1) ).
   ṭ        Tack; append the result to S.
\$\endgroup\$
1
\$\begingroup\$

Python 2, 48 bytes

a=lambda S,n:n<len(S)and S[n]or a(S,~a(S,~-n)+n)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

CJam, 10 bytes

{{(_j-j}j}

For CJam, this does very well (It even beats 05ab1e!).

This is an anonymous block that expects input in the form i n on the stack, where i is the index in the sequence and n is an array of starting numbers.

The reason this works so well is because of the j operator, which provides memoized recursion from a set of starting values.

Explanation:

{    Function j(n) with [j(0), j(1), j(2)] = [4, 3, 1], return j(6):
 (    Decrement:    5
 _    Duplicate:    5 5
 j    j(5):
  (    Decrement:   5 4
  _    Duplicate:   5 4 4
  j    j(4):
   (    Decrement:  5 4 3
   _    Duplicate:  5 4 3 3
   j    j(3):
    (    Decrement: 5 4 3 2
    _    Duplicate: 5 4 3 2 2
    j    j(2) = 1:  5 4 3 2 1
    -    Subtract:  5 4 3 1
    j    j(1) = 3:  5 4 3 3
   -    Subtract:   5 4 0
   j    j(0) = 4:   5 4 4
  -    Subtract:    5 0
  j    j(0) = 4:    5 4
 -    Subtract:     1
 j    j(1) = 3:     3
}j   End:           3
\$\endgroup\$
1
\$\begingroup\$

Java (8), 60 bytes

int a(int[]a,int n){return n<a.length?a[n]:a(a,--n-a(a,n));}

Takes two inputs (integer-array a and integer n), and outputs the n'th value of the sequence.

Explanation:

Try it here. (Might take a few seconds.)

int a(int[]a,int n){        // Method with int[] and int parameters and int return-type
  return n<a.length?        //  If input `n` is smaller than the length of the array:
          a[n]              //   Output the `n`'th item of the array
         :                  //  Else:
          a(a,--n-a(a,n));  //   Recursive call with `n-1-a(n-1)`
}                           // End of method
\$\endgroup\$
0
\$\begingroup\$

Perl, 38 +3 (-anl) bytes

{print;push@F,$_=$F[$#F-$F[$#F]];redo}

Try It Online

\$\endgroup\$
  • \$\begingroup\$ Your TIO link goes to a different program. \$\endgroup\$ – Xcali Oct 11 '17 at 18:22
  • \$\begingroup\$ @Xcali i fixed the link but couldn't execute because could not established a connection with the server. \$\endgroup\$ – Nahuel Fouilleul Oct 11 '17 at 19:19
0
\$\begingroup\$

05AB1E, 20 bytes

#`r[=ˆŽ¼}[¯¾¯¾è-è=ˆ¼

Expects the input as a space-separated string, keeps outputting indefinitely; pretty straightforward implementation

Example run:

$ 05ab1e -e '#`r[=ˆŽ¼}[¯¾¯¾è-è=ˆ¼' <<< '3 2 1'
3
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
\$\endgroup\$
0
\$\begingroup\$

Java (OpenJDK 8), 95 93 91 90 bytes

a->i->{int j=0,b[]=new int[++i];for(;j<i;j++)b[j]=j<a.length?a[j]:b[~-j-b[j-1]];return b;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Is not b[(j-1)-...] equivalent to b[~-j-...]? \$\endgroup\$ – Jonathan Frech Oct 11 '17 at 16:51
  • \$\begingroup\$ You can reverse the ternary from j>=a.length to j<a.length to save a byte: j<a.length?a[j]:b[~-j-b[j-1]]. Also I'm curious: why did you go with a loop approach, when the recursive approach that is also explained in the challenge description itself is just 60 bytes? \$\endgroup\$ – Kevin Cruijssen Oct 12 '17 at 7:18
  • \$\begingroup\$ I do not like to answer with methods and AFAIK a self-referencing Function needs a full program answer \$\endgroup\$ – Roberto Graham Oct 12 '17 at 9:33
  • \$\begingroup\$ @RobertoGraham No, a recursive method can't be a lambda, so has to be a Java 7 style method. But it's still allowed to just post a (Java 7 style) method instead of the full program. \$\endgroup\$ – Kevin Cruijssen Oct 12 '17 at 9:50
  • \$\begingroup\$ @KevinCruijssen I've made your answer into a BiFunction, Try it online!. It's possible but you need to post whole program because it references Main \$\endgroup\$ – Roberto Graham Oct 12 '17 at 10:04
0
\$\begingroup\$

Perl 5, -a 30 bytes

#!/usr/bin/perl -a
use 5.10.0
say$F[@F]=$F[-1-$F[-1]]while 1

Try it online!

\$\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.