# Is it traversable?

Imagine that a list of integers describes the heights of some two-dimensional terrain as seen from the side.

Stamina: [   4   4   4   4   4   4   3   3   3   3   2   2   2   -   ]
O
/|\
/ \
+---+               +---+
|   |               |   |
+---+           +---+---+           +---+
|   |           |   |   |           |   |
+---+           +---+---+           +---+           +---+
|   |           |   |   |           |   |           |   |
+---+           +---+---+       +---+---+           +---+
|   |           |   |   |       |   |   |           |   |
+---+---+   +---+---+---+   +---+---+---+           +---+
|   |   |   |   |   |   |OW!|   |   |   |OW!  STUCK!|   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Height:  [   6   2   1   2   5   6   1   2   3   5   1   1   1   4   ]


A climber is standing on the first piece of terrain. Her goal is to reach the far end. She has a stamina rating that determines the maximum height she can climb. Unfortunately, she has never heard of rappelling before, so she simply jumps off any cliffs she encounters. If she falls a greater distance than her current stamina, her stamina drops by one.

Determine whether the climber can traverse the terrain.

## Rules

• The climber moves strictly from left to right.
• The climber must visit every piece of reachable terrain.
• Stamina determines maximum climbing height.
• Stamina decreases by one when fall height exceeds stamina — no matter how long the drop.
• Zero is the minimum stamina.
• The terrain is untraversable if the climber encounters a cliff above her that is taller than her current stamina level.
• The terrain is traversable if the climber is able to stand on the last piece of terrain.
• This is , so the answer with the fewest bytes (in each language) wins.

## Format

• You must accept an integer (representing starting stamina) and a list of integers (representing heights) in any reasonable format.
• You must output a truthy/falsy value. You may either use your language's convention for truthy/falsy or any two distinct values representing truthy and falsy.
• Starting stamina will be $$\\geq0\$$.
• The length of the list will be $$\\geq2\$$.
• All heights in the list will be $$\\geq1\$$.

## Test cases

The farthest reachable piece of terrain is in bold.

Truthy What is this testing?
0, [1,1,1,1,1]0, [50,45,20,19,18,10,1,1,1]5, [1,6,11,16,21,26,31]100, [500,1,100]45, [20,50]4, [6,2,1,2,5,6,1,2,3,5,1,1,1,3]17, [59,61,47,64,23,34,21,22,25,29,25]
Flat terrain with 0 staminaDrops with 0 staminaArduous climb, barely doableLong drop, strong climberShort trek, excess staminaExample with a shorter cliff at the endRandomly generated
Falsy What is this testing?
4, [6,2,1,2,5,6,1,2,3,5,1,1,1,4]0, [1,1,2,1,1]5, [30,28,22,18,13,9,7,9,11,14,22,23]6, [40,47,49,55,61,66,69,70,50,55]45, [79,48,41,70,76,85,27,12,31,66,13,17,94,77]31, [65,21,20,32,9,9,37,14,23,19,32,63]
ExampleSmall hill with no staminaValley with too many dropsEarly failureRandomly generatedRandomly generated
• From your examples, if the climber has 0 stamina and falls again, stamina stays at 0 and the climber can continue? Mar 15 at 9:05
• @quarague That's correct. Mar 15 at 14:17
• Related Mar 15 at 19:16

# JavaScript (ES6), 39 bytes

Expects (stamina)(list). Returns false for truthy and true for falsy.

n=>a=>a.some(v=>-n>a-(n-=n&&a-v>n,a=v))


Try it online!

### Commented

n =>             // outer function taking the stamina n
a =>             // inner function taking the array of heights a[],
// re-used to store the previous height
a.some(v =>      // for each height v in a[]:
-n >           //   trigger some() if -n > a - v (i.e. n < v - a,
a - (          //   meaning that we can't climb)
n -=         //   decrement n if:
n &&       //     it's not already 0
a - v > n, //     and a - v is greater than n
a = v        //   update a to v
)              //   NB: a - v is always NaN the first time
)                // end of some()


# Excel (ms365), 75, 64 bytes

