| Bytes | Lang | Time | Link |
|---|---|---|---|
| 065 | C gcc | 250818T130146Z | CaydendW |
| 088 | Haskell | 250816T172336Z | Hayden B |
| 054 | Python 3.8 prerelease | 250813T172618Z | DialFros |
| nan | Commodore 64 Assembler | 250701T224417Z | Jani Joe |
| 016 | x8664 machine code | 250628T084818Z | m90 |
| 031 | Wolfram Language Mathematica | 250627T141813Z | att |
| 014 | Jelly | 250627T204219Z | Jonathan |
| 018 | Charcoal | 250627T203652Z | Neil |
| 032 | JavaScript Node.js | 250627T163432Z | l4m2 |
| 107 | Maple | 250627T162042Z | dharr |
| 040 | JavaScript ES6 | 250627T132059Z | Arnauld |
| 017 | 05AB1E | 250627T090652Z | Kevin Cr |
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;}
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.
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.
Python 3.8 (pre-release), 54 bytes
f=lambda a,p=0:any((p:=p+a[p])>=len(a)or p<0for _ in a)
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).
x86-64 machine code, 16 bytes
31 C0 8D 4E 01 03 04 87 39 F0 73 03 E2 F7 91 C3
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.
Wolfram Language (Mathematica), 36 31 bytes
aHead@a[[i=1;i+=a[[i]]&/@a]]
Returns Part if we escape, and List otherwise.
Wolfram Language (Mathematica), 37 32 bytes
aListQ@a[[i=1;i+=a[[i]]&/@a]]
Returns False if we escape, and True otherwise.
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
Charcoal, 18 bytes
FθM∧¬÷ⅈLθ§θⅈ→¬÷ⅈLθ
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:
Fθ
Take (up to) as many steps as there are elements in the array. For each step...
M∧¬÷ⅈLθ§θⅈ→
... if the current element is in the array then move that number of positions.
¬÷ⅈLθ
Output whether the current element is still in the array. (A second ¬ would be needed to output whether we escape.)
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;
JavaScript (ES6), 40 bytes
Returns a Boolean value.
f=(a,i=0)=>1/(v=a[i])?f(a,i+v,a[i]=f):!v
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).