Determine the Widest Valley

Clash Royale CLAN TAG#URR8PPP

up vote
5
down vote

favorite

1

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

code-golf array-manipulation

share|improve this question

asked 1 hour ago

BMO

10.4k21879

add a comment | 

up vote
5
down vote

favorite

1

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

code-golf array-manipulation

share|improve this question

asked 1 hour ago

BMO

10.4k21879

add a comment | 

up vote
5
down vote

favorite

1

up vote
5
down vote

favorite

1

1

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

code-golf array-manipulation

share|improve this question

asked 1 hour ago

BMO

10.4k21879

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

code-golf array-manipulation

code-golf array-manipulation

share|improve this question

asked 1 hour ago

BMO

10.4k21879

share|improve this question

asked 1 hour ago

BMO

10.4k21879

share|improve this question

share|improve this question

asked 1 hour ago

BMO

10.4k21879

asked 1 hour ago

BMO

10.4k21879

asked 1 hour ago

BMO

10.4k21879

10.4k21879

add a comment | 

add a comment | 

3 Answers
3

active

oldest

votes

up vote
1
down vote

Python 2, 120 115 89 87 86 bytes

lambda a:max(r-l+1for l,v in e(a)for r,w in e(a)if v==w>max(a[l+1:r]+[0]))
e=enumerate

Try it online!

_{-1 byte, thanks to BMO}

share|improve this answer

edited 1 hour ago

answered 1 hour ago

TFeld

12.9k2836

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does replacing [-1] with [0] work?
  – BMO
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BMO Yeah, I guess it does. A valley must always start with n>0 right?
  – TFeld
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, there can only be non-negative integers and as such a valley has to start with n>0.
  – BMO
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
1
down vote

Haskell, 66 bytes

f(a:b)|(_:h,i:_)<-span(<a)b,i==a=max(length h+3)$f b|1<2=f b
f _=0

Try it online!

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

add a comment | 

up vote
1
down vote

Jelly, 17 16 bytes

Ẇ>þị@€.¬Ø.¦ȦƲƇẈṀ

Try it online!

 ẈṀ Maximum of lengths of…
Ẇ Ƈ All sublists satisfying:
 Ʋ This funky 4-link monad:
 >þ ị@€. ¬Ø.¦ Ȧ Is a valley.

First, >þ makes a table of $a[x]>a[y]$ for our valley candidate. For $[6, 2, 3, 1, 4, 6]$ it's:

beginbmatrix
color#0000&0&0&0&0&colorred0\
colorblue1&color#0000&1&0&1&colorblue1\
colorblue1&0&color#0000&0&1&colorblue1\
colorblue1&1&1&color#0000&1&colorblue1\
colorblue1&0&0&0&color#0000&colorblue1\
colorred0&0&0&0&0&color#0000
endbmatrix

We want the $colorredtextred$ elements to be both zero, representing that the start and end are equal.

We want the $colorbluetextblue$ elements to be all ones, representing that the endpoints are > everything in the middle.

We apply ị@€.: index each by 0.5, i.e. get the start and end of every row. This gets us

beginbmatrix
color#0000&colorred0\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorred0&color#0000
endbmatrix

Then ¬Ø.¦ negates the first and last rows, and Ȧ checks that the matrix is all ones.

(The top-left and bottom-right corners are guaranteed to be 0s in the table we started from, as they're on the diagonal, and $ x not> x $. So we don't need to check them at all.)

share|improve this answer

edited 3 mins ago

answered 12 mins ago

Lynn

49k694223

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Also, L€ → Ẉ.
  – Erik the Outgolfer
  7 mins ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175321%2fdetermine-the-widest-valley%23new-answer', 'question_page');

);

Post as a guest

Name Email

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote

Python 2, 120 115 89 87 86 bytes

lambda a:max(r-l+1for l,v in e(a)for r,w in e(a)if v==w>max(a[l+1:r]+[0]))
e=enumerate

Try it online!

_{-1 byte, thanks to BMO}

share|improve this answer

edited 1 hour ago

answered 1 hour ago

TFeld

12.9k2836

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does replacing [-1] with [0] work?
  – BMO
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BMO Yeah, I guess it does. A valley must always start with n>0 right?
  – TFeld
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, there can only be non-negative integers and as such a valley has to start with n>0.
  – BMO
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
1
down vote

Python 2, 120 115 89 87 86 bytes

lambda a:max(r-l+1for l,v in e(a)for r,w in e(a)if v==w>max(a[l+1:r]+[0]))
e=enumerate

Try it online!

_{-1 byte, thanks to BMO}

share|improve this answer

edited 1 hour ago

answered 1 hour ago

TFeld

12.9k2836

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does replacing [-1] with [0] work?
  – BMO
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BMO Yeah, I guess it does. A valley must always start with n>0 right?
  – TFeld
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, there can only be non-negative integers and as such a valley has to start with n>0.
  – BMO
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

Python 2, 120 115 89 87 86 bytes

lambda a:max(r-l+1for l,v in e(a)for r,w in e(a)if v==w>max(a[l+1:r]+[0]))
e=enumerate

Try it online!

_{-1 byte, thanks to BMO}

