5
\$\begingroup\$

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 (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
\$\endgroup\$
  • \$\begingroup\$ Title: "Saddle points in a matrix". Challenge: "Order-2 saddle points in a matrix". \$\endgroup\$ – Erik the Outgolfer Jul 3 '18 at 14:58
  • \$\begingroup\$ @EriktheOutgolfer when codegolf draws inspiration from journalism :) \$\endgroup\$ – ngn Jul 3 '18 at 15:09
  • \$\begingroup\$ @LuisMendo I have 3 non-golfed solutions in different languages - k, apl, and python, and they all agree. Here's a gist with the locations of the (order-2) saddle points I got for the last test. Can you identify a saddle point that's not there? \$\endgroup\$ – ngn Jul 3 '18 at 15:26
  • \$\begingroup\$ @LuisMendo for that point the clockwise neighbours are: 52952294, or relative to the centre: =-+=--+- (+ for higher, etc), so they form five (not four) non-= segments: -,+,--,+,-. Note that the last - is not in the same segment as the first - as there's a = separating them, like in my second worked example. \$\endgroup\$ – ngn Jul 3 '18 at 15:48
  • 1
    \$\begingroup\$ @LuisMendo I added a couple of sentences to make it more clear. \$\endgroup\$ – ngn Jul 3 '18 at 16:05
4
+100
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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!

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

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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