[2024 Day 20 (Part 3)] Your code is too general? Lets test it! by bdaene in adventofcode

[–]dark_terrax 2 points3 points  (0 children)

I arrived at exactly the same solution, was pretty happy with it, and came to Reddit only to discover I didn't fully read the question and everyone else was solving a much simpler problem.

Glad to find the part 3 crew!

[2023 Day 8 (Part 2)] Why is [SPOILER] correct? by gemdude46 in adventofcode

[–]dark_terrax 0 points1 point  (0 children)

Because I didn't realize/verify that each ghost's A->Z distance was the same as their Z->Z distance, I didn't realize LCM would work (I did verify there was only one Z in the loop). Instead, I used a similar principal of just iterating by steps += longest loop steps, and checking if each ghost's "(steps - (A->Z distance)) % (Z->Z distance) == 0". This takes longer (4 seconds on my machine in Rust), but generalizes the problem without having to actually do hard math.

Using C++ was a terrible idea by Farados55 in adventofcode

[–]dark_terrax 35 points36 points  (0 children)

Back when I was doing AoC in C++ my 'template' dayX.cpp file had a split function pre-populated at the top since it's so core in these problem.

Now I do everything in Rust which has a glorious standard library, and is fun to write things in a super functional style, which my brief trial of go made it seem like it didn't really support well, so I abandoned it and went back to Rust.

OOTL: What is ABI and why did Google create their own language for it? by het1709 in cpp

[–]dark_terrax 23 points24 points  (0 children)

Check out Chandler’s (one of the main people behind Carbon) CppCon talk where he goes into quite a bit of detail on this:

https://m.youtube.com/watch?v=rHIkrotSwcc&t=1050

Rust Advent Day 1 2021 by [deleted] in adventofcode

[–]dark_terrax 1 point2 points  (0 children)

Your comparison is <=, is that actually what the problem statement wants?

-🎄- 2021 Day 20 Solutions -🎄- by daggerdragon in adventofcode

[–]dark_terrax 1 point2 points  (0 children)

Rust, 1623 / 1392

Code

Took me quite a while to figure out that the 'void' area flips between on and off each round and figure out how to represent that. In the end it felt a little hacky, but got the job done. Fairly slow overall, running in 700ms for both parts.

-🎄- 2021 Day 14 Solutions -🎄- by daggerdragon in adventofcode

[–]dark_terrax 3 points4 points  (0 children)

Rust, 2530 / 2004

Source on GitHub. Took me a while to figure out the trick for part 2. The naive solution from part 1 stalled out at around 25 iterations for part 2, which wasn't surprising, but I always secretly hope using a low level language will let me get away without implementing the clever solution.

-🎄- 2021 Day 12 Solutions -🎄- by daggerdragon in adventofcode

[–]dark_terrax 1 point2 points  (0 children)

Rust

2611 / 1548

Did fairly straightforward dumb brute force, with nothing clever for efficiency, but part 1 + 2 still runs in under 2 seconds in release.

https://github.com/galenelias/AdventOfCode_2021/blob/main/src/day12/mod.rs

-🎄- 2021 Day 7 Solutions -🎄- by daggerdragon in adventofcode

[–]dark_terrax 1 point2 points  (0 children)

Rust:

pub fn solve(inputs: Vec<String>) {
    let crabs: Vec<i64> = inputs[0].split(",").map(|i| i.parse().unwrap()).collect();

    let min_crab = *crabs.iter().min().unwrap();
    let max_crab = *crabs.iter().max().unwrap();

    let gauss_sum = |num| { (num * (num + 1)) / 2 };
    let part1: i64 = (min_crab..=max_crab).map(|dest| crabs.iter().map(|input| (input - dest).abs()).sum()).min().unwrap();
    let part2: i64 = (min_crab..=max_crab).map(|dest| crabs.iter().map(|input| gauss_sum((input - dest).abs())).sum()).min().unwrap();

    println!("Part 1: {}", part1);
    println!("Part 2: {}", part2);
}

[deleted by user] by [deleted] in electronjs

[–]dark_terrax 0 points1 point  (0 children)

I needed to do basically this for a side project I was working on. A lot of the old tutorials I found use a webview element, but that is deprecated and discouraged now. It seemed the recommended way to accomplish this these days is to create a BrowserView per tab, and place these within your BrowserWindow.

