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

51 Answers 51

1
2
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\$
3
\$\begingroup\$

Phooey, 35 bytes

(>2&.)(<2)@1(1>(>2&-1@)<$i" "@(<2))

Try it online!

Input is one-indexed space separated integers followed by a zero.

The output is a list of space separated integers to stdout.

Today, I learned something "interesting" about Phooey.

If you looked at my other post, I mentioned the ! modifier, which makes any instruction use the value from the stack.

I figured, okay, I could do something like this, using the stack modifier to do a variable offset. Easy.

...>@<(1>!@$i" "(<))

It turns out that it wasn't entirely true.

    else if(op.payload_type == PayloadType::SPECIAL) {
        switch(op.payload.special) {
            // snip
            case SpecialPayload::STACK:
                op.payload_type = PayloadType::NORMAL;
                op.payload.normal = pop();
                return op.payload.normal;
            // Snip
        }
    }

While the user input variants don't do this, for some dumb reason, using the ! operator will only work once: after that, it will be constant.

So therefore, I had to do this manually.

(>2&.)(<2)@1(1>(>2&-1@)<$i" "@(<2))

# do
(
    # We write into every other cell, as we
    # need a temp buffer for indexing.

    # Additionally, we need a null terminator to
    # mark the start of the list.
    >2
    # Read integer into tape
    &.
    # Loop until the user enters a zero.
    #
    # This could be made easier if the developer
    # initialized their variables to zero:
    #   int64_t read_int(std::istream& stream) {
    #       int64_t res; // <= uninitialized
    #       stream >> res;
    #       return res;
    #   }
    # but no, this is a terribly coded esolang.
    # Instead, we either have to do ~i or require
    # a sentinel.
# while (*cell)
)
# Scan back to the beginning with another do-while.
# Again, we are writing every two cells.
(<2)
# Push the first index to the stack.
@1
# do
(1
    # move to a scratch cell
    >
    # move to the cell position
    #   do { ptr++; } while (--n);
    # do
    (
        # go to the next scratch cell
        >2
        # pop into the scratch cell
        &
        # subtract 1
        -1
        # push back
        @
    # while index is not zero
    )
    # BUG: we have a memory leak here: we leave the last
    # index on the stack cuz it's PPCG and we dgaf about that
    # To fix it, add an ampersand here.
    #   &
    
    # Move backwards to the numerical index
    <
    # print the integer and a space
    $i" "
    # push the new index
    @
    # scan back to the beginning
    (<2)
# loop forever
# while (1)
)

