37
\$\begingroup\$

For this challenge, a linked list looks like this:

[1, 2, 4, 0, 6, 1, 3, 1]

You'll notice there's no data; each item in the list is just a reference to the index of the next one. Your task is to write a program or function which will follow a linked list like this forever, outputting each item as it is encountered. For example, for the above input:

[1, 2, 4, 6, 3, 0, 1, ...]

Input and output can be represented in any reasonable manner. All numbers in the input will be valid indices in the list, and you can choose if it's 0- or 1-indexed. The output will be infinite, and as long as your program would theoretically give a correct result given infinite time and resources it's valid.

Test cases:

Zero indexed, using lists.

[0]         -> [0, 0, ...]
[1, 0]      -> [1, 0, 1, ...]
[0, 1, 2]   -> [0, 0, ...]
[2, 1, 0]   -> [2, 0, 2, ...]
[4]         -> (does not need to be handled)
\$\endgroup\$
4
  • 4
    \$\begingroup\$ That's nuts: I was thinking of a challenge exactly like this the other day! I was gonna provide a 2nd input as the index to start at and require solutions to stop once they started looping. \$\endgroup\$
    – Shaggy
    Dec 11, 2020 at 16:06
  • \$\begingroup\$ can there be one extra zero at the beginning? \$\endgroup\$
    – Danis
    Dec 11, 2020 at 18:51
  • 2
    \$\begingroup\$ @Danis No, sorry \$\endgroup\$ Dec 11, 2020 at 18:57
  • 3
    \$\begingroup\$ @Shaggy One interesting challenge idea would be to have them return the period of the loop \$\endgroup\$ Dec 11, 2020 at 21:29

46 Answers 46

16
\$\begingroup\$

Haskell, 17 bytes

f x=iterate(x!!)0

0-indexed

Try it online!

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

convey, 36 29 bytes

