Tuenti Challenge 10: nivel 18

Hemos construido un nuevo servicio, y debido a la falta de coordinación entre dos equipos, cada uno necesita recibir ciertos datos en un formato distinto: Elements Separated by Commas (ESC) y List-Oriented Language with Multiple Advanced Options (LOLMAO).

Matters with Formatters, fue el último del Tuenti Challenge 10 al que llegué. Como la solución optimizada para el caso de submit se me quedó en el tintero, me propuse terminarla y aquí va el resultado. Puedes encontrar en mi repositorio de Github del concurso mi solución completa.

Dada una cadena válida en uno de los dos formatos, debemos calcular el número mínimo de cambios necesarios para hacerla válida en el otro. No nos importa lo que represente esta cadena, lo único que queremos es que la cadena resultante sea válida en ambos formatos.

Para que una cadena sea válida en formato ESC nos basta con que cada línea del texto contenga al menos dos elementos separados por una coma.

alfa,beta,gamma
,,
foo,bar
test,a[5],asdf

El formato LOLMAO es algo más restrictivo:

[[],foo,[[[,],[1,2],5,,],some0literal
with3multiple
lines]]

La cadena de entrada del problema puede ser un texto de hasta 400 caracteres en formato LOLMAO que debemos convertir a ESC, o un texto de hasta 4000 caracteres en formato ESC que debemos convertir a LOLMAO.

En caso de que no sea posible generar una cadena válida en ambos, debemos devolver IMPOSSIBLE. Viendo estas reglas es fácil deducir que toda cadena en ESC debe contener al menos una lista de dos elementos, y por tanto una coma. Para que una cadena con una coma sea válida en LOLMAO, deberá estar rodeada de corchetes. Así, la cadena más pequeña que es válida en ambos formatos es [,] y cualquier cadena menor será imposible.

Ejemplo de exploración de solución

El resto de casos debemos resolverlos explorando cambios en la cadena de entrada. Nos enfrentamos a un problema de programación dinámica, en el que partiendo de un estado inicial —la cadena de entrada— debemos alcanzar un estado final —la cadena válida— en el mínimo número de pasos.

A fin de simplificar las cadenas de entrada, voy a reemplazar cualquier símbolo de la siguiente forma:

def standarize(text):
    res = ''
    for char in text:
        if char in '[],':
            res += char
        elif char == '\n':
            res += 'N'
        else:
            res += 'O'
    return res

A continuación, podríamos representar los estados como cadenas modificadas pero esto permitiría que pudiéramos explorar estados inválidos. Una de las máximas para optimizar la exploración es escoger una representación de estados que permita representar el mínimo número de estados inválidos.

Si nos peleamos un rato con este problema, veremos que cualquier estado se puede reducir a cuatro valores:

  1. La posición en la cadena: inicialmente será cero, y cada modificación consistirá en alterar el valor del símbolo en esta posición y generar un nuevo estado cuya posición se incremente en uno. Un estado final será aquel cuya posición sea igual a la longitud de la cadena.
  2. La profundidad: como el formato LOLMAO permite anidar listas, cada vez que encontremos un símbolo [ en la cadena la profundidad aumentará en uno, y cada vez que encontremos un símbolo ] la profundidad se reducirá en uno. Inicialmente, la profundidad es cero.
  3. El último símbolo encontrado: inicialmente no estará definido, y vez que pasemos al siguiente estado, tendrá el valor del último símbolo que hemos usado. Nos será útil para evitar combinaciones inválidas como ]O, N[ o ][.
  4. Si ha habido una coma en esta línea: este valor comenzará siendo falso, siempre que lleguemos a una coma será verdadero, y cuando alcancemos una nueva línea volverá a ser falso. Nos servirá para cumplir la restricción de ESC de tener una coma por línea.

Como esta representación está muy reducida, algunas cadenas distintas se pueden representar mediante un mismo estado. Esto quiere decir que si guardamos en memoria los resultados de nuestra exploración, se reutilizarán con bastante frecuencia.

@lru_cache(None)
def changes(pos, depth, last_char, comma_since_newline):
    # TODO compute here the alternatives "alts" as a list of symbols
    res = min(
        (alt != _text[pos]) + changes(
            pos + 1,
            depth + (alt == '[') - (alt == ']'),
            alt,
            alt != 'N' and comma_since_newline or alt == ','
        )
        for alt in alts
    )
    return res

Mientras resolvía este problema descubrí ese decorador @lru_cache(size), que se puede usar en cualquier función para almacenar en memoria su resultado, de forma que la próxima vez que se llame a esa función con los mismos argumentos, su resultado no sea calculado de nuevo.

Ya sólo nos queda saber cuándo debemos generar como alternativa cada uno de los cinco símbolos posibles:

Con esta aproximación conseguimos resolver el caso de test con facilidad. Pero al llegar al caso de submit la cosa se complica. Algunas cadenas son excesivamente largas y no logramos resolverlas mediante este método. Pero aun nos queda un as bajo la manga.

Como sabemos que las cadenas que deben ser convertidas a LOLMAO tienen como máximo 400 caracteres, cualquier cadena más larga que nos llegue deberá ser convertida a formato ESC. Si encontramos una forma rápida de hacer esta conversión sin romper el formato LOLMAO no tendremos que lanzar el algoritmo de exploración.

En este caso, el truco es el siguiente: en primer lugar, cambiar si fuera necesario el primer símbolo por [ y el último por ]. A continuación, cada vez que lleguemos a un salto de línea que no ha tenido una coma en esa línea, reemplazaremos ese salto por una coma.

De esta forma lograremos reducir el problema rápidamente y todos los casos se resolverán sin problema. El único cambio que tuve que hacer fue aumentar la profundidad máxima de la pila de llamadas debido a mi implementación recursiva de la solución.

setrecursionlimit(10000)  # we need to go deeper

Y aquí acaba la serie sobre el Tuenti Challenge 10. Todavía quedan dos niveles que no llegué a resolver, aunque igual algún día me pongo a resolverlos. Puedes consultar además los niveles anteriores:

Sé el primero en comentar

Recibir un mail

🍪 ¿Cookies?

Esta web usa cookies para identificar qué contenido es interesante y escribir más contenido similar. Puedes obtener más información aquí.