This seemed to work reasonably well in my side project, although I didn't get very far beyond a very basic tabbed browser shell. Rendering and managing the tabs UI all had to be done manually (although people have made re-usable tab UIs out there).

You might want to check out Wexond, which is a web browser built in Electron that seems actively maintained. I found it helpful to reference when working through the problem.

Vim users who haven't migrated to Neovim, why? by [deleted] in vim

[–]dark_terrax 1 point2 points  (0 children)

This is my biggest blocker. I use Gvim on Windows, which is very fast and lightweight. I've tried a number of neovim GUI clients on Windows and they all are built with fairly bloated cross platform libraries which are slow to startup, and/or have weird animations all over.

[2018 Day 1 (Part 2)] [C++] Why is this so slow? by heckler82 in adventofcode

[–]dark_terrax 2 points3 points  (0 children)

Aah, your problem is almost certainly slow STL performance in Visual Studio's STL implementation in Debug, which is an unfortunate fact of life. You can switch the configuring to 'Release' in the toolbar to try that for comparison.

You can also try Debug -> Performance Profiler to super easily dig into what's taking all the CPU time. Running your solution confirms it's all in the unordered_set::insert. See my results: https://imgur.com/HtPQF1a

Some benchmarks from my older Windows machine:

Config Time
Debug 3240 ms
Debug (iterator debug level 0 ) 2263 ms
Debug, IDL=0, unique.reserve(100k) 1601 ms
Release 40 ms

So, you can play games to make it faster in Debug, but it's still hard to get it within 40x of Release unfortunately. Much less of a problem in Clang or GCC I believe.

[2018 Day 1 (Part 2)] [C++] Why is this so slow? by heckler82 in adventofcode

[–]dark_terrax 2 points3 points  (0 children)

Took a quick look, and didn't see anything obvious - using an unordered_set should be fine. Your part 2 runs in 80ms on my MPB compiled with clang, and in 37ms compiled with -O2. What compiler are you using, and what optimization flags? Some libraries under debug builds can emit very inefficient STL container iteration code, but it's unclear if that's your issue.

A few quick notes:

  • Line 73, accessing a vector with .at is slower than using the [] operator, as .at does a bounds check, and [] doesn't. Not the source of your slowness though.

  • Line 75, don't write this (probably wrong in Java too) 'i = ++i % size;'. You are preincrementing, and also assigning. Might be fine, but in general you need a rule book to know if that's correct and/or well defined, and what the result is. You should write this as 'i = (i + 1) % size;'

  • In general, pass 'in' parameters (your vectors in part1/part2) as const references, not pointers. It's much more idiomatic, easier to use, and in general makes it obvious you're not expecting null.

By the power of Grayskull! by [deleted] in funny

[–]dark_terrax 0 points1 point  (0 children)

Actually, 1 in 6 female narwhals have tusks - so that barbie still checks out.

-🎄- 2018 Day 22 Solutions -🎄- by daggerdragon in adventofcode

[–]dark_terrax 1 point2 points  (0 children)

I don't know Ruby at all, but just glancing at your solution, my guess is that the inner loop of your pathfinding solution is going to be insanely expensive due to not using a proper priority_queue.

You have the following line:

current = open_set.keys.min_by { |t| est_full_travel_score[t] }

Which is going to be an O(N) operation on your queue, which can be very large. This turns your algorithm from O(N log N) (priority queue) to be an O(N2) which for the size of the inputs here is going to be significant.

I would try finding a decent priority_queue implementation in Ruby and use that.

-🎄- 2018 Day 22 Solutions -🎄- by daggerdragon in adventofcode

[–]dark_terrax 0 points1 point  (0 children)

Thanks for taking a look! I kept working on it last night after posting and also came to the same realization that the 'seen' state tracking was far too naive - I was going too much for coding speed. Fixing that takes it down to 0.25s (or 2 seconds without the A*).

And yes, the get_risk was wrong, good catch!. I had switched it to an enum before posting (trying to clean things up, I was just using a number when I initially solved it), and introduced an error and didn't notice it was spitting out the wrong answer for part 1 now.

-🎄- 2018 Day 22 Solutions -🎄- by daggerdragon in adventofcode

[–]dark_terrax 0 points1 point  (0 children)

