Day 12: Hill Climbing Algorithm

=ARRAYFORMULA(BYROW(A1:A41,LAMBDA(x,IFERROR(VLOOKUP(SPLIT(REGEXREPLACE(REGEXREPLACE(x,"S|E","$"),"(.)","$1|"),"|"),{REGEXEXTRACT(ADDRESS(1,SEQUENCE(26)),"[A-Z]+"),SEQUENCE(26)},2,FALSE),"S"))))

lolicopters.

So I wrote my own breadth first search, which I tend to do a lot for AoC. No need for dijkstra or A* since each step of the path only adds 1 to its size/cost.

For part 2 I went even dumber and ran that on all starting points ('a' in the input). I wanted to add caching so that on subsequent searches if any point during the search is in the cache the solution is already there. This is definitely over-engineered since running all searches without the cache would have been OK anyway. Now, towards the end of that process, I realised... Holy crap. If I start at the end point -'E and stop searching as soon as I find the first 'a' - that's the answer for part 2. I needed some functions to get the appropriate neighbours for the reverse path and to check whether the search was complete - i.e, have we found an 'a' height marker and... oooh myyyyy G, I had myself the same generalised bfs as in my library.

(define (part-01 input)
  (define-values (heights start end) (parse-mountain input))
  (shortest-path start (higher+1 heights) (found? (set end))))

