29
\$\begingroup\$

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.

Task

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 stamina
Drops with 0 stamina
Arduous climb, barely doable
Long drop, strong climber
Short trek, excess stamina
Example with a shorter cliff at the end
Randomly 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]
 
Example
Small hill with no stamina
Valley with too many drops
Early failure
Randomly generated
Randomly generated
Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ From your examples, if the climber has 0 stamina and falls again, stamina stays at 0 and the climber can continue? \$\endgroup\$
    – quarague
    Mar 15 at 9:05
  • \$\begingroup\$ @quarague That's correct. \$\endgroup\$
    – chunes
    Mar 15 at 14:17
  • 1
    \$\begingroup\$ Related \$\endgroup\$
    – emanresu A
    Mar 15 at 19:16

17 Answers 17

Reset to default
17
\$\begingroup\$

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()
Improve this answer
\$\endgroup\$
10
\$\begingroup\$

Excel (ms365), 75, 64 bytes

-11 bytes thanks to @Dominic

enter image description here

=REDUCE(B1,A2:A5-A1:A4,LAMBDA(a,b,IF(b>a,-1,a-(-b>a)*(a>0))))>=0
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – Kevin Cruijssen
    Mar 13 at 9:11
  • 1
    \$\begingroup\$ @KevinCruijssen, you were right. +5 bytes to add MAX(). \$\endgroup\$
    – JvdV
    Mar 13 at 9:24
  • 1
    \$\begingroup\$ Can you swap ABS(b) for -b and MAX(0,a-1) for a-(a>0)...? \$\endgroup\$
    – Dominic van Essen
    Mar 13 at 12:18
  • \$\begingroup\$ It appears to work for the test cases. Clever, I could golf this down a bit further too! @DominicvanEssen =) \$\endgroup\$
    – JvdV
    Mar 13 at 13:18
7
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Haskell, 66 56 bytes

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
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$
    – The Thonnu
    Mar 13 at 18:05
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – Joseph Sible-Reinstate Monica
    Mar 19 at 17:32
  • 1
    \$\begingroup\$ damn, a 15% reduction on a program that size is impressive! \$\endgroup\$
    – ShapeOfMatter
    Mar 19 at 20:17
5
\$\begingroup\$

PowerShell Core, 77 bytes

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

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 15 bytes

¥vDyÄ‹i<y1‹ˆ]¯P

Inputs in the order \$heights,stamina\$.

Try it online or verify all test cases.

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)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 71 bytes

Length@a<2||(a[[2]]-a[[1]]<=b&&f[Rest@a,b-Boole[a[[1]]-a[[2]]>b&&b>0]])

Try it online!

Original Code is

f[a_List, b_Integer] := 
  Length[a] < 2 || (
    a[[2]] - a[[1]] <= b && 
    f[
      Rest[a], 
      b - Boole[a[[1]] - a[[2]] > b && b > 0]
    ]
  )

It defines a recursive function f that takes two arguments: a slice of integers a and an integer b. The function returns a boolean value that checks if the difference between consecutive elements in the slice is less than or equal to b. If the difference is greater than b, it deducts 1 from b for the next recursive call.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Consists of two links.

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

