The Array Walker (part 2)

Question

The Array Walker (part 2)

Input: A non-empty array of integers (without nesting¹). This can have negative values!

Output: A boolean value² indicating whether we can reach the end of the array when starting from the first element and moving n positions forward, where n is the value of the current cell. Upon reaching a new cell, the same rule is applied. If you reach a negative value, it's simple - go n cells backward (n = current negative cell).

True: Following this rule allows us to reach the end of the array, or we get before the first cell by a negative value.
False: Following this rule results in an infinite loop, preventing us from reaching the end.

Tip: Reaching an element with a value of 0 prevents progress since moving 0 positions forward keeps us at the same element indefinitely.

Example #1

Input: [1]

Output: true³

Why: The first element is 1, meaning we move 1 step forward and immediately reach the end of the array.

Example #2

Input: [1,4,0]

Output: true³

Why:

We start at first cell which is 1, moving 1 step forward.
We're now on next cell, and after moving 4 steps forward—this goes beyond the array, meaning we have successfully escaped.

Example #3

Input: [0,4,1,78,2]

Output: false³

Why: The first element is 0, meaning we move 0 steps forward and remain in the same position, a infinite loop.

Example #4

Input: [2,-1,-1]

Output: false³

Why: First we reach in a 2, and go two cells forward. Here is a -1, and go 1 cells backward. In another -1, we go 1 cells backward again. This is still the previous 2. This repeats infinte times.

Example #5

Input: [-10,2,-4,7,-1]

Output: true³

Why: In the first cell, we go 10 cells backward, and it's before first cell - we escaped the array.

Rules

This is code-golf, shortest code⁴ per language wins!
You don't need to handle empty arrays.
Markup (e.g., HTML) languages, or languages without output/input support are banned.
Cheating languages for zero-size programs like MetaGolfScript and is banned.
If a language includes a built-in function that can directly solve this problem, you must implement it manually instead.
All loopholes forbidden by default is included (banned) in this question.
The code runs without internet connection. Thus you cannot cheat by fetching to a site does it for you.
Programs must not use self-modifying code or undefined behaviors to shorten the solution artificially.
Programs must have clear input-output behavior. Solutions cannot rely on hidden side effects or unusual language behavior⁵ to compute results.
You cannot use tricks to compress your code⁶.
No depending on execution time or system date/time to manipulate the result.
Example: Using System.currentTimeMillis() % 2 == 0 as your answer is not valid.
Never use AI (e.g., ChatGPT) to create code. AIs are always rarely clear, and an AI-generated code is extremely likely to be invalid.

Answer Header Format

Normally, make your answer start with:

# <lang-name>, <byte-count> bytes

Where <lang-name> is the name of language and <byte-count> is number of bytes your code used.

If you have multiple files for correct code execution, you must to sum the number of bytes in all files you need and use this sum instead of length of code in answer header.

If you improved this answer (decreased code length), you can keep old scores in header, by using strikeouted old scores in header with <s> and </s> HTML tags.
For example, if old code was 156 bytes and new improved code is 133 bytes, you can use this header if want:
# <lang-name>, <s>156</s> 133 bytes

If your code requires a compiler flag or footer/header, you need to add your code length (plus other files length if need) with length of entire compiler flags and header and footer of code. So if your code needs -s flag and foo() footer, you add your code length by 7 bytes, since -s is 2 bytes, foo() is 5 bytes and 2+5 = 7.

