1votos

Coordenadas de un número en una matriz caracol. en C#

por josejuan hace 6 años

¡Coste O(1)!, se puede obtener explícitamente la coordenada de un número en el caracol, sólo hay que desarrollar la serie, que resulta en un polinomio de segundo grado y despejarlo.

Gracias a Enrique, ya sabemos cómo generar una matriz caracol pero, ¿una forma eficiente de devolver las coordenadas de un único número dentro de la matriz caracol?.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Tomandos los cuadros del más exterior al interior x = 1, 2, 3, ... su perímetro 
Func<int, int, int> perimeter = ( x, n ) => 4 * ( n - 2 * x + 1 ); 
 
// Dada las coordenadas de la diagonal principal (1, 1), (2, 2), ... devuelve el número que contiene 
Func<int, int, int> diagonalPos = ( x, n ) => -4 * x * x + ( 4 * n + 8 ) * x - 4 * n - 3; 
 
// Dado un número, indica en qué cuadro está 
Func<int, int, int> inSquare = ( z, n ) => (int) Math.Floor(n * 0.5 - 0.5 * Math.Sqrt(n * n - z + 1.0) + 1.0); 
 
Func<int, int, Point> coords = ( z, n ) => { 
    var s = inSquare(z, n); 
    var l = perimeter(s, n) / 4; // lado del subcuadro -1 
    var l2 = l + l; 
    var l3 = l2 + l; 
    var d = diagonalPos(s, n); 
    if( z <= d + l ) 
        return new Point(s + z - d, s); 
    if( z <= d + l2 ) 
        return new Point(s + l, s + z - d - l); 
    if( z <= d + l3 ) 
        return new Point(s + d + l3 - z, s + l); 
    return new Point(s, s + d + l2 + l2 - z); 
}; 
3 comentarios
0votos

Escrito por rchavarriat hace 6 años

No entiendo exactamente cómo has llegado a la implementación del método inSquare, pero por lo demás la solución no puede ser más eficiente.
1votos

Escrito por josejuan hace 6 años

"No entiendo exactamente cómo has llegado a la implementación del método inSquare"

Dada una matriz caracol, podemos enumerar los "cuadros" concéntricos que posee, por ejemplo, para n = 2

12
43

sólo hay un "cuadro" con perímetro 1234

Para n = 3 es

123
894
765

tiene por "cuadros" el 12345678 y el 9

Para n = 4 es

 1, 2, 3, 4
12,13,14, 5
11,16,15, 6
10, 9, 8, 7

que tiene por "cuadros" el 1..12 y el 13..16.

Si nos fijamos, el perímetro de un cuadrado de lado N lo podemos hacer con 4 fichas de longitud N-1, por ejemplo el primer cuadro del caracol n=4 tiene por fichas [1,2,3], [4,5,6], [7,8,9] y [10,11,12].

Ésto se puede hacer para cualquier cuadro de cualquier caracol.

Por otro lado, si un cuadrado tiene lado N, entonces el cuadrado inmediatamente interior tendrá (siempre) N-2 de lado.

Por resumir todo lo anterior, si "n" es la dimensión de la matriz caracol y "c" es el cuadrado en el que estamos (1º, 2º, 3º, ...) entonces, el perímetro "C" de dicho cuadrado "c-ésimo" hemos dicho que es:

    C(c, n) = (n - 1 - 2 * (c - 1)) * 4

Ahora bien, si sumamos los perímetros de todos los cuadros de AFUERA hacia ADENTRO hasta el "c-ésimo", tenemos que dicho perímetro "P" es:

    P(c, n) = C(1, n) + C(2, n) + ... + C(c, n)
    P(c, n) = (n - 1) * 4 + (n - 1 - 2) * 4 + (n - 1 - 2 * 2) * 4 + ...
    P(c, n) = 4 (n - 1 + n - 1 - 2 + n - 1 - 2 * 2 + ... + n - 1 - 2 * (c - 1))
    P(c, n) = 4 (n * c - c - 2 (1 + 2 + ... + (c - 1)))
    P(c, n) = 4 (n * c - c - c (c - 1))
    P(c, n) = 4 (n * c - c^2)

Quedándonos la ecuación de segundo grado

    c^2 - n * c + P(c, n) / 4 = 0

Cuya solución es:

    2 c = n - sqrt(n^2 - P)

Pero resulta que precisamente los números de la matriz caracol nos dan el perímetro, así, basta sustituir P por cada número para obtener el cuadrado al que pertenecen.

Hay que tener en cuenta, que los números de la diagonal, son la frontera de cada cuadrado, por lo que no es hasta "cerrar" el cuadro que obtenemos el perímetro completo, por eso, todos los números de un "cuadro" quedan "por debajo" de su perímetro (parece complicado pero es que me explico fatal, si tengo un metro, en el centímetro 50 tengo 0,5 metros, en el centímetro 75 tengo 0,75 metros por eso no es hasta "pasarme del metro" que empiezo a obtener 1,.. metros), de ahí, que la función final sea:

   cuadrado = Floor(n * 0.5 - 0.5 * Sqrt(n * n - z + 1))

Si además queremos enumerar los cuadros como 1, 2, 3, ... en lugar de como 0, 1, 2, ... pues sólo hay que añadir uno, que es la función que yo he usado.

0votos

Escrito por rchavarriat hace 6 años

O_o
Cómo he echado de menos una pizarra, ains.
Gracias profe, una explicación genial!

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.