Skip Navigation

❄️ - 2023 DAY 10 SOLUTIONS -❄️

Day 10: Pipe Maze

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ


🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Unlocked after 40 mins

25 comments
  • Rust Solution

    Used Shoelace Algorithm to get the interior area and then Pick's Theorem to get the number of interior points based on the area and the points along the boundary loop.

    • It's so humbling when you've hammered out a solution and then realise you've been paddling around in waters that have already been mapped out by earlier explorers!

    • Thanks for that state machine. I was a bit lost in part 2, but after reading this, it totally makes sense.

  • The squeezing component in part 2 made this really interesting.

    I had a thought on a naïve solution consisting of expanding the input grid, painting all the walked pipes, and then doing a flood fill from the outside of the expanded map. There are a lot cleverer ways to do it, but the idea stuck with me and so...

    The code's a bit of a mess, but I actually kind of like the result. It visualizes really well and still runs both parts in under 8 seconds, so it's not even particularly slow considering how it does it.

    E.g;

  • C# I had fun with this one and overbuilt it somewhat. Disappointed I didn't get/need to implement Dijkstra's algorithm.

    For part two I did a x2 expand, so the example input expanded and found the middles like this (0s for the targets as their easier to distinguish):

    Part 2 is too big to post... see pastebin link

  • Nim

    I got a late start on part 1, and then had to sleep on part 2. Just finished everything up with a little time to spare before day 11.

    Part 2 probably would have been easier if I knew more about image processing, but I managed:

    • Made a copy of the grid and filled it with . tiles
    • Copied all of the path tiles that I had calculated in part 1
    • Flood-filled all the . tiles that are connected to the outside edges of the grid with O tiles
    • Walked along the path, looking for an adjacent O tile at each step. Stopped when one was found, and recorded whether it was to the left or right of the path.
    • Walked the path again, flood-filling any adjacent inside . tiles with I, and counted them

    Code:

    • btw if you put the url to nim as /c/nim@programming.dev I dont think the url bot will trigger since it does the same thing the ! format does

       
          
      [Nim](/c/nim@programming.dev)
      
        

      Nim

      Edit: yeah looks like it didnt reply to me so this format works

      • Unfortunately then it'll be broken for kbin users. I can do it anyway though if the bot is too annoying, just lmk.

    • Hi there! Looks like you linked to a Lemmy community using a URL instead of its name, which doesn't work well for people on different instances. Try fixing it like this: !nim@programming.dev

  • Rust

    This one was tricky but interesting. In part 2 I basically did Breadth-First-Search starting at S to find all spots within the ring. The trick for me was to move between fields, meaning each position is at the corner of four fields. I never cross the pipe ring, and if I hit the area bounds I know I started outside the ring not inside and start over at a different corner of S.

    Part 2 runs in 4ms.

  • Dart

    Finally got round to solving part 2. Very easy once I realised it's just a matter of counting line crossings.

    Edit: having now read the other comments here, I'm reminded me that the line crossing logic is actually an application of Jordan's Curve Theorem which looks like a mathematical joke when you first see it, but turns out to be really useful here!

     
        
    var up = Point(0, -1),
        down = Point(0, 1),
        left = Point(-1, 0),
        right = Point(1, 0);
    var pipes = >>{
      '|': [up, down],
      '-': [left, right],
      'L': [up, right],
      'J': [up, left],
      '7': [left, down],
      'F': [right, down],
    };
    late List> grid; // Make grid global for part 2
    Set> buildPath(List lines) {
      grid = lines.map((e) => e.split('')).toList();
      var points = {
        for (var row in grid.indices())
          for (var col in grid.first.indices()) Point(col, row): grid[row][col]
      };
      // Find the starting point.
      var pos = points.entries.firstWhere((e) => e.value == 'S').key;
      var path = {pos};
      // Replace 'S' with assumed pipe.
      var dirs = [up, down, left, right].where((el) =>
          points.keys.contains(pos + el) &&
          pipes.containsKey(points[pos + el]) &&
          pipes[points[pos + el]]!.contains(Point(-el.x, -el.y)));
      grid[pos.y][pos.x] = pipes.entries
          .firstWhere((e) =>
              (e.value.first == dirs.first) && (e.value.last == dirs.last) ||
              (e.value.first == dirs.last) && (e.value.last == dirs.first))
          .key;
    
      // Follow the path.
      while (true) {
        var nd = dirs.firstWhereOrNull((e) =>
            points.containsKey(pos + e) &&
            !path.contains(pos + e) &&
            (points[pos + e] == 'S' || pipes.containsKey(points[pos + e])));
        if (nd == null) break;
        pos += nd;
        path.add(pos);
        dirs = pipes[points[pos]]!;
      }
      return path;
    }
    
    part1(List lines) => buildPath(lines).length ~/ 2;
    part2(List lines) {
      var path = buildPath(lines);
      var count = 0;
      for (var r in grid.indices()) {
        var outside = true;
        // We're only interested in how many times we have crossed the path
        // to get to any given point, so mark anything that's not on the path
        // as '*' for counting, and collapse all uninteresting path segments.
        var row = grid[r]
            .indexed()
            .map((e) => path.contains(Point(e.index, r)) ? e.value : '*')
            .join('')
            .replaceAll('-', '')
            .replaceAll('FJ', '|') // zigzag
            .replaceAll('L7', '|') // other zigzag
            .replaceAll('LJ', '') // U-bend
            .replaceAll('F7', ''); // n-bend
        for (var c in row.split('')) {
          if (c == '|') {
            outside = !outside;
          } else {
            if (!outside && c == '*') count += 1;
          }
        }
      }
      return count;
    }
    
      
  • Nim

    I have zero idea how this functions correctly. I fear to touch it more than necessary or it would fall apart in a moment.
    I got second star after 8 hours (3 hours for part 1 + 4 hour break + 1 hour part 2), at that moment I've figured out how to mark edges of enclosed tiles. Then I just printed the maze and counted all in-between tiles manually. A bit later I've returned and fixed the code with an ugly regex hack, but atleast it works.
    Code: day_10/solution.nim

    • I printed the loop using box drawing characters, zoomed out, took a screenshot, and used GIMP to separate the inside and outside, and count the number of inside tiles.

  • Raku

    My solution for today is quite sloppy. For part 2, I chose to color along both sides of the path (each side different colors) and then doing a fill of the empty space based on what color the empty space is touching. Way less optimal than scanning, and I didn't cover every case for coloring around the start point, but it was interesting to attempt. I ran into a bunch of issues on dealing with nested arrays in Raku, I need to investigate if there's a better way to handle them.

    View code on github

    Edit: did some cleanup, added some fun, and switched to the scanning algorithm for part 2, shaved off about 50 lines of code.

  • Nim

    This was a great challenge, it was complex enough to get me to explore more of the Nim language, mainly (ref) types, iterators, operators, inlining.

    I first parse the input to Tiles stored in a grid. I use a 1D seq for fast tile access, in combination with a 2D Coord type. From the tile "shapes" I get the connection directions to other tiles based on the lookup table shapeConnections. The start tile's connections are resolved based on how the neighbouring tiles connect.

    Part 1 is solved by traversing the tiles branching out from the start tile in a sort of pathfinding-inspired way. Along the way I count the distance from start, a non-negative distance means the tile has already been traversed. The highest distance is tracked, once the open tiles run our this is the solution to part 1.

    Part 2 directly builds on the path found in Part 1. Since the path is a closed loop that doesn't self-intersect, I decided to use the raycast algorithm for finding if a point lies inside a polygon. For each tile in the grid that is not a path tile, I iterate towards the right side of the grid. If the number of times the "ray" crosses the path is odd, the point lies inside the path. Adding all these points up give the solution for Part 2.

    Initially it ran quite slow (~8s), but I improved it by caching the tile connections (instead of looking them up based on the symbol), and by ditching the "closed" tiles list I had before which kept track of all the path tiles, and switched to checking the tile distance instead. This and some other tweaks brought the execution speed down to ~7ms, which seems like a nice result :)

    Part 1 & 2 combined

  • I always felt I was one fix away from the solution, which was both nice and bad.

    Walking the path was fine, and part 2 looked easy until I missed the squeezed pipes. I for some silly reason thought I only had to expand the grid by x2 instead of x3 and had to re-do that. Fill is hyper bad but works for <1 minute.

  • Language: Python

    Github

    Decided to use a graph to solve (which expanded the size). Part 1 was cycle detection, and part 2 was flooding of the outside.

  • Kotlin

    Github

    Double expansion seams like a nice approach, but I didn't think of that. Instead, I just scan the lines and “remember” if I am in a component or not by counting the number of pipe crossings.

  • Well, star one is solved. I don't love the code, but yet again, it works for now. I don't love the use of a label to continue/break a loop, and the valid_steps function is a mess that could probably be done much cleaner.

    Upon looking at star 2 I don't even have the slightest idea of where to start. I may have to come back to this one at a later date. Sigh.

    https://github.com/capitalpb/advent_of_code_2023/blob/main/src/solvers/day10.rs

     rust
        
    use crate::Solver;
    
    #[derive(Debug)]
    struct PipeMap {
        start: usize,
        tiles: Vec,
        width: usize,
    }
    
    impl PipeMap {
        fn from(input: &str) -> PipeMap {
            let tiles = input
                .lines()
                .rev()
                .flat_map(|row| row.chars())
                .collect::>();
    
            let width = input.find('\n').unwrap();
            let start = tiles.iter().position(|tile| tile == &'S').unwrap();
    
            PipeMap {
                start,
                tiles,
                width,
            }
        }
    
        fn valid_steps(&self, index: usize) -> Vec {
            let mut tiles = vec![];
            let current_tile = *self.tiles.get(index).unwrap();
    
            if "S|LJ".contains(current_tile) {
                let north = index + self.width;
                if let Some(tile) = self.tiles.get(north) {
                    if "|7F".contains(*tile) {
                        tiles.push(north);
                    }
                }
            }
    
            if "S|7F".contains(current_tile) {
                if let Some(south) = index.checked_sub(self.width) {
                    if let Some(tile) = self.tiles.get(south) {
                        if "|LJ".contains(*tile) {
                            tiles.push(south);
                        }
                    }
                }
            }
    
            if "S-J7".contains(current_tile) {
                if let Some(west) = index.checked_sub(1) {
                    if (west % self.width) != (self.width - 1) {
                        if let Some(tile) = self.tiles.get(west) {
                            if "-LF".contains(*tile) {
                                tiles.push(west);
                            }
                        }
                    }
                }
            }
    
            if "S-LF".contains(current_tile) {
                let east = index + 1;
                if east % self.width != 0 {
                    if let Some(tile) = self.tiles.get(east) {
                        if "-J7".contains(*tile) {
                            tiles.push(east);
                        }
                    }
                }
            }
    
            tiles
        }
    }
    
    pub struct Day10;
    
    impl Solver for Day10 {
        fn star_one(&self, input: &str) -> String {
            let pipe_map = PipeMap::from(input);
    
            let mut current_pos = pipe_map.start;
            let mut last_pos = pipe_map.start;
            let mut steps: usize = 0;
    
            'outer: loop {
                for pos in pipe_map.valid_steps(current_pos) {
                    if pos != last_pos {
                        last_pos = current_pos;
                        current_pos = pos;
                        steps += 1;
    
                        continue 'outer;
                    }
                }
                break;
            }
    
            steps.div_ceil(2).to_string()
        }
    
        fn star_two(&self, input: &str) -> String {
            todo!()
        }
    }
    
      
25 comments