(define (parse-mountain input)
  (for*/fold ([heights (hash)]
              [start #f]
              [end #f])
             ([(l row) (in-indexed (in-list input))]
              [(c col) (in-indexed (in-string l))])
    (define p (list row col))
    (cond [(eq? #\S c) (values (hash-set heights p -1) p end)]
          [(eq? #\E c) (values (hash-set heights p 26) start p)]
          [else (values (hash-set heights p (- (char->integer c) (char->integer #\a)))
                        start end)])))

(define ((found? targets) p) (set-member? targets p))

(define (path-size steps end [size 0])
  ;; result is (sub1 size) because final iteration (@ start) sets
  ;; - next := steps[start] = #f
  ;; - size := size + 1
  (for/fold ([p end] [size size] #:result (sub1 size))
            ([i (in-naturals 1)] #:break (not p))
    (define next (hash-ref steps p))
    (values next (add1 size))))

(define (shortest-path start next stop?)
  (define (bfs)
    (cond [(queue-empty? Q) #f]
          [else
           (match-define (cons current from) (dequeue! Q))
           (cond [(stop? current) (hash-set! steps current from)
                                  (path-size steps current)]
                 [else (for ([next (in-list (next current))]
                             #:unless (hash-has-key? steps next))
                         (enqueue! Q (cons next current))
                         (hash-set! steps next current))
                       (bfs)])]))
  (define Q (make-queue))
  (enqueue! Q (cons start #f))
  (define steps (make-hash `((,start . #f))))
  (bfs))

(match-define (list N S E W)
  '((-1 0) (1 0) (0 1) (0 -1)))

(define ((higher+1 heights) p)
  (define h (hash-ref heights p))
  (for/list ([n (in-list (list (map + p N)
                               (map + p S)
                               (map + p E)
                               (map + p W)))]
             #:when (<= (- (hash-ref heights n +inf.0) h) 1))
    n))

Part 2 then become: search from 'E' and stop searching when you hit the first 'a'. Need to make a new function that only allow neighbours that are at most 1 lower. This makes part 2 unusually faster than part 1.

(define ((lower-1 heights) p)
  (define h (hash-ref heights p))
  (for/list ([n (in-list (list (map + p N)
                               (map + p S)
                               (map + p E)
                               (map + p W)))]
             #:when (<= (- h (hash-ref heights n -inf.0)) 1))
    n))

(define (part-02 input)
  (define-values (heights start end) (parse-mountain input))
  (define starts
    (for/set ([(k v) (in-hash heights)]
              #:when (zero? v)) k))
  (shortest-path end (lower-1 heights) (found? starts)))

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::{HashMap,HashSet};

use std::collections::BinaryHeap;
use std::cmp::Ordering;

use point2d::point2d::Point2D;

fn elevation(ch: char) -> i64 {
    match ch {
        'a'..='z' => { ch as i64 - 96 },
        'S'=> { 1  },
        'E'=> { 26 },
        _ => panic!("Unknown character: {}", ch),
    }
}

#[derive(PartialEq,Eq)]
struct Path {
    pt: Point2D,
    steps: i64,
}
impl Ord for Path {
    fn cmp(&self, other: &Self) -> Ordering {
        other.steps.cmp(&self.steps)
    }
}
impl PartialOrd for Path {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(other.steps.cmp(&self.steps))
    }
}

fn neighbor_addresses(pt: &Point2D) -> Vec<Point2D> {
    vec![Point2D { x: pt.x  , y: pt.y-1 },  // up
         Point2D { x: pt.x+1, y: pt.y   },  // right
         Point2D { x: pt.x  , y: pt.y+1 },  // down
         Point2D { x: pt.x-1, y: pt.y   }]  // left
}

fn shortest_path(map: &HashMap<Point2D,i64>, start: Point2D, end: Point2D) -> i64 {

    // Explore
    let mut visited: HashSet<Point2D> = HashSet::new();
    let mut heap: BinaryHeap<Path> = BinaryHeap::new();
    heap.push(Path{pt: start, steps: 0});
    while heap.len() > 0 {

        let path = heap.pop().unwrap();
        let (now,current_steps) = (path.pt, path.steps);
        let current_elevation = map.get(&now).unwrap();

        'neighbor_loop: for neighbor in neighbor_addresses(&now) {

            // Determine if visitable
            let new_elev = match map.get(&neighbor) {
                Some(e) => e,
                None => { continue 'neighbor_loop; }, // off the map
            };
            if new_elev > &(current_elevation + 1) { continue 'neighbor_loop; }

            // Check already visited
            if visited.get(&neighbor).is_some() { continue 'neighbor_loop; }
            visited.insert(neighbor);

            // New steps
            let new_steps = current_steps + 1;

            // Found the end
            if neighbor == end { return new_steps; }
            heap.push(Path{pt: neighbor, steps: new_steps});
        }
    }
    i64::MAX
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Build map
    let mut elev_map: HashMap<Point2D,i64> = HashMap::new();
    let mut start = Point2D {x: 0, y: 0 };
    let mut end = Point2D {x: 0, y: 0 };
    let mut possible_starts: Vec<Point2D> = Vec::new();
    for (y,line) in input.iter().enumerate() {
        for (x,elev_ch) in line.chars().enumerate() {
            let pt = Point2D { x: x as i64, y: y as i64 };
            elev_map.insert(pt, elevation(elev_ch));
            // Identify start and end points
            match elev_ch {
                'a' => possible_starts.push(pt),
                'S' => start = pt,
                'E' => end   = pt,
                _ => {},
            }
        }
    }

    // Part 1
    let part1 = shortest_path(&elev_map.clone(), start, end);
    println!("Part 1: {part1}"); // 380

    // Part 2
    let best = possible_starts.iter().map(|s| shortest_path(&elev_map,*s,end)).min().unwrap();
    println!("Part 2: {best}"); // 375

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

//#[macro_use]
//extern crate text_io;

pub mod point2d {
    use std::ops::{Add,AddAssign};
    use std::iter::Sum;
    extern crate num_complex;
    use num_complex::Complex;

    #[derive(Debug, Copy, Clone, Hash)]
    pub struct Point2D {
        pub x: i64,
        pub y: i64,
    }

    impl Point2D {
        pub fn new(x: i64, y: i64) -> Self {
            Self {
                x: x, y: y,
            }
        }
        pub fn zeros() -> Self {
            Self {
                x: 0, y: 0,
            }
        }
        pub fn from_complex(cmplx: Complex<i64>) -> Self {
            Self {
                x: cmplx.re, y: cmplx.im,
            }
        }
        pub fn as_complex(self) -> Complex<i64> {
            Complex::new(self.x, self.y)
        }
        pub fn as_tuple(self) -> (i64,i64) {
            (self.x, self.y)
        }
    }
    impl Add for Point2D {
        type Output = Self;
        fn add(self, other: Self) -> Self {
            Self {
                x: self.x + other.x,
                y: self.y + other.y,
            }
        }
    }
    impl AddAssign for Point2D {
        fn add_assign(&mut self, other: Self) {
            *self = Self {
                x: self.x + other.x,
                y: self.y + other.y,
            };
        }
    }
    impl PartialEq for Point2D {
        fn eq(&self, other: &Self) -> bool {
            self.x == other.x && self.y == other.y
        }
    }
    impl Eq for Point2D {}

    /*impl<'a> Sum<&'a Self> for Point2D {
        fn sum<I>(iter: I) -> Self
        where
            I: Iterator<Item = &'a Self>,
        {
            iter.fold(Self { x: 0, y: 0 }, |a, b| Self {
                x: a.x + b.x,
                y: a.y + b.y,
            })
        }
    }*/

    impl Sum for Point2D {
        fn sum<I>(iter: I) -> Self
        where
            I: Iterator<Item = Self>,
        {
            iter.fold(Self { x: 0, y: 0 }, |a, b| Self {
                x: a.x + b.x,
                y: a.y + b.y,
            })
        }
    }
}