Advent of Code, día 19

Validando mensajes: a veces hay que reformular el problema para que se pueda resolver

Parte 1

En esta primera parte, he optado por convertir las reglas de la entrada a una regex que me permita validar los mensajes.

El detalle importante del enunciado era que no había bucles en las reglas, así que podíamos construir la regex recorriendo las reglas de forma recursiva sin preocuparnos de quedarnos atrapados en un bucle infinito.

El código:

def replace_regex(rules, start):
    regex = ''
    for child in rules[start].split():
        if child[0] + child[-1] == '""':
            regex += child[1]
        elif child == '|':
            regex += '|'
        else:
            child_regex = replace_regex(rules, int(child))
            if child_regex in 'ab':
                regex += child_regex
            else:
                regex += '(' + child_regex + ')'
    return regex

def solve(input):
    rules_section, messages = input.strip().split('\n\n')

    rules = {}
    for rule_line in rules_section.split('\n'):
        id, rule = rule_line.strip().split(': ')
        rules[int(id)] = rule

    regex = replace_regex(rules, 0)

    return sum(
        1 if re.fullmatch(regex, message) else 0 
        for message in messages.strip().split('\n')
    )

Para las reglas del ejemplo, la regex que se construye es esta:

a((aa|bb)(ab|ba)|(ab|ba)(aa|bb))b

que valida correctamente los mensajes.

Parte 2

Problema con truco. Las reglas que cambian hacen que las reglas tengan recursión infinita, por lo que ya no es viable construir la regex explícita de la misma manera.

Entonces… ¿qué hacemos? Ese año Eric está dando más pistas, y en esta ocasión nos deja dos detalles importantes:

• Una pista que contiene el enunciado:

Fortunately, many of the rules are unaffected by this change; it might help to start by looking at which rules always match the same set of values and how those rules (especially rules 42 and 31) are used by the new versions of rules 8 and 11.

(Remember, you only need to handle the rules you have; building a solution that could handle any hypothetical combination of rules would be significantly more difficult.)

• y por otro lado, el hecho de que las reglas de la entrada aparezcan desordenadas, me ha hecho pensar… “¿qué nos quieren esconder?”

Teniendo en cuenta estos dos detalles, me he puesto a mirar con “cariño” las reglas, empezando por la 0:

0: 8 11
8: 42 | 42 8
11: 42 31 | 42 11 31

La regla 0 se basa únicamente en las reglas 8 y 11 que son las que cambian… ¿casualidad?

La regla 8 me ha recordado sospechosamente a la regla de la gramática que hice ayer en la parte 2 y he tratado de entender qué significaba. La regla 8 es equivalente a decir que queremos una o mas repeticiones de la regla 42… bueno, podríamos generar la regex de la regla 42 (que no es recursiva) y generar una regex de esta forma:

(regex_42)+

La regla 11 es más complicada: nos pide n repeticiones de la regla 42 seguida por el mismo número de repeticiones de la regla 31. Es decir, estas expresiones serían válidas:

42 31
42 42 31 31
42 42 42 31 31 31

pero estas no

42 31 31
42 42 31
42 42 42 31

Mientras exploraba opciones para resolver el problema, he leído esta parte del enunciado “looking at which rules always match the same set of values” y he pensado que sería una buena idea generar los posibles valores para las reglas 31 y 42.

Viendo que la variabilidad de las reglas está bastante acotada, me ha parecido factible. Esta función construye todos los posibles valores que cumplen una determinada regla:

def gen_values(rules, start):
    for part in rules[start].split(' | '):
        if part in 'ab':
            yield part
        else:
            children = part.split()
            if len(children) == 1:
                for value in gen_values(rules, int(children[0])):
                    yield value
            elif len(children) == 2:
                for v1 in gen_values(rules, int(children[0])):
                    for v2 in gen_values(rules, int(children[1])):
                        yield v1 + v2
            else:
                assert False, 'unexpected'

Llamando a gen_values(rules, 31) y gen_values(rules, 42) he visto dos cosas interesantes:

• todos los valores posibles son de la misma longitud (5 en el ejemplo, 8 en la entrada real)
• los valores posibles de la regla 31 son disjuntos de los valores posibles de la regla 42:

values_42 = set(generate_values(rules, 42))
values_31 = set(generate_values(rules, 31))
assert len(set.intersection(values_42, values_31)) == 0

Y ya que tenemos los valores, podemos simplificar las reglas 42 y 31 de esta forma:

regex_42 = '|'.join(set(generate_values(rules, 42)))
regex_31 = '|'.join(set(generate_values(rules, 31)))

Recapitulando:

• sabemos que la regla 8 nos pide 1 o más repeticiones de regex_42
• sabemos que la regla 11 nos pide n repeticiones de regex_42 seguidas de exactamente n repeticiones de regex_31
• si ponemos una regla a continuación de la otra, podemos reformular la regla 0: “queremos n repeticiones de regex_42 seguida de m repeticiones de regex_31 y n > m”

El código:

def solve(input):
    rules_section, messages = input.strip().split('\n\n')

    new_rules = [
        '8: 42 | 42 8',
        '11: 42 31 | 42 11 31',
    ]

    rules = {}
    for rule_line in rules_section.split('\n') + new_rules:
        id, rule = rule_line.strip().split(': ')
        rules[int(id)] = rule.replace('"', '')

    regex_42 = '|'.join(set(generate_values(rules, 42)))
    regex_31 = '|'.join(set(generate_values(rules, 31)))

    full_regex = f'(({regex_42})+)(({regex_31})+)'

    def is_valid(message, full_regex):
        matches = re.fullmatch(full_regex, message)
        return matches and \
            len(matches.group(1)) > len(matches.group(3))

    return sum(
        1 
        for message in messages.strip().split('\n') 
        if is_valid(message, full_regex)
    )

La expresiónlen(matches.group(1)) > len(matches.group(3)) merece ser analizada en detalle:

En Python no hay forma de saber cuántas repeticiones ha matcheado un capture group:

>>> re.fullmatch("(ab|ba)+", "abababba").groups()
('ba',)

Aunque se ha matcheado 4 veces, el group() correspondiente solo contiene el último match. Para saber cuántas repeticiones hemos encontrado, tenemos que encerrar todo en otro capture group:

>>> re.fullmatch("((ab|ba)+)", "abababba").groups()
('abababba', 'ba')

No sabemos cuantas repeticiones hemos matcheado pero si sabemos la longitud total de de todos los matches encontrados.

Los capture group se ordenan según la posición del paréntesis izquierdo: es decir el group(1) es ((ab|ba)+) y el group(2) es (ab|ba).

La regex con la que validamos los mensajes es esta:

full_regex = f'(({regex_42})+)(({regex_31})+)'

Donde {regex_42} y {regex_31} se reemplazan por todos los valores posibles separados por |.

Los grupos interesantes son el 1 y el 3 (contando paréntesis izquierdos)

Entonces, no podemos saber cuántas repeticiones del capture group hemos encontrado, pero si podemos saber la longitud de todos los capture groups repetidos… y como hemos visto que — en nuestro caso — todos los valores son de la misma longitud, entonces podemos asumir que si la longitud de la cadena que matchea ((regex_42)+) es mayor que la longitud de la cadena que matchea ((regex_31)+) es porque tenemos más repeticiones de la valores 42 que repeticiones de valores 31, que es exactamente lo que veníamos buscando.

Tenía miga… bastante miga.

El código completo aquí: https://github.com/jabadia/adventOfCode2020/tree/main/d19