Create a pointer sequence

Question

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 code-golf 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 ...

• Luis Mendo: 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?
• Wheat Wizard: @LuisMendo Sure any indexing is fine.

Answer 1

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

• Wheat Wizard: You call f(n) from in f(n). I don't think that will ever terminate, but I don't know JS.
• ETHproductions: @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.
• Wheat Wizard: 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.
• Erik the Outgolfer: @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.
• ETHproductions: @FunkyComputerMan --n decrements n, which means that f(--n-f(n)) is the same as f((n-1)-f(n-1))

Answer 2

Husk, (削除) 7 (削除ここまで) 6 bytes

¡S!o_→

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_→ Implicit input.
¡ Construct infinite list by iterating this function on input:
 S! Element at index
 → last element
 o_ negated.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

Husk, 6 bytes

¡Ṡ!o_→

Try it online!

Figured this out after a lot of frustration with Jo King's help.

• Wheat Wizard: Why subtract from the length when you can just index by a negative?
• Razetime: @WheatWizard you mean this? Try it online!
• Kevin Cruijssen: "Figured this out after a lot of frustration with Jo King's help." I'm having a déjà vu moment. You put that sentence in every Husk submission to a challenge of @WheatWizard, do you? xD
• Razetime: no it's generally -1 byte from Jo King @KevinCruijssen
• Wheat Wizard: Yeah that was what I had in mind. Although this now seems suspiciously similar to the existing Husk answer.

Answer 10

Python 2, 48 bytes

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

Try it online!

Answer 11

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

Answer 12

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

Answer 13

05AB1E, 5 bytes

λN<α5

Outputs the infinite sequence.

Try it online. (No test suite with all test cases at once, because there is a bug when using the recursive environment within an iterator.)

Outputting the \$n^{th}\$ value or first \$n\$ values would cost an additional byte:
Output the (0-based) \$a(n)\$.
Output the first \$n\$ values.

Explanation:

λ # Start a recursive environment
 # to output the infinite sequence
 # Using the (implicit) input-list I, start the sequence at a(0)=I[0], a(1)=I[1],
 # ..., a(n)=I[n],
 # For which we calculate the next a(n) value as follows:
 # (implicitly push a(n-1))
 N< # Push n-1
 α # Calculate the absolute difference between the two: |a(n-1)-(n-1)|
 5 # And use that as n'th value: a(|a(n-1)-(n-1)|)

• Razetime: And I thought using Husk was cheating.

Answer 14

Japt, (削除) 8 (削除ここまで) 7 bytes

Outputs the nth term, 0-indexed. Change the second g to h to output the first n terms instead.

ÈgZw}gV

Try it

Answer 15

Wolfram Language (Mathematica), (削除) 34 (削除ここまで) (削除) 31 (削除ここまで) (削除) 30 (削除ここまで) 29 bytes

a_f@n_:=a[--t-a@t]&@@a[[t=n]]

Try it online!

Input f[initial...][n], e.g. as f[2, 1][3].

a_f@n_:= f[initial...][n], where a=f[initial...]
 a[[t=n]] attempt to take an index
 a[--t-a@t]&@@ if out of bounds, recurse

---

Alternative input formats (also 29 bytes):

f=f[#,--t-#~f~t]&@@#[[t=#2]]&

Try it online!

Input [initial, n], e.g. as f[{2, 1}, 3].

h:f@a_=h[--t-h@t]&@@a[[t=#]]&

Try it online!

Input [initial][n], e.g. as f[{2, 1}][3].

Answer 16

Nibbles, 4 bytes

.~~_=`($

explanation

.~~ # append until null (aka always in this case)
 _ # first input int list
 = # array subscript (aka haskell !!)
 `( # uncons (returning head)
 $ # second value from uncons (the tail)

Note that the $ can't also be implicit due to part of the uncons bin representation using part of its encoding after its arg :(

I say this is non competing because this problem influenced the idea to have the .~~ operator, although something like this was definitely needed and its a standard op in Husk.

• caird coinheringaahing: I've removed the "non-competing" label, as it's no longer a thing. I'd recommend keeping the disclaimer about the .~~ operator, but otherwise, its fine

Answer 17

Perl, 38 +3 (-anl) bytes

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

Try It Online

• Xcali: Your TIO link goes to a different program.
• Nahuel Fouilleul: @Xcali i fixed the link but couldn't execute because could not established a connection with the server.

Answer 18

05AB1E, 20 bytes

#`r[=ˆŽ1⁄4}[ ̄3⁄4 ̄3⁄4è-è=ˆ1⁄4

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

Example run:

$ 05ab1e -e '#`r[=ˆŽ1⁄4}[ ̄3⁄4 ̄3⁄4è-è=ˆ1⁄4' <<< '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

Answer 19

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!

• Jonathan Frech: Is not b[(j-1)-...] equivalent to b[~-j-...]?
• Kevin Cruijssen: 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?
• Roberto Graham: I do not like to answer with methods and AFAIK a self-referencing Function needs a full program answer
• Kevin Cruijssen: @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.
• Roberto Graham: @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

Answer 20

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!