share|improve this answer

edited 1 hour ago

answered 1 hour ago

TFeld

12.9k2836

Python 2, 120 115 89 87 86 bytes

lambda a:max(r-l+1for l,v in e(a)for r,w in e(a)if v==w>max(a[l+1:r]+[0]))
e=enumerate

Try it online!

_{-1 byte, thanks to BMO}

share|improve this answer

edited 1 hour ago

answered 1 hour ago

TFeld

12.9k2836

share|improve this answer

share|improve this answer

edited 1 hour ago

edited 1 hour ago

edited 1 hour ago

answered 1 hour ago

TFeld

12.9k2836

answered 1 hour ago

TFeld

12.9k2836

answered 1 hour ago

TFeld

12.9k2836

12.9k2836

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does replacing [-1] with [0] work?
  – BMO
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BMO Yeah, I guess it does. A valley must always start with n>0 right?
  – TFeld
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, there can only be non-negative integers and as such a valley has to start with n>0.
  – BMO
  1 hour ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Does replacing [-1] with [0] work?
  – BMO
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @BMO Yeah, I guess it does. A valley must always start with n>0 right?
  – TFeld
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, there can only be non-negative integers and as such a valley has to start with n>0.
  – BMO
  1 hour ago
  

  
  
  
  

Does replacing [-1] with [0] work?
– BMO
1 hour ago

Does replacing [-1] with [0] work?
– BMO
1 hour ago

@BMO Yeah, I guess it does. A valley must always start with n>0 right?
– TFeld
1 hour ago

@BMO Yeah, I guess it does. A valley must always start with n>0 right?
– TFeld
1 hour ago

Yes, there can only be non-negative integers and as such a valley has to start with n>0.
– BMO
1 hour ago

Yes, there can only be non-negative integers and as such a valley has to start with n>0.
– BMO
1 hour ago

add a comment | 

up vote
1
down vote

Haskell, 66 bytes

f(a:b)|(_:h,i:_)<-span(<a)b,i==a=max(length h+3)$f b|1<2=f b
f _=0

Try it online!

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

add a comment | 

up vote
1
down vote

Haskell, 66 bytes

f(a:b)|(_:h,i:_)<-span(<a)b,i==a=max(length h+3)$f b|1<2=f b
f _=0

Try it online!

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

add a comment | 

up vote
1
down vote

up vote
1
down vote

Haskell, 66 bytes

f(a:b)|(_:h,i:_)<-span(<a)b,i==a=max(length h+3)$f b|1<2=f b
f _=0

Try it online!

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

Haskell, 66 bytes

f(a:b)|(_:h,i:_)<-span(<a)b,i==a=max(length h+3)$f b|1<2=f b
f _=0

Try it online!

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

share|improve this answer

share|improve this answer

answered 35 mins ago

nimi

30.5k31985

answered 35 mins ago

nimi

30.5k31985

answered 35 mins ago

nimi

30.5k31985

30.5k31985

add a comment | 

add a comment | 

up vote
1
down vote

Jelly, 17 16 bytes

Ẇ>þị@€.¬Ø.¦ȦƲƇẈṀ

Try it online!

 ẈṀ Maximum of lengths of…
Ẇ Ƈ All sublists satisfying:
 Ʋ This funky 4-link monad:
 >þ ị@€. ¬Ø.¦ Ȧ Is a valley.

First, >þ makes a table of $a[x]>a[y]$ for our valley candidate. For $[6, 2, 3, 1, 4, 6]$ it's:

beginbmatrix
color#0000&0&0&0&0&colorred0\
colorblue1&color#0000&1&0&1&colorblue1\
colorblue1&0&color#0000&0&1&colorblue1\
colorblue1&1&1&color#0000&1&colorblue1\
colorblue1&0&0&0&color#0000&colorblue1\
colorred0&0&0&0&0&color#0000
endbmatrix

We want the $colorredtextred$ elements to be both zero, representing that the start and end are equal.

We want the $colorbluetextblue$ elements to be all ones, representing that the endpoints are > everything in the middle.

We apply ị@€.: index each by 0.5, i.e. get the start and end of every row. This gets us

beginbmatrix
color#0000&colorred0\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorred0&color#0000
endbmatrix

Then ¬Ø.¦ negates the first and last rows, and Ȧ checks that the matrix is all ones.

(The top-left and bottom-right corners are guaranteed to be 0s in the table we started from, as they're on the diagonal, and $ x not> x $. So we don't need to check them at all.)

share|improve this answer

edited 3 mins ago

answered 12 mins ago

Lynn

49k694223

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Also, L€ → Ẉ.
  – Erik the Outgolfer
  7 mins ago
  

  
  
  
  

add a comment | 

up vote
1
down vote

Jelly, 17 16 bytes

Ẇ>þị@€.¬Ø.¦ȦƲƇẈṀ

Try it online!

 ẈṀ Maximum of lengths of…
Ẇ Ƈ All sublists satisfying:
 Ʋ This funky 4-link monad:
 >þ ị@€. ¬Ø.¦ Ȧ Is a valley.