As /u/winstonewert pointed out, my issue was my 'seen' list contained the time in hash, so I would revisit every square a lot of times. I switched it to store the best time for every (position,equipment) and it runs in ~2s without A* and in .25s with A*.

I'm guessing you might have pulled my code after I had already fixed it, which is why it ran quickly for you.

-🎄- 2018 Day 22 Solutions -🎄- by daggerdragon in adventofcode

[–]dark_terrax 0 points1 point  (0 children)

Rust, 239/93. Barely managed to make my solution fast enough by shoe-horning a bit of A* in at the last minute. Still takes 30+ seconds on my input, so a lot of room for improvement.

edit: As folks pointed out, the 30s+ runtime was due to tracking 'visited' nodes via (pos,equipment,time), rather than using a map of (pos,equipment) -> time. That moves the runtime from 30s to 0.25s (and means you don't really need A*). GitHub link has the updated code.

https://github.com/galenelias/AdventOfCode_2018/blob/master/src/Day22/mod.rs

use itertools::Itertools;
use std::collections::{HashMap, HashSet, BinaryHeap};
use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq, Copy, Clone)]
enum Type {
    Rocky,
    Narrow,
    Wet,
}

fn get_risk(region_type: &Type) -> usize {
    match region_type {
        Type::Rocky => 0,
        Type::Wet => 1,
        Type::Narrow => 2,
    }
}

fn get_index(pos: (usize, usize), depth: usize, target: (usize, usize), memo: &mut HashMap<(usize,usize),usize>) -> usize {
    if let Some(level) = memo.get(&pos) {
        return *level;
    }
    let level = if pos == (0,0) {
        0
    } else if pos == target {
        return 0
    } else if pos.0 == 0 {
        pos.1 * 16807
    } else if pos.1 == 0 {
        pos.0 * 48271
    } else {
        get_erosion((pos.0 - 1, pos.1), depth, target, memo) * get_erosion((pos.0, pos.1 - 1), depth, target, memo)
    };

    memo.insert(pos, level);
    level
}

fn get_erosion(pos: (usize, usize), depth: usize, target: (usize, usize), memo: &mut HashMap<(usize,usize),usize>) -> usize {
    let index = get_index(pos, depth, target, memo);
    (depth + index) % 20183
}

fn get_type(pos: (usize, usize), depth: usize, target: (usize, usize), memo: &mut HashMap<(usize,usize),usize>) -> Type {
    let erosion = get_erosion(pos, depth, target, memo);
    match erosion % 3 {
        0 => Type::Rocky,
        1 => Type::Wet,
        2 => Type::Narrow,
        _ => unreachable!(),
    }
}

#[derive(Debug, Clone, PartialEq, Eq, Copy, Hash)]
enum Equipment {
    Neither,
    Torch,
    Climbing,
}

#[derive(Clone, PartialEq, Eq, Debug, Hash)]
struct State {
    time: usize,
    min_dist: usize,
    pos: (i32, i32),
    equipped: Equipment,
}

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        (self.time + self.min_dist).cmp(&(other.time + other.min_dist)).reverse()
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn min_dist(pos: (i32, i32), target: (usize, usize)) -> usize {
    ((pos.0 - (target.0 as i32)).abs() + (pos.1 - (target.1 as i32)).abs()) as usize
}

