Advent of Code 2024 - Queréis problemas? | Página 4

desu #91 11d

#90 ayer yo me tire también mas de 1h...

buscaba las esquinas, pero primero lo hacia mirando 2 vecinos, y tras dibujar en la tablet 1h vi que necesitaba 3 vecinos...

        let corner_checks = [
            (
                current_position + UP,
                current_position + RIGHT,
                current_position + UP_RIGHT,
            ),
            (
                current_position + UP,
                current_position + LEFT,
                current_position + UP_LEFT,
            ),
            (
                current_position + DOWN,
                current_position + RIGHT,
                current_position + DOWN_RIGHT,
            ),
            (
                current_position + DOWN,
                current_position + LEFT,
                current_position + DOWN_LEFT,
            ),
        ];

    for (n1, n2, diagonal) in corner_checks {
        let n1_match = input.get(n1).map_or(false, |v| *v == value);
        let n2_match = input.get(n2).map_or(false, |v| *v == value);
        let diagonal_match = input.get(diagonal).map_or(false, |v| *v == value);

        if (!n1_match && !n2_match) || (n1_match && n2_match && !diagonal_match) {
            corners += 1;
        }
    }

el de hoy... a ver que tal, enunciado largo

hoy un truquito que aprendi de gente top, el input siempre esta estructurado... si es muy verboso y te da pereza parsear, como a mi hoy, cambialo, he quitado con el editor y ctrl+r todo el texto para solo dejar los numeros:

y ya... no queria parsear hoy jaja

1 1 respuesta

Flashk #92 11d

#91 es un buen truco ese! Personalmente, no me importa trastear con regex un poco (y así practico para no olvidar lo poco que sé), pero habría tardado menos de esa manera también...

desu #93 11d

yo hoy lo he resuelto de dos maneras, de la buena y... haciendo una busqueda, para practicar, total llevamos haciendo busquedas cada dia jaja, eso si la parte 2 no he sabido hacerla con busqueda.

y para la parte dos, he tenido que abrir la wikipedia y un par de tutoriales de mates que hace años que no tocaba esto jaja

Mandarino #94 11d

day13

pereza maxima parsear eso, mas que nada porque vienen en bloques de 3 lineas xD

la primera parte la hice a fuerza bruta probando todos los valores posibles de a y luego calculando b.

en la parte 2 pues ahi ya estaba forzado a sacar la libreta y resolver las 2 ecuaciones, pero lo hice en el IDE para hacerlo mas infumable xdd copypaste para que disfruteis de como aislo las variables:

(tx/ty = target x/y = prize x/y)

        # f1 = a * AX + b * BX = TX
        # f2 = a * AY + b * BY = TY
        # --- Aislo b en f2
        # b * BY = TY - a * AY
        # b = (TY - a * AY) / BY
        # --- Reemplazo b en f1
        # a * AX + BX * (TY - a * AY) / BY = TX
        # (a * BY * AX + BX * (TY - a * AY)) / BY = TX
        # (a * BY * AX + BX * TY - a * BX * AY) / BY = TX
        # TX * BY = a * (BY * AX - BX * AY) + BX * TY
        # ecuacion magnifica final:
        # a = (TX * BY - BX * TY) / (BY * AX - BX * AY)

si (TX * BY - BX * TY) es divisible por (BY * AX - BX * AY) entonces hay solución, si no no.
y ya tal

desu #95 11d

como curiosidad voy por el dia 13 de 2015... lo que tardo en hacer 1 ejercicio de 2024 en que me atasco (1-2h) hago 2-3 de 2015... son mucho mas directos en su mayoria y faciles de entender.

MartiONE #96 10d El reportero de guerra sonriente

Lo de la segunda parte de hoy que cojones es?

spoiler

1

Mandarino #97 10d

ostia que guapo el dia 14 , me ha encantado

dia 14 parte 1

dia 14 parte 2

1 respuesta

MartiONE #98 10d El reportero de guerra sonriente

