DEV Community

Emmanuel / Manny (eapl.me)
Emmanuel / Manny (eapl.me)

Posted on

Reto 1 - Emparejar puntos

#retodelasemana

Conoce más del reto de la semana

En mi empleo actual encontré un reto que me tuvo pensando por varios días, pues me pareció muy curioso, y encontré una manera elegante de resolverlo. Espero que también lo encuentres interesante.

Descripción del reto

Hay una serie de puntos en un espacio en 2 dimensiones. Cada punto tiene una coordenada aproximada (que después será confirmada con más precisión), un texto que lo describe, y un identificador único (UUID).

Recibiremos una tabla como la siguiente, en formato CSV:

|--------|-------|-------------|--------------------------------------|
| X      | Y     | Text        | UUID                                 |
|--------|-------|-------------|--------------------------------------|
| 100    | 250   | PLACEHOLDER | fb202d64-2d1a-4c43-9927-63b12ecfa175 |
| 150    | 300   | PLACEHOLDER | c90ee93a-b6c9-4bad-b046-1cea3a9912ca |
| 118    | 45    | Object 1    | 2ef679df-3eba-4396-ba99-32aca2bbbdd9 |
| 129.34 | 98.01 | Object 2    | d9f17009-7f0c-47ee-ae98-387a7777e590 |
|--------|-------|-------------|--------------------------------------|
Enter fullscreen mode Exit fullscreen mode

Para los elementos provisionales (Con texto 'PLACEHOLDER') sabemos que más adelante nos darán la posición exacta, y además reemplazaremos el texto temporal con el correcto.

La confirmación de los puntos vendrá en otra tabla como esta:

|---------|---------|-------|
| X       | Y       | Text  |
|---------|---------|-------|
| 100.108 | 249.981 | 1001  |
| 150.057 | 300.087 | 1002  |
|---------|---------|-------|
Enter fullscreen mode Exit fullscreen mode

Entonces en la primera tabla se debe buscar el punto confirmado más cercano, reemplazarse sus coordenadas, y también su valor.

Al combinar las dos tablas, el resultado será el siguiente:

|---------|---------|-------------|--------------------------------------|
| X       | Y       | Text        | UUID                                 |
|---------|---------|-------------|--------------------------------------|
| 100.108 | 250.981 | 1001        | fb202d64-2d1a-4c43-9927-63b12ecfa175 |
| 150.057 | 300.087 | 1002        | c90ee93a-b6c9-4bad-b046-1cea3a9912ca |
| 118     | 45      | Object 1    | 2ef679df-3eba-4396-ba99-32aca2bbbdd9 |
| 129.34  | 98.01   | Object 2    | d9f17009-7f0c-47ee-ae98-387a7777e590 |
|---------|---------|-------------|--------------------------------------|
Enter fullscreen mode Exit fullscreen mode

Explicado de otra manera, cada punto confirmado se buscará en la primera tabla para emparejar con el punto más cercano. Cuando se encuentre se reemplaza la coordenada y su texto. Por ejemplo, para el punto confirmado (100.108, 249.981) tendremos el placeholder más cercano en (100, 250) que corresponde al texto "1001".

Se trabajarán unos 10,000 puntos. El procesamiento debería tomar menos de 1 segundo.

¿Cómo lo resolverías?

Algunas pistas

  1. Empieza pensando ¿Cómo puedes calcular la distancia entre dos puntos? ¿Ya existe alguna dependencia en tu lenguaje que te puede ayudar?
  2. Asume que siempre habrá un punto suficientemente cercano que corresponda con otro punto confirmado.

Top comments (0)