Clasifica una región por su pendiente

16

Definiciones

El anillo k th de una matriz cuadrada de tamaño N , donde 1 ≤ k ≤ techo (N / 2) es la lista formada por los elementos de las filas y columnas k th y (N-k + 1) th , pero sin el primer y último elemento k-1 .

Ejemplo:

Matriz:

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

Delimitado en anillos:

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

El primer anillo de lo anterior es 1,2,3,4,5,1,4,8,3,4,5,6,7,3,8,6, el segundo es 7,8,9,5,9,1,2,7y el tercero es 6.

Una matriz N por N de enteros positivos es (a los efectos de este desafío):

  • cóncavo si todos los enteros en la k ésimo anillo son estrictamente mayor que aquellos en el (k + 1) ésimo anillo, donde k es cualquier número entero entre 1 y N (aquellos en el primer anillo son mayores que los de la segunda, que son a su vez mayor que los del tercero, etc.). Ejemplo:

    4 5 6 4 7 -> porque 4,5,6,4,7,4,8,5,5,4,6,5,9,5,5,4 son todos más altos que
    4 3 2 2 4 cualquiera de 3,2,2,3,2,3,3,2, que son todos superiores a 1
    5 2 1 3 8
    5 3 3 2 5
    9 5 6 4 5
    
  • plano si todos los enteros en la matriz son iguales. Otro ejemplo (quizás redundante):

    2 2 2 2
    2 2 2 2
    2 2 2 2
    2 2 2 2
    
  • convexa si todos los números enteros en el k ésimo anillo están estrictamente inferior a las de la (k + 1) ésimo anillo, donde k es cualquier número entero entre 1 y N (aquellos en el primer anillo son más bajos que los de la segunda, que son a su vez más bajos que los del tercero, etc.). Ejemplo:

    1 2 1 -> porque 1 y 2 son inferiores a 6
    2 6 2
    1 2 1
    
  • mezclado si la matriz no satisface ninguno de los criterios anteriores. Ejemplo:

    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
    

Desafío

Dada una matriz cuadrada de enteros positivos de tamaño al menos 3 , clasifíquela de acuerdo con las definiciones anteriores. Es decir, genera uno de cuatro valores consistentes diferentes en función de si la matriz es cóncava, plana, convexa o mixta.

Puede competir en cualquier lenguaje de programación y puede recibir información y proporcionar resultados a través de cualquier método estándar y en cualquier formato razonable, mientras toma nota de que estas lagunas están prohibidas de forma predeterminada. Este es el , por lo que gana el envío más corto (en bytes) para cada idioma .

Casos de prueba

Aquí hay un montón de ejemplos para que pueda elegir: seleccioné 6 de cada categoría.

Cóncavo

[[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]]

Plano

[[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]]

Convexo

[[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]]

Mezclado

[[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]]
Sr. Xcoder
fuente
Este desafío ha sido publicado previamente en el Sandbox . Gracias a aquellos que han brindado valiosos comentarios allí.
Sr. Xcoder
2
Muchacho, ¿no sería bueno tener algo de variedad-de-array conversión de cadenas a / de la matriz de funciones útiles para procesar todos los casos esas pruebas en una variedad de idiomas :)
NGM
@ngm ¡No te atrevas a pensar que ya no tenemos uno ! : P
Sr. Xcoder

Respuestas:

5

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;}

Pruébalo en línea!

Salidas:

  • 1 para "cóncavo"
  • 2 para "plano"
  • 3 para "convexo"
  • 4 para "mixto"

Sin golf:

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
}
SamYonnou
fuente
5

Jalea ,  18 17  16 bytes

Creo que hay mucho potencial para que este esfuerzo sea superado

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

Un enlace monádico que acepta una lista de listas de números que devuelve una lista de enteros:

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

Pruébalo en línea! O vea el conjunto de pruebas .

L‘Hpodría ser reemplazado por el menos eficiente pero atómicamente más corto JÆm.

¿Cómo?

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]
Jonathan Allan
fuente
5

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

Pruébalo en línea!

Salidas set([1]), set([0]), set([-1]),o Falsepara cóncavo, plano, convexo o mixto, respectivamente.

Gracias por: La friolera de 27 bytes de algunas optimizaciones por ovs . Y luego otros 13 bytes después.

La comprensión de la lista A(debido a los ovs) crea una lista de los elementos de cada anillo, ordenados.