v<<<<,{
\~./."
>"`=>!
 >!0<"}

Try it online!

top

{ gets the input, that will get looped around in the upper two rows, while outputting downwards the length \, its indices /. and a copy of itself ". It will only continue after ~. (batch) if n elements reach ~., whereas n will be the length.

run for 2 1 0

We then take ! n copies of the current index i (starting with 0) and compare = them to the indices of the list. This returns either 1 or 0. We take the correspondent element of the copied list so many times, effectively filtering the others out. The next index then gets copied to the output "} and waits for the next iteration.

\$\endgroup\$
0
10
\$\begingroup\$

Husk, 4 bytes

¡!¹←

Try it online!

1-indexed, returns an infinite list.

Explanation

¡!¹←
   ← take the first element as the start
¡    apply the following infinitely:
 !¹  index into the input
\$\endgroup\$
9
\$\begingroup\$

JavaScript (V8), 29 bytes

Zero-indexed. Prints forever. (Where forever means until the call stack overflow.)

f=a=>print(a.i=a[~~a.i])|f(a)

Try it online!

Commented

f = a =>       // f is a recursive function taking the input array a[]
  print(       // print:
    a.i =      //   update the current index, which is stored in the
               //   property 'i' of the surrounding object of a[]:
      a[~~a.i] //     it's initially undefined, so we use '~~' to coerce
               //     it to a number (zero) on the first iteration
  )            // end of print()
  | f(a)       // unconditional recursive call

The a.i trick saves 2 bytes over the more straightforward version:

f=(a,i=0)=>print(i=a[i])|f(a,i)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I've never seen the ~~ trick before, that's really useful! \$\endgroup\$ Dec 11, 2020 at 15:07
  • 3
    \$\begingroup\$ too bad +undefined is NaN instead of zero.. would save a byte \$\endgroup\$
    – Kaddath
    Dec 11, 2020 at 15:12
7
\$\begingroup\$

R, 35 32 bytes

-3 bytes thanks to Giuseppe.

function(l)repeat show(T<-l[+T])

Try it online!

1-indexed, prints the list indefinitely. A rare use for show, which is 1 byte shorter than print, and separates the output unlike cat.

The variable T is initially TRUE; +T converts it to the integer 1, and thereafter it is updated at each step to the relevant list entry.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 32 bytes \$\endgroup\$
    – Giuseppe
    Dec 11, 2020 at 19:08
  • \$\begingroup\$ @Giuseppe Thanks! I should try to remember that +T trick, it's a good one! \$\endgroup\$ Dec 11, 2020 at 20:44
6
\$\begingroup\$

05AB1E, 4 bytes

0[è=

0-based indexing.
Prints the numbers newline-delimited to STDOUT indefinitely.

Try it online or verify all test cases, but only printing the first 10 numbers of each.

Explanation:

0     # Start with index 0
 [    # Loop indefinitely:
  è   #  Use the current integer to index into the (implicit) input-list
   =  #  Print it with trailing newline (without popping, so it'll become the index for
      #  the next iteration)
\$\endgroup\$
6
\$\begingroup\$

dc, 29 28 bytes

[z1-:az0<L]dsLx0[;aplLx]dsLx

Try it online!

0-indexed; takes input on the stack (just prepend it). If we assume input is already in a, cut off the first 16 bytes. Will perish when the call stack overflows.

[ # Phase 1: shove stuff into an array
  z1-  # if there are 7 things on the stack, push 6
  :a   # store whatever was on top into e.g. a[6]
  z0<L # loop while stack isn't empty
]dsLx  # execute immediately and with extreme prejudice

0 # first index to check out
[ # Phase 2: the challenge
  ;a  # push a[tos]
  p   # print it
  lLx # loop forever
]dsLx # autobots, roll out

I feel like the 0!= should be reducible to 1> never mind, I just can't read. Woohoo!

\$\endgroup\$
6
\$\begingroup\$

APL (Dyalog Unicode), 12 11 bytes

{⍺∇⎕←⍵⌷⍺}∘0

Try it online!

0-indexed, takes input as the left argument.

-1 byte from user.

{⍺∇⎕←⍵⌷⍺}∘0
{⍺∇⎕←⍵⌷⍺}∘0 take 0 as initial right argument
   ⎕←⍺⌷⍵    print element at right arg
 ⍺∇ ⍵⌷⍺     recursive call with the input and new right arg
\$\endgroup\$
1
  • \$\begingroup\$ 11 bytes by switching order \$\endgroup\$
    – user
    Dec 11, 2020 at 15:18
5
\$\begingroup\$

Whitespace, 89 bytes

[S S S T    N
_Push_1][S N
S _Duplicate_1][S N
S _Duplicate_1][S N
S _Duplicate_1][N
S S N
_Create_Label_READ_INPUT_LOOP][T    N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve][N
T   S S N
_If_0_Jump_to_Label_DONE_READING][S S S T   N
_Push_1][T  S S S _Add][S N
S _Duplicate][S N
S _Duplicate][N
S N
N
_Jump_to_Label_READ_INPUT_LOOP][N
S S S N
_Create_Label_DONE_READING][S N
N
_Discard_top][N
S S T   N
_Create_Label_PRINT_LOOP][T T   T   _Retrieve_at_address][S N
S _Duplicate][T N
S T _Print_as_integer][S S S T  S S T   N
_Push_9_tab][T  N
S S _Print_as_character][N
S N
T   N
_Jump_to_Label_PRINT_LOOP]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

1-based indexing.
Whitespace doesn't have any lists, so we'll read the numbers one at a time from STDIN. Input numbers will end with a trailing 0, so the program knows when all the numbers are read from STDIN. I.e. test case [1,2,4,0,6,1,3,1] would be taken as input 2\n3\n5\n1\n7\n2\n4\n2\n0.
Outputs the numbers tab-delimited to STDOUT indefinitely.

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer index = 1
Start READ_INPUT_LOOP:
  Read input as integer from STDIN, and store it in the heap at address `index`
  Integer input = retrieve the input from address `index`
  If(input == 0):
    Jump to DONE_READING
  index = index + 1
  Go to next iteration of READ_INPUT_LOOP

Label DONE_READING:
  Reset index to 1
  Start PRINT_LOOP:
    index = retrieve integer from heap at address `index`
    Print `index` as integer to STDOUT
    Print character '\t'
    Go to next iteration of PRINT_LOOP
\$\endgroup\$
5
\$\begingroup\$

Rust, 50 49 bytes

|a|(|mut i|loop{i=a[i];println!("{}",i)})(0usize)

Try it online!

\$\endgroup\$
5
\$\begingroup\$

CJam, 14 12 bytes

q~{_T=:Tp1}g

Input is taken from STDIN, 0-based, with format [1 2 4 0 6 1 3 1].

Output is printed to STDOUT, separated by newlines.

Try it online! Or verify test cases: 1, 2, 3, 4.

How it works

q               e# Read input as a string
 ~              e# Evaluate: gives the input as a list of numbers
  {       }g    e# Do...while, popping condition from the stack
         1      e# Push 1 at the end of each iteration, to produce an infinite loop
   _            e# Duplicate the input list
    T           e# Push variable T. This is initially 0
     =          e# Get entry at that index (0-based)
      :T        e# Assign the result to variable T
        p       e# Print with newline
\$\endgroup\$
5
+100
\$\begingroup\$

Rattle, 11 bytes

|IP0[gpP~]0

Try it online!

Note:

  • I am currently waiting for Rattle to be added to TIO, so the current TIO link is a bit messy. You can just minimise the header and footer...

Explanation

|                  takes the user's input
  I                stores the user's input in an array
    P0             sets the pointer to 0
       [ ...... ]0 infinite loop
         g         gets the value at the pointer
           p       prints this value
             P~    sets the pointer to this value
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Neat answer! Are you the creator of Rattle? \$\endgroup\$ Feb 11, 2021 at 3:28
  • 1
    \$\begingroup\$ @RedwolfPrograms thank you! Yes, I am the creator. Rattle is designed to be super easy to learn! \$\endgroup\$
    – Daniel H.
    Feb 11, 2021 at 3:29
  • 3
    \$\begingroup\$ This looks like a really cool language! I've got a bounty for interesting languages, and I think this definitely counts. I can start a bounty for this answer if you'd like, or another if you think it'd be a better demonstration of the language's features! \$\endgroup\$ Feb 11, 2021 at 3:58
  • 1
    \$\begingroup\$ @RedwolfPrograms that would be awesome! I think this answer is the best I currently have in Rattle in terms of demonstrating the power of the language (some of the older answers are a bit outdated and don't make use of the newer, more powerful features) \$\endgroup\$
    – Daniel H.
    Feb 11, 2021 at 4:03
  • \$\begingroup\$ Bounty started. It should draw a lot of attention to Rattle! \$\endgroup\$ Feb 11, 2021 at 4:16
5
\$\begingroup\$

Julia 1.0, 24 21 bytes

>(a,i=1)=a>@show a[i]

Try it online!

1-indexed

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

PHP, 34 bytes

for($i=1;;)echo($i=$argv[$i])."
";

1-indexed, because $argv contains the script name at index 0, first argument is then $argv[1]. Too bad the new line takes a lots of bytes more, without it the brackets around $i=$argv[$i] are not necessary..

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 30 with zero-indexed: Try it online! If you change your delimiter you can get 29 with something like ~_ instead of the newline. \$\endgroup\$
    – Sisyphus
    Dec 11, 2020 at 21:00
  • \$\begingroup\$ @Sisyphus your version is much better, I feel I shouldn't take credit of it, if you want to post another answer sure I'll upvote it! \$\endgroup\$
    – Kaddath
    Dec 14, 2020 at 8:16
4
\$\begingroup\$

Java (JDK), 46 bytes

a->{for(int i=0;;)System.out.println(i=a[i]);}

Try it online!

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

Python 3.8 (pre-release), 37 34 bytes

def f(l,i=0):print(l[i]);f(l,l[i])

Try it online!

thanks user for helping save 3 bytes

slightly modified version of 31 bytes, but it prints an extra zero at the beginning

def f(l,i=0):print(i);f(l,l[i])

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 36 bytes (and 33 if a leading 0 were allowed). Actually, yours can be 34 bytes. \$\endgroup\$
    – user
    Dec 11, 2020 at 16:21
  • \$\begingroup\$ 31 bytes :-) --- see link after ( - sorry can't figure out neat hyperlink in comment :-( ) tio.run/##K6gsycjPM7YoKPr/… \$\endgroup\$
    – tom
    Dec 14, 2020 at 23:19
  • \$\begingroup\$ ok so now I see I have just reinvented the wheel .... by tiniest modification of the code already shown for 31 bytes to give........ def f(l,i=1):print(i);f(l,l[i])...............advantage is no leading zero \$\endgroup\$
    – tom
    Dec 14, 2020 at 23:20
4
\$\begingroup\$

C (gcc), 38 bytes

i;f(int*a){printf("%d ",i=a[i]);f(a);}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I guess nonterminating functions don't have to be reusable... \$\endgroup\$
    – Neil
    Dec 12, 2020 at 0:44
  • \$\begingroup\$ @Neil That's what I thought, so I don't need the usual reinitialisation of i=0. \$\endgroup\$
    – Noodle9
    Dec 12, 2020 at 1:07
4
\$\begingroup\$

R, 31 bytes

Note that tests don't work, but print returns its input so we can recurse. Curiously this is different from cat and show which return NULL.

function(l,i=1)f(l,print(l[i]))

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ I'm not sure why, but even if the number of recursive calls is restricted like this, it doesn't seem to output as intended... \$\endgroup\$ Dec 13, 2020 at 18:58
  • \$\begingroup\$ Thanks @DominicvanEssen, I've gotten it to output with an additional change but it's definitely not what I was expecting. Maybe my submission was not correct. \$\endgroup\$
    – Cong Chen
    Dec 13, 2020 at 22:01
  • \$\begingroup\$ It isn't what I was expecting either. Your changed version also only seems to output the final 0 (from the innermost recursive call), not all the prints from each call... \$\endgroup\$ Dec 13, 2020 at 22:15
4
\$\begingroup\$

Bash, 51 50 bytes

f(){
A=($@)
I=0
while
I=${A[$I]}
do
echo $I
done
}

Try it online!

I was disappointed to find I could not use $@ as an array. I had to copy it to A.

The test code limits the output to 20 lines, and wraps it (or tries). Terminates only on signal, like SIGPIPE.

Edit: TIO seems to say I don't need the final newline. -1. Note that all my other newlines could become either spaces or semicolons, but I felt newlines had a better (weirder?) style in this case.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can use get rid of the f(){ } because the function body alone would qualify as a full program. Also, for((;;)){ } is a shorter infinite loop, and variables are 0 by default in arithmetic contexts: tio.run/… \$\endgroup\$ Dec 14, 2020 at 17:13
4
\$\begingroup\$

MATLAB and Octave, 20 bytes 32 bytes

(I've been informed that it is not allowed on this site to assume the input is an array, original answer below the line.)

@(x)eval('1,while 1,x(ans),end')

Thanks to Luis Mendo for this solution to make a function out of my original answer. It is two bytes shorter than the more obvious solution:

function f(x),1,while 1,x(ans),end

Try it online!


1,while 1,x(ans),end

1-indexed, the input is in matrix x. For example:

>> x = [1, 2, 4, 0, 6, 1, 3, 1] + 1;
>> 1,while 1,x(ans),end
ans =
     1
ans =
     2
ans =
     3
ans =
     5
ans =
     7
ans =
     4
ans =
     1
...

ans is the default variable expression results get assigned to. The code above is equivalent to:

ans = 1
while 1
   ans = x(ans)
end

The result of the assignment is shown to the command line because statements are not terminated with a semicolon.

\$\endgroup\$
1
  • \$\begingroup\$ While you cannot assume the input is saved in any variable, it is explicitly allowed for ans (see here, I don't agree with this rule, but this is the law:), so you could write x=ans;1,while 1,x(ans),end. \$\endgroup\$
    – flawr
    Dec 15, 2020 at 11:42
4
\$\begingroup\$

Common Lisp, 44 bytes

(Function prints in the square bracket + comma style of most languages)

I used Common Lisp's format specifiers to handle all the control flow.

(defun f(l)(format t"[~{~a~:*~v@*~^, ~}]"l))

Example usage:

(defparameter *test* '(1 2 4 0 6 1 3 1))

(f *test*) ; Will print [1, 2, 4, 6, 3, 0, 1, ... and so forth forever.

Edit: Technically the ending square bracket would never be reached, so we may omit the closing square bracket in the format string to have a 43 byte solution.

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

Python 3, 49 37 bytes

Thanks to Jo King for -12 bytes!

def f(l,c=0):
 while 1:c=l[c];yield c

Try it online!

Original

def f(l):
    c=l[0]
    while 1:c = l[c];yield c

Try it online!

This code takes an input, sets c(which holds the index), then continuosly yields c after updating it to the new location. While this isn't the best answer on here, even for python, I don't think it can really be improved upon without using recursion. Clearly, I was wrong.

\$\endgroup\$
1
  • \$\begingroup\$ You can save some bytes by removing unneccesary whitespace, as well as initialising c to 0 rather than l[0]. Technically, you should be yielding the first element first, which this fixes. Try it online! \$\endgroup\$
    – Jo King
    Feb 11, 2021 at 4:11
3
\$\begingroup\$

Batch, 94 bytes

@set n=0
:g
@call:c %*
@echo %n%
@goto g
:c
@for /l %%i in (1,1,%n%)do @shift
@set n=%1

Takes a 0-indexed list of command line arguments (change =0 to =1 and %1 to %0 for 1-indexing). The :c subroutine exists to shift a copy of the command line, thus avoiding destroying the command line. For short lists (up to 9 elements), the following 51-byte 1-indexed script suffices:

@set n=1
:g
@call set n=%%%n%
@echo %n%
@goto g
\$\endgroup\$
3
\$\begingroup\$

Perl 5 -a, 22 bytes

$_=$F[$_]while say$_*1

Try it online!

Input needs to be space separated.

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 15 bytes

≔⁰ηW¹«≔§θηηIηD⎚

Try it online! Link is to verbose version of code. 0-indexed. Charcoal rate-limits its output, so TIO will probably time out rather than fill its output buffer. Explanation:

≔⁰η

Start at index 0.

W¹«

Repeat forever.

≔§θηη

Update the index.

IηD⎚

Output the index, clearing the canvas for the next loop.

\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 39 bytes

(,)*(((?<-1>,)|\d+)+.*)
$3$*,$2,
}*`\G,

Try it online! 0-indexed. Explanation: The current index is encoded in unary as the number of leading ,s.

(,)*(((?<-1>,)|\d+)+.*)

Match the current index, then as many commas and integers as possible, but only matching as many commas as the current index. The last submatch is therefore the next index.

$3$*,$2,

Replace the current index with the submatch in unary, then append the original input and an extra comma to ensure that the buffer changes each time (since Retina 0.8.2 doesn't have truly infinite loops).

}`

Repeat until the buffer stops changing, which it won't because we append a comma to the end on each loop.

*`\G,

Convert the current index to decimal and print it.

\$\endgroup\$
3
\$\begingroup\$

k4, 17 13 bytes

{0W(0N!x@)/0}

Loops "infinitely" via 0W, outputting (0N!) the index in question. Begins with the first value in the input, i.e. x 0.

\$\endgroup\$
3
\$\begingroup\$

JQ, 37 bytes

[0,.]|recurse([.[1][.[0]],.[1]])|.[0]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Ruby, 27 23 bytes

Saved a whooping 4 bytes, thanks to Dingus!!

f=->a,i=0{f[a,p(a[i])]}

Try it online!


Ruby, 23 bytes

As suggested by Dingus, here is another way, and it prevents the "stack overflow" error!!

->a,i=0{loop{p i=a[i]}}

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 23 bytes. And here is an alternative (also 23 bytes) that doesn't hit the stack limit. \$\endgroup\$
    – Dingus
    Dec 11, 2020 at 22:40
  • \$\begingroup\$ @Dingus - does loop iterates over i, by default? It looks a bit unusual to me :p and when will it stops, or I guess we have to break it.. \$\endgroup\$
    – vrintle
    Dec 12, 2020 at 2:46
  • \$\begingroup\$ loop starts an indefinite loop - break is indeed one way to stop it. There isn't any default variable. Here I've created a variable i to store the current index (initialised to 0). Then in each iteration i updates itself by reading from the input array. \$\endgroup\$
    – Dingus
    Dec 12, 2020 at 8:46
  • \$\begingroup\$ @Dingus - okay. You're right i is defined as 0, I overlooked it, actually... \$\endgroup\$
    – vrintle
    Dec 12, 2020 at 8:52
3
\$\begingroup\$

FALSE, 65 24 21 bytes

[c;[1_][ø$.32,c;\-]#]

Try it online! Assumes that array is already pushed onto stack and len(array)-1 is stored in c.

-41 because Razetime pointed out that I could just submit a function instead.

-3 because of removed redundancy.

Explanation

[c; {Push len(array) on stack for index 0}
[1_] {Value for true}
[ø {Get value at current index}
$. {Dup and print int}
32, {Print space}
c;\- {Subtract c by this new value to get new index}
]#] {Do lambda 2 while lambda 1 outputs true (forever)}
\$\endgroup\$
2
  • 3
    \$\begingroup\$ if it's shorter, you can submit a function which take an array/list of ints as a parameter. \$\endgroup\$
    – Razetime
    Dec 31, 2020 at 3:34
  • 1
    \$\begingroup\$ No arrays in FALSE \$\endgroup\$ Dec 31, 2020 at 15:09

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.