7 votes

Day 14: Regolith Reservoir

Today's problem description: https://adventofcode.com/2022/day/14

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

3 comments

  1. bhrgunatha
    (edited )
    Link
    Part 2 is very slow so I'll have to come back to this. Hurt my knee today and pain > shame Data (match-define (list S SE SW) '((0 1) (1 1) (-1 1))) (define (point+ x y) (map + x y)) (define START...

    Part 2 is very slow so I'll have to come back to this. Hurt my knee today and pain > shame

    Data
    (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)))
    
    Part 1

    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]))
    
    Part 2

    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))
    
    "Speedrun"

    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))))
    
    1 vote
  2. wycy
    (edited )
    Link
    Rust I enjoyed this one. I was a bit afraid due to the problems reference to 2018 day 17, which I remember finding incredibly hard at the time, but this one wasn’t as bad. Rust use std::env; use...

    Rust

    I enjoyed this one. I was a bit afraid due to the problems reference to 2018 day 17, which I remember finding incredibly hard at the time, but this one wasn’t as bad.

    Rust
    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();
    }
    
    1 vote
  3. jzimbel
    Link
    Elixir I went through a lot of iterations on this one. Overall I did a few different combinations of It turned out that the simplest approach was also the fastest: model the data as a flat set,...

    Elixir

    I went through a lot of iterations on this one. Overall I did a few different combinations of

    Data structure: a flat set of {x, y} tuples OR a map {x => sorted_list(y)} to make accessing each column easier
    Falling logic: drop straight to the next available obstruction OR always drop 1 unit at a time

    It turned out that the simplest approach was also the fastest: model the data as a flat set, and always drop the sand grains one unit at a time. Other approaches introduced more edge cases and also required repeatedly searching through collections (either the column lists, or the entire set of coordinate pairs), which more than canceled out any efficiency gains from skipping steps.

    Both parts I used multiple function clauses in drop_sand/4 to separate out the 3 main checks (:d, :l, :r) and keep the number of nested branches to a minimum.
    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
    

    Part 1 runs in 26 ms, part 2 in 744 ms.

    1 vote