Link 2: Main link (dyadic with x = hill heights and y = starting 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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

MMIX machine language, 18 instrs (72 bytes)

Assumes terrain is 0-terminated, and at least one part long.

bool __mmixware f(octa stamina, octa *terrain);

00000000: e2020001 8d030100 8dff0108 e7010008  Ä£¡¢⁽¤¢¡⁽”¢®ḃ¢¡®
00000010: 42ff000d 320403ff 4c040007 260403ff  B”¡Æ2¥¤”L¥¡¬&¥¤”
00000020: 32040004 71040401 7a040004 26000004  2¥¡¥q¥¥¢z¥¡¥&¡¡¥
00000030: f1fffff5 2604ff03 32040004 78020402  ȯ””ṫ&¥”¤2¥¡¥x£¥£
00000040: f1fffff1 f8030000                    ȯ””ȯẏ¤¡¡

Disassembled:

f   SETL $2,1           // rv = 1
0H  LDO $3,$1,0         // start: curht = *terrain
    LDO $255,$1,8       // nextht = terrain[1]
    INCL $1,8           // terrain++
    BZ $255,2F          // if(!nextht) goto ret
    CMPU $4,$3,$255
    BNP $4,1F           // if(curht <= nextht) goto increase
    SUBU $4,$3,$255     // $4 = curht - nextht
    CMPU $4,$0,$4       // $4 = stamina <=> curht - nextht 
    ZSN  $4,$4,1        // $4 = stamina < curht - nextht
    ZSNZ $4,$0,$4       // $4 = (stamina < curht - nextht) && stamina
    SUBU $0,$0,$4       // decrement stamina if nonzero and drop is larger
    JMP 0B              // goto start
1H  SUBU $4,$255,$3     // increase: $4 = nextht - curht
    CMPU $4,$0,$4       // $4 = stamina <=> nextht - curht
    ZSNN $2,$4,$2       // rv &&= stamina >= nextht - curht
    JMP 0B              // goto start
2H  POP 3,0             // ret: return(rv, stamina, terrain)

A fairly simple algorithm. I could have put the return inline, but branches not taken are usually cheaper than branches taken in terms of time. The positioning of the second load before the increment is to decrease stalls, as the next usage of the incremented variable is in the next loop.

It was cheaper in terms of instructions to do two loads per iteration instead of transferring the next height to the current height, but it would probably take longer on a real machine; my initial plan was to transfer, hence the lack of stores to $255.

The reason for the usage of $3, $4, and $255 as temp registers instead of some other combination is that $3 and $4 go on the register stack, and it's expensive to use that too much, but $255 is a global scratch register.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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.) \$\endgroup\$
    – Misha Lavrov
    Mar 13 at 18:21
  • \$\begingroup\$ @MishaLavrov Thunno uses only the 96 printable ASCII characters, not all 128. It's just an estimation of what each character would take up. \$\endgroup\$
    – The Thonnu
    Mar 13 at 18:37
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby, 49 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You can invert boolean output and change none to any. Also _1 saves a byte (as usual) \$\endgroup\$
    – naffetS
    Mar 19 at 0:50
1
\$\begingroup\$

Java 8 (OpenJDK 8), 157 159 bytes

-2 bytes thanks to @ceilingcat !

Fun challenge and well presented too!

I get the feeling it may be shorter to do it in Java in a more classic way (probably under 100 bytes), but i wanted to try it using only the inline Stream approach :)

(n,l)->l.stream().map(e->new int[]{e}).reduce(new int[]{l.get(0),n,1},(a,b)->new int[]{b[0],a[1]-(a[0]-b[0]>a[1]&a[1]>0?1:0),a[2]<1|a[0]+a[1]<b[0]?0:1})[2]>0

Try it online!

It might be a bit hard to read so i'll try to explain a bit :

Each element of the list of heights is mapped to a single-cell integer array containing the corresponding value. This change of type in the Stream allows the reduce to carry an array of integers (with a different length) throughout the different iterations.

The accumulator of the reduce is a 3-cell integer array carrying :
[ height of previous position / current stamina / stuckness status ]
(we can't re-use the variable of the stamina parameter as itself, as it's forbidden in Java to rewrite in the Stream variables from outside of the Stream)

Each iteration in the reduce calculates and stores the informations for the next iteration. And at the end, we just have to extract the "stuckness status" of the resulting array.

Note : there are conditions to prevent the stamina from falling below zero, and for preserving the stuckness status until the end. Without these it would be bugged.

Improve this answer
\$\endgroup\$
0
0
\$\begingroup\$

Haskell, uncompetitive for now

traversable stamina terrain = length terrain == 1 ||
    ((head terrain + stamina) >= (terrain !! 1)) &&
    traversable (max (stamina - fromEnum ((head terrain - (terrain !! 1)) > stamina)) 0) (tail terrain)

I don't want golfing tips. It's uncompetitive for now, but I'll soon golf it, which will be PAINFUL.

Improve this answer
\$\endgroup\$

Your Answer

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

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