^{1: Nesting means creating arrays inside array (or "array of arrays"), or even more nested. In this challenge, we won't provide a nested array like [3,[[5],2],4] for example.}

^{2: You're free to use any boolean type, for example you can use true/false, 0/1, yes/no, or anything else you want. If you use a boolean type other than true/false, 0/1 or yes/no, please include what printed for true and false in your answer.}

^{3: This is a example output, you can use a boolean type other than true/false.}

^{4: Rankings are based on number of bytes, not characters. Ultragolf is a good example which number of bytes in a ultragolf code is more than characters.}

^{5: It's allowed to use language errors (e.g., Maximum Recursion Limit Reached), but not using unusual effects and language bugs.}

^{6: Unless your language uses golfing syntax like GolfScript. But if you first decode zipped data then execute it, this is banned.}

^{7: You can use your language unicode format or codepage.}

As already mentioned for your previous challenge, you don't have to (and should not) reinvent the wheel. Just rely on our default set of rules unless there's a really good reason to override some of them. — Arnauld
– Arnauld, Commented Jun 27 at 13:20
What does “You cannot use tricks to compress your code” mean? — Adamátor
– Adamátor, Commented Jun 27 at 21:56
@Arnauld I accept, but it's impossible to delete a question with 8+ answers. — QOO-OOKALAN
– QOO-OOKALAN, Commented Jun 30 at 16:20

l4m2 · Accepted Answer · 2025-06-27 16:34:32Z

6

JavaScript (Node.js), 32 bytes

a=>!a.every(_=>1/a[p+=a[p]],p=0)

Try it online!

answered Jun 27 at 16:34

l4m2

32.5k2 gold badges27 silver badges116 bronze badges

Add a comment |

m90 · Accepted Answer · 2025-06-28 08:48:18Z

x86-64 machine code, 16 bytes

31 C0 8D 4E 01 03 04 87 39 F0 73 03 E2 F7 91 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of an array of 32-bit integers in RDI and its length in ESI, and returns a 32-bit integer in EAX, which is nonzero if and only if the process exits the array.

In assembly:

f:  xor eax, eax    # Set EAX to 0. EAX will hold the current index.
    lea ecx, [rsi + 1]          # Set ECX to the length plus 1.
r:  add eax, [rdi + 4 * rax]    # Add to EAX the array's value at index EAX.
    cmp eax, esi    # Compare EAX to the length.
    jnb e   # Jump if EAX isn't less than the length, as unsigned integers
            #  (so going before the start overflows to a large value).
            #  The jump goes to the return instruction with EAX nonzero.
    loop r  # Loop, counting down ECX. (If this loop finishes,
            #  then by the Pigeonhole Principle the index repeats somewhere,
            #  and therefore it would go on forever.)
    xchg eax, ecx   # Swap the 0 value from ECX into EAX.
e:  ret             # Return.

Kevin Cruijssen · Accepted Answer · 2025-06-27 09:06:52Z

05AB1E, 17 bytes

0ˆv¯θDŠè+ˆ}ā<¯å_à

Try it online or verify all test cases.

Explanation:

0ˆ       # Add a 0 to the global array as starting index
v        # Loop the length of the (implicit) input-list amount of times †:
 ¯θ      #  Push the last value of the global array
   D     #  Duplicate it
    Š    #  Triple-swap, so the stack order becomes: index,input,index
     è   #  Get the value at that index from the input-list
      +  #  Add that value to the duplicated index
       ˆ #  Pop and add it to the global array for the next iteration
}        # After the loop:
 ā       # Push a list in the range [1, (implicit) input-length]
  <      # Decrease each by 1 to the 0-based range [0,length)
   ¯     # Push the global array
    å    # Check for each whether it occurs in the list of possible indices
     _   # Invert each check
      à  # Check if any is truthy (aka, it's beyond the bounds of the list)
         # (which is output implicitly as result)

† Looping the input-length amount of times is a sufficient amount to either escape the list or encounter duplicated indices (aka an infinite loop or standstill on a 0).

Arnauld · Accepted Answer · 2025-06-27 13:20:59Z

3

JavaScript (ES6), 40 bytes

Returns a Boolean value.

f=(a,i=0)=>1/(v=a[i])?f(a,i+v,a[i]=f):!v

Try it online!

answered Jun 27 at 13:20

Arnauld

206k21 gold badges187 silver badges670 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2025-06-27 20:59:55Z

Jelly, 14 bytes

+J;0»0«L$ịÐL`Ḣ

A monadic Link that accepts a list of integers and yields 0 (falsey) if we will escape or a positive integer (truthy) if we'll get stuck.

Try it online! Or see the test-suite.

How?

+J;0»0«L$ịÐL`Ḣ - Link: list of integers, A = [a, b, c, ...]
+J             - {A} add 1-indices of {A} -> [a+1, b+2, c+3, ...]
  ;0           - concatenate a zero
    »0         - maximum with zero
                  (Force any pointing off the left to point to zero (rightmost))
      «L$      - minimum with its length
                  (Force any pointing off the right to length(A)+1 (also rightmost))
            `  - use that as both arguments of - f(Current=Pointers, Pointers):
          ÐL   -   repeat until a fixed point with:
         ị     -     {Current} cyclical 1-index into {Pointers} (vectorises)
             Ḣ - head

att · Accepted Answer · 2025-06-27 23:02:33Z

3

Wolfram Language (Mathematica), 36 31 bytes

aHead@a[[i=1;i+=a[[i]]&/@a]]

Try it online!

Returns Part if we escape, and List otherwise.

Wolfram Language (Mathematica), 37 32 bytes

aListQ@a[[i=1;i+=a[[i]]&/@a]]

Try it online!

Returns False if we escape, and True otherwise.

edited Jun 27 at 23:02

answered Jun 27 at 14:18

att

22.8k2 gold badges19 silver badges70 bronze badges

Add a comment |

dharr · Accepted Answer · 2025-06-27 16:20:42Z

1

Maple, 107 bytes

proc(s)i,n:=1,op(1,s);do p:=s[i];s[i]:=0;i+=p;if p=0 then return 0 elif i<1 or i>n then return 1 fi od end;

Returns 0 for false and 1 for true.

f:=proc(s)
i,n:=1,op(1,s);        # initialize i=1 and n=length of Vector
do
  p:=s[i];
  s[i]:=0;             # set 0 to stop infinite loop    
  i+=p;
  if p=0 then
    return 0           # false
  elif i<1 or i>n then
    return 1           # true
  fi
od
end;

answered Jun 27 at 16:20

dharr

1,1162 silver badges8 bronze badges

Add a comment |

Neil · Accepted Answer · 2025-06-27 20:36:52Z

Charcoal, 18 bytes

ＦθＭ∧¬÷ⅈＬθ§θⅈ→¬÷ⅈＬθ

Try it online! Link is to verbose version of code. Outputs an inverted Charcoal boolean, i.e. nothing if we escape, - if we don't. Explanation:

Ｆθ

Take (up to) as many steps as there are elements in the array. For each step...

Ｍ∧¬÷ⅈＬθ§θⅈ→

... if the current element is in the array then move that number of positions.

¬÷ⅈＬθ

Output whether the current element is still in the array. (A second ¬ would be needed to output whether we escape.)

Jani Joeli · Accepted Answer · 2025-07-01 23:39:48Z

Commodore 64 Assembler, 20 17 Bytes (6502/KickAssembler)

Routine

CWEFTA: lax #0      // 2 Reset A and X.
walk:   dey         // 1 Have we taken more steps than the size of array?
        bmi end     // 2 If yes, we're stuck in a loop and couldn't escape.
        clc         // 1 Clear the carry flag...
        adc array,x // 3 ...and add the element in current index to A.
        tax         // 1 Make it the new array index.
        bmi end     // 2 If the result is negative we've escaped.
        cmp length  // 2 Have we gone past the end of the array yet?
        bcc walk    // 2 If not, continue walking the array.
end:    rts         // 1 Y is positive (escaped) or negative (didn't escape).

Explanation

System limitation: 6502 can only handle signed integers from -128 to 127, where the highest bit determines the sign. In order to keep the routine small (this is code golf after all), we consider a negative array index = escaped. In other words, array's size is limited to 128 elements, as MSB would be set for indexes 128-255, and thus CPU would think these are negative.
The array can be placed to the beginning of any 256 byte page in memory, excluding the memory locations reserved by the system, this routine, and the program calling it of course.
Before calling the routine, length of the array is loaded to Y register and stored on zero page.
If we've taken more steps than there are elements in the array, we know we are stuck in a loop (including zero loop).
At the end, Y register contains the result: a positive number if we escaped, a negative number if we didn't.

Try It Out (in your favourite IDE or CLI)

This test program calls our routine and changes the border colour based on result in Y register: White for successful escape, Black for failure.

BasicUpstart2(start)
start:  ldy #(array_end - array)    // Load length of array to Y
        sty $2                      // Store length on zero page
        jsr CWEFTA                  // CALL OUR ROUTINE
        cpy #0                      // Is Y positive or negative?
        bmi nega                    // Jump if negative
        ldy #WHITE                  // Otherwise, load white
        .by $2c                     // BIT abs to skip the next two bytes
nega:   ldy #BLACK                  // Load black
        sty $d020                   // White border=escaped, black=didn't
        rts                         // Return to BASIC prompt

.align $100
array:  .by 2,-2,-1 ; array_end:

// Can We Escape From The Array?
CWEFTA: lax #0      // 2 Reset A and X.
walk:   dey         // 1 Have we taken more steps than the size of array?
        bmi end     // 2 If yes, we're stuck in a loop and couldn't escape.
        clc         // 1 Clear the carry flag...
        adc array,x // 3 ...and add the element in current index to A.
        tax         // 1 Make it the new array index.
        bmi end     // 2 If the result is negative we've escaped.
        cmp $2      // 2 Have we gone past the end of the array yet?
        bcc walk    // 2 If not, continue walking the array.
end:    rts         // 1 Y is positive (escaped) or negative (didn't escape).

DialFrost · Accepted Answer · 2025-08-13 17:26:18Z

1

Python 3.8 (pre-release), 54 bytes

f=lambda a,p=0:any((p:=p+a[p])>=len(a)or p<0for _ in a)

Try it online!

answered Aug 13 at 17:26

DialFrost

5,1892 gold badges15 silver badges58 bronze badges

Add a comment |

Hayden Becker · Accepted Answer · 2025-08-16 17:23:36Z

Haskell, 88 bytes

f is the function to call, which takes a [Int] and returns a Bool.

f=g 0[]
g p m x|q>length x-1||q<0=True|elem q m=False|True=g q((x!!p):m)x where q=x!!p+p

I feel like there's definitely a more elaborate way to golf this, the ungolfed (or should I say pre-golfed) code is here:

walker :: [Int] -> Bool
walker xs = walker' xs 0 []

walker' :: [Int] -> Int -> [Int] -> Bool
walker' xs p ms
  | xs !! p + p > length xs - 1 || xs !! p + p < 0 = True
  | elem (xs !! p + p) ms                          = False
  | otherwise                                      = walker' xs (xs !! p + p) ((xs !! p) : ms)

where walker is f and walker' is g.

CaydendW · Accepted Answer · 2025-08-19 07:14:48Z

C (gcc), 68 65 bytes

i,m;f(n,r)int*r;{for(i=m=0;m<n+0u&i++<n;)m+=r[m];return m>=n+0u;}

Try it online!

Thanks to ceilingcat for shaving off three bytes :)

Feed the length of the array in the first parameter and the array itself as the second parameter. This can be golfed a tad more if I was allowed to use UB but the rules say no.

The TIO link has some testcases. It should print all ones (which it does) for this to pass.

How it works

I used the pigeonhole principle to figure out that the number of iterations can't be longer than the length of the array. If it did, we would have to repeat an index at least once and that index didn't take us out of the array before which means that we will fall into a pattern we did before which means we will loop forever. So, I just store a counter alongside the array index and loop until at most n. Once we break out of the loop, just check if m has escaped or not.

Stack Exchange Network

The Array Walker (part 2)

The Array Walker (part 2)

Example #1

Example #2

Example #3

Example #4

Example #5

Rules

Answer Header Format

12 Answers 12

JavaScript (Node.js), 32 bytes

x86-64 machine code, 16 bytes

05AB1E, 17 bytes

JavaScript (ES6), 40 bytes

Jelly, 14 bytes

How?

Wolfram Language (Mathematica), 36 31 bytes

Wolfram Language (Mathematica), 37 32 bytes

Maple, 107 bytes

Charcoal, 18 bytes

Commodore 64 Assembler, 20 17 Bytes (6502/KickAssembler)

Routine

Explanation

Try It Out (in your favourite IDE or CLI)

Python 3.8 (pre-release), 54 bytes

Haskell, 88 bytes

C (gcc), 68 65 bytes

How it works

Linked

Hot Network Questions

The Array Walker (part 2)

The Array Walker (part 2)

Example #1

Example #2

Example #3

Example #4

Example #5

Rules

Answer Header Format

12 Answers 12

JavaScript (Node.js), 32 bytes

x86-64 machine code, 16 bytes

05AB1E, 17 bytes

JavaScript (ES6), 40 bytes

Jelly, 14 bytes

How?

Wolfram Language (Mathematica), 36 31 bytes

Wolfram Language (Mathematica), 37 32 bytes

Maple, 107 bytes

Charcoal, 18 bytes

Commodore 64 Assembler, 20 17 Bytes (6502/KickAssembler)

Routine

Explanation

Try It Out (in your favourite IDE or CLI)

Python 3.8 (pre-release), 54 bytes

Haskell, 88 bytes

C (gcc), 68 65 bytes

How it works

Linked

Related

Hot Network Questions