Ayuda.

[Jonhy_xc]

Hola,

Necesitaría ayuda con un "problema" que consiste en calcular la distancia mínima de un número hasta el 1 en la espitar de Ulam. Solo te darían un número y la espiral de Ulam es infinita.

Se puede comprobar que los dígitos (comenzando por el 1) están dispuestos siguiendo un patrón en espiral de dentro hacia afuera.

17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23 --> ...

Se nos pide calcular la distancia más corta (distancia manhattan)
de un número entero n hasta el 1. Para calcular esta distancia sólo se
permiten movimientos hacia arriba, abajo, izquierda y derecha.

Un ejemplo sería: La distancia según este cálculo del 7 al 1 es 2.

Muchas gracias de antemano.

[CalgaryCorpus]

Tiene cara de ser la parte entera de la mitad de la raiz cuadrada del numero.

[MAFUS]

No, 3 tiene distancia 2. Debe ser otra cosa.

[K-YreX]

Tenía la intuición de que no parece un problema que se resuelva con una única fórmula. Por lo que intenté ir sacando relaciones a ver si llegaba a algo... Empecé encontrando algunas recurrencias que al final resultaron ser más sencillas. Mi planteamiento era el siguiente:

• La espiral podemos verla como si fueran anillos concéntricos (el 1 es el anillo 0).
  
• El máximo valor del anillo n es (2*n+1)*(2*n+1) y se encuentra en la esquina inferior derecha de su anillo correspondiente.
  
  El problema es que no tengo demasiado tiempo y como me parece un problema entretenido dejo aquí mis avances por si alguien quiere continuar con ello y que no se quede abandonado. (Tengo algunas recurrencias más por si le interesan a alguien... aunque creo que no son demasiado importantes).
  
  Luego he visto que por ahí se me iba a complicar mucho la cosa así que he pensado que se puede hacer una matriz donde dibujar la espiral calculando antes el número de anillos necesarios para que la espiral contenga el número que desea buscar el usuario. De ahí he sacado que:
  
• El orden de la matriz que contiene n anillos es (2*n-1).
  
  Me parece que la forma más sencilla es esta segunda (aunque sea un poco limitada).
  
  Código [Seleccionar] Expandir
  
crear matriz con la forma de la espiral
valor_actual := valor introducido por el usuario
mientras valor_actual != 1
    comparar con arriba, abajo, izquierda, derecha (cuidado con los limites)
    valor_actual := menor de los 4 valores anteriores
    distancia++

  Cuando tenga tiempo intentaré acabarlo

[Loretz]

Debe haber por ahí alguna fórmula genial, de esas del tipo (a+b)^2  que nos deje a todos con la boca abierta, pero andando a pie, siguiendo la descripción más pedestre posible, mi algoritmo es este:

Código [Seleccionar] Expandir

#include <iostream>
#include <cmath>
#include <array>

int main()
{
    // el primer círculo empieza en 2 y termina en 9
    // el segundo empieza en 10 y termina en 25
    // el tercero ... de 26 a 49 ...

    // Claramente, cada círculo empieza donde termina el anterior y
    // terminan en 9 (3*3) o en 25 (5*5) o en 49 (7*7) ... [los cuadrados del número de elementos de sus lados]

    // También, cada círculo tiene elementos que están más próximos al centro y están ubicados en cruz:

    // Se ve que en la rama de la derecha de esa cruz están:
    // el 2 (primer círculo),
    // el 11 (su número de círculo + los elementos del círculo anterior = 2 + 9),
    // el 28 (su número de círculo + los elementos del círculo anterior = 3 + 25).
    // y lo mismo para los siguientes...

    // Mirando también en las otras direcciones,
    // el primer círculo tiene en esa cruz al 2, que es por donde empieza,
    // y en las otras ramas al 4 (o sea, el 2 + su número de elementos por lado = 4),
    // tiene también al 6 (4 + su número de elementos por lado = 6)
    // y al 8 (6 + su número de elementos por lado -1 == 8).
    // Así que para el primer círculo esa cruz está formada por el 2, 4, 6, 8.

    // Lo mismo para los otros círculos:
    // el segundo círculo tiene al 11, 15, 19 y 23.

    // Cada círculo va a tener 4 números sobre la cruz:
    // el primero que está en el brazo horizontal de la derecha
    // y los otros tres distando entre sí la cantidad de elementos en cada lado.

    // Bueno, eso es todo.


    // Para calcular la distancia al centro de un número cualquiera habrá que calcular
    // la distancia a la rama más próxima de la cruz y sumar su número de círculo.

    // Por ejemplo: dado un númeo cualquiera:

    int n;
    std::cout << "numero: ";
    std::cin >> n;

    // Se puede determinar a qué círculo pertenece:
    int c = 0;
    for (int i = 1; ; i += 2, ++c) {  // 1, 3, 5, 7, ...
        if (i*i >= n) {
            break;
        }
    }
    std::cout << n << " pertenece al circulo " << c << '\n';

    // Este círculo tiene 4 números sobre la cruz central:
    std::array<int, 4> cruz;

    // El primero (rama de la derecha) es:
    cruz[0] = c + (2 * c - 1)*(2 * c - 1);  // su número de círculo más los elementos del círculo anterior

    // y los otros tres van a ser:
    for (int i = 1; i < 4; ++i) {
        cruz[i] = cruz[i - 1] + c * 2; // número anterior en la cruz + cantidad de elementos del lado
    }

    std::cout << "los elementos de la cruz son: ";
    for (const auto& i : cruz) {
        std::cout << i << "  ";
    }
    std::cout << '\n';

   
    // Ahora, la distancia al centro de este número es:
    // la distancia al elemento de la cruz más cercano + su número de círculo:

    int dist_cruz = 1000; // absurdamente grande
    for (int i = 0; i < 4; ++i) {
        if(abs(cruz[i] - n) < dist_cruz) {
            dist_cruz = abs(cruz[i] - n);
        }
    }
    int distancia = dist_cruz + c;

    std::cout << "distancia al centro = " << distancia << '\n';
}

