Autor Tema: Advent of Code Problema 14

0 Usuarios y 1 Visitante están viendo este tema.

14 Diciembre, 2021, 09:45 am
Leído 507 veces

geómetracat

  • Moderador Global
  • Mensajes: 3,330
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Aquí traigo el problema de hoy. Si la primera parte se hace bien, la segunda es inmediata, solo cambiar un número. Pero si se implementa el algoritmo naïf la segunda parte no sale (el tiempo de ejecución explota). Dejo el enunciado (traducido con Google) y mi solución.

Parte 1:


--- Día 14: Polimerización extendida ---

Las increíbles presiones a esta profundidad están comenzando a ejercer presión sobre su submarino. El submarino tiene un equipo de polimerización que produciría materiales adecuados para reforzar el submarino, y las cuevas volcánicamente activas cercanas deberían incluso tener los elementos de entrada necesarios en cantidades suficientes.

El manual del submarino contiene instrucciones para encontrar la fórmula de polímero óptima; específicamente, ofrece una plantilla de polímero y una lista de reglas de inserción de pares (su entrada de rompecabezas). Solo necesita averiguar qué polímero resultaría después de repetir el proceso de inserción del par varias veces.

Por ejemplo:

NNCB

CH -> B
HH -> N
CB -> H
NH -> C
HB -> C
HC -> B
HN -> C
NN -> C
BH -> H
NC -> B
NB -> B
BN -> B
BB -> N
BC -> B
CC -> N
CN -> C

La primera línea es la plantilla de polímero : este es el punto de partida del proceso.

La siguiente sección define las reglas de inserción de pares . Una regla similar AB -> Csignifica que cuando los elementos Ay Bson inmediatamente adyacentes, el elemento Cdebe insertarse entre ellos. Todas estas inserciones ocurren simultáneamente.

Entonces, comenzando con la plantilla de polímero NNCB, el primer paso considera simultáneamente los tres pares:

    El primer par ( NN) coincide con la regla NN -> C, por lo que el elemento Cse inserta entre el primero Ny el segundo N.
    El segundo par ( NC) coincide con la regla NC -> B, por lo que el elemento Bse inserta entre Ny C.
    El tercer par ( CB) coincide con la regla CB -> H, por lo que el elemento Hse inserta entre Cy B.

Tenga en cuenta que estos pares se superponen: el segundo elemento de un par es el primer elemento del siguiente par. Además, debido a que todos los pares se consideran simultáneamente, los elementos insertados no se consideran parte de un par hasta el siguiente paso.

Después del primer paso de este proceso, el polímero se convierte en .NCNBCHB

Estos son los resultados de algunos pasos que utilizan las reglas anteriores:

Template:     NNCB
After step 1: NCNBCHB
After step 2: NBCCNBBBCBHCB
After step 3: NBBBCNCCNBBNBNBBCHBHHBCHB
After step 4: NBBNBNBBCCNBCNCCNBBNBBNBBBNBBNBBCBHCBHHNHCBBCBHCB

Este polímero crece rápidamente. Después del paso 5, tiene una longitud de 97; Después del paso 10, tiene una longitud de 3073. Después del paso 10, Bocurre 1749 veces, Cocurre 298 veces, Hocurre 161 veces y Nocurre 865 veces; tomando la cantidad del elemento más común ( B, 1749) y restando la cantidad del elemento menos común ( H, 161) se produce .1749 - 161 = 1588

Aplique 10 pasos de inserción de pares a la plantilla de polímero y encuentre los elementos más y menos comunes en el resultado. ¿Qué obtienes si tomas la cantidad del elemento más común y restas la cantidad del elemento menos común?



Parte 2:

El polímero resultante no es lo suficientemente fuerte como para reforzar el submarino. Deberá ejecutar más pasos del proceso de inserción de pares; un total de 40 pasos deberían hacerlo.

En el ejemplo anterior, el elemento más común es B (aparece 2192039569602 veces) y el elemento menos común es H (aparece 3849876073 veces); restar estos produce 2188189693529.

Aplique 40 pasos de inserción de pares a la plantilla de polímero y encuentre los elementos más y menos comunes en el resultado. ¿Qué obtienes si tomas la cantidad del elemento más común y restas la cantidad del elemento menos común?



Mi solución:
La segunda parte corre en 3ms.

Código: [Seleccionar]
with open("input14.txt") as f:
    inp = [x[:-1] for x in f.readlines()]

temp = inp[0]
pair_ins = {x[0]:x[1] for x in [y.split(' -> ') for y in inp[2:]]}

def split_pairs(temp):
    """From line returns a dict with counts of pairs"""
    pairs = dict()
    for i in range(len(temp)-1):
        if temp[i:i+2] in pairs.keys(): pairs[temp[i:i+2]] = pairs[temp[i:i+2]] + 1
        else: pairs[temp[i:i+2]] = 1
    return pairs

def insert(pairs, pair_ins):
    new_pairs = dict()
    for key in pairs:
        letter = pair_ins[key]
        for pair in [key[0]+letter, letter+key[1]]:
            if pair in new_pairs.keys():
                new_pairs[pair] += pairs[key]
            else:
                new_pairs[pair] = pairs[key]
    return new_pairs

def iter_insert(pairs, pair_ins, nsteps):
    for _ in range(nsteps):
        pairs = insert(pairs, pair_ins)
    return pairs

def count_letters(pairs, first, last):
    let_count = {x:0 for y in pairs for x in y}
    for key in pairs:
        for l in key:
            let_count[l] += pairs[key]
    let_count[first] += 1
    let_count[last] += 1
    for key in let_count:
        let_count[key] = let_count[key]//2
    return let_count

pairs = split_pairs(temp)

#Part 1

counts = count_letters(iter_insert(pairs, pair_ins, 10), temp[0], temp[-1])
print(max(counts.values()) - min(counts.values()))

#Part 2
counts = count_letters(iter_insert(pairs, pair_ins, 40), temp[0], temp[-1])
print(max(counts.values()) - min(counts.values()))
La ecuación más bonita de las matemáticas: \( d^2=0 \)