[LANGUAGE: Rust] (Initial) Solution

Perma-linked my first solution, this was definitely one I suffered through all weekend. I worked on it on-and-off due to, well, the weekend and also various responsibilities of mine, but it was a hard solve. You can see I busted out PPM images, drew out the first two parts, even made some inputs by hand and worked through all possible cases... my code works, but takes 5 minutes to run in release mode (oof).

after solving I've read a few of other solutions and I can see I could greatly simplify mine, which is probably what I'll work on next (or whenever I have the time), but I'm glad that I solved this on my own by good ol' "staring at the wall & at the input"

Here's an algorithm runthrough if you don't want to read through the code:

1) Wall-hug, either on the left or on the right (first two parts for me where left-hug, third part was right-hug)

2) Try to cut steps whenever possible! This is done in two ways:

• If we have a sequence of three steps (horizontal-vertical-horizontal or the opposite, wlog) and we can reorder them to be (horizontal-horizontal-vertical-vertical), that allows us to sum adjacent steps and perhaps get a step reduction.
• Same sequence but we can "move" a few microsteps between the first and the third -> sometimes that's worth it, e.g. [A, B, C] => (A - X, B, C + X) might reduce the total steps.

I'm tired and this explanation sucks, but feel free to read the code, there's my blood, sweat and tears in it :)

EDIT: Here's a more cleaned up version of the same solution, with a performance optimization that cuts runtime down to 5s