#97

spoiler

2 respuestas

Mandarino #99 10d

#98 en el enunciado pone que y=0 va arriba y positivo es hacia abajo:

Positive x means the robot is moving to the right, and positive y means the robot is moving down

1 1 respuesta

Flashk #100 10d

#98

jajaja

day14

1 1 respuesta

MartiONE #101 10d El reportero de guerra sonriente

#99 #100 Sierto, al pintar la matriz la he pintado al reves, my bad!

1

Mandarino #102 9d

day15

desu #103 9d

Yo ya logre mi objetivo principal de este año que eran 10 dias seguidos ahora... hare lo que pueda.

Finde fuera, empieza la temporada de ski... se empiezan a acomular jaja Ire a mi ritmo, que me he propuesto hacerlos todos.

Learnings y comentarios, va hoy que tengo el dia libre sacare learnings:

spoiler

Mi codigo siempre se ejecuta con este patron:

#[test]
fn part1_test() {
    let input = parse(EXAMPLE);
    assert_eq!(part1(&input), 12);
}

Como hago para cambiar el tamaño de la grid? uso un flag de test?

const EXAMPLE: &str = "\
11 7
0,4 3,-3
6,3 -1,-3
10,3 -1,2
2,0 2,-1
0,0 1,3
3,0 -2,-2
7,6 -1,-3
3,0 -1,-2
9,3 2,3
7,3 -1,2
2,4 2,-3
9,5 -3,-3";

He modificado el ejemplo. Mucha mas facil meterle el tamaño de la grid asi. Aunque el flag de test seria la opción B que recomendaria.

El truco de modificar con regex/ctrl+replace el input para que todo sea espacios y comas ya lo he comentado.

iteradores y collectores

spoiler

este es un patron que en rust y funcionales, al tener type inference potente es muy PLACENTERO, pero recomiendo usar en todos lenguajes como Java o C#. En lugar de tener un constructor que acepta array/vectores, tener un RECOELCTOR, asi podemoste usar .Collect() como con List, ArrayList, Set, Map... etc

Todo contenedor, deberia tener un collect() en su diseño. De la misma forma deberia tener un iterador. Son complementarios. iterar y recolectar. tener construstores que aceptan array/vectores es mala practica, porque no permiten optimizar las alocaciones y te comes una copia.

pub fn parse(input: &str) -> Grid<char> {
    input.lines().map(|line| line.chars().collect()).collect()
}

En rust, cualquier cosa que sea un iterador, sobre cualquier generico, puedo hacer un .collect() y me hara mi grid. Es una API muy agradable con el type inference.

Defaults y genericos.

spoiler

Es importante cuando trabajamos con genericos tener algun default() y usar interfaces/traits que nos permitan copiar si son value types.

    let mut grid = Grid::new_with_size(height, width, Default::default());

    pub fn new_with_size(length: usize, width: usize, value: T) -> Self {
        Self {
            grid: vec![vec![value; width]; length],
            length,
            width,
        }
    }

Y asi inicializamos cosas genericas muhco mas facil y rapido, y sobretodo, si tenemos que hacerlo en un "stream" o en codigo declarativo, funcionara.

Iteradores 2.0 y recolectores 2.0:

spoiler

me da este error... quiero ahora crear un vector a partir de un "123,42" por ejemplo... podria hacer un FromStr, que me permite escribir parse(), o puedo hacer el collect(), o puedo tener ambos... xq a veces tienes una lista de numeros y otras un solo numero...

aqui la clave es que el sistema de tipado solo entiende de string, si implementamos un trait para string, o &str, no sabe nuestra funcion si nos entra "123,42" que es correcto, o nos pasa tres numeros "123,42,-24"... como mi vector es 2D, puedo hacer esta decision si quiero esta API.

error[E0277]: a value of type `Vector` cannot be built from an iterator over elements of type `&str`
    --> src/year2024/day14.rs:23:44
     |
