[โ€“] 1 point 11 months ago

Rust

Seeing some of the other solutions in this thread, there are definitely simpler (and probably still faster) solutions possible, but I first sorted the bank by the highest batteries (keeping the index information) and then used a recursive greedy algorithm to find the largest battery that still follows the index order.

View on github

fn part1(input: String) {
    let mut sum = 0;
    'banks: for l in input.lines() {
        let mut sorted: Vec<(usize, u32)> = l
            .chars()
            .map(|c| c.to_digit(10).unwrap())
            .enumerate()
            .collect();
        sorted.sort_by(|(_, a), (_, b)| a.cmp(b).reverse());
        for (idx, first) in &sorted {
            for (id2, second) in &sorted {
                if id2 > idx {
                    sum += first * 10 + second;
                    continue 'banks;
                }
            }
        }
    }
    println!("{sum}");
}

// Recursive implementation of greedy algorithm.
// Returns Vec of length 12 if a result was found, guaranteed to be optimal.
// If there is no solution with the input, a shorter Vec is returned.
fn recursive(bank: &[(usize, u32)], mut cur: Vec<(usize, u32)>) -> Vec<(usize, u32)> {
    let pos = cur.last().unwrap().0;
    for &(idx, e) in bank.iter().filter(|(idx, _)| *idx > pos) {
        cur.push((idx, e));
        if cur.len() == 12 {
            // Recursion anchor: We have filled all 12 spots and therefore found
            // the best solution
            return cur;
        }
        // Recurse
        cur = recursive(bank, cur);
        if cur.len() == 12 {
            // Result found
            return cur;
        }
        // Nothing found, try next in this position
        cur.pop();
    }
    // Unsuccessful search with given inputs
    cur
}

fn part2(input: String) {
    let mut sum = 0;
    'banks: for l in input.lines() {
        let mut sorted: Vec<(usize, u32)> = l
            .chars()
            .map(|c| c.to_digit(10).unwrap())
            .enumerate()
            .collect();
        sorted.sort_by(|(_, a), (_, b)| a.cmp(b).reverse());
        let mut cur: Vec<(usize, u32)> = Vec::with_capacity(12);
        for &(idx, first) in &sorted {
            cur.push((idx, first));
            cur = recursive(&sorted, cur);
            if cur.len() == 12 {
                let num = cur.iter().fold(0u64, |acc, e| acc * 10 + e.1 as u64);
                sum += num;
                continue 'banks;
            }
            cur.pop();
        }
    }
    println!("{sum}");
}

util::aoc_main!();
  • source
  • [โ€“] 2 points 11 months ago

    Rust

    View on github

    I feared that this required some complicated maths to quickly figure out the next "invalid" number, but the total number of IDs to check was only about 2 million, so brute force it is.

    use std::ops::RangeInclusive;
    
    fn parse_input(input: &str) -> Vec<RangeInclusive<u64>> {
        input
            .trim()
            .split(',')
            .map(|r| {
                let (a, b) = r.split_once('-').unwrap();
                RangeInclusive::new(a.parse().unwrap(), b.parse().unwrap())
            })
            .collect()
    }
    
    fn part1(input: String) {
        let ranges = parse_input(&input);
        let mut sum = 0;
        for e in ranges.into_iter().flatten() {
            let width = e.ilog10() + 1;
            if width % 2 == 0 {
                let top = 10u64.pow(width / 2);
                if e / top == e % top {
                    sum += e;
                }
            }
        }
        println!("{sum}");
    }
    
    fn part2(input: String) {
        let ranges = parse_input(&input);
        let mut sum = 0;
        'nums: for e in ranges.into_iter().flatten() {
            let width = e.ilog10() + 1;
            for rep in 2..=width {
                if width % rep == 0 {
                    let top = 10u64.pow(width / rep);
                    let mut a = e;
                    let lowest = a % top;
                    let mut invalid = true;
                    while a > top {
                        a /= top;
                        if a % top != lowest {
                            invalid = false;
                            break;
                        }
                    }
                    if invalid {
                        sum += e;
                        // Don't check other numbers of repetitions
                        continue 'nums;
                    }
                }
            }
        }
        println!("{sum}");
    }
    
    util::aoc_main!();
    
  • source
  • [โ€“] 5 points 11 months ago (1 child)

    Nice solution. Just a little Rust tip if you don't mind: In this case you can avoid cloning the input Vec in the loops by instead looping over references into the list with for n in self.input.iter() or simpler for n in &self.input. The only difference is that n will be of type &i64 instead of i64.

  • source
  • parent
  • context
  • [โ€“] 4 points 11 months ago

    Rust

    Almost missed, that "the dial starts by pointing at 50".

    View on github

    const N: i32 = 100;
    
    fn parse_line(l: &str) -> (i32, i32) {
        let dir = match l.chars().next().unwrap() {
            'L' => -1,
            'R' => 1,
            _ => panic!(),
        };
        let dist = l[1..].parse::<i32>().unwrap();
        (dir, dist)
    }
    
    fn part1(input: String) {
        let mut pos = 50;
        let mut count0 = 0;
        for l in input.lines() {
            let (dir, dist) = parse_line(l);
            pos = (pos + dir * dist) % N;
            if pos == 0 {
                count0 += 1;
            }
        }
        println!("{count0}");
    }
    
    fn part2(input: String) {
        let mut pos = 50;
        let mut count0 = 0;
        for l in input.lines() {
            let (dir, dist) = parse_line(l);
            if dir == 1 {
                count0 += (pos + dist) / N;
            } else {
                count0 += ((N - pos) % N + dist) / N;
            }
            pos = (pos + dir * dist).rem_euclid(N);
        }
        println!("{count0}");
    }
    
    util::aoc_main!();
    
  • source
  • [โ€“] 13 points 11 months ago (2 children)

    The practical answer is: you drive as far as you legally can.

    As a disclaimer, pictured here are the Himalayas, which are at a completely different scale to where I've been, but in my experience there are typically parking spaces/bus stops at the end of public roads. At this point you leave the built up infrastructure and enter nature, and these are often located in a place where the flatter valley ends and a steeper ascent begins. In many cases there are smaller private roads further up to service more remote cabins or farmsteads. Sometimes there are even taxi services that drive you further along using private roads, which can be seen as not fully scaling the mountain yourself. Generally, the closest public parking is considered the starting point and most people will therefore start at the same spot.

  • source
  • parent
  • context
  • [โ€“] 5 points 1 year ago (3 children)

    Did an oopsie. I never realized that after upgrading the OS, my certbot renew service to renew the HTTPS certificate always failed. So now I had an expired certificate. At least it was an easy fix by reinstalling certbot.

  • source
  • view more: โ€น prev next โ€บ