Este repositorio contiene el código fuente usado para calcular la posición y contenido del mensaje proveniente de 3 fuentes diferentes.
Para el cálculo de la posición se utilizó el método de trilateración. La trilateración es un método matemático para determinar las posiciones relativas de objetos usando la geometría de triángulos de forma análoga a la triangulación. A diferencia de esta, que usa medidas de ángulo (junto con al menos una distancia conocida para calcular la localización del sujeto), la trilateración usa las localizaciones conocidas de dos o más puntos de referencia, y la distancia medida entre el sujeto y cada punto de referencia. Para determinar de forma única y precisa la localización relativa de un punto en un plano bidimensional usando solo trilateración, se necesitan generalmente al menos 3 puntos de referencia.
Este método nos permite calcular la posición de un punto teniendo como datos iniciales la ubicación de otros 3 puntos y sus respectivas distancias con respecto al punto a calcular. Para esto se utilizó una librería:
https://github.com/lemmingapex/trilateration
<dependency>
<groupId>com.lemmingapex.trilateration</groupId>
<artifactId>trilateration</artifactId>
<version>1.0.2</version>
</dependency>
Para el cálculo del mensaje se desarrolló un algoritmo basado en el cálculo de desfase proveniente de cada mensaje:
- La idea del algoritmo es primero identificar cual es el array que contiene la primera palabra, para esto primero calculamos en qué posición arranca cada array, y de acuerdo a sus tamaños determinamos cual es el que contiene la primera palabra.
- Teniendo esto podemos calcular cuál es la cantidad total de palabras que tiene el mensaje a reconstruir.
- Con esta longitud, podemos calcular los desfasajes que tiene cada array de entrada.
- Una vez calculado los desfasajes, nos queda construir substrings eliminando esos desfases de cada array. De esta forma todos los arrays nos quedarán ordenados, independientemente que haya o no un valor en cada posición.
- Por último lo que nos queda es combinar y reemplazar los substrings antes mencionados.
getMessage: Este método se encarga orquestar los llamados a las distintas funciones que nos va a permitir reconstruir el mensaje.
calculateStartPosition: Encargado de calcular la posición en la cual cada arreglo tiene el primer valor.
calculateSubString: Construye substring en base a longitud y desfase de cada arreglo.
replaceArrays: Suma arrays.
buildMessage: Construye string del mensaje final.
Nota: Alternativamente se desarrolló otra forma de resolverlo teniendo en cuenta anagramas, en este caso es condición necesario que en los mensajes de entrada al menos se pueda construir un bigrama para reconstruir el mensaje final. El algoritmo se encuentra la clase MessageCalculator2
El proyecto se realizó utilizando estas tecnologías:
- Java 11 con Spring-Boot 2.4.4
- Maven
- Mysql 8
- JUnit5
- Log4j2
Para la ejecución local es necesario:
- Tener Java 11 y Maven 3.6.0.
- Ejecutar mvn spring-boot:run el cuál iniciará el proyecto apuntando a una base de datos en memoria H2.
- Los endpoint tendrán url base /api/v1.
La URL base donde está hosteado el servicio es https://quasar-ms.rj.r.appspot.com/