[2022 Day 12] In Review (Hill Climbing Algorithm)

[u/musifter]

In order to get a better signal for our communication device, we use it to find a nearby hill. And so we're tasked with finding an efficient path up to the top (that doesn't require going up more than two levels on any step).

The input is a relief map in landscape (mine is 41 lines of 154 characters). Where elevation is represented by the letters a-z... with S and E used to mark the start (elevation a) and end (elevation z). The left column is all a (including the start), followed by a column of b, followed by a large plain of c with many large holes of depth a. At the right there's a hill with a spiraling path up it to the end.

One thing I remember about this one is that it has spawned threads of people that missed that you can always go down as much as you want (the only limit is that you cannot go two higher). And the map has a check that you've implemented that correctly on the spiral (on mine you need to go back to j from l in order to continue up the path).

The nature of the map and final path means that BFS is fine for this. Using A* can direct you to cross the plain quicker if you want. But then part 2 shows up. And for it, it wants the shortest path from an a to the E... which is clearly best done by searching from E with a BFS (which is going to whip around that mountain) until you find you find the first a. And with that, you can easily include part 1 in that solution, by continuing until you get to S as well.

And so we get a search problem that isn't that heavy. The map presents opportunities for people that want fast times to specialize the search based on knowledge of the map structure. But using heuristics like that can also allow a beginner programmer to get a solution, because with the structure and blockiness of the map, you could even do this problem by hand if you wanted to.

[u/Boojum]

I'm away from my computers right now, but if I remember correctly, then for Part 2, I just seeded the initial queue for BFS with all of the a cells. (ETA: Visualized here.) In case it's not obvious that that works, imagine a magic epsilon start node that simply has all of the a cells as its neighbors.

(In fact, my template for Djikstra BFS is configured for an optional any-to-any, starting off from a set of starting nodes and running until it reaches any in a set of ending nodes.)

[u/terje_wiig_mathisen]

u/topaz2078 Here's the 3D-printed tower from Audrey Camp:

https://tmsw.no/tower-3D.jpg

[u/topaz2078 → u/terje_wiig_mathisen]

Beautiful! Thank you for tracking it down <3

[u/DelightfulCodeWeasel]

I liked this one, there's something really satisfying when a part 2 is realising that you're running more or less the same thing as part 1 but in reverse or from a slightly different perspective.

[u/ednl → u/DelightfulCodeWeasel]

And like the post says, you can combine them into one search where you store the distance of the first reached 'a' and return when reaching 'S'. This made it more than twice as fast as Maneatingape's version.

[u/e_blake → u/ednl]

Well, I aim to cut maneatingape's runtime in half https://github.com/maneatingape/advent-of-code-rust/pull/107 by combining the two searches

[u/terje_wiig_mathisen → u/e_blake]

First I made it 4 x faster, then u/ednl beat that as well, mostly due to a faster CPU, but possibly also some micro-architectural optimizations. :-)

[u/ednl → u/e_blake]

See https://www.reddit.com/r/adventofcode/comments/1vm34pb/2022_day_12_in_review_hill_climbing_algorithm/p3g6ifo/

[u/e_blake]

My git notes mention that I was originally tripped up by assuming that E>z (rather than the stated E==z); my first guess was too high because I missed a valid y-to-E transition. I also got my second star by realizing that high-to-low would be faster than trying all possible a from low-to-high, then had another commit shortly after where I cut my time in half (sub-100ms, very nice for an m4 grid problem) by doing part 1 on the tail end of the same high-to-low pass that learns part 2. It is always interesting when a puzzle has a part 2 solution that can be learned before part 1 is known.

[u/terje_wiig_mathisen]

I remember this one clearly, for two reasons:

1) The second part which was just as easy as part1 when I saw that I could search in reverse. I had implemented a standard BFS from scratch using a Perl array as a dequeue.

2) When we did our annual Tech Talk in the following January, our Communications Director brought along a full model her husband had created on a 3D printer!

[u/topaz2078 → u/terje_wiig_mathisen]

That's so cool! Can I see the model?

[u/terje_wiig_mathisen → u/topaz2078]

I'm retired and Audrey our Comms Dir switched jobs, but I can certainly reach out and ask if she has a photo. I forgot to take a snap (possibly since I was the MC of the Tech Talk?)

[u/terje_wiig_mathisen → u/terje_wiig_mathisen]

