Classify a region by its slope

Question

Definitions

The k^th ring of a square matrix of size N, where 1 ≤ k ≤ ceiling(N/2) is the list formed by the elements of the k^th and (N-k+1)^th rows and columns, but without the first and last k-1 elements.

Example:

Matrix:

1 2 3 4 5
6 7 8 9 1
8 7 6 5 4
3 2 1 9 8
7 6 5 4 3

Delimited in rings:

+-------------------+
| 1   2   3   4   5 |
|   +-----------+   |
| 6 | 7   8   9 | 1 |
|   |   +---+   |   |
| 8 | 7 | 6 | 5 | 4 |
|   |   +---+   |   |
| 3 | 2   1   9 | 8 |
|   +-----------+   |
| 7   6   5   4   3 |
+-------------------+

The first ring of the above is 1,2,3,4,5,1,4,8,3,4,5,6,7,3,8,6, the second is 7,8,9,5,9,1,2,7 and the third is 6.

An N by N matrix of positive integers is (for the purposes of this challenge):

• concave if all the integers on the k^th ring are strictly greater than those on the (k+1)^th ring, where k is any integer between 1 and N (those on the first ring are greater than those on the second, which are in turn greater than those on the third etc.). Example:

  4 5 6 4 7   -> because 4,5,6,4,7,4,8,5,5,4,6,5,9,5,5,4 are all higher than
  4 3 2 2 4      any of 3,2,2,3,2,3,3,2, which are all higher than 1
  5 2 1 3 8
  5 3 3 2 5
  9 5 6 4 5
  

• flat if all the integers in the matrix are equal. Another example (perhaps redundant):

  2 2 2 2
  2 2 2 2
  2 2 2 2
  2 2 2 2
  

• convex if all the integers on the k^th ring are strictly lower than those on the (k+1)^th ring, where k is any integer between 1 and N (those on the first ring are lower than those on the second, which are in turn lower than those on the third etc.). Example:

  1 2 1   -> because 1 and 2 are both lower than 6
  2 6 2
  1 2 1
  

• mixed if the matrix doesn't satisfy any of the above criteria. Example:

  3 3 3 3 3
  3 2 2 2 3
  3 2 3 2 3
  3 2 2 2 3
  3 3 3 3 3
  

Challenge

Given a square matrix of positive integers of size at least 3, classify it according to the definitions above. That is, output one of four different consistent values based on whether the matrix is concave, flat, convex or mixed.

You can compete in any programming language and can take input and provide output through any standard method and in any reasonable format, while taking note that these loopholes are forbidden by default. This is code-golf, so the shortest submission (in bytes) for every language wins.

Test cases

Here's a bunch of examples for you to choose from – I selected 6 from each category.

Concave

[[3, 3, 3], [3, 1, 3], [3, 3, 3]]
[[2, 3, 4], [5, 1, 6], [7, 8, 9]]
[[19, 34, 45], [34, 12, 14], [13, 13, 13]]
[[3, 4, 3, 4], [4, 2, 1, 3], [3, 1, 2, 4], [4, 3, 4, 3]]
[[4, 5, 6, 4, 7], [4, 3, 2, 2, 4], [5, 2, 1, 3, 8], [5, 3, 3, 2, 5], [9, 5, 6, 4, 5]]
[[7, 7, 7, 7, 7], [7, 6, 6, 6, 7], [7, 6, 5, 6, 7], [7, 6, 6, 6, 7], [7, 7, 7, 7, 7]]

Flat

[[1, 1, 1], [1, 1, 1], [1, 1, 1]]
[[2, 2, 2], [2, 2, 2], [2, 2, 2]]
[[8, 8, 8], [8, 8, 8], [8, 8, 8]]
[[120, 120, 120], [120, 120, 120], [120, 120, 120]]
[[10, 10, 10, 10], [10, 10, 10, 10], [10, 10, 10, 10], [10, 10, 10, 10]]
[[5, 5, 5, 5, 5, 5], [5, 5, 5, 5, 5, 5], [5, 5, 5, 5, 5, 5], [5, 5, 5, 5, 5, 5], [5, 5, 5, 5, 5, 5], [5, 5, 5, 5, 5, 5]]

Convex

[[1, 2, 1], [2, 6, 2], [1, 2, 1]]
[[1, 1, 1], [1, 2, 1], [1, 1, 1]]
[[19, 34, 45], [34, 76, 14], [13, 6, 13]]
[[3, 3, 3, 3], [3, 4, 4, 3], [3, 4, 4, 3], [3, 3, 3, 3]]
[[192, 19, 8, 6], [48, 324, 434, 29], [56, 292, 334, 8], [3, 4, 23, 23]]
[[291, 48, 7, 5], [47, 324, 454, 30], [58, 292, 374, 4], [9, 2, 53, 291]]

