5 votes

Day 18: Boiling Boulder

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

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>

2 comments

  1. bhrgunatha
    (edited )
    Link
    My loony bun is fine Benny Lava Data My lava is a hash with key cube co-ordinates. I allowed myself mutable state for the limits of the lava. We live in dangerous times! DIRS '((1 0 0) (-1 0 0) (0...

    My loony bun is fine Benny Lava

    Data My lava is a hash with key cube co-ordinates. I allowed myself mutable state for the limits of the lava. We live in dangerous times!
     DIRS '((1 0 0) (-1 0 0) (0 1 0) (0 -1 0) (0 0 1) (0 0 -1)))
    (define (point+ a b) (map + a b))
    (define XMAX 0)
    (define YMAX 0)
    (define ZMAX 0)
    (define (read-lava input)
      (define cubes (map integers input))
      (for/hash ([c (in-list cubes)])
        (match-define (list x y z) c)
        (set! XMAX (max x XMAX))
        (set! YMAX (max y YMAX))
        (set! ZMAX (max z ZMAX))
        (values c 'lava)))
    
    Part 1

    I've come to realise I SUCK at geometry problems.
    I spent ages confused about what cubes that are "not connected" could mean when the first tiny example had CONNECTED cubes. Once I figured out what was actually required, it turned out to be pretty simple. You just count the faces of each cube that doesn't touch another. (Touching me... TOUCHING YOU..!!!!)

    (define (part-01 input)
      (define lava (read-lava input))
      (count-faces lava))
    
    (define (count-faces lava)
      (for/sum ([c (in-hash-keys lava)])
        (- 6 (length (neighbours lava c)))))
    
    ;; (define (in-bounds? p)
    ;;   (match-define (list x y z) p)
    ;;   (and (<= 0 x XMAX)
    ;;        (<= 0 y YMAX)
    ;;        (<= 0 z ZMAX)))
    
    (define (neighbours lava p)
      (for/list ([d (in-list DIRS)]
                 #:do [(define p+ (point+ p d))]
    ;;              #:when (in-bounds? p+) ; already testing for lava, no check needed
                 #:when (lava-ref lava p+))
        p+))
    
    ;;  a hangover from first attempt with a massive nested array. lol-ipops.
    (define (lava-ref l p)
      (hash-ref l p #f))    
    
    Part 2

    Had no idea what to do at first. I considered writing a 3d convex hull :(. Did I ever tell you how much I SUCK at geometry? I realised though, I could just start outside the lava and mark everything with higher co-ordinates that is non-cube and not yet marked. Then for all points NOT connected to a cube (now I know what that means!) and not marked external, count how many faces do touch another cube. Subtract that from the count of all faces (from part 1). Horribly inefficient but glad to get a finish. I'll speed it up later.
    Edit: Oh dear. I left in a set-union in mark-external from an experiment I abandoned. There's no need repeatedly merge sets that differ by 1 element! It really slow things down. smh

    (define (part-02 input)
      (define lava (read-lava input))
      (- (count-faces lava)
         (count-internal-faces lava)))
    
    (define (count-internal-faces lava)
      (define external (mark-external (list -1 -1 -1) lava))
      (for*/fold ([seen (set)]
                  [faces 0]
                  #:result faces)
                 ([c (in-hash-keys lava)]
                 [d (in-list DIRS)]
                 #:do [(define p+ (point+ c d))]
                 #:unless (set-member? external p+)
                 #:unless (set-member? seen p+)
                 #:unless (lava-ref lava p+))
        (values (set-add seen p+)
                (+ faces (length (neighbours lava p+))))))
    
    (define (out-of-bounds? p)
      (match-define (list x y z) p)
      (not (and (<= -1 x (add1 XMAX))
                (<= -1 y (add1 YMAX))
                (<= -1 z (add1 ZMAX)))))
    
    (define (mark-external p lava [external (set p)])
      (for/fold ([external external])
                ([d (in-list DIRS)]
                 #:do [(define p+ (point+ p d))]
                 #:unless (set-member? external p+)
                 #:unless (out-of-bounds? p+)
                 #:unless (lava-ref lava p+))
        ;; (set-union external (mark-external p+ lava (set-add external p+)))))
        (mark-external p+ lava (set-add external p+))))
    

    Now poop on them Oliver!

    1 vote
  2. wycy
    Link
    Rust I'm way behind. I need to get back to day 16/17 now. Rust use std::env; use std::io::{self, prelude::*, BufReader}; use std::fs::File; use std::collections::HashMap; use...

    Rust

    I'm way behind. I need to get back to day 16/17 now.

    Rust
    use std::env;
    use std::io::{self, prelude::*, BufReader};
    use std::fs::File;
    use std::collections::HashMap;
    
    use point3d::point3d::Point3D;
    
    #[derive(Eq,PartialEq)]
    enum Voxel {
        Lava,
        Air,
    }
    
    fn neighbors(pt: &Point3D) -> Vec<Point3D> {
        vec![
            Point3D { x: pt.x+1, y: pt.y  , z: pt.z   },
            Point3D { x: pt.x-1, y: pt.y  , z: pt.z   },
            Point3D { x: pt.x  , y: pt.y+1, z: pt.z   },
            Point3D { x: pt.x  , y: pt.y-1, z: pt.z   },
            Point3D { x: pt.x  , y: pt.y  , z: pt.z+1 },
            Point3D { x: pt.x  , y: pt.y  , z: pt.z-1 },
        ]
    }
    
    fn coords_voxel(s: &str) -> (Point3D,Voxel) {
        let coords: Vec<_> = s.split(",").collect();
        let (x,y,z) = (coords[0].parse().unwrap(), coords[1].parse().unwrap(), coords[2].parse().unwrap());
        (Point3D { x: x, y: y, z: z }, Voxel::Lava)
    }
    
    fn flood_fill(pt: &Point3D, map: &mut HashMap<Point3D,Voxel>, xrange: (i64,i64), yrange: (i64,i64), zrange: (i64,i64)) {
        let (xmin,xmax) = xrange;
        let (ymin,ymax) = yrange;
        let (zmin,zmax) = zrange;
        if pt.x == xmin || pt.x == xmax || pt.y == ymin || pt.y == ymax || pt.z == zmin || pt.z == zmax { return }
        match &map.get(&pt) {
            Some(Voxel::Lava) | Some(Voxel::Air) => return,
            _ => &map.insert(*pt,Voxel::Air),
        };
        flood_fill(&Point3D { x: pt.x + 1, y: pt.y    , z: pt.z    }, map, xrange, yrange, zrange);
        flood_fill(&Point3D { x: pt.x - 1, y: pt.y    , z: pt.z    }, map, xrange, yrange, zrange);
        flood_fill(&Point3D { x: pt.x    , y: pt.y + 1, z: pt.z    }, map, xrange, yrange, zrange);
        flood_fill(&Point3D { x: pt.x    , y: pt.y - 1, z: pt.z    }, map, xrange, yrange, zrange);
        flood_fill(&Point3D { x: pt.x    , y: pt.y    , z: pt.z + 1}, map, xrange, yrange, zrange);
        flood_fill(&Point3D { x: pt.x    , y: pt.y    , z: pt.z - 1}, map, xrange, yrange, zrange);
    }
    
    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 voxels: HashMap<Point3D,Voxel> = input.iter().map(|s| coords_voxel(s)).collect();
    
        // Part 1
        let part1 = &voxels.len()*6 
                  - &voxels.iter().map(|(pt,_)| {
                        neighbors(&pt).iter().map(|n| match &voxels.get(&n) {
                            Some(_) => 1, None => 0,
                        }).sum::<usize>()
                  }).sum::<usize>();
        println!("Part 1: {part1}"); // 3610
    
        // Determine maximum extents
        let (xmin,xmax) = (&voxels.keys().map(|pt| pt.x).min().unwrap() - 2, &voxels.keys().map(|pt| pt.x).max().unwrap() + 2);
        let (ymin,ymax) = (&voxels.keys().map(|pt| pt.y).min().unwrap() - 2, &voxels.keys().map(|pt| pt.y).max().unwrap() + 2);
        let (zmin,zmax) = (&voxels.keys().map(|pt| pt.z).min().unwrap() - 2, &voxels.keys().map(|pt| pt.z).max().unwrap() + 2);
    
        // Flood the outer area with air
        flood_fill(&Point3D { x: xmin+1, y: ymin+1, z: zmin+1 },&mut voxels, (xmin,xmax), (ymin,ymax), (zmin,zmax));
    
        // Calculate surface area
        let part2 = &voxels
            .iter()
            .filter(|(_,v)| **v == Voxel::Lava)
            .map(|(pt,_)| {
                neighbors(&pt).iter().map(|n| match &voxels.get(&n) {
                    Some(Voxel::Air) => 1, _ => 0,
                }).sum::<usize>()
            }).sum::<usize>();
        println!("Part 2: {part2}"); // 2082
    
    
        Ok(())
    }
    
    fn main() {
        let args: Vec<String> = env::args().collect();
        let filename = &args[1];
        solve(&filename).unwrap();
    }
    
    1 vote