A continuación, comparamos los valores maxy minentre los anillos adyacentes al observar los elementos 0th y -1th de cada lista ordenada en A. Tenga en cuenta que si, por ejemplo, Mes cóncavo, mincada anillo externo debe ser mayor que maxel siguiente anillo más interno ; y luego se deduce que el maxde cada anillo externo también será mayor que el mindel anillo más interno.

Si Mes cóncavo, plano o convexo, el conjunto de estas min/maxcomparaciones tendrá solo 1 elemento de {-1, 0, 1}; Si se mezcla, habrá dos o más elementos.

Chas Brown
fuente
@ovs: Eso es bastante bueno; Ahorré otro byte convirtiéndolo en una lista de comprensión (y pensando que esta podría ser una técnica muy útil para otros desafíos similares).
Chas Brown
Quizás haya una manera de acortar la comprensión de la lista, pero un ciclo while todavía parece ser más corto: while M:k=M[0]+M[-1];M=M[1:-1];A+=sorted(k+[i.pop(j)for j in[0,-1]for i in M]),(174 bytes)
ovs
@ovs: Has omitido ,A=()tu conteo de bytes ...
Chas Brown
Obtengo 174 bytes conA=()
ovs
Ah! Disculpas, entendí mal. Esto es diferente a su versión anterior, que fue de la forma: while M: A+= (some expression).
Chas Brown
4

Jalea , 17 bytes

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

Devuelve 1 para cóncavo , 0 para plano , -1 para convexo y nada para mixto .

Pruébalo en línea!

Dennis
fuente
4

JavaScript (ES6), 168 bytes

Devoluciones:

  • -1 para piso
  • 0 para mixto
  • 1 para convexo
  • 2 para cóncavo
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)

Pruébalo en línea!

¿Cómo?

Mínimo y máximo en cada anillo.

Calculamos el mínimo m y el máximo M en cada anillo.

Probamos si una celda está ubicada en un anillo dado calculando la distancia al cuadrado desde el centro de la matriz en cada eje. Tomar el valor absoluto funcionaría igual de bien, pero la cuadratura es más corta.

Una célula en (x, y) se encuentra en la n anillo-ésimo (0 indexados, a partir de la más exterior) si la siguiente fórmula es falso :

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

dónde:

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

Ejemplo: ¿ está la celda (1, 2) en el segundo anillo de una matriz de 6x6?

  | 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

Banderas

Al final de cada iteración, comparamos m y M contra el mínimo p y el máximo P del anillo anterior y actualizar la variable de indicador i en consecuencia:

  • i |= 1si m> P
  • i |= 2si M <p
  • establecemos bits más altos de i si M! = m

Al final del proceso, convertimos el valor final de i de la siguiente manera:

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)
Arnauld
fuente
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]}

Pruébalo en línea!

devuelve 1= cóncavo, ::= plano, -1= convexo, 0= mixto

( ::se utiliza como marcador de posición para valores faltantes en k)

ngn
fuente
Una estrategia diferente, usando oK:&/1_`{&/+(y>|/x;y<&/x;,/x=/:y)}':(,/*:'(|+:)\)'-1_(-1_1_+-1_1_)\
zgrep
@zgrep agradable! :) no dude en enviar como respuesta por separado y tomar ideas de la mía si quieres - por ejemplo, parece que mi división en anillos es más corto, pero no he probado en Aceptar todavía
NGN
Ooh, eso es una división de anillo muy ordenada! Me gusta.
zgrep
2

ok , 56 bytes

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

Basado en la respuesta de ngn .

Pruébalo en línea!

concave:1 0 0
   flat:0 0 1
 convex:0 1 0
  mixed:0 0 0
zgrep
fuente
no es necesario para @ si convierte todo en una gran lambda:{&/1_`{&/+(y>|/x;y<&/x;,/x=/:y)}':(,/x)@.=i&|i:&/!2##x}
ngn
1

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;};

Un nuevo puntaje alto! (al momento de publicar, al menos) Oh, bueno, es un poco ingenioso, pero sigue siendo C ++.

Pruébalo en línea!

Lambda Ctoma a std::vector<std::vector<int>>y devuelve 1 para cóncavo, 2 para convexo, 3 para plano o 0 para mixto.

Una versión más legible del código, con identificadores descriptivos, comentarios, R-> returny I-> intescritos, 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;
};
aschepler
fuente
1
No creo que 'ingenioso' signifique lo que crees que significa
solo ASCII el