Advent of Code 2024 - Queréis problemas?

La parte 1 primero la hice a lo guarro ya que la palabra "XMAS" es lo suficientemente corta como para examinar letra a letra en las cuatro direcciones para la parte de las diagonales al menos.

Luego ya por la tarde lo he cambiado por un stream de direcciones para ir evaluando recursivamente la aparición de la palabra XMAS desde cada X.

La parte 2 la he dejado tal cuál de guarra estaba. XD
https://github.com/Flashky/advent-of-code-2024/blob/master/src/main/java/com/adventofcode/flashk/day04/CeresSearch.java

diria que el truco es en lugar de guardar el orden que te dan, guardar el contrario, asi en lugar de buscar que TODO se cumpla, buscas UNA excepcion. cuando termine lo re-factorizo a ver.

también se me ocurre para la parte 2 un two pointers, L, R que vaya moviendolos. una especie de bubble sort donde el orden es la precedencia.

edit:
part 1 y part 2 fuerza bruta a tope, me he guardado las precedencias como te dice pero mejor del reves seguro... o iterar las paginas del reves la validar
y luego part 2 he hecho un bubble sort jaja
me lo tendre q revisar y ver como simplificar

he quitado el bubble sort metiendo un custom sort by

use std::collections::HashMap;

pub fn part1(input: &str) -> i32 {
    let mut pages_order: HashMap<i32, Vec<i32>> = HashMap::new();

let mut result = 0;
let mut should_build_pages_order = true;
for line in input.lines() {
    if line.is_empty() {
        should_build_pages_order = false;
        continue;
    }

    if should_build_pages_order {
        build_pages_order(&mut pages_order, line);
    } else {
        if let Some(middle) = validate_pages_order(
            &pages_order,
            &line
                .split(',')
                .map(|s| s.parse::<i32>().unwrap())
                .collect::<Vec<_>>(),
        ) {
            result += middle;
        }
    }
}

result
}

pub fn build_pages_order(map: &mut HashMap<i32, Vec<i32>>, line: &str) {
    if let Some((previous, next)) = line.split_once('|') {
        if let (Ok(previous), Ok(next)) = (previous.parse::<i32>(), next.parse::<i32>()) {
            map.entry(previous).or_insert_with(Vec::new).push(next);
        }
    }
}

pub fn validate_pages_order(pages_order: &HashMap<i32, Vec<i32>>, pages: &[i32]) -> Option<i32> {
    for i in 0..pages.len() {
        let previous = pages[i];
        for &posterior in pages.iter().skip(i + 1) {
            if let Some(values) = pages_order.get(&posterior) {
                if values.contains(&previous) {
                    return None;
                }
            }
        }
    }
    Some(pages[pages.len() / 2])
}

pub fn part2(input: &str) -> i32 {
    let mut pages_order: HashMap<i32, Vec<i32>> = HashMap::new();

let mut result = 0;
let mut should_build_pages_order = true;
for line in input.lines() {
    if line.is_empty() {
        should_build_pages_order = false;
        continue;
    }

    if should_build_pages_order {
        build_pages_order(&mut pages_order, line);
    } else {
        let mut pages = line
            .split(',')
            .map(|s| s.parse::<i32>().unwrap())
            .collect::<Vec<_>>();
        if validate_pages_order(&pages_order, &pages).is_none() {
            let middle = fix_page_order(&pages_order, &mut pages);
            result += middle;
        }
    }
}

result
}

fn fix_page_order(pages_order: &HashMap<i32, Vec<i32>>, pages: &mut [i32]) -> i32 {
    pages.sort_by(|previous, posterior| {
        if let Some(values) = pages_order.get(posterior) {
            if values.contains(previous) {
                return std::cmp::Ordering::Less;
            }
        }
        std::cmp::Ordering::Greater
    });
    pages[pages.len() / 2]
}

Parece que todos los años tenemos un puzzle en el que hay que hacer algún tipo de ordenación.

Cuando se da el caso, uso Comparable o Comparator (según me interese más) para facilitar luego la ordenación usando el sort de stream.

