12
\$\begingroup\$

Imagine we get a slice of some mountainous region, this would result in a shape similar to this:

4                   _
3   _    _       __/ \
2  / \__/ \    _/     \_   /
1 /        \  /         \_/
0           \/
  12322223210012233343221112

As we can see, we can represent this (to a certain degree) with a sequence of integers.

For the purpose of this challenge we define a valley as a contiguous subsequence where the values initially are decreasing and from some point on they are increasing. More formally for a sequence \$(a_i)_{i=1}^n\$ a valley will be indices \$1 \leq s < r < t \leq n\$ for which the following holds:

  • the valley's start and endpoint are the same: \$a_s = a_t\$
  • the valley starts and ends once the region gets lower: \$a_s > a_{s+1} \land a_{t-1} < a_t\$
  • the valley is not flat: \$a_s \neq a_r \land a_r \neq a_t\$
  • the valley initially decreases: \$\forall i \in [s,r): a_i \geq a_{i+1}\$
  • the valley will at some point increase: \$\forall j \in [r,t): a_j \leq a_{j+1}\$

Now we define the width of such a valley as the size of the indices \$[s,t]\$, ie. \$t-s+1\$.

Challenge

Given a height-profile (sequence of non-negative integers), your task is to determine the width of the widest valley.

Example

Given the height-profile [1,2,3,2,2,2,2,3,2,1,0,0,1,2,2,3,3,3,4,3,2,2,1,1,1,2], we can visualize it as before:

4                   _
3   _    _       __/ \
2  / \__/ \    _/     \_   /
1 /        \  /         \_/
0           \/
  12322223210012233343221112
    aaaaaa             ccccc
         bbbbbbbbb

Note how the second valley [3,2,1,0,0,1,2,2,3] does not extend further to the right because the left-most point is \$3\$ and not \$4\$. Furthermore we don't add the remaining two \$3\$s because we require that the endpoint is higher up than the second-last point.

Therefore the width of the widest valley is \$9\$.

Rules

  • Input will be a sequence of non-negative (sorry Dutch people) integers
    • you can assume that there is always at least one valley
  • Output will be the size of the widest valley as defined above

Testcases

[4,0,4] -> 3
[1,0,1,0,1] -> 3
[1,0,2,0,1,2] -> 4
[13,13,13,2,2,1,0,1,14,2,13,14] -> 4
[1,2,3,2,2,2,2,3,2,1,0,0,1,2,2,3,3,3,4,3,2,2,1,1,1,2] -> 9
[3,2,0,1,0,0,1,3] -> 4
\$\endgroup\$
  • 2
    \$\begingroup\$ Test case: [3,2,0,1,0,0,1,3]. All current answers return 8, by your definition I believe it should be 4. \$\endgroup\$ – Zgarb Nov 5 '18 at 17:36
  • \$\begingroup\$ Will the slope of the mountain ever be steeper than 1? (e.g. [3,1,2,3]) \$\endgroup\$ – Doorknob Nov 5 '18 at 17:51
  • \$\begingroup\$ @Zgarb: That's correct, yes. I added it to the testcases. \$\endgroup\$ – BMO Nov 5 '18 at 18:54
  • \$\begingroup\$ @Doorknob: There's nothing preventing that, yes. For example [4,0,4] would be such a case. \$\endgroup\$ – BMO Nov 5 '18 at 18:55
  • 1
    \$\begingroup\$ "Input will be a sequence of non-negative (sorry Dutch people) integers" Lol, as a Dutchman I giggled when I read this. ;) \$\endgroup\$ – Kevin Cruijssen Nov 6 '18 at 9:08
3
\$\begingroup\$

Jelly, 15 bytes

ẆµIṠḟ0ṢƑaMIḢ)Ṁ‘

Try it online!

Or see a test-suite (added two more test cases which I previously failed to fulfil).

How?

ẆµIṠḟ0ṢƑaMIḢ)Ṁ‘ - Link: list of integers
Ẇ               - all contiguous substrings
 µ          )   - for each substring, X:
  I             -   deltas
   Ṡ            -   sign (-ve:-1, 0:0, +ve:1)
    ḟ0          -   filter out zeros
       Ƒ        -   is invariant under:
      Ṣ         -     sort
         M      -   get maximal indices of X
        a       -   (vectorising) logical AND
          I     -   deltas
           Ḣ    -   head
             Ṁ  - maximum
              ‘ - increment
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 111 108 99 97 bytes

a=>a.map(o=(p,x)=>a.some(P=q=>(~x?x<0?i?q<P:q>P&&i++:i=0:q>=p)||(o=o<--x|q==P|q-p?o:x,P=q,0)))|-o

