Saddle points in a matrix

Question

A matrix can be thought of as the altitudes of a surface in 3D space. Consider the 8 neighbours (orthogonal and diagonal) of a cell as a cyclic sequence in clockwise (or anticlockwise) order. Some neighbours may be higher than the original cell, some lower, and some levelled at the same height as the original cell. We split the cycle of neighbours into segments according to that property and discard the levelled segments. If we end up with exactly 4 segments alternating between higher and lower, we call the original cell an order-2 saddle point. Boundary cells (edges and corners) are never considered to be saddle points. Your task is to output the number of order-2 saddle points in a given matrix.

For instance, in the matrix

3 3 1
4 2 3
2 1 2

the central cell's neighbours in clockwise order are

3 3 1 3 2 1 2 4
+ + - +   -   +  // + for higher, - for lower
a a b c   d   a  // segments

Note that the list is cyclic, so we consider the final 4 part of the initial segment a. The signs of segments abcd are alternating - this is indeed a saddle point.

Another example:

1 7 6
5 5 5
2 5 6

Neighbours:

1 7 6 5 6 5 2 5
- + +   +   -
a b b   c   d

We have 4 +/- segments but their signs are not alternating, so this is not a saddle point. Note how segment b is separated from segment c by a levelled segment. We discard the levelled segment, but b and c remain separated. Same goes for d and a.

Third example:

3 9 1
8 7 0
3 7 8

Neighbours:

3 9 1 0 8 7 3 8
- + - - +   - +
a b c c d   e f

The signs are alternating but the number of +/- segments is 6. This is known as a monkey saddle or an order-3 saddle point. For the purposes of this challenge we should not count it.

Write a function or a complete program. Input is an integer matrix as typically represented in your language. It will consist of integers between 0 and 9 inclusive. Output is a single integer. Standard loopholes are forbidden. The shortest solution per language wins, as code-golf (obviously?) indicates.

in                                   out

[[3,3,1],[4,2,3],[2,1,2]]             1

[[1,7,6],[5,5,5],[2,5,6]]             0

[[3,9,1],[8,7,0],[3,7,8]]             0

[[3,2,3,9,0,4,2,1,9,9,1,4,8,7,9,3],
 [1,1,5,7,9,9,0,9,8,9,9,8,8,9,0,5],
 [5,8,1,5,1,6,3,5,9,2,5,6,9,0,7,5],
 [3,0,2,4,7,2,9,1,0,0,7,2,4,6,7,2],
 [6,7,1,0,2,7,3,2,4,4,7,4,5,7,3,2],
 [6,5,1,1,6,2,1,2,8,9,4,6,9,7,1,0],
 [1,6,1,8,2,2,7,9,2,0,2,4,8,8,7,5],
 [0,6,5,4,1,3,9,3,2,3,7,2,2,8,5,4]]  19

[[2,3,2,0,8,5,5,1,2,3,7,5,6,0,0,5],
 [4,1,4,9,4,7,3,8,6,8,4,2,8,7,1,7],
 [4,1,4,6,9,3,0,1,0,7,8,5,3,0,5,3],
 [5,6,0,8,0,4,9,3,2,9,9,8,4,0,0,3],
 [7,4,1,6,7,8,7,3,6,1,4,9,4,6,2,0],
 [3,1,6,7,9,7,7,6,8,6,8,1,4,9,7,0],
 [8,9,1,1,2,4,8,2,3,9,8,7,5,3,1,9],
 [0,9,5,3,8,7,7,7,8,9,0,0,2,7,3,4]]  31

[[6,6,2,3,4,6,5,4,9,5,5,1,4,7,7,6],
 [1,5,0,5,6,7,9,8,5,0,5,6,1,5,2,9],
 [0,0,0,6,1,8,1,1,9,0,7,4,5,4,5,5],
 [4,5,3,6,3,8,0,0,7,3,9,1,3,9,2,2],
 [8,8,5,3,7,1,0,7,1,1,8,1,3,0,7,7],
 [4,5,8,0,7,2,0,4,6,7,3,3,2,8,1,2],
 [1,1,6,2,5,8,4,2,6,1,6,9,8,4,8,1],
 [3,9,1,7,0,8,1,1,7,8,5,4,8,2,0,3]]   7

Answer 1

JavaScript (ES6), 179 bytes

a=>a.map((r,y)=>r.map((v,x)=>t+=x*y/r[x+1]&&a[y+1]?[...(S='12221000')+S].map((n,i)=>p-(p=d=Math.sign(v-a[y+~-n][x+~-S[i+2&7]]))&&d?s&s!=-(s=d)?T=a:T++:0,T=s=p=0)|T>>1==4:0),t=0)|t

Try it online!

How?

We iterate on each cell \$v_{y,x}\$ of each row \$r_y\$ of the input matrix.

We first make sure that we're not located over an edge of the matrix with:

x * y / r[x + 1] && a[y + 1]

(neither \$x\$ or \$y\$ is \$0\$ and both \$v_{y,x+1}\$ and \$r_{y+1}\$ are defined)

We iterate twice on each neighbor cell and keep track of the number of valid segments in \$T\$. By doing this, each segment is guaranteed to be counted twice, except the first one which may be counted either twice or three times, depending on its starting point in relation to the starting point of the cycle. Either way, we have \$\lfloor{T/2}\rfloor=4\$ for order-2 saddle points, in which case we increment the counter \$t\$.

Example:

If the first segment is aligned with the starting point:

neighbor cells: AAAABCCD --> AAAABCCDAAAABCCD
                             ^   ^^ ^^   ^^ ^  --> T = 8

If it is not aligned:

neighbor cells: AABCCDAA --> AABCCDAAAABCCDAA
                             ^ ^^ ^^   ^^ ^^   --> T = 9

We iterate on neighbor cells by starting with the rightmost one and moving clockwise with:

[...(S = '12221000') + S].map((n, i) => a[x + ~-n][y + ~-S[i + 2 & 7]])

Try it online!

We store the sign of the difference between the current cell and its current neighbor in \$d\$. We keep track of the previous value of \$d\$ in \$p\$ and the previous sign (for non-zero values) in \$s\$.

The logic to update \$p\$, \$s\$ and \$T\$ reads as follows:

p - (p = d) && d ? s & s != -(s = d) ? T = a : T++ : 0

In plain English:

• Ignore identical consecutive values.
• Ignore segments with \$d=0\$.
• Increment \$T\$ on valid sign transitions.
• Whenever an invalid sign transition is detected, do T = a to force all upcoming operations on \$T\$ to either NaN or \$0\$, thus invalidating the final test.

Answer 2

Python 2, 254 bytes

lambda m:sum(s(m[i][j:j+3],m[i+1][j:j+3],m[i+2][j+2::-1][:3])for j in range(len(m[0])-2)for i in range(len(m)-2))
t=['-','+']*2
def s(q,(x,m,y),w):a=''.join(' -+'[cmp(m,v)]for v in q+[y]+w+[x]);return[v for v,_ in zip(a,a[-1:]+a)if' '!=v!=_]in(t,t[::-1])

Try it online!

Answer 3

Ruby, 237 218 207 bytes

->a,z=0,i=j=1{l=z+=1if[[*a[i-1][h=j-1,3],(x=a[i])[j+1],*a[i+1][h,3].reverse,x[h]].map{|n|l=n<=>x[j]}.drop_while{|i|i==l}.map{|b|b==l||(l=b)==0?5:l}-[5]]-[[1,-1]*2,[-1,1]*2]==[];x[1+j+=1]||a[1+i+=j=1]?redo:z}

Try it online!