-11 bytes thanks to @Dominic

=REDUCE(B1,A2:A5-A1:A4,LAMBDA(a,b,IF(b>a,-1,a-(-b>a)*(a>0))))>=0

• I'm pretty sure this fails for test case 0, [50,45,20,19,18,10,1,1,1]. As long as you don't climb, the result of multiple drops may be negative at the end. So the >=0 check will fail in that case. Mar 13 at 9:11
• @KevinCruijssen, you were right. +5 bytes to add MAX().
– JvdV
Mar 13 at 9:24
• Can you swap ABS(b) for -b and MAX(0,a-1) for a-(a>0)...? Mar 13 at 12:18
• It appears to work for the test cases. Clever, I could golf this down a bit further too! @DominicvanEssen =)
– JvdV
Mar 13 at 13:18

# R, 52 49 bytes

\(s,t)any(Map(\(i)s<<-s-(-i>s)*!!s,d<-diff(t))<d)


Attempt This Online!

Outputs TRUE if the terrain is untraversable, FALSE otherwise.

With Joseph Sible-Reinstate Monica's suggestions:
(doesn't change typing or behavior, except now it's a total function, which is a plus!)

s%(h:j@(i:_))=i-h<=s&&max 0(s-fromEnum(h-i>s))%j;_%_=1>0