Mixed

[[1, 2, 3], [4, 5, 9], [6, 7, 8]]
[[10, 14, 21], [100, 8, 3], [29, 2, 19]]
[[5, 5, 5, 5], [5, 4, 4, 5], [5, 4, 6, 5], [5, 5, 5, 5]]
[[3, 3, 3, 3], [3, 1, 2, 3], [3, 3, 2, 3], [3, 3, 3, 3]]
[[12, 14, 15, 16], [12, 18, 18, 16], [12, 11, 11, 16], [12, 14, 15, 16]]
[[5, 5, 5, 5, 5], [5, 4, 4, 4, 5], [5, 4, 6, 4, 5], [5, 4, 4, 4, 5], [5, 5, 5, 5, 5]]

Answer 1

Jelly,  18 17  16 bytes

^{I believe there is a lot of potential for this effort to be out-golfed}

L‘HạŒỤṀ€IṠQṢ«FE$

A monadic link accepting a list of lists of numbers which returns a list of integers:

Concave ->  [0, 0]
Flat    ->  [-1, 0, 1]
Convex  ->  [-1, 0]
Mixed   ->  [-1, 0, 0]

Try it online! Or see the test-suite.

L‘H could be replaced with the less efficient but atomically shorter JÆm.

How?

L‘HạŒỤṀ€IṠQṢ«FE$ - Link: list of (equal length) lists of numbers
L                - length
 ‘               - increment
  H              - halve
                 -   = middle 1-based index (in both dimensions as the input is square)
    ŒỤ           - sort multi-dimensional indices by their corresponding values
                 -   = a list of pairs of 1-based indexes
   ạ             - absolute difference (vectorises)
                 -   = list of [verticalDistanceToMiddle, horizontalDistanceToMiddle] pairs
      Ṁ€         - maximum of €ach
                 -   each = N/2-k (i.e. 0 as middle ring and N/2 as outermost)
        I        - incremental deltas (e.g. [3,2,2,3,1]->[3-2,2-2,3-2,1-3]=[-1,0,1,-2])
         Ṡ       - sign (mapping -n:-1; 0:0; and +n:1)
          Q      - de-duplicate
           Ṣ     - sort
                 -   = concave:[0, 1]; convex:[-1, 0]; flatOrMixed:[-1, 0, 1]
               $ - last two links as a monad
             F   -   flatten
              E  -   all equal? (1 if flat otherwise 0)
            «    - minimum (vectorises)
                 -   = concave:[0, 0]; convex:[-1, 0]; mixed:[-1, 0, 0]; flat:[-1, 0, 1]

Answer 2

Python 2, 219 216 189 176 bytes

def g(M):A=[sorted((M[1:]and M.pop(0))+M.pop()+[i.pop(j)for j in[0,-1]for i in M])for k in M[::2]];S={cmp(x[j],y[~j])for x,y in zip(A,A[1:])for j in[0,-1]};return len(S)<2and S

Try it online!

Outputs set([1]), set([0]), set([-1]), or False for concave, flat, convex, or mixed, respectively.

Thx for: A whopping 27 bytes from a few optimizations by ovs. And then another 13 bytes afterwards.

The list comprehension A (due to ovs) creates a list of the elements of each ring, sorted.

Next, we compare the max and min values between adjacent rings by looking at the 0th and -1th elements of each sorted list in A. Note that if, for example, M is concave, min of each outer ring must be greater than max of the next inner-most ring; and it then follows that max of each outer ring will also be greater than min of the next inner-most ring.

If M is concave, flat, or convex, the set of these min/max comparisons will have only 1 element from {-1, 0, 1}; if it is mixed, there will be two or more elements.

Answer 3

Java (JDK 10), 247 232 220 bytes

x->{int i=0,j=x.length,k,m,M,p=0,P=0,r=0;for(;i<j;){for(M=m=x[k=i][--j];k<=j;)for(int q:new int[]{x[i][k],x[j][k],x[k][i],x[k++][j]}){m=m<q?m:q;M=M<q?q:M;}r=i++>0?(k=P<m?3:p>M?1:P==m?2:4)*r!=r*r?4:k:0;p=m;P=M;}return r;}

Try it online!

Outputs:

• 1 for "concave"
• 2 for "flat"
• 3 for "convex"
• 4 for "mixed"

Ungolfed:

