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

  • landreville@lemmy.world
    link
    fedilink
    arrow-up
    5
    ·
    11 months ago

    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.

    • mykl@lemmy.world
      link
      fedilink
      arrow-up
      1
      ·
      11 months ago

      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!

  • hades
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    3 months ago

    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
    
    • SteveDinn@lemmy.ca
      link
      fedilink
      arrow-up
      2
      ·
      11 months ago

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

  • Ananace@lemmy.ananace.dev
    link
    fedilink
    arrow-up
    4
    ·
    11 months ago

    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;
    Picture of solution output

    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
    
    • hades
      link
      fedilink
      arrow-up
      3
      ·
      11 months ago

      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?

      • Ananace@lemmy.ananace.dev
        link
        fedilink
        arrow-up
        2
        ·
        11 months ago

        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.

        • Massahud@programming.dev
          link
          fedilink
          arrow-up
          1
          ·
          edit-2
          11 months ago

          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.

          • Ananace@lemmy.ananace.dev
            link
            fedilink
            arrow-up
            1
            ·
            edit-2
            11 months ago

            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.

  • Nighed@sffa.community
    link
    fedilink
    English
    arrow-up
    3
    ·
    edit-2
    11 months ago

    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

  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    3
    ·
    edit-2
    11 months ago

    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;
    }
    
  • Gobbel2000@feddit.de
    link
    fedilink
    arrow-up
    2
    ·
    11 months ago

    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.

  • vole@lemmy.world
    link
    fedilink
    English
    arrow-up
    2
    ·
    edit-2
    11 months ago

    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.

    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";
    }
    
  • cvttsd2si@programming.dev
    link
    fedilink
    arrow-up
    2
    ·
    11 months ago

    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
    
  • cacheson@kbin.social
    link
    fedilink
    arrow-up
    2
    ·
    11 months ago

    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:

  • janAkali@lemmy.one
    link
    fedilink
    English
    arrow-up
    2
    ·
    11 months ago

    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

    • abclop99@beehaw.org
      link
      fedilink
      English
      arrow-up
      4
      ·
      11 months ago

      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.

  • Zarlin@lemmy.world
    link
    fedilink
    arrow-up
    1
    ·
    edit-2
    11 months ago

    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

    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)
    
  • purplemonkeymad@programming.dev
    link
    fedilink
    arrow-up
    1
    ·
    11 months ago

    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) &amp; second.value) or
                ((first.value &lt;&lt; 1) &amp; second.value))
    
    def opposite_direction(dir:Connection) -> Connection:
        if dir.value &amp; 0b00011:
            return Connection(dir.value ^ 0b00011)
        if dir.value &amp; 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 &amp; direction):
                return False
            
            if self.connection &amp; direction and pipe.connection &amp; 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 &lt; 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 &lt; 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()
    
  • Massahud@programming.dev
    link
    fedilink
    arrow-up
    1
    ·
    11 months ago

    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.

  • to_urcite_ty_kokos@lemmy.world
    link
    fedilink
    English
    arrow-up
    1
    ·
    edit-2
    11 months ago

    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.

  • capitalpb@programming.dev
    link
    fedilink
    English
    arrow-up
    1
    ·
    11 months ago

    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: &amp;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 == &amp;'S').unwrap();
    
            PipeMap {
                start,
                tiles,
                width,
            }
        }
    
        fn valid_steps(&amp;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(&amp;self, input: &amp;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(&amp;self, input: &amp;str) -> String {
            todo!()
        }
    }