##### Original:
f _[_]=True;f s(h:j@(i:_))=(i-h<=s)&&f(max 0$s-fromEnum((h-i)>s))j  try it online f has an intuitive type signature, and matches my reference implementation (on legal inputs). f :: Int -> [Int] -> Bool  basic :: Int -> [Int] -> Bool basic _ [] = True basic _ [h] = True basic s (h1 : hs@(h2 : _)) = (r <= s') && basic (s' - (if (-r) > s' then 1 else 0)) hs where r = h2 - h1 s' = max 0 s  • Welcome to Code Golf, and nice first answer! Mar 13 at 18:05 • A few improvements I see: 1. Name your function % instead of f. The infix notation will let you remove two spaces as well as reshuffle parentheses to remove the $ (saves 3 bytes). 2. Swap the order of the base case and the recursive case so you can just use _ in the base case instead of [_] (saves 2 bytes). 3. The parentheses around i-h<=s and h-i are unnecessary (saves 4 bytes). 4. Write 1>0 instead of True (saves 1 byte). Mar 19 at 17:32
• damn, a 15% reduction on a program that size is impressive! Mar 19 at 20:17

param($s,$l)$args|?{if(($l-=$_)-ge0){$s-=+($l-gt$s)*!!$s}else{-$l-gt$s}$l=$_}  Try it online! Passes the obstacle list using splatting. Returns an empty array if traversable, false in PowerShell Non empty otherwise, true in Powershell # Rust, 90 bytes fn f(a:&[i32],b:i32)->bool{a.len()<2||a[1]-a[0]<=b&&f(&a[1..],b-(a[0]-a[1]>b&&b>0)as i32)}  Attempt This Online! Recursive approach # 05AB1E, 15 bytes ¥vDyÄ‹i<y1‹ˆ]¯P  Inputs in the order $$\heights,stamina\$$. Explanation: ¥ # Get the deltas (forward differences) of the first (implicit) input-list v # Pop and loop over each difference y of this list: D # Duplicate the current stamina # (which will be the second implicit input-integer in the first iteration) yÄ # Push the absolute value of difference y ‹i # If the stamina is smaller than the absolute y: < # Decrease the stamina by 1 y1‹ # Check if y is negative (it's a drop) or 0 (it's flat terrain) ˆ # Add that check to the global array ] # Close both the if-statement and loop ¯ # Push the global array P # Check if all are truthy by taking the product (aka, none were climbs) # (which is output implicitly as result)  # Nekomata + -e, 16 bytes R↔$∆çJᵐ{CᵈAc}-0≥


Attempt This Online!

This works in Nekomata v0.2.0.0, and uses some new built-ins.

The flag -e set the interpreter to CheckExistence mode, which prints True if the computation has any result, and False otherwise.

R↔                  Take the range from the starting stamina down to 1
$Swap ∆ Get the deltas of the list of heights ç Prepend zero J Non-deterministically split the list into a list of sublists The concatenation of these sublists should be the original list ᵐ{ } For each sublist CᵈAc Replace each item except the head with its absolute value - Subtract (automatically vectorize and pad zeros) 0≥ Check if all items in the result are greater than zero  ## Nekomata v0.1.1.0 + -e, 21 bytes R↔$:t-i_0cJᵐ{CᵈAc}-0≥


This is the original answer in Nekomata v0.1.1.0.

R↔                       Take the range from the starting stamina down to 1
\$                      Swap
:t-i_                 Get the deltas of the list of heights
0c               Prepend zero
J              Non-deterministically split the list into a list of sublists
The concatenation of these sublists should be the original list
ᵐ{    }       For each sublist
CᵈAc          Replace each item except the head with its absolute value
-      Subtract (automatically vectorize and pad zeros)
0≥    Check if all items in the result are greater than zero


# Python 3, 56 bytes

f=lambda s,n,m=0,*t:m<1or(s>=m-n)&f(s-min(s,n-m>s),m,*t)


Try it online!

Takes the stamina as first argument and the splatted terrain as consecutive arguments.

# Jelly, 20 bytes

’¹¹?{ḷ<?N-N>?
_Ɲçƒ<0


Takes a comma-separated list of integers on the left-hand side and the starting stamina on the right-hand side. Returns 1 if stuck, 0 if traversable.

Link 1: Update stamina (set stamina to -1 if we can't keep going; dyadic with x = current stamina and y = fall distance)

      <?                      If stamina < fall distance then
’¹¹?{                         Decrement stamina if nonzero, else return stamina
ḷ                        Else return current stamina
N                     Negate stamina
>?                 If - stamina > fall distance
(i.e. if stamina < hill height)
-                    Then return -1 (we're stuck)
N                   Else return stamina


_Ɲ                            Take difference of consecutive elements of heights list
çƒ                          Update stamina for each hill/fall we have to traverse
<0                        Return 1 if stamina is less than zero, or
0 if stamina is still nonnegative


# Thunno, $$\24\log_{256}(96)\approx\$$ 19.75 bytes

lXz[{YDyZA<?1-y1<xsTX}xP


Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

#### Explanation

lX  # Store an empty list in x (for later)
z[  # Get the deltas of the first input
{Y  # Loop through with variable y:
Dy  #  Duplicate and push y
ZA  #  Absolute value of y
<?  #  If it is less than the absolute value:
1-  #   Decrement it
y   #   Push y again
1<  #   Is it less than 1?
xs  #   Push x and swap
TX  #   Append and store in x
}x  # After the loop, push x
P   # Take the product
# Implicit output

• I don't think there's very much approval of the $\log_{256}(k)$ scoring method here. (For one thing, arguably any language which only allows ASCII source code would deserve a factor of $\log_{256}(128) = 0.875$ on its byte count, which nobody includes.) Mar 13 at 18:21
• @MishaLavrov Thunno uses only the 96 printable ASCII characters, not all 128. It's just an estimation of what each character would take up. Mar 13 at 18:37

# Charcoal, 29 bytes

¹≔§η⁰ζＦη«≧⁻∧θ‹ι⁻ζθθ¿›ι⁺ζθ⎚≔ιζ


Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for traversable, nothing if not. Explanation:

¹


Assume that the terrain is traversable.

≔§η⁰ζ


Get the starting height.

Ｆη«


Loop through the heights.

≧⁻∧θ‹ι⁻ζθθ


If this is a drop of more than the stamina then decrement the stamina.

¿›ι⁺ζθ⎚


If this is a climb of more than the stamina then clear the canvas.

≔ιζ


(Otherwise) Save the current value as the previous value.

# Ruby, 49 bytes

->s,h{h.none?{|w|h,=*h;s<h-w&&s-=s<=>0;s<-h+h=w}}


Try it online!

• You can invert boolean output and change none to any. Also _1 saves a byte (as usual) Mar 19 at 0:50