public class PrintQueue {

private final Map<Integer, Set<Integer>> orderingRules = new HashMap<>();
private final List<Update> updates = new ArrayList<>();

public PrintQueue(List<String> inputs) {
    boolean isUpdate = false;
    for(String input : inputs) {
        if(StringUtils.isBlank(input)) {
            isUpdate = true;
            continue;
        }

        if(!isUpdate) {
            String[] keyValue = input.split("\\|");

            Integer key = Integer.valueOf(keyValue[0]);
            Integer value = Integer.valueOf(keyValue[1]);

            Set<Integer> values = orderingRules.getOrDefault(key, new HashSet<>());
            values.add(value);
            orderingRules.putIfAbsent(key, values);

        } else {
            updates.add(new Update(input));
        }
    }
}


public long solveA() {
    return updates.stream()
            .filter(update -> update.isOrdered(orderingRules))
            .mapToInt(Update::getMiddlePage)
            .sum();
}

public long solveB() {
    PageComparator comparator = new PageComparator(orderingRules);
    return updates.stream()
            .filter(update -> !update.isOrdered(orderingRules))
            .mapToInt(update -> update.order(comparator))
            .sum();
}

public class Update {

private List<Integer> pages;

@Getter
private int middlePage;

public Update(String input) {
    pages = Arrays.stream(input.split(",")).map(Integer::valueOf).toList();
    middlePage = pages.get(pages.size()/2);
}

public boolean isOrdered(Map<Integer, Set<Integer>> orderingRules) {

    boolean isOrdered = true;

    int i = 0;
    while(isOrdered && i < pages.size()) {
        int page = pages.get(i);
        isOrdered = isOrdered(i, orderingRules.getOrDefault(page, Collections.emptySet()));
        i++;
    }

    return isOrdered;
}

public int order(PageComparator comparator) {
    pages = pages.stream().sorted(comparator).toList();
    middlePage = pages.get(pages.size()/2);

    return middlePage;
}

private boolean isOrdered(int pageIndex, Set<Integer> orderingRules) {

    if(orderingRules.isEmpty()) {
        return true;
    }

    boolean isOrdered = true;
    int i = pageIndex-1;

    // Look back
    while(isOrdered && i >= 0) {
        int previousPage = pages.get(i);
        isOrdered = !orderingRules.contains(previousPage);
        i--;
    }

    return isOrdered;
}
}

public class PageComparator implements Comparator<Integer> {

private final Map<Integer, Set<Integer>> orderingRules;

public PageComparator(Map<Integer, Set<Integer>> orderingRules) {
    this.orderingRules = orderingRules;
}

@Override
public int compare(Integer o1, Integer o2) {

    // -1 si o1 precede a o2
    // 1 si o2 precede a o1
    // Resto de casos: 0

    Set<Integer> afterPagesO1 = orderingRules.getOrDefault(o1, Collections.emptySet());

    if(afterPagesO1.contains(o2)) {
        return -1;
    }

    Set<Integer> afterPagesO2 = orderingRules.getOrDefault(o2, Collections.emptySet());

    if(afterPagesO2.contains(o1)) {
        return 1;
    }

    return 0;
}

Al hacer la parte 2, mi primera intención ha sido usar una PriorityQueue inicializada con el Comparator que he implementado pero ¡oh! cuál ha sido mi sorpresa al ver que los elementos no salían ordenados al hacer esto:

    PriorityQueue<Integer> queue = new PriorityQueue<>(comparator);
    queue.addAll(pages);

    pages = queue.stream().toList();
    middlePage = pages.get(pages.size()/2);

    return middlePage;

Al parecer, al hacer el collect a list con un stream de una PriorityQueue, no se tiene en cuenta el comparator, así que probé a montar ese Comparator directamente en el sorted del stream:

    pages = pages.stream().sorted(comparator).toList();
    middlePage = pages.get(pages.size()/2);

    return middlePage;
}

Cuando ya saqué la solución, me puse a trastear de nuevo con la PriorityQueue. Descubrí que la única manera de sacar los elementos de una PriorityQueue que usa comparator es usando el método poll, con esto ya me daba un resultado correcto:

    PriorityQueue<Integer> queue = new PriorityQueue<>(comparator);
    queue.addAll(pages);

    pages = new ArrayList<>();
    while(!queue.isEmpty()) {
        pages.add(queue.poll());
    }

    middlePage = pages.get(pages.size()/2);

    return middlePage;
}

Usar la PriorityQueue no vale demasiado la pena, ya que se recorre la lista dos veces cada vez que hay que se invoca el método:

1. Una vez en el método addAll.
2. Una segunda vez al vaciar la cola con poll.

Rebuscando más info por internet encontré esto:
https://4comprehension.com/maintaining-priorityqueue-order-with-java-streams/

Básicamente mi solución final es similar a la primera parte de la solución 2 que plantean ahí, solo que yo lo hice directamente con la lista (para que volcar los datos en una queue si puedo usar directamente el comparator en la lista?).

En conclusión, cuidado con la ordenación de colas de prioridad y streams:

• Si usas Comparable, sorted() funcionará bien directamente con un stream de la PriorityQueue.
• Si usas Comparator, sorted() solo funcionará si le pasas el comparator como parámetro.
• Alternativa: usar poll(), ya sea con un bucle normal, o con Stream.generate(queue::poll).limit(queue.size()).toList() (el limit es importante, si no, petará la memoria heap).

Yo el único pruning que le he metido es que si el resultado parcial supera al resultado esperado, devuelva directamente false.
No mejora demasiado el tiempo de ejecución de esa manera. He probado con y sin pruning, y con pruning es de media... unos 0,3 segundos más rápido... xDDD

Es algo, pero no es un impacto significativo.

pub fn part2(input: &str) -> u64 {
    input
        .lines()
        .par_bridge() // esto ejecuta en un thread pool 
        .map(|line| line.parse::<Equation>().unwrap())
        .filter(Equation::has_solution_part2)
        .map(|equation| equation.result)
        .sum()
}

fn has_solution_part2(&self) -> bool {
    // state: (index, result)
    let mut stack = VecDeque::new();
    stack.push_back((1, self.elements[0]));
    while let Some((index, result)) = stack.pop_back() {
        if index + 1 > self.elements.len() {
            if result == self.result {
                return true;
            }
            continue;
        }
        if result > self.result {
            continue;
        }
        stack.push_back((index + 1, result + self.elements[index]));
        stack.push_back((index + 1, result * self.elements[index]));
        stack.push_back((
            index + 1,
            format!("{}{}", result, self.elements[index])
                .parse()
                .unwrap(),
        ));
    }
    false
}

Pensé que si un anti-node cae sobre una letra, teniamos que anular los anti-nodes generados por esa letra. Pero no, se sobre-escribe y ale.