Drop heuristic to improve runtime

[ahans]

This drops the heuristic, since using it is a net negative. Improves the runtime by ~30% on Intel Core i7-12900k.

[maneatingape]

Thanks for the PR!

That's an interesting result about the heuristic. On my input it results in a 15% speedup from eliminating branches.

Loop repetitions	Part One	Part Two
Heuristic	54784	72387
No heuristic	63926	85068

Would you mind checking if the speedup is from the structure of your input?

I modified the code to add a simple counter:

    let mut counter = 0;

    loop {
        while let Some((x, y, direction)) = todo[index % 100].pop() {
           <...snip...>

            counter += 1;

            // Check if we've reached the end.
            if x == width - 1 && y == height - 1 {
                println!("{counter}");
                return steps;
            }

[ahans]

Good to see those numbers. Also explains the runtime differences somewhat. I find it quite surprising that there are such differences in the inputs. This is the result I get:

Loop repetitions	Part One	Part Two
Heuristic	63452	145385
No Heuristic	68011	89913

So it looks like for my input the heuristic actually makes it a lot worse.

Anyway, I would find it reasonable for you to optimize for your input, so feel free to close the PR.

[maneatingape]

I'm curious what could cause such a difference. Let's leave the PR open for now until I can dig into it a little.

Visualizing the path taken may provide some insight.

[maneatingape]

Following up nine months later... 🙂

Implemented an animation visualizing the frontier in order to debug. With your input and the heuristic set as the Manhattan distance towards the bottom 2 * size - x - y, a second cheaper frontier occurs because a move up or left near the top left origin is cheaper. This causes double the work as two frontiers propagate towards the goal simultaneously

Tweaked the heuristic from 2 * size - x - y to (2 * size - x - y).min(size + size / 2). This "flattens" the heuristic in the top left quadrant, preferring all directions equally. This performs almost as well as the original and improves performance for your input.

Loop repetitions	Part One	Part Two
Heuristic	54784	72387
Modified Heuristic	55210	73286

[maneatingape]

Tweak heuristic to fix performance regression on some inputs. Thanks for flagging this!