Advent of Code 2021: Casi no llegamos edition

#include <stdio.h>
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <map>

void split(const std::string value,std::map<int,unsigned long> &list)
{
    std::stringstream ss(value);
    std::string item;  
    

while (std::getline(ss,item,','))
    list[std::stoi(item)] ++;
}

int main(int, char**) {
    std::ifstream myfile("/home/vicquecon/AoC/day_6/data.txt", std::ios_base::in);
    std::map<int,unsigned long> lanternfish_v { {0,0},{1,0},{2,0},{3,0},{4,0},{5,0},{6,0},{7,0},{8,0} };
    std::string input;
    while (myfile >> input)
    {
        split(input,lanternfish_v);
    }
    // END PARSE
    unsigned long new_fish = 0;
    for (int days = 0; days != 256; days ++)
    {
        for(int iter = 0; iter < 9; ++iter)
        {
            if (iter == 0)
            {
                new_fish = lanternfish_v[iter];
            }
            else
            {
                lanternfish_v[iter - 1] = lanternfish_v [iter];
            }
        }
        lanternfish_v[6] += new_fish;
        lanternfish_v[8] = new_fish;
    }

unsigned long sum = 0;
for(int iter = 0; iter < 9; ++iter)
{
        sum += lanternfish_v[iter];
}
std::cout << sum << std::endl;
}

import sys

nums = list(sorted(map(int, sys.stdin.readline().split(','))))

print(sum(abs(x - nums[len(nums) // 2]) for x in nums))

def pyramid(x):
  return x * (x + 1) // 2

pdiffs = [
  sum(pyramid(abs(x - y)) for x in nums)
  for y in range(min(nums), max(nums) + 1)
]
print(min(pdiffs))

Para la parte 1 me parece obvio que el punto óptimo coincide con alguno de los puntos de la entrada. Lo más razonable me parece probar con la mediana. Si para la mediana la suma es S puedes ver que moviendo el punto a cualquiera de los dos lados o bien mantienes S o le añades alguna unidad, pero en ningún caso lo decrementas.

Si tienes L elementos a la izquierda de la mediana y R a la derecha moverse a la izquierda la nueva suma es S' = S + R - L, al ser la mediana justamente L = R o como mucho se llevan una unidad de diferencia, que es lo mejor que puedes conseguir en cualquier caso. Moverse a la derecha es simétrico, así que no hace falta volver a explicarlo.

La parte 2 se puede hacer trivialmente probando cada posición entre [min, max], pero me gustaría pensar si se puede hacer mejor. Como mucho darse cuenta de que la fórmula de coste que te proponen es la de la suma de los n primeros numeros para no volverse loco calculando, pero ya.

La primera parte lo hice con la mediana pero las segunda parte ha caído un bucle a fuego buscando minimizar la función de coste.

lines_list = open('input.txt').read().splitlines()
patterns = [line.split('|')[0].split() for line in lines_list]
output = [line.split('|')[1].split() for line in lines_list]
print("Part 1", sum(sum(len(word) in [2,3,4,7] for word in line) for line in output))

def union(word1,word2):
    string=[char for char in word1]
    string.extend([char for char in word2 if char not in word1])
    return "".join(string)

def not_coinciding_wire(word1,word2):
    return "".join([char for char in word1 if char not in word2])

def sort_string(string):
    return "".join(sorted(string))

total = 0
for i, pattern in enumerate(patterns):
    one = [word for word in pattern if len(word) ==2][0]
    four = [word for word in pattern if len(word) == 4][0]
    seven = [word for word in pattern if len(word) == 3][0]
    eight = [word for word in pattern if len(word) == 7][0]
    nine = [word for word in pattern if len(word) == 6 and len(not_coinciding_wire(word,union(four,seven)))==1][0]
    five = [word for word in pattern if len(word) == 5 and len(not_coinciding_wire(nine,word))==1 and not len(not_coinciding_wire(one,word))==0][0]
    three = [word for word in pattern if len(word) == 5 and len(not_coinciding_wire(nine,word))==1 and len(not_coinciding_wire(one,word))==0][0]
    six = [word for word in pattern if len(word) == 6 and len(not_coinciding_wire(eight,union(word, one)))==0][0]
    zero = [word for word in pattern if len(word) == 6 and not word == nine and not word == six][0]
    two = [word for word in pattern if len(word) == 5 and not word == three and not word == five][0]
    matching_patterns = {sort_string(one) : "1",sort_string(two) : "2",sort_string(three) : "3",sort_string(four) : "4",sort_string(five) : "5",sort_string(six) : "6",sort_string(seven) : "7",sort_string(eight) : "8",sort_string(nine) : "9",sort_string(zero) : "0"}
    total += int("".join([matching_patterns[sort_string(out)] for out in output[i]]))
print("Part 2", total)

Entiendo que vas probando todas las permutaciones del pattern hasta que coincide con la configuración del ejemplo?

Sí xd, básicamente considero todas las funciones 'abcdefg' -> 'abcdefg' hasta que encuentro una que convierte todos los símbolos del input en símbolos que representan números. Hay 5040 funciones posibles, así que haces 5040 * num_lines iteraciones, que tampoco es muy descabellado.

Como detalle, tienes que ordenar las letras una vez mapeadas para poder hacer match bien.

Como no me apetecía jugar al Cluedo y sólo había 7 letras posibles lo he hecho a fuerza bruta, es decir:

Tú sabes que en realidad lo que han hecho ha sido traducir cada letra a otra completamente al azar, sin más. Es como si tuvieran un hashmap
a: d, b: a, c: d, ... y lo hubieran pasado por cada letra antes de enseñarte el input.

Si lo piensas, puedes representar todos los hashmaps posibles como las permutaciones que existen de abcdefg

abcdefg
cdbgaef

seria una que traduce a como c, b como d y así sucesivamente. Hay 7! = 5040 permutaciones posibles, así que es razonable probarlas todas. Sabes que has encontrado el hashmap bueno cuando eres capaz de traducir todas las palabras que te dan a palabras en el "idioma original" (que es lo que llamo "canon" en mi código).

Me refiero, es una solución de no querer pensar y abusar de que el problema da números muy pequeños que no evitan las fuerzas brutas, pero vuestras soluciones son mucho mejores desde luego.