23   |         let velocity = velocity.split(",").collect();
     |                                            ^^^^^^^ value of type `Vector` cannot be built from `std::iter::Iterator<Item=&str>`
     |
     = help: the trait `FromIterator<&str>` is not implemented for `Vector`

en este caso he decidio hacer un parse() mejor:

        let position: Vector = position.parse().unwrap();

resultado:

spoiler

bastante clean, idiomatico, composable, usando parse() collect() default() iteradores... blah blah.

pub fn parse(input: &str) -> (Grid<u16>, Vec<(Position, Velocity)>) {
    let mut line_iter = input.lines();
    let (width, height) = line_iter.next().unwrap().split_once(" ").unwrap();
    let width: usize = width.parse().unwrap();
    let height: usize = height.parse().unwrap();

let grid = Grid::new_with_size(height, width, Default::default());

let positions = line_iter
    .map(|line| line.split_once(" ").unwrap())
    .map(|(position, velocity)| {
        let position: Vector = position.parse().unwrap();
        let velocity: Vector = velocity.parse().unwrap();
        (position, velocity)
    })
    .collect();

(grid, positions)
}

1

Flashk #104 9d

day 15 WIP

1 respuesta

Mandarino #105 9d

#104 me pasó 100% lo mismo xd

1

Mandarino #106 8d

Hoy hasta la noche no creo ni que me de tiempo a mirar el enunciado :')

Mandarino #107 8d

day16

desu #108 7d

https://sailor.li/aocnds.html
Advent of Code on the Nintendo DS

jaja

2

Mandarino #109 7d

la parte2 de hoy si que se complica ... luego a la noche sigo

edit: Bueno pues la parte 2 de hoy no me ha salido

dia 17

Estaba yendo por un camino demasiado complicado y me ha agobiado al final y he acabado mirando como lo han solucionado otros. Creo que mi idea iba bien pero es bastante complicado programarla bien ...

En mi caso, el programa de mi input se puede ver como el siguiente pseudocodigo:

    b = a % 8
    b ^= 1
    c = a >> b
    b ^= 5 ^ c
    print(b % 8)  # output
    a >>= 3
    if a!= 0: goto 0 (repeat)

Basicamente:

Coges 3 bits de mas a la derecha de A
Sacas 3 bits entre los bits 0..7 de A
Haces unos XOR y lo sacas por el output

Mi idea era ejecutar los comandos "al reves". Por ejemplo si el primer output que queremos es "2" pues podriamos sacarlo de formas diferentes. Como los 3bits de "c" de la izquierda no sabemos que valores pueden tener, pruebo con todos los releantes (0 a 7) y sacamos, por ejemplo:

A = 101xxxx000
Significa que cualquier A=101xxxx000 (reemplaza x por 0 o 1, da lo mismo) nos dara el primer numero de output que queremos. Cada "c" distinto nos dara diferentes constraints de que valor tiene que haber en los bits a la izquierda.
Con las constraints que toquen, podemos "llamar recursivamente" a la misma función que busca A pasandole los constraints de "estos bits tienen que valer 101" e ir haciendo. La cosa es que me funciona para los 3 primeros digitos del programa pero luego ya no da nada bien, seguramente por algún fallo en los bitmask de constraints, pero es muy dificil debugarlo la verdad ... xd

tenia este codigo, pero como he dicho no funciona bien:

