Day 14: Regolith Reservoir

(match-define (list S SE SW) '((0 1) (1 1) (-1 1)))
(define (point+ x y) (map + x y))
(define START '(500 0))
(define (read-rock input)
  (let next-line ([lines input]
                  [rock (hash)])
    (cond [(null? lines) rock]
          [else (next-line (rest lines) (parse-rocks rock (integers (first lines))))])))

(define (parse-rocks rock rocks)
  (match rocks
    [(list* x/from x/to y/from y/to _)
     (parse-rocks (add-rock rock x/from x/to y/from y/to)
                  (drop rocks 2))]
    [(list _ _) rock]))

;; lol couldn't think of a neater way of dealing with horizontal and vertical
(define (add-rock rock x/from y/from x/to y/to)
  (define (horizontal)
    (for/fold ([rock rock])
              ([k (in-inclusive-range (min x/from x/to) (max x/from x/to))])
      (hash-set rock (list k y/from) "▓")))
  (define (vertical)
    (for/fold ([rock rock])
              ([k (in-inclusive-range (min y/from y/to)
                                      (max y/from y/to))])
      (hash-set rock (list x/from k) "▓")))
  (if (= y/from y/to) (horizontal) (vertical)))

Of course this is the refactored count-sand after completing part 2 as I didn't want the headache of dealing with the new conditions.

(define (part-01 input)
  (define rock (read-rock input))
  (define bottom (apply max (map second (hash-keys rock))))
  (count-sand rock START bottom 'void))

(define (count-sand rock u bottom floor? [sand 0])
  (define depth (second u))
  (cond [(and (eq? floor?  'void) (> depth bottom)) sand]
        [(and (eq? floor? 'floor) (hash-has-key? rock START)) sand]
        [else (case (dir rock bottom u floor?)
                [(blocked) (count-sand (hash-set rock u "░") START bottom floor? (add1 sand))]
                [(S)  (count-sand rock (point+ u S)  bottom floor? sand)]
                [(SE) (count-sand rock (point+ u SE) bottom floor? sand)]
                [(SW) (count-sand rock (point+ u SW) bottom floor? sand)]
                [else 'count-sand "HWAT ~a ~a ~a ~a" u bottom floor? sand])]))

(define (dir rock bottom u floor?)
  (cond [(and (eq? floor? 'floor) (= bottom (second u))) 'blocked]
        [(not (hash-has-key? rock (point+ u S)))   'S]
        [(not (hash-has-key? rock (point+ u SW))) 'SW]
        [(not (hash-has-key? rock (point+ u SE))) 'SE]
        [else 'blocked]))

Now the bottom is the floor, not the void. Why of course I dumbly added 2 to bottom.

(define (part-02 input)
  (define rock (read-rock input))
  (define bottom (apply max (map second (hash-keys rock))))
  (count-sand rock START (+ bottom 1) 'floor))

Attempt 1: ~55% elapsed time.
Mutatis Maledictis. I "caved" in and changed to a mutable hash table which is essentially a re-write. It forced me to make some (ugly) changes to the conditions, but at least both parts together run in under a second now. The beauty of mutable state and only building the data structure once (rather than once for each part) is that part 2 already has the sand in-place from part 1. I don't think the change in rules invalidates that and the results are the same so...

Since it's a pretty major change I'll link the new code here and just show the combined driver for both parts. I'm tempted to try a vector instead of a hash-table, but my knee isn't giving me any relief so that's it for today.

 (define rock (make-hash))
 (define deepest (set-rock! rock (file->lines "day14.input")))
 (list
  (count sand?
         (hash-values
          (drop-sand! rock (first START) (second START) deepest 'void)))
  (count sand?
         (hash-values
          (drop-sand! rock (first START) (second START) (add1 deepest) 'floor))))

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

use point2d::point2d::Point2D;

const ORIGIN_X: i64 = 500;
const ORIGIN_Y: i64 = 0;
const ORIGIN: Point2D = Point2D { x: ORIGIN_X, y: ORIGIN_Y };

enum MapType {
    Origin,
    Rock,
    Sand,
}

fn can_move(sand_map: &HashMap<Point2D,MapType>, pt: &Point2D) -> bool {
    match sand_map.get(&pt) {
        None => true,
        Some(_) => false,
    }
}

fn drop_sand(sand_map: &mut HashMap<Point2D,MapType>, abyss: i64, part1: bool) -> bool {

    let mut new_pt = Point2D { x: ORIGIN_X, y: ORIGIN_Y };
    loop {

        // Assess movements
        let try_down  = Point2D { x: new_pt.x,   y: new_pt.y+1 };
        let try_left  = Point2D { x: new_pt.x-1, y: new_pt.y+1 };
        let try_right = Point2D { x: new_pt.x+1, y: new_pt.y+1 };

        let can_down  = can_move(&sand_map, &try_down);
        let can_left  = can_move(&sand_map, &try_left);
        let can_right = can_move(&sand_map, &try_right);

        // Assign movements
        if can_down {
            new_pt = try_down;
            if part1 && new_pt.y + 1 == abyss { return false; } // Fell to the abyss
        } else if can_left {
            new_pt = try_left;
        } else if can_right {
            new_pt = try_right;
        } else {
            if !part1 && new_pt == ORIGIN { return false; } // Blocking origin
            sand_map.insert(new_pt,MapType::Sand);
            return true; // At rest
        }
    }
}

fn build_map(input: &Vec<String>) -> HashMap<Point2D,MapType> {
    let mut sand_map: HashMap<Point2D,MapType> = HashMap::new();
    let origin = Point2D { x: ORIGIN_X, y: ORIGIN_Y };
    sand_map.insert(origin, MapType::Origin);
    for line in input {
        let segments: Vec<_> = line.split("->").collect();
        for segment in segments.windows(2) {
            let p1: Vec<_> = segment[0].split(",").map(|v| v.trim().parse::<i64>().unwrap()).collect();
            let p2: Vec<_> = segment[1].split(",").map(|v| v.trim().parse::<i64>().unwrap()).collect();
            let (x1,y1) = (p1[0], p1[1]);
            let (x2,y2) = (p2[0], p2[1]);
            let xrange = if x2 > x1 { x1..=x2 } else { x2..=x1 };
            let yrange = if y2 > y1 { y1..=y2 } else { y2..=y1 };
            for x in xrange.clone() {
                for y in yrange.clone() {
                    sand_map.insert(Point2D { x: x, y: y }, MapType::Rock);
                }
            }
        }
    }
    sand_map
}

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,
    };

    // Part 1
    let mut sand_map = build_map(&input);

    // Identify the extent of the abyss
    let abyss = &sand_map.keys().map(|&pt| pt.y).max().unwrap() + 2;

    // Simulate sand
    'sand_lp: for sand in 0.. {
        let result = drop_sand(&mut sand_map,abyss,true);
        if !result { println!("Part 1: {sand}"); break 'sand_lp; } // 1061
    }

    // Part 2 (reset map)
    let mut sand_map = build_map(&input);

    // Build floor
    for x in 0..=1000 {
        sand_map.insert(Point2D { x: x, y: abyss },MapType::Rock);
    }

    'sand_lp2: for sand in 1.. {
        let result = drop_sand(&mut sand_map,abyss,false);
        if !result { println!("Part 2: {sand}"); break 'sand_lp2; } //  25055
    }

    Ok(())
}

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

defmodule AdventOfCode.Solution.Year2022.Day14 do
  @source {500, 0}

  def part1(input) do
    input
    |> stream_states(fn coords, _sand -> coords end)
    |> Stream.map(&MapSet.size/1)
    |> Stream.chunk_every(2, 1)
    |> Enum.find_index(&match?([count, count], &1))
  end

  def part2(input) do
    input
    |> stream_states(&MapSet.put(&1, &2))
    |> Enum.find_index(&MapSet.member?(&1, @source))
  end

  defp stream_states(input, use_floor) do
    {coords, floor_y} = parse(input)
    Stream.iterate(coords, &drop_sand(&1, {floor_y, use_floor}))
  end

  defp drop_sand(coords, floor, sand \\ @source, move \\ :d)

  defp drop_sand(coords, {floor_y, use_floor} = floor, {x, y} = sand, :d) do
    next = {x, y + 1}

    cond do
      MapSet.member?(coords, next) -> drop_sand(coords, floor, sand, :l)
      y == floor_y - 1 -> use_floor.(coords, sand)
      true -> drop_sand(coords, floor, next, :d)
    end
  end

  defp drop_sand(coords, floor, {x, y} = sand, :l) do
    next = {x - 1, y + 1}

    if MapSet.member?(coords, next),
      do: drop_sand(coords, floor, sand, :r),
      else: drop_sand(coords, floor, next, :d)
  end

  defp drop_sand(coords, floor, {x, y} = sand, :r) do
    next = {x + 1, y + 1}

    if MapSet.member?(coords, next),
      do: MapSet.put(coords, sand),
      else: drop_sand(coords, floor, next, :d)
  end

  defp parse(input) do
    coords =
      input
      |> String.split("\n", trim: true)
      |> Enum.map(&parse_path/1)
      |> Enum.reduce(MapSet.new(), &MapSet.union/2)

    floor_y =
      coords
      |> Enum.max_by(&elem(&1, 1))
      |> elem(1)
      |> Kernel.+(2)

    {coords, floor_y}
  end

  defp parse_path(line) do
    ~r/(\d+),(\d+)/
    |> Regex.scan(line, capture: :all_but_first)
    |> Enum.chunk_every(2, 1, :discard)
    |> Enum.flat_map(&parse_stroke/1)
    |> MapSet.new()
  end

  defp parse_stroke([[x1, y1], [x2, y2]]) do
    for x <- String.to_integer(x1)..String.to_integer(x2),
        y <- String.to_integer(y1)..String.to_integer(y2),
        do: {x, y}
  end
end