[Jonhy_xc]

Debe haber por ahí alguna fórmula genial, de esas del tipo (a+b)^2  que nos deje a todos con la boca abierta, pero andando a pie, siguiendo la descripción más pedestre posible, mi algoritmo es este:

Código [Seleccionar] Expandir

#include <iostream>
#include <cmath>
#include <array>

int main()
{
    // el primer círculo empieza en 2 y termina en 9
    // el segundo empieza en 10 y termina en 25
    // el tercero ... de 26 a 49 ...

    // Claramente, cada círculo empieza donde termina el anterior y
    // terminan en 9 (3*3) o en 25 (5*5) o en 49 (7*7) ... [los cuadrados del número de elementos de sus lados]

    // También, cada círculo tiene elementos que están más próximos al centro y están ubicados en cruz:

    // Se ve que en la rama de la derecha de esa cruz están:
    // el 2 (primer círculo),
    // el 11 (su número de círculo + los elementos del círculo anterior = 2 + 9),
    // el 28 (su número de círculo + los elementos del círculo anterior = 3 + 25).
    // y lo mismo para los siguientes...

    // Mirando también en las otras direcciones,
    // el primer círculo tiene en esa cruz al 2, que es por donde empieza,
    // y en las otras ramas al 4 (o sea, el 2 + su número de elementos por lado = 4),
    // tiene también al 6 (4 + su número de elementos por lado = 6)
    // y al 8 (6 + su número de elementos por lado -1 == 8).
    // Así que para el primer círculo esa cruz está formada por el 2, 4, 6, 8.

    // Lo mismo para los otros círculos:
    // el segundo círculo tiene al 11, 15, 19 y 23.

    // Cada círculo va a tener 4 números sobre la cruz:
    // el primero que está en el brazo horizontal de la derecha
    // y los otros tres distando entre sí la cantidad de elementos en cada lado.

    // Bueno, eso es todo.


    // Para calcular la distancia al centro de un número cualquiera habrá que calcular
    // la distancia a la rama más próxima de la cruz y sumar su número de círculo.

    // Por ejemplo: dado un númeo cualquiera:

    int n;
    std::cout << "numero: ";
    std::cin >> n;

    // Se puede determinar a qué círculo pertenece:
    int c = 0;
    for (int i = 1; ; i += 2, ++c) {  // 1, 3, 5, 7, ...
        if (i*i >= n) {
            break;
        }
    }
    std::cout << n << " pertenece al circulo " << c << '\n';

    // Este círculo tiene 4 números sobre la cruz central:
    std::array<int, 4> cruz;

    // El primero (rama de la derecha) es:
    cruz[0] = c + (2 * c - 1)*(2 * c - 1);  // su número de círculo más los elementos del círculo anterior

    // y los otros tres van a ser:
    for (int i = 1; i < 4; ++i) {
        cruz[i] = cruz[i - 1] + c * 2; // número anterior en la cruz + cantidad de elementos del lado
    }

    std::cout << "los elementos de la cruz son: ";
    for (const auto& i : cruz) {
        std::cout << i << "  ";
    }
    std::cout << '\n';

   
    // Ahora, la distancia al centro de este número es:
    // la distancia al elemento de la cruz más cercano + su número de círculo:

    int dist_cruz = 1000; // absurdamente grande
    for (int i = 0; i < 4; ++i) {
        if(abs(cruz[i] - n) < dist_cruz) {
            dist_cruz = abs(cruz[i] - n);
        }
    }
    int distancia = dist_cruz + c;

    std::cout << "distancia al centro = " << distancia << '\n';
}