Try it online!

Commented

a =>                        // a[] = input array
  a.map(o =                 // initialize the output o to a non-numeric value
    (p, x) =>               // for each value p at position x in a[]:
    a.some(P =              //   initialize P to a non-numeric value
      q =>                  //   for each value q in a[]:
      (                     //     exit if something goes wrong:
        ~x ?                //       if x is not equal to -1:
          x < 0 ?           //         if x is negative:
            i ?             //           if we're in the increasing part:
              q < P         //             exit if q is less than P
            :               //           else:
              q > P && i++  //             increment i if q is greater than P
          :                 //         else:
            i = 0           //           initialize i to 0 (decreasing part)
        :                   //       else:
          q >= p            //         exit if q is greater than or equal to p
      ) || (                //     if we didn't exit:
        o =                 //       update the output o:
          o < --x |         //         decrement x; if o is less than x
          q == P |          //         or the last value is equal to the previous one
          q - p ?           //         or the last value is not equal to the first one
            o               //           leave o unchanged
          :                 //         else:
            x,              //           update o to x
        P = q,              //       update the previous value P to q
        0                   //       force this iteration to succeed
      )                     //
    )                       //   end of some()
  ) | -o                    // end of map(); return -o
\$\endgroup\$
3
\$\begingroup\$

Python 2, 120 115 89 87 86 152 149 bytes

lambda a:max(r-l+1for l,v in e(a)for r,w in e(a)if max(a[l+1:r]+[0])<v==w*any(s(a[l:i])[::-1]+s(a[i:r])==a[l:r]for i,_ in e(a)));e=enumerate;s=sorted

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 77 bytes

\d+
$*
M&!`\b(1+),((?!\1)(?!1+\2)1*,)+((?!\1)1*(?(3)\3|\2))*\1\b
1

O^`
\G,|$

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

M&!`

List, rather than counting, overlapping matches.

\b(1+),

The valley's start is captured into \1. This must then not match again until the end. Since we don't capture the comma, this also prevents higher values from matching.

((?!\1)(?!1+\2)1*,)+

Match the decreasing values. The (?!1+\2) prevents the any pass through the loop from being greater than the previous. (The first time through \2 isn't set so it fails to match trivially.) The capture includes the trailing comma as that's golfier.

((?!\1)1*(?(3)\3|\2))*

Match the increasing values. This time ((?3)\3|\2) means that each match is required to be at least as long as the previous value, or the last decreasing capture the first time through the loop.

\1\b

Finally the end of the valley must be the same height as the start.

1

Delete the heights, leaving the commas. (This is slightly easier than counting the heights as some of them might be zero.)

O^`

Sort in reverse order i.e. most commas first.

\G,|$

Count the number of commas on the first line, plus one.

\$\endgroup\$
1
\$\begingroup\$

Husk, 13 bytes

→▲mΓ€fȯΛEtġ≤Q

Try it online!

Explanation

I use a similar algorithm as Jonathan Allan.

→▲mΓ€fȯΛEtġ≤Q  Input is a list, say [3,1,0,1,1,0,2,3]
            Q  Nonempty slices: [[3],[1],[3,1],[0],...,[3,1,0,1,1,0,2,3]]
     f         Keep those that satisfy this:
                Argument is a slice, say [3,1,0,1,1,0,2]
          ġ≤    Cut into non-increasing pieces: [[3,1,0],[1,1,0],[2]]
         t      Drop first piece: [[1,1,0],[2]]
      ȯΛ        Each remaining piece
        E       has all elements equal: false, [1,1,0] has different elements
  m            Map over remaining slices:
                Argument is a slice, say [1,0,1,1]
   Γ            Break into head 1 and tail [0,1,1]
    €           Index of first occurrence of head in tail: 2
 ▲             Maximum: 2
→              Increment: 3
\$\endgroup\$
0
\$\begingroup\$

Japt, 31 bytes

¡ãYÄÃrc k_ò< Åd_äa x}îbZvÃrÔ+2

Try it online!

Saved a 10 bytes by taking inspiration from Zgarb's Husk answer. I still think this can be improved, but I haven't found it yet.

Explanation:

¡ãYÄÃrc                            Get all segments
        k_           Ã             Remove ones where:
          ò<                        A non-increasing sub-segment
             Å                      Other than the first one
              d_äa x}               Has different heights
                      ®   Ã        For each remaining segment:
                       bZv          Get the second index of the first character
                           rÔ      Maximum
                             +2    Increase by 2
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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