32
\$\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
  • 3
    \$\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 '20 at 16:06
  • \$\begingroup\$ can there be one extra zero at the beginning? \$\endgroup\$ – Danis Dec 11 '20 at 18:51
  • 2
    \$\begingroup\$ @Danis No, sorry \$\endgroup\$ – Redwolf Programs Dec 11 '20 at 18:57
  • 2
    \$\begingroup\$ @Shaggy One interesting challenge idea would be to have them return the period of the loop \$\endgroup\$ – Redwolf Programs Dec 11 '20 at 21:29

44 Answers 44

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
15
\$\begingroup\$

Haskell, 17 bytes

f x=iterate(x!!)0

0-indexed

Try it online!

\$\endgroup\$
2
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\$ – Redwolf Programs Dec 11 '20 at 15:07
  • 3
    \$\begingroup\$ too bad +undefined is NaN instead of zero.. would save a byte \$\endgroup\$ – Kaddath Dec 11 '20 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 '20 at 19:08
  • \$\begingroup\$ @Giuseppe Thanks! I should try to remember that +T trick, it's a good one! \$\endgroup\$ – Robin Ryder Dec 11 '20 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 '20 at 15:18
5
\$\begingroup\$

Julia 1.0, 24 bytes

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

1-indexed

Try it online!

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

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\$ – Redwolf Programs Feb 11 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 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\$ – Redwolf Programs Feb 11 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 at 4:03
  • \$\begingroup\$ Bounty started. It should draw a lot of attention to Rattle! \$\endgroup\$ – Redwolf Programs Feb 11 at 4:16
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 '20 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 '20 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\$

Rust, 50 49 bytes

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

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 '20 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 '20 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 '20 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 '20 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 '20 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\$ – Dominic van Essen Dec 13 '20 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 '20 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\$ – Dominic van Essen Dec 13 '20 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\$ – GammaFunction Dec 14 '20 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 '20 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\$
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 '20 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 '20 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 '20 at 8:46
  • \$\begingroup\$ @Dingus - okay. You're right i is defined as 0, I overlooked it, actually... \$\endgroup\$ – vrintle Dec 12 '20 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 '20 at 3:34
  • 1
    \$\begingroup\$ No arrays in FALSE \$\endgroup\$ – ReedsShorts Dec 31 '20 at 15:09
3
\$\begingroup\$

x86 machine code, 6 bytes

Binary:

00000000: 33c0 d7aa ebfc                           3.....

Listing:

33 C0       XOR  AX, AX         ; AL = 0
        L1: 
D7          XLAT                ; AL = [BX+AL]
AA          STOSB               ; [DI++] = AL
EB FC       JMP  L1             ; loop infinitely

Input array (0 indexed) at [BX], output to array at [ES:DI].

Run with DOS DEBUG:

enter image description here

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