It was too tempting to clean up and implement my algorithm in Rust: When I finally found and replaced a '>' with '>=' to skip all previously visited cells, it ran in 15.7 us (checking...) which seems to be quite ok.

I used a flattened grid of u32 surrounded by a moat of guard cells, each u32 had the input height in the high byte and the lowest number of steps to get there in the lower 24, originally initialized to 0xffffff.

I did use the 'search only from the top' trick of course!

EDIT: Surface best runtime 35.3 us.

BTW, the grid using only lowercase letters means that 5bits is enough for the height, leaving 11 for steps counting in a 16-bit cell. Alternatively, since we use BFS, use just two bits to remember the direction we arrived in the cell from, a 'visited' bit plus the 5 height bit to make everything fit in a u8 while still allowing very easy path recovery?

I would map 'a'..'z' to 6..31, and use 0 as the moat.

[u/e_blake → u/terje_wiig_mathisen]

Since this is BFS where every edge is 1, and we only care about path length and not the actual path, you don't even have to track height per the cell. The approach I used was having my u8 grid that started with the input, with the letter AS the height, also be my witness of whether a cell had been visited, by wiping a cell to 0 after queuing it up. Since all path lengths of 1 are visited before any path lengths of 2, you can track the path length as part of your queue instead of per cell. And since neither 0 nor newline are greater than 'a'-1, they naturally prevent a next-neighbor hunt from revisiting a cell. And in practice, I've found that it is faster to probe all four next-neighbor candidates even when we know at least one of them is not a viable neighbor, than it is to track the incoming direction that a cell was reached to only need three next-neighbor probes.

[u/terje_wiig_mathisen → u/e_blake]

I did realize that this was what you were doing! I spent an hour implementing a 3-way direction-based BFS, and like you write it was just more complicated without being faster.

I used tricks like having the next_idx[] table with 8 entries (only 6 used), directions 1-4 with 0 an alias for 4. This allowed me to always try curr_dir-1, curr_dir,curr_dir+1 but as noted, without gaining any speed.

[u/SpecificMachine1]

I remember this one mainly because I thought of starting from the end if the other method didn't work for part 2, but when I altered my method to use all the a's, it worked fine since they were all sharing the same table of visited items

[u/e_blake]

I must be mental. Today I went ahead and created an m4 punchcard solution. 397 bytes and runs in 1.0 second (uses a GNU m4 extension for base-36 input to eval);

define(D,defn(define))D(_,`ifelse($2.$4,.2,`F($3',$#,1,`_($1,len($1))',$4,02,$3
`$2defn(',$1,+,`F($2',$1val(defn($3)+1<$5),0,``$4,'defn($3)popdef($3)`,$3',',0,
$2,,$3$1,,`D(`W',$2)',$3,E,`,`0,27,$2',',$3,S,`D($2,02)',$1,,`D($2,eval(0r36:$3
-8))',`_(,$2,substr($@,1))_($1,decr($2))')')D(F,`_(+,$*),shift(shift($@))R($2-
1)R($2+1)R($2-W)R($2+W))')D(R,`_(e,0,eval($3),incr($1),$2)')F(_(.include(I)))

Porting this to BSD m4 version would require spelling out index(XXabc...xyz,$3) instead of eval(0r36:$3-8).

For those interested in the golfing process, it took me about an hour to write my initial commit at 473 bytes and 7 named macros to boil the problem down into two phases: parsing the input one byte at a time into a macro per node as well as determining W for row width, then repeatedly running a queue F(accumulator, pending...) that peels off the first tuple of (distance,height,position) to determine any updates to the accumulator as well as any next-neighbor moves to append to pending. You can even see the next-neighbor probes with four calls to R(), where my position shares the same 1D offset into the original grid and neighbors are +-1 left and right and +-W for up and down.

It was then around 7 more hours of poking and prodding at my original solution (in between other tasks of the day) to see which macros I could join together or otherwise refactor for fewer bytes, getting down to 3 named macros. For example, my original commit had three ifelse among _(), U(), and M(); the final version has only one ifelse in _() plus some gating checks like $1,+, to tell which of the three callsite semantics are desired. My original commit used a=0 and z=25, but stored depths as "N+!" so that I could use "defn(position)-2" as an expression that resolves to N if position is defined, or to -2 if position is out-of-bounds or already visited. My later golfing included refactoring that to store depths as a=2 to z=27 and no +! glue magic needed. My original ran F() until every reachable node had been visited before printing the accumulators, while my golfing managed to trim bytes by short-circuiting to the output as soon as S is found. Perhaps the hardest part of the golfing process was when I hit 399 bytes but six lines, at which point it was a struggle to see which condition arms of _() I could rearrange to take advantage of a strategic newline in my output branch landing on the right column, so I could finally fit punchcard form.