First, >þ makes a table of $a[x]>a[y]$ for our valley candidate. For $[6, 2, 3, 1, 4, 6]$ it's:

beginbmatrix
color#0000&0&0&0&0&colorred0\
colorblue1&color#0000&1&0&1&colorblue1\
colorblue1&0&color#0000&0&1&colorblue1\
colorblue1&1&1&color#0000&1&colorblue1\
colorblue1&0&0&0&color#0000&colorblue1\
colorred0&0&0&0&0&color#0000
endbmatrix

We want the $colorredtextred$ elements to be both zero, representing that the start and end are equal.

We want the $colorbluetextblue$ elements to be all ones, representing that the endpoints are > everything in the middle.

We apply ị@€.: index each by 0.5, i.e. get the start and end of every row. This gets us

beginbmatrix
color#0000&colorred0\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorred0&color#0000
endbmatrix

Then ¬Ø.¦ negates the first and last rows, and Ȧ checks that the matrix is all ones.

(The top-left and bottom-right corners are guaranteed to be 0s in the table we started from, as they're on the diagonal, and $ x not> x $. So we don't need to check them at all.)

share|improve this answer

edited 3 mins ago

answered 12 mins ago

Lynn

49k694223

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Also, L€ → Ẉ.
  – Erik the Outgolfer
  7 mins ago
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

Jelly, 17 16 bytes

Ẇ>þị@€.¬Ø.¦ȦƲƇẈṀ

Try it online!

 ẈṀ Maximum of lengths of…
Ẇ Ƈ All sublists satisfying:
 Ʋ This funky 4-link monad:
 >þ ị@€. ¬Ø.¦ Ȧ Is a valley.

First, >þ makes a table of $a[x]>a[y]$ for our valley candidate. For $[6, 2, 3, 1, 4, 6]$ it's:

beginbmatrix
color#0000&0&0&0&0&colorred0\
colorblue1&color#0000&1&0&1&colorblue1\
colorblue1&0&color#0000&0&1&colorblue1\
colorblue1&1&1&color#0000&1&colorblue1\
colorblue1&0&0&0&color#0000&colorblue1\
colorred0&0&0&0&0&color#0000
endbmatrix

We want the $colorredtextred$ elements to be both zero, representing that the start and end are equal.

We want the $colorbluetextblue$ elements to be all ones, representing that the endpoints are > everything in the middle.

We apply ị@€.: index each by 0.5, i.e. get the start and end of every row. This gets us

beginbmatrix
color#0000&colorred0\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorred0&color#0000
endbmatrix

Then ¬Ø.¦ negates the first and last rows, and Ȧ checks that the matrix is all ones.

(The top-left and bottom-right corners are guaranteed to be 0s in the table we started from, as they're on the diagonal, and $ x not> x $. So we don't need to check them at all.)

share|improve this answer

edited 3 mins ago

answered 12 mins ago

Lynn

49k694223

Jelly, 17 16 bytes

Ẇ>þị@€.¬Ø.¦ȦƲƇẈṀ

Try it online!

 ẈṀ Maximum of lengths of…
Ẇ Ƈ All sublists satisfying:
 Ʋ This funky 4-link monad:
 >þ ị@€. ¬Ø.¦ Ȧ Is a valley.

First, >þ makes a table of $a[x]>a[y]$ for our valley candidate. For $[6, 2, 3, 1, 4, 6]$ it's:

beginbmatrix
color#0000&0&0&0&0&colorred0\
colorblue1&color#0000&1&0&1&colorblue1\
colorblue1&0&color#0000&0&1&colorblue1\
colorblue1&1&1&color#0000&1&colorblue1\
colorblue1&0&0&0&color#0000&colorblue1\
colorred0&0&0&0&0&color#0000
endbmatrix

We want the $colorredtextred$ elements to be both zero, representing that the start and end are equal.

We want the $colorbluetextblue$ elements to be all ones, representing that the endpoints are > everything in the middle.

We apply ị@€.: index each by 0.5, i.e. get the start and end of every row. This gets us

beginbmatrix
color#0000&colorred0\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorblue1&colorblue1\
colorred0&color#0000
endbmatrix

Then ¬Ø.¦ negates the first and last rows, and Ȧ checks that the matrix is all ones.

(The top-left and bottom-right corners are guaranteed to be 0s in the table we started from, as they're on the diagonal, and $ x not> x $. So we don't need to check them at all.)

share|improve this answer

edited 3 mins ago

answered 12 mins ago

Lynn

49k694223

share|improve this answer

share|improve this answer

edited 3 mins ago

edited 3 mins ago

edited 3 mins ago

answered 12 mins ago

Lynn

49k694223

answered 12 mins ago

Lynn

49k694223

answered 12 mins ago

Lynn

49k694223

49k694223

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Also, L€ → Ẉ.
  – Erik the Outgolfer
  7 mins ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Also, L€ → Ẉ.
  – Erik the Outgolfer
  7 mins ago
  

  
  
  
  

Also, L€ → Ẉ.
– Erik the Outgolfer
7 mins ago

Also, L€ → Ẉ.
– Erik the Outgolfer
7 mins ago

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175321%2fdetermine-the-widest-valley%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email