def finda(target_outs: tuple[int],
          mask_values: int = 0,
          mask_bits: int = 0,
          depth=0) -> tuple[bool, int]:
    if depth == 3:
        return True, mask_values & mask_bits
    target = target_outs[0]
    tab = "   " * depth
    print(f"{tab}Target = {target:03b}")
    print(f"{tab}MaskB = {mask_bits:010b}")
    print(f"{tab}MaskV = {mask_values:010b}")
    for c in range(8):
        bpad = target ^ 5 ^ c
        amask = c << bpad
        b = bpad ^ 1
        if bpad == 2 and c & 1 != b >> 2:
            continue
        elif bpad == 1 and c & 0b11 != b >> 1:
            continue
        elif bpad == 0 and c != b:
            continue
        if (amask | b) & mask_bits != mask_values:
            # Constraints do not match
            continue
        print(f"{tab}A={'.' * (10 - bpad - 3)}"
              f"{c:03b}{'x' * (bpad - 3)}[{b:03b}]")
        isok, sol = finda(
            target_outs[1:],
            mask_values=(mask_values | amask) >> 3,
            mask_bits=(mask_bits | (0b111 << bpad)) >> 3,
            depth=depth + 1
        )
        if isok:
            return True, (sol << 3) | b
    return False, 0

QuitCat #110 6d Gafe

Estoy teniendo un problema con el

dia 15 parte 2

Probando con el ejemplo, llego al mapa de la solución, las cajas están en su sitio
Pero algo que estoy haciendo mal en el conteo de la puntuación... me quedo bastante lejos del número que se busca
Solo por confirmar:

#############
##...[]....##
##.........##
#############

Esa caja solo puntua por 100 * 1 + 5 = 105, correcto?
O se calcula la puntuación para cada lado de la caja?
El resultado final tiene que ser 9xxx y me esta dando 4xxx... Luego reviso igualmente

2 respuestas

Mandarino #111 6d

#110

spoiler

1 respuesta

Flashk #112 6d

#110

day15 tip

1 respuesta

QuitCat #113 6d Gafe

#111 #112
Gracias

La confusión venía porque había malentendido el enunciado

spoiler

For these larger boxes, distances are measured from the edge of the map to the closest edge of the box in question

Daba por hecho que cada caja puntuaba a su extremo del mapa más cercano.
Por ej:

#############
##...[]....##
##.........##
##....[]...##
#############

en este caso pensaba que las dos cajas tendrían la misma puntuación, la de arriba mirando las distancias de top/left, y la de abajo mirando distancias de bottom/right

Ahora ya todo claro y nivel superado

1

Mandarino #114 5d

dia 18

Mandarino #115 5d

dia 19

Si se tiene practica con dynamic programming es facil.

Función que hice que calcula la parte2:

def possibilities(patterns, design):
    @cache
    def dp(i):
        if i == len(design):
            return 1
        ans = 0
        for pattern in patterns:
            n = len(pattern)
            if design[i:i+n] == pattern:
                ans += dp(i+n)
        return ans
    return dp(0)

optimización parte 2

Una optimización que he pensado es convertir los patterns en un Trie y asi solo probar los patterns que empiecen por ese color.
Por ejemplo, si los siguientes colores en el disseño son "brrw" pues tengo que mirar si tengo b, br, brr y brrw en mis patterns. El Trie hace esto fácil

Utilizando "for pattern in pattern" = 940ms
Utilizando Trie = 15ms

Codigo:

END = "$"

def make_trie(words):
    root = {}
    for word in words:
        node = root
        for c in word:
            node = node.setdefault(c, {})
        node[END] = ''
    return root


def possibilities_trie(trie, design):
    @cache
    def dp(i):
        if i == len(design):
            return 1
        ans = 0
        node = trie
        while node and i < len(design):
            node = node.get(design[i])
            i += 1
            if node and END in node:
                ans += dp(i)
        return ans
    return dp(0)

El trie de los patterns del enunciado seria:

