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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
🔒 Thread is locked until there’s at least 100 2 star entries on the global leaderboard
🔓 Unlocked after 40 mins
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!
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;
Ruby
A snippet from the expansion/flood fill;
def flood_fill(used: []) new_dim = @dim * 3 new_map = Array.new(new_dim.size, '.') puts "Expanding #{@dim} to #{new_dim}, with #{used.size} visited pipes." if $args.verbose # Mark all real points as inside on the expanded map (0..(@dim.y - 1)).each do |y| (0..(@dim.x - 1)).each do |x| expanded_point = Point.new x * 3 + 1, y * 3 + 1 new_map[expanded_point.y * new_dim.x + expanded_point.x] = 'I' end end # Paint all used pipes onto the expanded map used.each do |used_p| expanded_point = Point.new used_p.x * 3 + 1, used_p.y * 3 + 1 new_map[expanded_point.y * new_dim.x + expanded_point.x] = '#' offsets = @links[used_p].connections offsets.shift offsets.each do |offs| diff = offs - used_p new_map[(expanded_point.y + diff.y) * new_dim.x + (expanded_point.x + diff.x)] = '#' end end puts "Flooding expanded map..." if $args.verbose # Flood fill the expanded map from the top-left corner to_visit = [Point.new(0, 0)] until to_visit.empty? at = to_visit.shift new_map[at.y * new_dim.x + at.x] = ' ' (-1..1).each do |off_y| (-1..1).each do |off_x| next if (off_x.zero? && off_y.zero?) || !(off_x.zero? || off_y.zero?) off_p = at + Point.new(off_x, off_y) next if off_p.x < 0 || off_p.y < 0 \ || off_p.x >= new_dim.x || off_p.y >= new_dim.y \ || to_visit.include?(off_p) val = new_map[off_p.y * new_dim.x + off_p.x] next unless %w[. I].include? val to_visit << off_p end end end return new_map, new_dim end
That’s an interesting approach!
I wonder why it runs so slow, though, as far as I can tell the flooding code is just a BFS on the grid, so should be linear in number of cells?
With the fully expanded map for the actual input it ends up working a 420x420 tile grid, and it has to do both value lookups as well as mutations into that, alongside inclusion testing for the search array (which could probably be made cheaper by building it as a set). It ends up somewhat expensive simply on the number of tests.
The sample I posted the picture of runs in 0.07s wall time though.
Maybe you are adding the same point multiple times to to_visit. I don’t know ruby but couldn’t see a check for visited points before adding, and to_visit appears to be an array instead of set, which can store the same point multiple times.
There’s a
next if [...] to_visit.include?(off_p)
, and I also only visit points that haven’t been flood filled yet (next unless %w[. I].include? val
), so there shouldn’t be any superfluous testing going on.Went back and did a quick test of thing, and yep, converting the to_visit array to a set pulls execution time down to ~600ms. But the code becomes much messier.
Going to move the mutation of the map down to the point where I pick a point for visitation instead, so I can re-use the check for already flooded tiles instead.
Python
from .solver import Solver _EXITS_MAP = { '|': ((0, -1), (0, 1)), '-': ((-1, 0), (1, 0)), 'L': ((1, 0), (0, -1)), 'J': ((-1, 0), (0, -1)), '7': ((-1, 0), (0, 1)), 'F': ((1, 0), (0, 1)), '.': (), 'S': (), } class Day10(Solver): def __init__(self): super().__init__(10) self.maze: dict[tuple[int, int], str] = {} self.start: tuple[int, int] = (0, 0) self.dists: dict[tuple[int, int], int] = {} def _pipe_has_exit(self, x: int, y: int, di: int, dj: int, inverse: bool = False) -> bool: if inverse: di, dj = -di, -dj return (di, dj) in _EXITS_MAP[self.maze[(x, y)]] def presolve(self, input: str): self.maze: dict[tuple[int, int], str] = {} self.start: tuple[int, int] = (0, 0) for y, line in enumerate(input.rstrip().split('\n')): for x, c in enumerate(line): self.maze[(x, y)] = c if c == 'S': self.start = (x, y) next_pos: list[tuple[int, int]] = [] directions_from_start = [] for di, dj in ((0, -1), (1, 0), (0, 1), (-1, 0)): x, y = self.start[0] + di, self.start[1] + dj if (x, y) not in self.maze: continue if not self._pipe_has_exit(x, y, di, dj, inverse=True): continue next_pos.append((x, y)) directions_from_start.append((di, dj)) self.maze[self.start] = [c for c, dmap in _EXITS_MAP.items() if set(directions_from_start) == set(dmap)][0] dists: dict[tuple[int, int], int] = {} cur_dist = 0 while True: cur_dist += 1 new_next_pos = [] for x, y in next_pos: if (x, y) in dists: continue dists[(x, y)] = cur_dist for di, dj in ((0, -1), (1, 0), (0, 1), (-1, 0)): nx, ny = x + di, y + dj if (nx, ny) not in self.maze: continue if not self._pipe_has_exit(x, y, di, dj): continue new_next_pos.append((nx, ny)) if not new_next_pos: break next_pos = new_next_pos self.dists = dists def solve_first_star(self) -> int: return max(self.dists.values()) def solve_second_star(self) -> int: area = 0 for y in range(max(y for _, y in self.dists.keys()) + 1): internal = False previous_wall = False wall_start_symbol = None for x in range(max(x for x, _ in self.dists.keys()) + 1): is_wall = (x, y) == self.start or (x, y) in self.dists wall_continues = is_wall pipe_type = self.maze[(x, y)] if is_wall and pipe_type == '|': internal = not internal wall_continues = False elif is_wall and not previous_wall and pipe_type in 'FL': wall_start_symbol = pipe_type elif is_wall and not previous_wall: raise RuntimeError(f'expecting wall F or L at {x}, {y}, got {pipe_type}') elif is_wall and previous_wall and pipe_type == 'J': wall_continues = False if wall_start_symbol == 'F': internal = not internal elif is_wall and previous_wall and pipe_type == '7': wall_continues = False if wall_start_symbol == 'L': internal = not internal elif not is_wall and previous_wall: raise RuntimeError(f'expecting wall J or 7 at {x}, {y}, got {pipe_type}') if internal and not is_wall: area += 1 previous_wall = wall_continues return area
Thanks for that state machine. I was a bit lost in part 2, but after reading this, it totally makes sense.
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 1
namespace AdventOfCode2023.Days.Ten { internal class Day10Task1 : IRunnable { private HashSet<(int, int)> _visitedNodes = new HashSet<(int, int)>(); public void Run() { //var inputLines = File.ReadAllLines("Days/Ten/Day10ExampleInput.txt"); //var inputLines = File.ReadAllLines("Days/Ten/Day10ExampleInput2.txt"); var inputLines = File.ReadAllLines("Days/Ten/Day10Input.txt"); var map = new PipeMap(inputLines); _visitedNodes.Add((map.XCoord, map.YCoord)); while (true) { bool haveMoved = false; for (int i = 0; i < 4; i++) { if (map.CanMove((Direction)i)) { map.Move((Direction)i); if (_visitedNodes.Contains((map.XCoord, map.YCoord))) { map.Move(GetOppositeDirection((Direction)i)); } else { _visitedNodes.Add((map.XCoord, map.YCoord)); haveMoved = true; } } } if (!haveMoved) { break; } } Console.WriteLine("Nodes Visited: "+ _visitedNodes.Count); Console.WriteLine("Furthest Node: "+ _visitedNodes.Count/2); } public class PipeMap { public int XCoord { get; private set; } public int YCoord { get; private set; } public char CurrentPipe { get { return Map[YCoord][XCoord]; } } private string[] Map { get; set; } public PipeMap(string[] mapString) { Map = mapString; for (int y = 0; y < mapString.Length; y++) { for (int x = 0; x < mapString[y].Length; x++) { if (mapString[y][x] == 'S') { YCoord = y; XCoord = x; } } } } public void Move(Direction direction) { var adjacent = GetAdjacent(direction); XCoord = adjacent.Item1; YCoord = adjacent.Item2; } public bool CanMove(Direction direction) { bool currentPositionAllow = CanMoveFromCoord(direction, XCoord, YCoord); if (!currentPositionAllow) return false; var adjacent = GetAdjacent(direction); if (adjacent.Item3 != '.' && CanMoveFromCoord(GetOppositeDirection(direction), adjacent.Item1, adjacent.Item2)) { return true; } return false; } private bool CanMoveFromCoord(Direction direction, int xCoord, int yCoord) { switch (Map[yCoord][xCoord]) { case '|': return direction == Direction.Up || direction == Direction.Down; case '-': return direction == Direction.Left || direction == Direction.Right; case 'L': return direction == Direction.Up || direction == Direction.Right; case 'J': return direction == Direction.Up || direction == Direction.Left; case '7': return direction == Direction.Left || direction == Direction.Down; case 'F': return direction == Direction.Right || direction == Direction.Down; case 'S': return true; case '.': default: throw new Exception("you dun fucked up"); } } private (int, int, char) GetAdjacent(Direction direction) { var newXCoord = XCoord; var newYCoord = YCoord; switch (direction) { case Direction.Up: newYCoord--; break; case Direction.Down: newYCoord++; break; case Direction.Left: newXCoord--; break; case Direction.Right: newXCoord++; break; } return (newXCoord, newYCoord, Map[newYCoord][newXCoord]); } } public enum Direction { Up, Right, Down, Left } public static Direction GetOppositeDirection(Direction direction) { switch (direction) { case Direction.Up: return Direction.Down; case Direction.Down: return Direction.Up; case Direction.Right: return Direction.Left; case Direction.Left: return Direction.Right; default: throw new Exception("You dun fucked up... again"); } } } }
Part 2 is too big to post… see pastebin link
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 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.nimI 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.
haha, thats genius
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 ofS
.Part 2 runs in 4ms.
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.
Edit: did some cleanup, added some fun, and switched to the scanning algorithm for part 2, shaved off about 50 lines of code.
Code
use v6; sub MAIN($input) { my $file = open $input; my @map = $file.lines».comb».Array; my @starting-point = @map».grep('S', :k)».[0].grep(*.defined, :kv).List; my @path = (@starting-point,); my %tile-neighbors = '|' => (( 1, 0),(-1, 0)), '-' => (( 0,-1),( 0, 1)), 'L' => ((-1, 0),( 0, 1)), 'J' => ((-1, 0),( 0,-1)), '7' => (( 1, 0),( 0,-1)), 'F' => (( 1, 0),( 0, 1)), ; sub connecting-neighbor(@position, @neighbor) { my @neighbor-position = @position Z+ @neighbor; return False if any(@neighbor-position Z< (0, 0)); return False if any(@neighbor-position Z> (@map.end, @map.head.end)); my $neighbor-tile = @map[@neighbor-position[0]; @neighbor-position[1]]; my @negative-neighbor = @neighbor X* -1; return %tile-neighbors{$neighbor-tile}.grep(@negative-neighbor, :k).elems > 0; } # replace starting-point with the appropriate pipe my @start-tile-candidates = <| - L J 7 F>; for @start-tile-candidates -> $candidate { next if %tile-neighbors{$candidate}.map({!connecting-neighbor(@starting-point, $_)}).any; @map[@starting-point[0]; @starting-point[1]] = $candidate; last; } repeat { my @position := @path.tail; my $tile = @map[@position[0]; @position[1]]; my @neighbors = %tile-neighbors{$tile}.List; for @neighbors -> @neighbor { my @neighbor-position = @neighbor Z+ @position; next if @path.elems >= 2 && @neighbor-position eqv @path[*-2]; if connecting-neighbor(@position, @neighbor) { @path.push(@neighbor-position); last; } } } while @path.tail !eqv @path.head; my $part-one-solution = (@path.elems / 2).floor; say "part 1: {$part-one-solution}"; my %pipe-set = @path.Set; my %same-side-pairs = ; my $part-two-solution = 0; for ^@map.elems -> $y { my $inside = False; my $entrance-pipe = Nil; for ^@map.head.elems -> $x { if %pipe-set{$($y, $x)} { given @map[$y; $x] { when '|' { $inside = !$inside } when 'F' | 'L' { $entrance-pipe = $_ } when 'J' | '7' { $inside = !$inside if %same-side-pairs{$entrance-pipe} ne $_; $entrance-pipe = Nil; } } } elsif $inside { $part-two-solution += 1; } } } say "part 2: $part-two-solution"; }
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 withO
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 withI
, and counted them
Code:
btw if you put the url to nim as /c/[email protected] I dont think the url bot will trigger since it does the same thing the ! format does
[Nim](/c/nim@programming.dev)
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: [email protected]
- Made a copy of the grid and filled it with
Scala3
forgot to post this
import Area.* import Dir.* enum Dir(num: Int, diff: (Int, Int)): val n = num val d = diff case Up extends Dir(3, (0, -1)) case Down extends Dir(1, (0, 1)) case Left extends Dir(2, (-1, 0)) case Right extends Dir(0, (1, 0)) def opposite = Dir.from(n + 2) object Dir: def from(n: Int): Dir = Dir.all.filter(_.n == n % 4).ensuring(_.size == 1).head def all = List(Up, Down, Left, Right) enum Area: case Inside, Outside, Loop case class Pos(x: Int, y: Int) type Landscape = Map[Pos, Pipe] type Loop = Map[Pos, LoopPiece] def walk(p: Pos, d: Dir): Pos = Pos(p.x + d.d._1, p.y + d.d._2) val pipeMap = Map('|' -> List(Up, Down), '-' -> List(Left, Right), 'L' -> List(Up, Right), 'J' -> List(Up, Left), 'F' -> List(Right, Down), '7' -> List(Left, Down)) case class Pipe(neighbors: List[Dir]) case class LoopPiece(from: Dir, to: Dir): def left: List[Dir] = ((from.n + 1) until (if to.n < from.n then to.n + 4 else to.n)).map(Dir.from).toList def right: List[Dir] = LoopPiece(to, from).left def parse(a: List[String]): (Pos, Landscape) = val pipes = for (r, y) <- a.zipWithIndex; (v, x) <- r.zipWithIndex; p <- pipeMap.get(v) yield Pos(x, y) -> Pipe(p) val start = for (r, y) <- a.zipWithIndex; (v, x) <- r.zipWithIndex if v == 'S' yield Pos(x, y) (start.head, pipes.toMap) def walkLoop(start: Pos, l: Landscape): Loop = @tailrec def go(pos: Pos, last_dir: Dir, acc: Loop): Loop = if pos == start then acc else val dir = l(pos).neighbors.filter(_ != last_dir.opposite).ensuring(_.size == 1).head go(walk(pos, dir), dir, acc + (pos -> LoopPiece(last_dir.opposite, dir))) Dir.all.filter(d => l.get(walk(start, d)).exists(p => p.neighbors.contains(d.opposite))) match case List(start_dir, return_dir) => go(walk(start, start_dir), start_dir, Map(start -> LoopPiece(return_dir, start_dir))) case _ => Map() def task1(a: List[String]): Long = walkLoop.tupled(parse(a)).size.ensuring(_ % 2 == 0) / 2 def task2(a: List[String]): Long = val loop = walkLoop.tupled(parse(a)) val ys = a.indices val xs = a.head.indices val points = (for x <- xs; y <- ys yield Pos(x, y)).toSet // floodfill @tailrec def go(outside: Set[Pos], q: List[Pos]): Set[Pos] = if q.isEmpty then outside else val nbs = Dir.all.map(walk(q.head, _)).filter(points.contains(_)).filter(!outside.contains(_)) go(outside ++ nbs, nbs ++ q.tail) // start by floodfilling from the known outside: beyond the array bounds val boundary = ys.flatMap(y => List(Pos(-1, y), Pos(xs.end, y))) ++ xs.flatMap(x => List(Pos(x, -1), Pos(x, ys.end))) val r = go(boundary.toSet ++ loop.keySet, boundary.toList) // check on which side of the pipe the outside is, then continue floodfill from there val xsl = List[LoopPiece => List[Dir]](_.left, _.right).map(side => loop.flatMap((p, l) => side(l).map(d => walk(p, d))).filter(!loop.contains(_)).toSet).map(a => a -> a.intersect(r).size).ensuring(_.exists(_._2 == 0)).filter(_._2 != 0).head._1 (points -- go(r ++ xsl, xsl.toList)).size
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
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!() } }
If you’re still stuck on part 2, have a look at my comment which shows an unreasonably easy approach :-)
Language: Python
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
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.
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 :)
Condensed version:
proc solve*(input:string):array[2, int]= let lines = input.readFile.strip.splitLines.filterIt(it.len != 0) # build grid var grid = Grid(width:lines[0].len, height:lines.len) for line in lines: grid.tiles.add(line.mapIt(Tile(shape:it))) # resolve tile connections for t in grid.tiles: t.connections = shapeConnections[t.shape] # find start coordinates and resolve connections for it let startCoords = grid.find('S') let startTile = grid[startCoords] startTile.connections = startCoords.findConnections(grid) startTile.distance = 0 # Traverse both ends of path from start var open: Deque[Coord] open.addLast(startCoords) while open.len != 0: let c = open.popFirst # current coordinate let ct = grid[c] # tile at c #find and add connected neighbour nodes for d in ct.connections: let n = c+d let nt = grid[n] # if not already on found path and not in open tiles if nt.distance == -1 and not (n in open): nt.distance = ct.distance + 1 result[0] = max(result[0], nt.distance) open.addLast(n) # Part 2 for c in grid: let ct = grid[c] #path tiles are never counted if ct.distance >= 0: continue # search from tile to end of row var enclosed = false for sx in c.x.. 0): enclosed = not enclosed result[1] += ord(enclosed)
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.
Python
import re import math import argparse import itertools from enum import Flag,Enum class Connection(Flag): Empty = 0b0000 North = 0b0001 South = 0b0010 East = 0b01000 West = 0b10000 def connected_directions(first:Connection,second:Connection) -> bool: return bool(((first.value >> 1) & second.value) or ((first.value << 1) & second.value)) def opposite_direction(dir:Connection) -> Connection: if dir.value & 0b00011: return Connection(dir.value ^ 0b00011) if dir.value & 0b11000: return Connection(dir.value ^ 0b11000) return Connection(0) class PipeElement: def __init__(self,symbol:chr) -> None: self.symbol = symbol self.connection = Connection.Empty if symbol in [*'|LJS']: self.connection |= Connection.North if symbol in [*'|7FS']: self.connection |= Connection.South if symbol in [*'-LFS']: self.connection |= Connection.East if symbol in [*'-J7S']: self.connection |= Connection.West if self.connection == Connection.Empty: self.symbol = '.' def __repr__(self) -> str: return f"Pipe({self.connection})" def __str__(self) -> str: return self.symbol def connected_to(self,pipe,direction:Connection) -> bool: if not (self.connection & direction): return False if self.connection & direction and pipe.connection & opposite_direction(direction): return True return False class Navigator: def __init__(self,list:list,width) -> None: self.list = list self.width = width def at(self,position): return self.list[position] def neighbor(self,position,direction:Connection) -> tuple | None: match direction: case Connection.North: return self.prev_row(position) case Connection.South: return self.next_row(position) case Connection.East: return self.next(position) case Connection.West: return self.prev(position) raise Exception(f"Direction not found: {direction}") def prev_row(self,position) -> tuple | None: p = position - self.width if p < 0: return None return (p,self.list[p]) def next_row(self,position) -> tuple | None: p = position + self.width if p >= len(self.list): return None return (p,self.list[p]) def prev(self,position) -> tuple | None: p = position - 1 if p < 0: return None return (p,self.list[p]) def next(self,position) -> tuple | None: p = position + 1 if p >= len(self.list): return None return (p,self.list[p]) def all_neighbors(self,position) -> list: l = list() for f in [self.next, self.prev, self.next_row,self.prev_row]: t = f(position) if t != None: l.append(t) return l def find_connected(self,position,exclude=Connection.Empty) -> tuple | None: for dir in [Connection.East,Connection.West,Connection.North,Connection.South]: if dir == exclude: continue n = self.neighbor(position,dir) if n == None: continue if self.at(position).connected_to(n[1],dir): return (*n,dir) return None class TileType(Enum): Inside = 1 Outside = 0 Pipe = 2 PlaceHolder = 3 def pipe_to_tile_expand(pipe:PipeElement) -> list: s = str(pipe) expansions = { '.': '.PP'+ 'PPP' + 'PPP', '-': 'PPP'+ '---' + 'PPP', '|': 'P|P'+ 'P|P' + 'P|P', 'F': 'PPP'+ 'PF-' + 'P|P', '7': 'PPP'+ '-7P' + 'P|P', 'J': 'P|P'+ '-JP' + 'PPP', 'L': 'P|P'+ 'PL-' + 'PPP', 'S': 'P|P'+ '-S-' + 'P|P' } l = expansions[s] return [pipe_to_tile(x) for x in [*l]] def pipe_to_tile(pipe:str) -> TileType: expansions = { '.': TileType.Inside, '-': TileType.Pipe, '|': TileType.Pipe, 'F': TileType.Pipe, '7': TileType.Pipe, 'J': TileType.Pipe, 'L': TileType.Pipe, 'S': TileType.Pipe, 'P': TileType.PlaceHolder } return expansions[pipe] def chunks(lst, n): """Yield successive n-sized chunks from lst.""" for i in range(0, len(lst), n): yield lst[i:i + n] def print_tiles(tile_list:list,width:int): for c in chunks(tile_list,width): print("".join([str(t.value) for t in c])) def print_pipes(tile_list:list,width:int): for c in chunks(tile_list,width): print("".join([str(t) for t in c])) def main(line_list:list,part:int): width = None pipe_list = list() tile_list = list() start_o = None for line in line_list: line = line + ' ' # stops east/west joining over new lines if width == None: width = len(line) for c in [*line]: o = PipeElement(c) pipe_list.append(o) tile_list.append(TileType.Inside) if c == 'S': start_o = o #print(pipe_list) start_pos = pipe_list.index(start_o) start_co = (start_pos // width, start_pos % width) print(f"starting index: {start_pos}: {start_co}") nav = Navigator(pipe_list,width) cur_pos = None last_dir = Connection.Empty steps = 0 while cur_pos != start_pos: if cur_pos == None: cur_pos = start_pos pipe = nav.find_connected(cur_pos,exclude=opposite_direction(last_dir)) if pipe == None: raise Exception(f"end of pipe at: {cur_pos}, {nav.at(cur_pos)}") cur_pos = pipe[0] last_dir = pipe[2] steps += 1 #print(f"{cur_pos}->",end="") tile_list[cur_pos] = TileType.Pipe print(f"end: {cur_pos}, steps: {steps}") clean_pipe = list() for i in range(0,len(pipe_list)): if tile_list[i] == TileType.Pipe: clean_pipe.append(pipe_list[i]) else: clean_pipe.append(PipeElement('.')) print_pipes(clean_pipe,width) print(f"part 1: {steps/2}") # part 2 outputs #print("start tile:") #print_tiles(tile_list,width) # add outsides to edge of map tile_list2 = list() #first row expanded_width = (width*3)+2 for i in range(0,expanded_width): tile_list2.append(TileType.Outside) for row in chunks(clean_pipe, width): ## we need to expand this to 2x size tiles t_rows = [ list() for x in range(0,3)] [ x.append(TileType.Outside) for x in t_rows] for r in row: parts = pipe_to_tile_expand(r) [ t_rows[x].extend( parts[x*3:(x*3)+3] ) for x in range(0,3)] [ x.append(TileType.Outside) for x in t_rows] [ tile_list2.extend(x) for x in t_rows] for i in range(0,expanded_width): tile_list2.append(TileType.Outside) #print("with o tile:") #print_tiles(tile_list2,width+2) tilenav = Navigator(tile_list2,expanded_width) changes = True while changes == True: changes = False count_in = 0 for i in range(0,len(tile_list2)): t = tilenav.at(i) if t == TileType.Inside or t == TileType.PlaceHolder: n = tilenav.all_neighbors(i) if any([x[1] == TileType.Outside for x in n]): tilenav.list[i] = TileType.Outside changes = True continue if t == TileType.Inside: count_in += 1 print("with outside tile:") print_tiles(tile_list2,expanded_width) print(count_in) if __name__ == "__main__": parser = argparse.ArgumentParser(description="template for aoc solver") parser.add_argument("-input",type=str) parser.add_argument("-part",type=int) args = parser.parse_args() filename = args.input if filename == None: parser.print_help() exit(1) part = args.part file = open(filename,'r') main([line.rstrip('\n') for line in file.readlines()],part) file.close()
huh… expand x2 worked for me. I wonder if I had a nice input set