danielsarmiento.dev

Tuenti Challenge 2019

May 07, 2019

Como siempre hago después de los Tuenti Challenge, aquí traigo mis soluciones y enfoques a los desafíos de la edición de 2019. Puedes consultar mis soluciones de años anteriores aquí.

Índice

Challenge 1 - Onion Wars

Como siempre, el primer desafío suele ser sencillo y pensado para que los nuevos participantes se habituen al formato que más o menos seguirá el resto de los problemas. En este caso, se trataba de averiguar el número de tortillas que teníamos que cocinar para poder satisfacer las necesidades y gustos de nuestros compañeros de trabajo. Me recordó a algunos de los otros primeros desafíos de ediciones anteriores como el de las pizzas y los gofres.

La entrada tenía la siguiente estructura:

50 ------> Número de casos
0 1 -----> Caso #1:
1 1              ├── Primera columna (0): Nº de personas que quieren tortilla CON cebolla
2 2              └── Segunda columna (1): Nº de personas que quieren tortilla SIN cebolla
3 2
28 28
12 51
100 22
64 63
...
...
...
100 27 -> Caso #50

Además, como información adicional, se nos dice que cada uno de las personas se come media tortilla, por lo que no basta sólo sumar las dos columnas. Para saber el número de tortillas necesarias basta con usar la siguiente fórmula:

Que, implementada en Python, quedaría de la siguiente manera:

import math

def total_tortillas(onion, not_onion):
    total = math.ceil(onion / 2) + math.ceil(not_onion / 2)
    return total

Challenge 2 - Help Battlestar Galactica and save humanity

El segundo desafío consistía en encontrar el número de caminos posibles entre un planeta de salida (Galactica) y otro y otro de llegada (New Earth). Para ello la información que se nos daba para cada caso era:

  1. El número de planetas que no eran el destino final.
  2. Qué otros planetas eran accesibles desde cada uno de los planetas.

Los datos de entrada tenían la siguiente estructura:

6 -------> Número de casos
1 ------------------------> Caso #1
Galactica:New Earth
2 ------------------------> Caso #2
Galactica:A
A:New Earth
8 ------------------------> Caso #3
Galactica:A,B,New Earth     ├── Planetas accesibles desde Galactica: A, B, New Earth
A:C,D                       ├── Planetas accesibles desde A: C, D
B:C,D                       ├── Planetas accesibles desde B: C, D
C:E                         ├── Planetas accesibles desde B: C, D
D:E                         ├── Planetas accesibles desde B: C, D
E:F,G                       ├── Planetas accesibles desde B: C, D
F:New Earth                 ├── Planetas accesibles desde B: C, D
G:New Earth                 └── Planetas accesibles desde B: C, D
...
...
...

Aunque con esta información era bastante obvio el enfoque, se nos da la pista de la representación en forma de grafo de uno de los ejemplos:

Graph representing planet map

Para averiguar el número de caminos desde un origen a una meta en un grafo basta con hacer búsqueda en profundidad (DFS) y contar el número de veces que se llega a la meta desde el mismo origen. Mi primer enfoque fue implementar la propia búsqueda en profundidad, pero acabé optando por usar la librería de gestión de grafos networkx.

Paso 1: Parsear la información para construir un grafo.

Para cada caso, la información era obtenida y luego transformada en un diccionario con la forma siguiente:

graph = {
        galactica: [planet2],
        planet_2: [planet_3, planet_4, planet_8],
        ...
        planet_x: [new_earth]
        }

Donde cada clave (key) del diccionario es un nodo del grafo y sus valores (values) representan las aristas del grafo, es decir, los planetas accesibles desde cada uno de ellos.

for case in range(cases):
    planets = int(infile.readline())
    graph = {}

    for i in range(planets):
        route = infile.readline().split(':')
        origin = route[0]
        destinations = route[1].rstrip().split(',')
        graph[origin] = destinations

Paso 2: Construir el grafo.

Para construir el grafo con la información del diccionario he importado networkx y construido un grafo acíclico dirigido con la siguiente función:

def graph_from_dict(graph_dict):
    g = nx.DiGraph()
    # Create the nodes from the dictionary keys
    g.add_nodes_from(graph_dict.keys())
    # Loop through the dictionary items to create the edges
    # between nodes
    for k, v in graph_dict.items():
        g.add_edges_from([(k, t) for t in v])
    return g

Paso 3: Contar el número de caminos entre origen y meta.

Finalmente, para contar los posibles caminos entre origen y meta (nuestro objetivo), he usado el metodo all_simple_paths(graph, source, target) de networkx de la siguiente manera, ya que los nodos origen y destino son siempre los mismos: Galactica y New Earth.

def count_graph_paths(graph):
    list_paths = list(nx.all_simple_paths(graph,
                                          source='Galactica',
                                          target='New Earth'))
    return len(list_paths)

Challenge 4 - Candy

Challenge 5 - Forbidden Love

Este desafío, basado en una historia real consistía en descifrar la correspondencia entre dos amantes que habían encriptado cada uno sus mensajes.

La información que tenemos es la siguiente:

  • Siempre finalizaban sus mensajes con una letra (firma): G para Gordon y B para Bradley.
  • Usaban un método de cifrado por desplazamiento en torno a una máquina de escribir Underwood.
  • El desplazamiento podía ser entre filas, columnas o filas y columnas.
  • El desplazamiento es distinto para cada mensaje.

Lo primero es representar la máquina de escribir en una estructura que permita acceder por filas y columnas. Basta una lista de listas:

typewriter = [['1', '2', '3', '4', '5', '6', '7', '8', '9', '0'],
              ['Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'],
              ['A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L', ';'],
              ['Z', 'X', 'C', 'V', 'B', 'N', 'M', ',', '.', '-']]