Muchísimas gracias!!

[Serapis]

Tiene cara de ser la parte entera de la mitad de la raiz cuadrada del numero.

Más o menos es así... puede  sumar o restar 1 según el caso, es decir según lo que dice si para 7 distancia es 2, para 1 distancia es 1, entonces debe sumarse 1...

Está mal dibujado, los cuadrados pares son las diganoles de las esquinas a la izquierda arriba y los cuadrados impares son las diagonales de la esquina abajo a la derecha...

d0 = int(int(sqr(n))/2) +1

Ahora bien, precisa algún ajuste pués difiere... yo toda la vida lo he visto dibujado empezando con el 0, así los cuadrados pares son diagonales al 0, y los cuadrados impares diagonales al 1...

...por otro lado como es la distancia Manhattan lo que se pide y no la euclidiana, no basta con una simple fórmula, pero para los cuadrados (las 4 diagnales) es esta:
d1 = int(sqr(n)) +1

...y el resto de casos debe resolverse con pequeños ajustes... conociendo los valores al este, oeste, norte y sur (según cada caso) entre el cuadrado menor que encaja y el siquiente que cubre al número pedido.

Dicho de otro modo, hay que calcular de qué cuadrado queda más cerca de 'n', para saber porque lado queda afectado (vertical/horizontal al centro) hasta el que tiene que llegar, entonces la fórmula general sería... Desde ese punto 'p' al N,E,S,O  (N=norte, E=este, etc...) el valor es:

Si queda más cerca del cuadrado mayor que 'n':
    d2 = (d0 + (n-p))
Si queda más cerca del cuadrado menor que 'n':
    d2 = (d0 + (p-n))
Nótese que igual que d1 es la distancia para las diagonales d0, los es para los valores en N,E,S,O...

Así que dejo a tu esfuerzo calcuar 'p'... que con logaritmo 2 resulta fácil calcular...

[Alfil]

Para los números impares cuya raíz cuadrada es entera, como puede ser 9, 25, 49, ... da un resultado inesperado.

La solución a la que yo he llegado:

Código [Seleccionar] Expandir



#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int n;
    cout << "Numero: ";
    cin >> n;

    int indice = 0;     // indice mínimo necesario de la matriz
    for( int i = 1; i * i <= n; i += 2 ) {
        indice++;
    }

     // almacena los 4 puntos cardinales de 1 respecto a n
    int cardinales[4];

    // primer punto cardinal
    cardinales[0] = indice + (2 * indice - 1) * (2 * indice - 1);

    // resto de puntos cardinales
    for( int i = 1; i < 4; i++ ){
        cardinales[i] = cardinales[i - 1] + indice * 2;
    }

    // distancia al mayor cardinal menor que n
    int distancia = abs(cardinales[0] - n);
    for( int i = 1; i < 4; i++ ) {
        if(  abs(cardinales[i] - n) < distancia )
            distancia = abs(cardinales[i] - n);
    }

    int manhatan = distancia + indice;

    float raiz = sqrt(n);
    int raiz_entera = (int)raiz;

    // Si n es impar y su raiz cuadrada es entera
    if( (n % 2 != 0) && (raiz == raiz_entera) )
        manhatan = manhatan - 2;

    cout << "\nDistancia Manhatan al #1: " << manhatan << endl;

    return 0;
}




[MAFUS]

¿Y qué tal una autocompletado?
Cuando se crea la espiral se usa la técnica de ver qué número es menor de los adyacentes. De igual forma se introduce otro número, por tanto es una tupla, que sumará en una unidad el número de pasos. El 1 tienen 0 pasos.
Por tanto
El 2, cuyo número más bajo cercano será el 1 tendrá 0+1 pasos.
El 3, cuyo número más bajo cercano será el 2 tendrá que 1+1 pasos.
El 4, cuyo número más bajo cercano será el 1 tendrá 0+1 pasos.
...
El 11, cuyo número más bajo cercano será el 2 tendrá 1+1 pasos.
Etc.

Creo que un número de tamaño máximo MAX_INT será rápido de calcular.