Reto de programación 1 - Emparejar puntos #reto

En mi empleo actual encontré un reto que quiero compartir contigo.

Me ha tenido pensando por unos días, 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    |Texto      |UUID                                |
|100   |250  |PLACEHOLDER|fb202d64-2d1a-4c43-9927-63b12ecfa175|
|150   |300  |PLACEHOLDER|c90ee93a-b6c9-4bad-b046-1cea3a9912ca|
|118   |45   |Círculo 1  |2ef679df-3eba-4396-ba99-32aca2bbbdd9|
|129.34|98.01|Círculo 2  |d9f17009-7f0c-47ee-ae98-387a7777e590|

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      |Texto|
|100.108|249.981|1001 |
|150.057|300.087|1002 |

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        |Texto    |UUID                                |
|100.108   |249.981  |1001     |fb202d64-2d1a-4c43-9927-63b12ecfa175|
|150.057   |300.087  |1002     |c90ee93a-b6c9-4bad-b046-1cea3a9912ca|
|118       |45       |Círculo 1|2ef679df-3eba-4396-ba99-32aca2bbbdd9|
|129.34    |98.01    |Círculo 2|d9f17009-7f0c-47ee-ae98-387a7777e590|

Es decir, 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, por lo que se debe considerar un buen desempeño.

Podríamos comenzar diciendo que este procesamiento debería tomar menos de 1 segundo.

¿Cómo lo resolverías?

Mándame tu respuesta en Mastodon

⁂

EOT

---

Cómo enviar una respuesta

Send me your comments to

text.eapl.mx.mebiu [at] slmail.me

My Microblogging