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

APL (Dyalog Unicode), 70 66 bytes

D←⊢-1∘⌽
+/,{16=×/|D⍵/⍨×⍵×D⍵}¨(⍉1↓⌽)⍣4×(⊢-{⊂(,⍵)[8(-,⊢)3,⍳3]}⌺3 3)⎕

Try it online!

-4 bytes thanks to @Bubbler and @ngn

Full program that requires ⎕IO←0

⍝ Helper function D: cyclic differences of a list
D←⊢-1∘⌽
  ⊢     ⍝ Each element
   -    ⍝ Subtract
    1∘⌽ ⍝ The one after
⍝ Main code
+/,{16=×/|D⍵/⍨×⍵×D⍵}¨¯2 ¯2↓1⊖1⌽×(⊢-{⊂(,⍵)[6 9 8 7 4,⍳3]}⌺3 3)⎕
⎕           ⍝ The input grid
{...}⌺3 3   ⍝ For the 3×3 window centered on each cell:
 (,⍵)[8(-,⊢)3,⍳3] ⍝ Obtain the cycle elements clockwise from the right
 ⊂                ⍝ Ensure that the output is the same shape as G
×⊢-         ⍝ The sign of the difference between each cycle and its center in G
(⍉1↓⌽)⍣4    ⍝ Trim off the entries with centers on an edge/corner
{...}¨      ⍝ For each sign-difference cycle:
 ×⍵×D⍵      ⍝ The indices where a +/- segment ends
              ⍝ (nonzero and different from the following element)
 ⍵/⍨        ⍝ The signs of each segment in order
              ⍝ (must be ¯1 1 ¯1 1 or reverse to be truthy --- can only have entries +/- 1)
 D          ⍝ Cyclic differences (must be 2 ¯2 2 ¯2 or reverse to be truthy --- can only have entries ¯2, 0, or 2)
 16=×/      ⍝ Test if product is 16: ensures right length and right values.
            ⍝ Note that the sum of the cyclic differences are always 0, so 2 2 2 2 is impossible)
+/,         ⍝ Count the total number that meet the condition

A creative idea I had was taking 2×2 stencils of 2×2 stencils with ({⊂⍵}⌺2 2)⍣2⊢G then extracting cycles with {1⌷⊃,/0 1 2 3{⍉∘⌽⍣⍺⊢⍵}¨,⍵}¨. This might have been shorter (if golfed a bit more) because it didn't initially require ¯2 ¯2↓1⊖1, but unfortunately we still had to subtract corresponding elements of G.

Answer 3

05AB1E, 66 bytes

gÍF3£D¬gÍFε3£}`R«ćªćU«X.Sγ€Ù˜ÐнsθQsʒ0Ê}©gs-4Q®ü‚€OÄO0Q&ˆ€¦}\\¦D}¯O

I'm 100% sure that I can reduce some bytes here, working on it :) Meanwhile, I'll post this basic idea.

Explenation:

gÍF3£D¬gÍFε3£}`R«ćªćU«X.Sγ€Ù˜ÐнsθQsʒ0Ê}©gs-4Q®ü‚€OÄO0Q&ˆ€¦D}\\¦}¯O
              `R«ćªćU«X.Sγ€Ù˜ÐнsθQsʒ0Ê}©gs-4Q®ü‚€OÄO0Q&ˆ                 Expects a 3x3 matrix. We will run this part for each relevant cell in the overall matrix.
                                                                         Pushes 1 to the global array when this cell is order-2 saddle point, pushes 0 otherwise.
                                                                         ----------
gÍ                                                                       number of rows in the matrix minus 2.
  F                                                            }         Loop Rows-2 times
   3£                                                                    Take 3 first rows.
     D¬                                                                  Push itself and the first element (first line)
       gÍ                                                                Size. (number of columns)
         F                                                 }             Loop Cols-2
          ε3£}                                                           Trim first 3 elements from each of the selected 3 rows.
                                                        €¦D              Remove the first element of each row and duplicate it for the next iteration.
                                                            \\¦          Clear remaining elements on stack, remove current first row of the 3 rows, prepare for next iteration.
                                                                         ----------
              `                                                          Push the 3x3 matrix we got from the nested loop in 3 separate values to the stack. Last row on top.
               R                                                         Reverse last row.
                «                                                        Merge with the second row.
                 ćª                                                      Extract head and append
                   ćU                                                    Extract head and save in X
                     «                                                   Merge with the first row. Now all values of the cell are in order clockwise.
                      X.S                                                For each element in the list, put -1 if lower than X (middle of cell), 0 if equal, 1 if greater.
                         γ                                               Split a into chunks of equal adjacent elements. (segment)
                          €Ù˜                                            Uniquify each element and flat the list.
                             Ð                                           Triplicate
                              нsθQ                                       Extract head, extract tail, are they equal? 
                                  sʒ0Ê}©                                 Filter (remove zeros from the list), save the filtered list in register C
                                        g                                Size of the filtered list.
                                         s-                              Size of the filtered list - [1 if head was equal to the tail]
                                           4Q                            Is it equal to 4 (segments)? {{Condition I}}
                                             ®ü‚                         Overlapping pairs
                                                €O                       Sum each pair (desired: [-1,1] or [1,-1] will give 0)
                                                  Ä                      Abs(a)
                                                   O0Q                   Is the sum of all sums of pairs equals 0? (which means there was alternating 1/-1) {{Condition II}}
                                                      &                  Does both of the conditions were okay?
                                                       ˆ                 Push the result to the global array.
                                                                         ----------
                                                                ¯O       Push the global array and sum its values to get the number of order-2 saddle points. 

Try it online!

Answer 4

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 5

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!