Is it traversable?

Question

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 code-golf, 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

From your examples, if the climber has 0 stamina and falls again, stamina stays at 0 and the climber can continue? — quarague, Mar 15 at 9:05

Arnauld · Accepted Answer · 2023-03-13 09:11:37Z

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()

JvdV · Accepted Answer · 2023-03-13 18:16:27Z

10

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

edited Mar 13 at 18:16

answered Mar 13 at 8:52

JvdV

2,6635 silver badges23 bronze badges

\$\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

Add a comment |

Dominic van Essen · Accepted Answer · 2023-03-13 12:05:55Z

6

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.

edited Mar 13 at 12:05

answered Mar 13 at 11:31

Dominic van Essen

30.1k2 gold badges15 silver badges48 bronze badges

Add a comment |

ShapeOfMatter · Accepted Answer · 2023-03-19 20:16:39Z

6

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

edited Mar 19 at 20:16

answered Mar 13 at 17:57

ShapeOfMatter

1715 bronze badges

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

Add a comment |

Julian · Accepted Answer · 2023-03-13 01:56:43Z

5

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

edited Mar 13 at 1:56

answered Mar 13 at 1:21

Julian

2,3085 silver badges12 bronze badges

Add a comment |

mousetail · Accepted Answer · 2023-03-13 07:37:12Z

4

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

answered Mar 13 at 7:37

mousetail

8,6251 gold badge21 silver badges59 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2023-03-13 09:00:50Z

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)

alephalpha · Accepted Answer · 2023-03-20 11:26:47Z

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

Jitse · Accepted Answer · 2023-03-13 13:27:43Z

2

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.

edited Mar 13 at 13:27

answered Mar 13 at 12:09

Jitse

6,7862 gold badges17 silver badges40 bronze badges

Add a comment |

Silvio Mayolo · Accepted Answer · 2023-03-14 05:17:27Z

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

The Thonnu · Accepted Answer · 2023-03-13 18:39:53Z

1

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

edited Mar 13 at 18:39

answered Mar 13 at 18:05

The Thonnu

9,2661 gold badge7 silver badges57 bronze badges

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

Add a comment |

Neil · Accepted Answer · 2023-03-13 22:30:13Z

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.

G B · Accepted Answer · 2023-03-14 15:05:53Z

1

Ruby, 49 bytes

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

Try it online!

answered Mar 14 at 15:05

G B

19.7k1 gold badge19 silver badges50 bronze badges

\$\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

Add a comment |

Stack Exchange Network

Is it traversable?

Task

Rules

Format

Test cases

13 Answers 13

JavaScript (ES6), 39 bytes

Commented

Excel (ms365), 75, 64 bytes

R, 52 49 bytes

Haskell, 66 56 bytes

Original:

PowerShell Core, 77 bytes

Rust, 90 bytes

05AB1E, 15 bytes

Nekomata + `-e`, 16 bytes

Nekomata v0.1.1.0 + `-e`, 21 bytes

Python 3, 56 bytes

Jelly, 20 bytes

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

Explanation

Charcoal, 29 bytes

Ruby, 49 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
array
decision-problem
or ask your own question.

Linked

Hot Network Questions

Is it traversable?

Task

Rules

Format

Test cases

13 Answers 13

JavaScript (ES6), 39 bytes

Commented

Excel (ms365), 75, 64 bytes

R, 52 49 bytes

Haskell, 66 56 bytes

Original:

PowerShell Core, 77 bytes

Rust, 90 bytes

05AB1E, 15 bytes

Nekomata + -e, 16 bytes

Nekomata v0.1.1.0 + -e, 21 bytes

Python 3, 56 bytes

Jelly, 20 bytes

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

Explanation

Charcoal, 29 bytes

Ruby, 49 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Nekomata + `-e`, 16 bytes

Nekomata v0.1.1.0 + `-e`, 21 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
array
decision-problem
or ask your own question.