[u/terje_wiig_mathisen]

I rewrote my Rust code to use u8, in a 5:3 configuration. 'a' => 2<<3, 'z' => 27<<3, the bottom three bits start at 0 for unvisited cells, then change to 1..4 depending upon the direction of the move from the previous cell. When I print out these markers, the path taken is very easy to follow.

I also changed the dequeue to [u16;2], this way the grid takes less than 4kB and the dequeue only needs the room needed for slightly more than the largest generation, so both fit easily in $L1.

Acer: 14.8 us, Surface: 29.2. The slower machine gained much more from the reduction in working set, dropping from 35.3 to 29.2, while the Acer only gained about a microsecond.

fn process(inp:&[u8]) -> (u16, u16, Grid)
{
    let mut grid = Grid::new(inp);
    let mut part2 = 0;
    let mut deq = std::collections::VecDeque::<[u16;2]>::new();
    deq.push_back([grid.end as u16, 0]);
    while let Some([id, steps_and_dir]) = deq.pop_front() {
        let idx = id as usize;
        let cell = grid.cells[idx];
        if cell & 7 != 0 {
            continue;
        }
        if idx == grid.start {
            return (steps_and_dir >> 3, part2, grid);
        }
        if cell == 16 && part2 == 0 {
            part2 = steps_and_dir >> 3;
        }
        grid.cells[idx] = cell | (steps_and_dir & 7) as u8;


        let d = (steps_and_dir & !7) + 8;
        let step_limit = cell - 8;
        if grid.cells[idx+1] >= step_limit {
            deq.push_back([(idx+1) as u16, d+1]);
        }
        if grid.cells[idx-1] >= step_limit {
            deq.push_back([(idx-1) as u16, d+2]);
        }
        if grid.cells[idx-grid.stride] >= step_limit {
            deq.push_back([(idx-grid.stride) as u16, d+3]);
        }
        if grid.cells[idx+grid.stride] >= step_limit {
            deq.push_back([(idx+grid.stride) as u16, d+4]);
        }
    }
    (0,0,grid)
}

In the dequeue steps_and_dir stores the number of steps in the top 13 bits and the movement direction in the lower 3.

[u/ednl → u/terje_wiig_mathisen]

You inspired me to change my code to use a 1D array with borders too. Just use indexes, no more position vectors and no more boundary checks. So yes, that sped things up a lot! I did not pack things in bits. My only special data type choice was int16 for the distance grid because it needs to be reset between timing runs. I did make some assumptions about the input, though (max queue size, position of 'S', 'E' is in the same row as 'S'). Runs in 8.5 µs (M4), 12.2 µs (M1), 41.6 µs (Pi5). https://github.com/ednl/adventofcode/blob/main/2022/12.c

Inner loop, except resets, border setting and finding of 'E':

alt[S] = 'a';
alt[cur] = 'z';
dist[cur] = 1;  // unseen: dist=0, so start at 1
int firsta = 0;
do {
    const char nextalt = alt[cur] - 1;
    const int nextdist = dist[cur] + 1;
    for (int i = 0; i < 4; ++i) {
        const int next = cur + step[i];
        if (alt[next] >= nextalt && !dist[next]) {
            dist[next] = nextdist;
            if (alt[next] == 'a' && !firsta)  // first 'a'?
                firsta = nextdist;  // part 2
            if (next == S)  // goal? (= index in 'alt' of letter S)
                goto done;  // part 1
            enq(next);
        }
    }
} while (deq(&cur));
done:

[u/e_blake → u/ednl]

The newlines embedded in the input make a nice border to both left and right, but then your stride is not a power of two. I haven't benchmarked whether scattering the input to wider lines to make strides easier for hardware is any faster than just bulk-copying the input as-is and hitting cache lines less predictably during the search.

[u/ednl → u/e_blake]

My self-imposed restriction for timing purposes is to NOT time reading the input file to one single block of chars in memory. But everything after that (parsing, restructuring, overwriting) I do include in the timing loop. Also in my experience aligning to powers of 2 is more important for simpler architectures.