Animated version with the memory leak fixed (which I totally didn't create manually using raw ANSI escape codes in a Phooey file): animated version

\$\endgroup\$
3
+300
\$\begingroup\$

Factor, 33 30 bytes

Saved 3 bytes thanks to @Bubbler

[ 0 [ over nth 2dup . ] loop ]

Try it online!

[ 0 [ over nth 2dup . ] loop ]
  0                            ! Push the start index
                        loop   ! Repeatedly do:
      over                     ! Bring the list to the top
           nth                 ! Get the element at the current index
                2dup           ! Duplicate the list and the index
                     .         ! Print and discard the copy of the index
                               ! The copy of the list is used as a truthy value
                               ! to keep the loop going
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 30 bytes. Repeatedly copying from below is an alternative to using a local variable (or fry or other ways of currying). Everything that is not f is truthy, so you can change dup to 2dup (which will copy the input array as well) and remove the explicit t. \$\endgroup\$
    – Bubbler
    Commented Mar 29, 2021 at 23:41
3
\$\begingroup\$

Bash, 39 37 bytes

f()(x=${x-1}
echo ${!x}
x=${!x}
f $@)

Try it online!

-2 thanks to "tail spark rabbit ear"

One-based indexing.

  • The bash indirection operator ${!v} returns the value of the variable whose name is $v
  • Function arguments are named $1, $2, etc.
  • These two features, along with recursion and a default value of 1 x=${x-1} are all we need. The current index is stored in $x and the input array is the function arguments.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 37 bytes \$\endgroup\$
    – user100411
    Commented Mar 30, 2021 at 14:16
3
\$\begingroup\$

Vim, 15 bytes

YPqq@"Y`.p@qq@q

Try it online! (slightly modified version to loop 99 times instead of indefinitely, the result wouldn't show on TIO otherwise)

Language of the month! I'm learning to work with Vim thanks to that :D

This takes 1-based indices each on a separate line, and output is the sequence of indices visited (also one per line) followed by the original list... Fortunately, since we are assuming this will be running for infinite time we will never see that final part.

Explanation

YPqq@"Y`.p@qq@q
YP                 Duplicate the first line (to write the first index)
  qq        q      Record macro q (kind of like a recursive function)
    @"               Jump down a number of lines equal to the last copied number
      Y              Copy the number at that line
       `.            Jump back to where we did our last change
         p           Write the copied number after that
          @q         Call macro q recursively
             @q    Call macro q and start the infinite loop

I found out how to use @" by accident: it is supposed to run the last copied text as a macro. Since with Y we are copying a full line (newline terminated), the macro will be n<CR>, meaning a number followed by enter, which has the effect of going to the next line for n times.

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

><>, 55 bytes

i:0(?v
v&0{~<
<~v?:  -1r<r%-1l+l$&:$-&:oan:
  >rl1-[}]^

Try it

Explanation

Since fish has no concept of a "array" I had to get a bit creative. Keeps the current index in the register, then subtract it from the number. Shift the stack left that many times (since the stack is reversed)

I just want the hat.

enter image description here

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

SmileBASIC 4, 33 bytes

DIM C=COPY(L)@_?C[SHIFT(L)]GOTO@_

DIM C=COPY(L)  'L[] is the infinite input stack, C[] is a separate copy.
?C[SHIFT(L)]  'Remove the 0th element from the infinite stack, print the value corresponding to that 0th element from the copy.
GOTO@_  'Return the pointer to the label @_ and repeat forever.
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 28 27 bytes

1//.i_:>0Print[a=#[[i]]]+a&

Try it online!

1-indexed. Prints each item on its own line.

20 bytes

1//.i_:>Echo@#[[i]]&

Try it online!

Precedes each line with >> .


By default, //. only does up to 65536 iterations.

29 bytes

For[i=1,1>0,Print[i=#[[i]]]]&

Try it online!

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

Zsh, 23 bytes

echo $i
i=$@[++i] $0 $@

Try it online!

The ++i is necessary because Zsh is 1-indexed and by default parameters are 0 in arithmetic mode.

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

PowerShell Core, 27 22 bytes

for(){($i=$args[+$i])}

-5 bytes thanks to mazzy!

Try it online!

0 indexed, takes the list as an array as parameters and outputs the result list on the standard output

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

Pyth, 7 bytes

#=Z
@QZ

Try it online!

Takes a 0-indexed list as input, prints each term on a new line until an error is thrown.

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

Python, 84 61 bytes

s=input()
i=s.split(" ")
n=0
o=[]
while True:
o.append(i[n])
n=i[n]

Short, sweet, and simple: takes the input list, finds the index, adds the number to the list<s, and repeat. (With thanks to Redwolf for the edits)

\$\endgroup\$
3
  • \$\begingroup\$ I don't think you need the spaces, and the variable names could be shortened. Also I think you need to either use input or take input via a function argument \$\endgroup\$
    – rydwolf
    Commented Feb 11, 2021 at 15:06
  • \$\begingroup\$ Sure that unindented code works in any Python? \$\endgroup\$
    – manatwork
    Commented Feb 11, 2021 at 15:35
  • \$\begingroup\$ The indents are there, they just don't like to work. \$\endgroup\$ Commented Feb 11, 2021 at 15:36
2
\$\begingroup\$

Vyxal, 4 bytes

0{i…

Try it Online!

Note that the -5 flag is purely for code time-out purposes: it makes the online interpreter stop execution if it takes longer than 5 seconds.

Explained

0{i…
0       # Push 0 to the stack
 {      # Repeat the following infinitely:
  i     #   Push the item at index (top of stack) in the input
   …    #   Print that without popping
\$\endgroup\$
1
  • \$\begingroup\$ great, tied with husk \$\endgroup\$
    – Razetime
    Commented Dec 12, 2020 at 3:00
2
\$\begingroup\$

Fig 0.1.0, \$4\log_{256}(96)\approx\$ 3.292 bytes

(,iQ

See the README to see how to run this

I cannot believe I saw the Vyxal answer and did not think of porting it.

(,iQ - Takes input like "[1,0]"
(    - Repeat forever
 ,   - Print
  iQ - The item at the last index obtained
\$\endgroup\$
2
\$\begingroup\$

Raku, 21 bytes

{$^a[0],{$a[$_]}...*}

Try it online!

Anonymous function that takes an array and returns an infinite sequence

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

Go, 60 bytes

import."fmt"
func f(L[]int){for i:=L[0];;i=L[i]{Println(i)}}

Attempt This Online!

This one prints each step.

Go, 65 bytes, invalid

func f(L[]int)(P[]int){for i:=L[0];;i=L[i]{P=append(P,i)}
return}

Attempt This Online!

It's an infinite loop, but the path it takes is stored in P.

Go, 84 bytes, invalid

import."fmt"
func f(L[]int)func()int{i:=L[0]
return func()int{n:=i;i=L[i]
return n}}

Attempt This Online!

Returns a generator function that takes no arguments and returns the next element when called.

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

x86 32-bit machine code (Linux), 25 bytes

00000000: 9631 c08b 0486 5068 1500 0000 93e8 fcff  .1....Ph........
00000010: ffff 93eb ee25 7520 00                   .....%u .

Assembly (NASM):

section .text
extern printf
global func
func:				; Arg passed in EAX (regparm conv.)
	xchg esi, eax		; ESI=base ptr
	xor eax, eax		; EAX=offset, starts at 0
	loop:
		mov eax, [esi + 4*eax]	; Load offset with next LL item (4x bc each item is 32 bits wide)
		push eax
		push fmt
		xchg eax, ebx	; Store EAX contents before printf call
		call printf	; Print
		xchg ebx, eax	; Retrieve EAX contents
		jmp loop	; Loop forever
				; Ret isn't needed as we don't return
fmt: db '%u ',0x00

Try it online!

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

Pip, 7 bytes

W1YPg@y

Zero-indexed. Takes the input list as separate command-line arguments. Attempt This Online!

Explanation

W1       ; While 1 (loop forever):
    g    ;   The argument list
     @y  ;   Get the item at index y
  YP     ;   Print that value and assign it to y

The initial value of y is "", which acts as 0 in a numeric context.

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

APL (Dyalog Unicode), 24 bytes

Much longer than the other APL answer, but I just wanted to use matrix-vector multiplication instead of indexing.

⊢(∘.=∨.∧⍣{≡⎕←⊃⍸⍺}0=⊢)⍳∘≢

Try it online!

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

Fig, commit 41637b2, \$6\log_{256}(96)\approx\$ 4.939 bytes

G0'i#!

To run this, download the source and then run in the root directory:

./gradlew run --args="code.txt <args>"

Explanation:

G0'i#! - Takes input like "[1,0]"
G      - Generate an infinite list using...
 0     - 0 as the initial value...
  '    - And using the generator function...
   i   - Index into
    #! - The program's input
       - Using the last index generated
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 4 bytes

Ties Kevin Cruijssen's 05AB1E answer, Razetime's Husk answer, and Lyxal's Vyxal answer for #1.

н[=è

Try it online!

н[=è  # full program
н     # push first element of...
      # implicit input
 [    # forever...
  =   # output top of stack
   è  # element in...
      # implicit input...
   è  # at index top of stack
      # (implicit) exit loop

Do I get extra points for the [=? :P

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.