16
\$\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\$
2
  • \$\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, 2017 at 19:34
  • \$\begingroup\$ @LuisMendo Sure any indexing is fine. \$\endgroup\$
    – Wheat Wizard
    Oct 11, 2017 at 20:41

20 Answers 20

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\$
11
  • \$\begingroup\$ You call f(n) from in f(n). I don't think that will ever terminate, but I don't know JS. \$\endgroup\$
    – Wheat Wizard
    Oct 11, 2017 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\$ Oct 11, 2017 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\$
    – Wheat Wizard
    Oct 11, 2017 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\$ Oct 11, 2017 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\$ Oct 11, 2017 at 15:23
8
\$\begingroup\$

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.
\$\endgroup\$
0
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\$
0
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\$
2
\$\begingroup\$

Husk, 6 bytes

¡Ṡ!o_→

Try it online!

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

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Why subtract from the length when you can just index by a negative? \$\endgroup\$
    – Wheat Wizard
    Oct 9, 2020 at 7:57
  • 1
    \$\begingroup\$ @WheatWizard you mean this? Try it online! \$\endgroup\$
    – Razetime
    Oct 9, 2020 at 8:03
  • \$\begingroup\$ "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 \$\endgroup\$ Oct 9, 2020 at 8:10
  • \$\begingroup\$ no it's generally -1 byte from Jo King @KevinCruijssen \$\endgroup\$
    – Razetime
    Oct 9, 2020 at 8:16
  • 2
    \$\begingroup\$ Yeah that was what I had in mind. Although this now seems suspiciously similar to the existing Husk answer. \$\endgroup\$
    – Wheat Wizard
    Oct 9, 2020 at 8:46
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\$
0
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\$
1
\$\begingroup\$

05AB1E, 5 bytes

λN<α₅

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)|
    ₅  #  And use that as n'th value: a(|a(n-1)-(n-1)|)
\$\endgroup\$
1
  • \$\begingroup\$ And I thought using Husk was cheating. \$\endgroup\$
    – Razetime
    Oct 9, 2020 at 8:17
1
\$\begingroup\$

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

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

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

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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 \$\endgroup\$ Dec 22, 2021 at 22:19
0
\$\begingroup\$

Perl, 38 +3 (-anl) bytes

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

Try It Online

\$\endgroup\$
2
  • \$\begingroup\$ Your TIO link goes to a different program. \$\endgroup\$
    – Xcali
    Oct 11, 2017 at 18:22
  • \$\begingroup\$ @Xcali i fixed the link but couldn't execute because could not established a connection with the server. \$\endgroup\$ Oct 11, 2017 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\$
6
  • \$\begingroup\$ Is not b[(j-1)-...] equivalent to b[~-j-...]? \$\endgroup\$ Oct 11, 2017 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\$ Oct 12, 2017 at 7:18
  • \$\begingroup\$ I do not like to answer with methods and AFAIK a self-referencing Function needs a full program answer \$\endgroup\$ Oct 12, 2017 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\$ Oct 12, 2017 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\$ Oct 12, 2017 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.