x -> { // lambda that takes in the input int[][]
  int i = 0, // index of right bound of ring
      j = x.length, // index of left bound of ring
      k, // index of row-column-pair in ring
      m, // minimum of ring
      M, // maximum of ring
      p = 0, // minimum of previous ring
      P = 0, // maximum of previous ring
      r = 0; // result
  for (; i < j; ) { // iterate the rings from outside inwards
    // set both min and max to be to top right corner of the ring (and sneakily set some loop variables to save space)
    for (M = m = x[k = i][--j]; k <= j; ) // iterate the row-column pairs of the ring from top-right to bottom-left
      for (int q : new int[] {x[i][k], x[j][k], x[k][i], x[k++][j]}) { // iterate all of the cells at this row-column pair (and sneakily increment the loop variable k)
        // find new minimum and maximum
        m = m < q ? m : q;
        M = M < q ? q : M;
      }
    r = // set the result to be...
      i++ > 0 ? // if this is not the first ring... (and sneakily increment the loop variable i)
              // if the new result does not match the old result...
              (k = P < m ? // recycling k here as a temp variable to store the new result, computing the result by comparing the old and new mins/maxes
                         3
                         : p > M ?
                                 1
                                 : P == m ? 
                                          2
                                          : 4) * r != r * r ? // multiplying by r here when comparing because we want to avoid treating the case where r = 0 (unset) as if r is different from k
                                                            4 // set the result to "mixed"
                                                            : k // otherwise set the result to the new result
              : 0; // if this is the first ring just set the result to 0
    // set the old ring mins/maxes to be the current ones
    p = m; 
    P = M;
  }
  return r; // return the result
}

Answer 4

K (ngn/k), 100 71 69 bytes