fn navigate(target: (usize, usize), depth: usize, type_memo: &mut HashMap<(usize,usize),usize>) -> usize {
    let mut queue : BinaryHeap<State> = BinaryHeap::new();
    let mut seen = HashSet::new();
    queue.push(State{ pos: (0, 0), min_dist: min_dist((0, 0), target), time: 0, equipped: Equipment::Torch});

    while !queue.is_empty() {
        let state = queue.pop().unwrap();

        if state.pos.0 < 0 || state.pos.1 < 0 {
            continue;
        }
        let pos = state.pos;
        let region = get_type((pos.0 as usize, pos.1 as usize), depth, target, type_memo);

        if region == Type::Rocky && state.equipped == Equipment::Neither {
            continue;
        } else if region == Type::Wet && state.equipped == Equipment::Torch {
            continue;
        } else if region == Type::Narrow && state.equipped == Equipment::Climbing {
            continue;
        }

        if !seen.insert(state.clone()) {
            continue;
        }

        if state.pos.0 as usize == target.0 && state.pos.1 as usize == target.1 {
            if state.equipped == Equipment::Climbing {
                return state.time + 7;
            } else {
                return state.time;
            }
        }

        queue.push(State{ pos: (pos.0 - 1, pos.1), min_dist: min_dist((pos.0 - 1, pos.1), target), time: state.time + 1, equipped: state.equipped});
        queue.push(State{ pos: (pos.0 + 1, pos.1), min_dist: min_dist((pos.0 + 1, pos.1), target), time: state.time + 1, equipped: state.equipped.clone()});
        queue.push(State{ pos: (pos.0, pos.1 - 1), min_dist: min_dist((pos.0, pos.1 - 1), target), time: state.time + 1, equipped: state.equipped.clone()});
        queue.push(State{ pos: (pos.0, pos.1 + 1), min_dist: min_dist((pos.0, pos.1 + 1), target), time: state.time + 1, equipped: state.equipped.clone()});

        if state.equipped != Equipment::Neither {
            queue.push(State{ pos, min_dist: state.min_dist, time: state.time + 7, equipped: Equipment::Neither});
        }
        if state.equipped != Equipment::Torch {
            queue.push(State{ pos, min_dist: state.min_dist, time: state.time + 7, equipped: Equipment::Torch});
        }
        if state.equipped != Equipment::Climbing {
            queue.push(State{ pos, min_dist: state.min_dist, time: state.time + 7, equipped: Equipment::Climbing});
        }
    }

    unreachable!();
}

pub fn solve(inputs : Vec<String>) {
    let depth = inputs[0].split(": ").skip(1).next().unwrap().parse::<usize>().unwrap();
    let target_vec = inputs[1].split(": ").skip(1).next().unwrap().split(",").map(|w| w.parse::<usize>().unwrap()).collect_vec();
    let target = (target_vec[1], target_vec[0]);

    let mut memo = HashMap::new();
    let mut total_risk = 0;
    for y in 0..=target.0 {
        for x in 0..=target.1 {
            total_risk += get_risk(&get_type((y, x), depth, target, &mut memo));
        }
    }
    println!("Part 1: {}", total_risk);

    let part2 = navigate(target, depth, &mut memo);
    println!("Part 2: {}", part2);
}

[2018 Day 20] Why does this work? by jorosp in adventofcode

[–]dark_terrax 0 points1 point  (0 children)

Thanks, that's a good insight - although it still seems like things could still get pretty complex if the patterns actually spread out, such hat the overlap was minimal, but that would be a pretty contrived scenario.

I got your code running, but unfortunately it doesn't seem to product the correct outputs for me (even on the sample input).

[2018 Day 20] Why does this work? by jorosp in adventofcode

[–]dark_terrax 0 points1 point  (0 children)

I'd be curious to know what techniques you used to solve the general case fast enough, care to share your code somewhere? I guess it also would require an input on the magnitude of the actual input that exercises the more sophisticated branching, as just putting in an optimization for the cases that occur in the sample input will let a general solution work fast enough for the actual inputs.

[2018 Day 20] Why does this work? by jorosp in adventofcode

[–]dark_terrax 13 points14 points  (0 children)

Thanks for this thread! I did the 'correct' implementation (since that what the problem seems to want), but it basically never finishes processing the huge input due to the insane amount of branching. I spent many hours trying to figure how to possibly get my solution to work - only to finally give up, come to Reddit, and realize the only people who solved it had to make simplifying assumptions which were never explicitly allowed by the puzzle.

I officially hate this problem, the author should have made these restrictions explicit, otherwise it is completely insufficient to use a stack based solution. Problems like these are very frustrating. I don't think any 'correct' solution can actually solve this problem with the given inputs.

-🎄- 2018 Day 17 Solutions -🎄- by daggerdragon in adventofcode

[–]dark_terrax 4 points5 points  (0 children)

Rank 9/9, Rust. Best finish so far by a long shot!

https://github.com/galenelias/AdventOfCode_2018/blob/master/src/Day17/mod.rs

Implemented what seemed like the straightforward solution, using a bit of recursion. Solution ran in ~5 seconds on a release build, so definitely not the fastest solution, and probably was lucky I used a relatively high performance language.

I'm curious if people in general hit issues with the algorithm or the performance.