{
  "r": {
    "$": "",
    "b": {
      "$": ""
    }
  },
  "w": {
    "r": {
      "$": ""
    }
  },
  "b": {
    "$": "",
    "w": {
      "u": {
        "$": ""
      }
    },
    "r": {
      "$": ""
    }
  },
  "g": {
    "$": "",
    "b": {
      "$": ""
    }
  }

Flashk #116 5d

day 19

Total que:

Parte1

Para la memoization he usado un map de String-Boolean y el algoritmo raro que he dicho antes:

public class LinenLayout {

private final List<String> patterns;
private final List<String> designs;

private final Map<String,Boolean> memo = new HashMap<>();

public LinenLayout(List<String> inputs) {
    patterns = Arrays.stream(inputs.getFirst().replace(StringUtils.SPACE, StringUtils.EMPTY).split(",")).toList();
    inputs.removeFirst();
    inputs.removeFirst();
    designs = inputs;
}

public int solveA() {
    int result = 0;
    for(String design : designs) {
        if(isPossible(design)) {
            result++;
        }
    }
    return result;
}

private boolean isPossible(String design){

    if(memo.containsKey(design)) {
        return memo.get(design);
    }

    if(StringUtils.EMPTY.equals(design)) {
        return true;
    }

    for(String pattern : patterns) {
        int index = design.indexOf(pattern);
        if(index != - 1) {
            String leftSide = design.substring(0, index);
            String rightSide = design.substring(index+pattern.length());

            memo.put(leftSide, isPossible(leftSide));
            memo.put(rightSide, isPossible(rightSide));

            if(memo.get(leftSide) && memo.get(rightSide)) {
                return true;
            }
        }
    }

    return false;
}

Parte1

1

Mandarino #117 4d

day 20

Otro de mapas. Inicialmente parecia más facil pero me ha gustado el reto.

Primero probé a hacer un dijkstra buscando el camino mas corto y luego repetir lo mismo por cada posible cheat. La forma en la que lo implementé lo hacia con la misma cola usando "(cost, cheated_at, (y,x))" (cheated_at=None para cuando aun no habia hecho cheat hasta ese punto). Me funcionaba bien para el ejemplo pero para el input era demasiado lento.
Sabia que tardaba porque, cuando por ejemplo hacia un cheat de A a B, el calculo de B a END lo estaba repitiendo siempre. Además, si de A a B iba hacia atrás entonces otro x2.

La realidad es que al repensarlo la solución era mucho mas facil:
1 - Buscar el camino de START a END sin cheats de nada, y guardarme el camino de puntos + el coste para llegar a cada punto.
2 - Por cada punto del camino legal, probar a hacer trampas desde ahi: Al saltar 2 casillas, el punto nuevo deberia estar en el camino original. Si el coste original en ese punto es mas grande que el coste actual + 2, entonces es un cheat bueno.

De esta forma la parte de hacer cheats es O(n) y super rapido

Parte 2:
La mayoria del tiempo la perdí intentando cambiar la parte de "cheating" de la parte1 e intentar enchufarle otro dijkstra para navegar por los "#" con distancia maxima 20. No me di cuenta que en esos "20 pasos" se podia pasar por multiples ".", osea que lo estaba haciendo mal ...
Al final lo que hice fue, iterar todos los puntos del camino legal y, por cada punto, mirar sus puntos vecinos a distancia 20 (y-20 a y+20, x-20 a x+20) y ya.
Perdi unos minutos porque no me di cuenta que (y-20 a y+20, x-20 a x+20) incluye puntos a mas de 20 de distancia.

Codigo (despues de limpiarlo xD)

def solve(rawinput):
    mat: dict[tuple[int, int], str]
    mat, start, end = read(rawinput)

# Find normal path
legal_path = [start]
legal_cost = {start: 0}
while (p := legal_path[-1]) != end:
    for p2 in neighbors4(*p):
        if p2 not in legal_cost and mat[p2] == ".":
            legal_path.append(p2)
            legal_cost[p2] = len(legal_path) - 1
print("Legal Cost =", legal_cost[start])

# Find cheats
for k in (2, 20):
    ans = 0
    for current_cost, (y, x) in enumerate(legal_path):
        for y2 in range(y - k, y + k + 1):
            for x2 in range(x - k, x + k + 1):
                p2 = (y2, x2)
                dist = abs(y - y2) + abs(x - x2)
                if dist > k or p2 not in legal_cost:
                    continue
                new_cost = current_cost + dist
                saved = legal_cost[p2] - new_cost
                if saved >= 100:
                    ans += 1
    print(f"max cheats={k:<2} -> {ans}")

optimización?

Por cierto, parece que la parte2 tenia un error en el enunciado y ya lo han corregido: https://www.reddit.com/r/adventofcode/comments/1hid65a/2024_day_20_part_2_how_to_interpret_weird_clause/

Flashk #118 4d

day 20

Hoy me ha gustado. Las parte 2 me ha obligado a refactorizar, pero he disfrutado del proceso.

Parte 1

No era muy rápido el algoritmo, y cuando vi la parte 2 me di cuenta enseguida de que no escalable ni a nivel de tiempos, ni a nivel de como calcular como atravesar los números. Así que cogí papel y boli y me puse a hacer un boceto de una nueva idea.

Parte 2

La idea es tal que así:
La distancia total desde un nodo de inicio S hasta un nodo final E que pasa por un atajo entre dos nodos A y B es la siguiente:
distance = d(S,A) + d(A,B) + d(B,E)

Donde:

d(S,A) lo puedo calcular con dijkstra.
d(B,E) lo puedo calcular después de aplicar dijkstra: d(B,E) = d(S,E) - d(S,B). En otras palabras, en cada nodo, además de guardar su distancia desde el inicio, he guardado su distancia hasta el final.
Finalmente, nos queda d(A,B). En realidad da igual como sea dicho movimiento, lo que importa es que la distancia de A a B es igual que la distancia manhattan entre ambos nodos. De tal forma que, independientemente del tiempo de cheat. Si empiezo en un nodo en posición (2,5) y acabo en un nodo en posición (3,8), entonces la distancia es abs(2-3) + abs(5-8) = 1 + 3 = 4

La única parte que me faltaba por encajar es como calcular los movimientos.
Me monté un doble bucle que dado un cheat time de n, me generase un listado de movimientos como Vector2 (esta es una clase que codifiqué hace un par de años y que me ayuda en tareas de sumas, restas y cálculos de distancias entre vectores). Antes de ponerme a lanzar ejecuciones sin ton ni son, como me parecía la parte más crítica del algoritmo, dediqué unos minutos a ver si me salían tantos movimientos como esperaba y a las posiciones que había calculado a mano.

Finalmente, junté todas las piezas. Por orden:

Inicializo el mapa y la lista de nodos del camino original.
Ejecuto dijkstra.
Para cada nodo parte del camino original, calculo su distancia hasta el final.
Genero los posibles movimientos para el cheat time indicado.
Para cada celda del camino original voy mirando todos los posibles movimientos.
5.1. Si es un movimiento válido (celda no vacía), calculo la distancia total: distance =
d(S,A) + d(A,B) + d(B,E)
5.2. Añado el resultado al mapa de resultados únicamente si el tiempo ahorrado es > 0. Podría haberlo optimizado un poco más para evitar calcular tiempos negativos (si, pueden salir si el movimiento de A a B se produce a un B que está más atrás en el camino) como para evitar añadir al mapa tiempos que no lleguen al umbral mínimo, pero creo que tampoco me iba a ahorrar mucho tiempo, ya que el cálculo igualmente ya estaba hecho.
Finalmente, filtro el mapa de resultados.

PD: dijkstra puede parecer un poco overkill ya que el camino óptimo es único y sin bifuraciones. En mi caso, más que usarlo para calcular un camino mínimo lo uso para poder calcular cuál es el coste de llegar a cualquier nodo. Esto se podría hacer perfectamente con un algoritmo BFS o incluso DFS, pero si ya tenemos el algoritmo de dijkstra a mano porque ha salido varias veces este año... why not use it?

Hoy me he tirado más tiempo haciendo cálculos en papel, leyendo bien el enunciado y pensando como resolver cada subproblema por separado que lo que luego me ha costado implementarlo en si. Es gratificante cuando las cuentas salen bien.