{$[1=#?,/a:(,/x)@.=i&|i:&/!2##x;;(&/m>1_M,0)-&/(m:&/'a)>-1_0,M:|/'a]}

Try it online!

returns 1=concave, ::=flat, -1=convex, 0=mixed

(:: is used as a placeholder for missing values in k)

Answer 5

JavaScript (ES6), 168 bytes

Returns:

• -1 for flat
• 0 for mixed
• 1 for convex
• 2 for concave

f=(a,k=w=~-a.length/2,p,P,i,m,M,y=w)=>k<0?i%4%3-!i:a.map(r=>r.map(v=>Y|(X=k*k-x*x--)<0&&X|Y<0||(m=v>m?m:v,M=v<M?M:v),x=w,Y=k*k-y*y--))|f(a,k-1,m,M,i|M-m<<2|2*(M<p)|m>P)

Try it online!

How?

Minimum and maximum on each ring

We compute the minimum m and the maximum M on each ring.

We test whether a cell is located on a given ring by computing the squared distance from the center of the matrix on each axis. Taking the absolute value would work just as well, but squaring is shorter.

A cell at (x, y) is located on the n-th ring (0-indexed, starting from the outermost one) if the following formula is false:

((Y != 0) or (X < 0)) and ((X != 0) or (Y < 0))

where:

• X = k² - (x - w)²
• Y = k² - (y - w)²
• w = (a.length - 1) / 2
• k = w - n

Example: is the cell (1, 2) on the 2nd ring of a 6x6 matrix?

  | 0 1 2 3 4 5   w = (6 - 1) / 2 = 2.5
--+------------   (x, y) --> ( x-w,  y-w) --> ((x-w)²,(y-w)²)
0 | 0 0 0 0 0 0   (1, 2) --> (-1.5, -0.5) --> (  2.25,   0.5)
1 | 0 1 1 1 1 0   
2 | 0[1]0 0 1 0   k = w - 1 = 1.5
3 | 0 1 0 0 1 0   k² = 2.25
4 | 0 1 1 1 1 0   X = 2.25 - 2.25 = 0 / Y = 2.25 - 0.5 = 1.75
5 | 0 0 0 0 0 0   ((X != 0) or (Y < 0)) is false, so (1,2) is on the ring

Flags

At the end of each iteration, we compare m and M against the minimum p and the maximum P of the previous ring and update the flag variable i accordingly:

• i |= 1 if m > P
• i |= 2 if M < p
• we set higher bits of i if M != m

At the end of the process, we convert the final value of i as follows:

i % 4  // isolate the 2 least significant bits (for convex and concave)
% 3    // convert 3 to 0 (for mixed)
- !i   // subtract 1 if i = 0 (for flat)

Answer 6

Jelly, 17 bytes

ŒDŒH€ẎUÐeZ_þƝṠFf/

Returns 1 for concave, 0 for flat, -1 for convex, and nothing for mixed.

Try it online!

Answer 7

oK, 56 bytes

&/1_`{&/+(y>|/x;y<&/x;,/x=/:y)}':{(,/x)@.=i&|i:&/!2##x}@

Based off of ngn's answer.

Try it online!

concave:1 0 0
   flat:0 0 1
 convex:0 1 0
  mixed:0 0 0

Answer 8

C++17 (gcc), 411 bytes

#import<map>
#define R return
#define T(f,s)X p,c;for(auto&e:r){c=e.second;if(p.a&&!p.f(c)){s;}p=c;}R
using I=int;struct X{I a=0;I z=0;I f(I n){R!a||n<a?a=n:0,n>z?z=n:0;}I
l(X x){R z<x.a;}I g(X x){R a>x.z;}I e(X x){R a==z&a==x.a&z==x.z;}};I
N(I i,I j,I s){i*=s-i;j*=s-j;R i<j?i:j;}auto C=[](auto&&m){I
s=size(m),i=-1,j;std::map<I,X>r;for(;++i<s;)for(j=-1;++j<s;)r[N(i,j,s-1)].f(m[i][j]);T(g,T(l,T(e,R 0)3)2)1;};

A new high score! (at the time of posting, at least) Oh well, it's a bit nifty, but still C++.

Try it online!

Lambda C takes a std::vector<std::vector<int>> and returns 1 for concave, 2 for convex, 3 for flat, or 0 for mixed.

A more legible version of the code, with descriptive identifiers, comments, R->return and I->int written out, etc.:

#include <map>

// Abbreviation for golfing. Spelled out below.
#define R return

// Macro to test whether all pairs of consecutive Ranges in `rings`
// satisfy a condition.
// func: a member function of Range taking a second Range.
// stmts: a sequence of statements to execute if the condition is
//        not satisfied. The statements should always return.
//        May be missing the final semicolon.
// Expands to a statement, then the return keyword.
// The value after the macro will be returned if all pairs of Ranges
// satisfy the test.
#define TEST(func, stmts)                                     \
    Range prev, curr;                                         \
    for (auto& elem : rings) {                                \
        curr = elem.second;                                   \
        // The first time through, prev.a==0; skip the test.  \
        if (prev.a && !prev.func(curr))                       \
        { stmts; }                                            \
        prev = curr;                                          \
    }                                                         \
    return

// Abbreviation for golfing. Spelled out below.
using I = int;

// A range of positive integers.
// A default-constructed Range is "invalid" and has a==0 && z==0.
struct Range
{
    int a = 0;
    int z = 0;
    // Add a number to the range, initializing or expanding.
    // The return value is meaningless (but I is shorter than void for golfing).
    int add(int n) {
        return !a||n<a ? a=n : 0, n>z ? z=n : 0;
        /* That is:
        // If invalid or n less than previous min, set a.
        if (a==0 || n<a)
            a = n;
        // If invalid (z==0) or n greater than previous max, set z.
        if (n>z)
            z = n;
        return dummy_value;
        */
    }

    // Test if all numbers in this Range are strictly less than
    // all numbers in Range x.
    int less(Range x)
    { return z < x.a; }

    // Test if all numbers in this Range are strictly greater than
    // all numbers in Range x.
    int greater(Range x)
    { return a > x.z; }

    // Test if both this Range and x represent the same single number.
    int equal(Range x)
    { return a==z && a==x.a && z==x.z; }
};

// Given indices into a square matrix, returns a value which is
// constant on each ring and increases from the first ring toward the
// center.
// i, j: matrix indices
// max: maximum matrix index, so that 0<=i && i<=max && 0<=j && j<=max
int RingIndex(int i, int j, int max)
{
    // i*(max-i) is zero at the edges and increases toward max/2.0.
    i *= max - i;
    j *= max - j;
    // The minimum of these values determines the ring.
    return i < j ? i : j;
}

// Takes a container of containers of elements convertible to int.
// Must represent a square matrix with positive integer values.
// Argument-dependent lookup on the outer container must include
// namespace std, and both container types must have operator[] to
// get an element.  (So std::vector or std::array would work.)
// Returns:
//   1 for a concave matrix
//   2 for a convex matrix
//   3 for a flat matrix
//   0 for a mixed matrix
auto C /*Classify*/ = [](auto&& mat)
{
    int mat_size=size(mat), i=-1, j;
    std::map<int, Range> rings;

    // Populate rings with the range of values in each ring.
    for (; ++i<mat_size;)
        for (j=-1; ++j<mat_size;)
            rings[RingIndex(i, j, mat_size-1)].add(mat[i][j]);

    // Nested macros expand to
    // Range prev, curr; for ... if (...) {
    //   Range prev, curr; for ... if (...) {
    //     Range prev, curr; for ... if (...) {
    //       return 0;
    //     } return 3;
    //   } return 2;
    // } return 1
    // Note each scope declares its own prev and curr which hide
    // outer declarations.
    TEST(greater, TEST(less, TEST(equal, return 0) 3) 2) 1;
};