Como sabemos a qué persona (Gordon o Bradley) corresponde cada mensaje, podemos deducir el desplazamiento de cada mensaje gracias a la firma al final de estos.

G
P .PFF IQOZ J -------> La J sustituye a la G (Gordon)
B
J 6JZZ GKH FKK8 4 ---> El 4 sustituye a la B (Bradley)

Paso 1: Obtener el desplazamiento

# Simple shifting: The encrypted and original character are in the same row

def get_displacement(sender, encripted):
    for line in typewriter:
        if sender in line and encripted in line:
            displacement = line.index(sender) - line.index(encripted)
            return displacement
        else:
            continue
    displacement = get_special_displacement(sender, encripted)
    return displacement

# Complex shifting: The encrypted and original character are NOT
# in the same row AND/OR COLUMN

def get_special_displacement(sender, encripted):
    for line in typewriter:
        if sender in line:
            sender_line = line
        elif encripted in line:
            encripted_line = line
        else:
            continue

    row_displacement = typewriter.index(sender_line)
                            - typewriter.index(encripted_line)
    column_displacement = sender_line.index(sender)
                            - encripted_line.index(encripted)

    displacement = [row_displacement, column_displacement]
    return displacement

Paso 2: Decodificar el mensaje cifrado para obtener el original

Una vez hallado el desplazamiento sólo queda aplicarlo a cada uno de los caracteres del mensaje cifrado, teniendo en cuenta que al llegar a los límites de la máquina de escribir se vuelva a comenzar como en una lista circular sin llegar a un índice de la lista que no existe.

def decode(encripted, displacement):
    for line in typewriter:
        if encripted in line:
            encripted_line = line
            if type(displacement) == list:
                # When shifting is across rows AND columns
                decoded_line_index = (typewriter.index(encripted_line) + displacement[0])
                if decoded_line_index >= len(typewriter):
                    decoded_line_index -= len(typewriter)
                elif decoded_line_index < 0:
                    decoded_line_index += len(typewriter)
                decoded_line = typewriter[decoded_line_index]
                decoded_col_index = encripted_line.index(encripted) + displacement[1]

                if decoded_col_index >= len(encripted_line):
                    decoded_col_index -= len(encripted_line)
                if decoded_col_index < 0:
                    decoded_col_index += len(encripted_line)
                decoded = decoded_line[decoded_col_index]
                return decoded

            else:
                # When shifting is only one-dimensional
                new_index = encripted_line.index(encripted) + displacement
                if new_index >= len(encripted_line):
                    new_index -= len(encripted_line)
                elif new_index < 0:
                    new_index += len(encripted_line)
                decoded = encripted_line[new_index]
                return decoded

Challenge 6 - Alien Language

El sexto desafío consistía en obtener el alfabeto ordenado de caracteres latinos que representaban un supuesto lenguaje alienígena a partir de una lista de palabras de dicho lenguaje ordenadas de forma alfabética.

Un ejemplo sencillo de entrada es el siguiente:

dad
bad
cab
cda
  • De la pareja dad < bad deducimos que d < b
  • De la pareja bad < cab deducimos que b < c
  • De la pareja cab < cda deducimos que a < d

Y tendríamos el orden resultante: a < d < b < c. En caso de no existir un único orden se deberá devolver como resultado AMBIGUOUS.

Para resolver este problema es útil de nuevo la teoría de grafos y redes. Cada caracter contenido en el alfabeto constituirá un nodo de nuestro grafo, mientras que las relaciones de precedencia entre caracteres distintos formarán las aristas. Para el ejemplo anterior tendríamos el siguiente grafo:

graph representing alien language alphabet and its order

Una vez construido el grafo cíclico dirigido, el orden vendrá dado por el orden topológico del grafo. En caso de haber más de un orden posible, se considerará un alfabeto ambiguo.

Paso 1: Construir el grafo

De manera similar al Challenge 2, primero habrá que construir un grafo estableciendo el orden entre los nodos (caracteres). Para las relaciones de adyacencia o aristas, se comparan pares de palabras caracter a caracter. Desde el momento en el que los caracteres no coincidan, se construye una arista de la letra en la palabra que va primero a la letra de la palabra que va después. Siguiendo con el ejemplo anterior:

Para la pareja cab, cda:

  • Iteración 1: c = c ----> Caracteres iguales, no se añade arista
  • Iteración 2: a =/= d --> Caracteres distintos, arista de (a,d)
# a is a list of sorted alien words
def build_graph(a):
    graph = {}
    # Create a node for each character in a
    for word in a:
        for char in word:
            if char not in graph.keys():
                graph[char] = []

    if len(graph) > len(a):
        return {}

    for i in range(len(a) - 1):
        word1 = a[i]
        word2 = a[i + 1]

        for j in range(min(len(word1), len(word2))):
            if word1[j] != word2[j]:
                graph[word1[j]].append(word2[j])
                break

    return graph

Paso 2: Orden topológico

Una vez más será útil la librería networkx en Python. Con la salida de la función anterior, se construye un grafo dirigido y se obtienen todos los órdenes topológicos posibles. Si este no es único, se trata de un caso ambiguo.

graph = build_graph(alphabet)
graph = networkx.DiGraph(graph)
order = networkx.all_topological_sorts(graph)
order = list(order)
if len(order) > 1:
    order = "AMBIGUOUS"
else:
    if len(order[0]) < 1:
        order = "AMBIGUOUS"
    else:
        order = " ".join(order[0])

Software Developer based in Madrid. This is my personal blog. I am also on Twitter and LinkedIn.