Day 6: Guard Gallivant

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)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • lwhjp@lemmy.sdf.org
    link
    fedilink
    arrow-up
    5
    ·
    edit-2
    18 days ago

    Haskell

    This was a fun one! Infinite loops, performance concerns and so on. Part 2 could be made a bit faster with a recursive approach (I think), but this is good enough for me. Lost quite a bit of time with an incorrect walk function that passed the test data and part 1 but not part 2.

    import Data.Array.Unboxed (UArray)
    import Data.Array.Unboxed qualified as Array
    import Data.List
    import Data.Maybe
    import Data.Set (Set)
    import Data.Set qualified as Set
    
    readInput :: String -> UArray (Int, Int) Char
    readInput s =
      let rows = lines s
       in Array.listArray ((1, 1), (length rows, length $ head rows)) $ concat rows
    
    startPos = fst . fromJust . find ((== '^') . snd) . Array.assocs
    
    walk grid = go (startPos grid) (-1, 0)
      where
        go pos@(i, j) dir@(di, dj) =
          (pos, dir)
            : let pos' = (i + di, j + dj)
               in if Array.inRange (Array.bounds grid) pos'
                    then case grid Array.! pos' of
                      '#' -> go pos (dj, -di)
                      _ -> go pos' dir
                    else []
    
    path = Set.fromList . map fst . walk
    
    part1 = Set.size . path
    
    part2 grid = Set.size $ Set.filter (isLoop . walk . addO) $ Set.delete (startPos grid) $ path grid
      where
        addO pos = grid Array.// [(pos, '#')]
        isLoop xs = or $ zipWith Set.member xs $ scanl' (flip Set.insert) Set.empty xs
    
    main = do
      input <- readInput <$> readFile "input06"
      print $ part1 input
      print $ part2 input
    
  • Ananace@lemmy.ananace.dev
    link
    fedilink
    arrow-up
    4
    ·
    18 days ago

    Not a big fan of this one, felt far too much like brute force for my liking.
    At least it works with AsParallel

    C#
    public struct Point : IEquatable<Point>
    {
      public int X { get; set; }
      public int Y { get; set; }
    
      public Point(int x = 0, int y = 0) {
        X = x;
        Y = y;
      }
    
      public static Point operator+(Point l, Point r) {
        return new Point(l.X + r.X, l.Y + r.Y);
      }
      public bool Equals(Point other) {
        return X == other.X && Y == other.Y;
      }
    }
    
    Point size = new Point(0, 0);
    HashSet<Point> obstructions = new HashSet<Point>();
    Point guard = new Point(0, 0);
    
    enum Direction
    {
      Up = 0,
      Right,
      Down,
      Left
    }
    
    public void Input(IEnumerable<string> lines)
    {
      size = new Point(lines.First().Length, lines.Count());
      char[] map = string.Join("", lines).ToCharArray();
    
      for (int y = 0; y < size.Y; ++y)
        for (int x = 0; x < size.X; ++x)
        {
          int pos = y * size.X + x;
          char at = map[pos];
          if (at == '#')
            obstructions.Add(new Point(x, y));
          else if (at == '^')
            guard = new Point(x, y);
        }
    }
    
    List<Point> path = new List<Point>();
    public void PreCalc()
    {
      path = WalkArea().path.Distinct().ToList();
    }
    
    public void Part1()
    {
      Console.WriteLine($"Visited {path.Count} points");
    }
    public void Part2()
    {
      int loopPoints = path.AsParallel().Where(p => !p.Equals(guard) && WalkArea(p).loop).Count();
      Console.WriteLine($"Valid loop points: {loopPoints}");
    }
    
    (IEnumerable<Point> path, bool loop) WalkArea(Point? obstruction = null)
    {
      HashSet<(Point, Direction)> loopDetect = new HashSet<(Point, Direction)>();
    
      Point at = guard;
      Direction dir = Direction.Up;
      while (true)
      {
        if (!loopDetect.Add((at, dir)))
          return (loopDetect.Select(p => p.Item1), true);
    
        Point next = at;
        switch(dir)
        {
        case Direction.Up: next += new Point(0, -1); break;
        case Direction.Right: next += new Point(1, 0); break;
        case Direction.Down: next += new Point(0, 1); break;
        case Direction.Left: next += new Point(-1, 0); break;
        }
    
        if (next.X < 0 || next.Y < 0 || next.X >= size.X || next.Y >= size.Y)
          break;
        else if (obstructions.Contains(next) || (obstruction?.Equals(next) ?? false))
          dir = (Direction)(((int)dir + 1) % 4);
        else
          at = next;
      }
    
      return (loopDetect.Select(p => p.Item1), false);
    }
    
  • VegOwOtenks@lemmy.world
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    18 days ago

    Haskell

    This one was fun, I think I wrote my first lazy infinite loop I cancel out at runtime, lost some time because I had misread the requirements on turning right.

    Runs in 45 seconds on my Laptop in power-saver mode, which isn’t very fast I fear.

    import Control.Arrow hiding (first, second)
    
    import Data.Map (Map)
    import Data.Set (Set)
    import Data.Bifunctor
    
    import qualified Data.Array.Unboxed as Array
    import qualified Data.List as List
    import qualified Data.Set as Set
    import Data.Array.Unboxed (UArray)
    
    parse :: String -> (UArray (Int, Int) Char, (Int, Int))
    parse s = (a, p)
            where
                    p = Array.indices 
                            >>> filter ((a Array.!) >>> (== '^'))
                            >>> head
                            $ a
                    a = Array.listArray ((1, 1), (n, m)) . filter (/= '\n') $ s
                    l = lines s
                    (n, m) = (length . head &&& pred . length) l
    
    rotate90 d@(-1, 0) = (0, 1)
    rotate90 d@(0,  1) = (1, 0)
    rotate90 d@(1,  0) = (0, -1)
    rotate90 d@(0, -1) = (-1, 0)
    
    walkGuard :: (UArray (Int, Int) Char) -> (Int, Int) -> (Int, Int) -> [((Int, Int), (Int, Int))]
    walkGuard a p d@(dy, dx)
            | not isInBounds                  = []
            | (maybe ' ' id tileAhead) == '#' = (p, d) : walkGuard a p rotatedDirection
            | otherwise                       = (p, d) : walkGuard a updatedPosition d
            where
                    isInBounds = Array.inRange (Array.bounds a) p
                    updatedPosition = bimap (+dy) (+dx) p
                    tileAhead = a Array.!? updatedPosition
                    rotatedDirection = rotate90 d
    
    ruleGroup :: Eq a => (a, b) -> (a, b') -> Bool
    ruleGroup = curry (uncurry (==) <<< fst *** fst)
                    
    arrayDisplay a = Array.indices
            >>> List.groupBy ruleGroup
            >>> map (map (a Array.!))
            >>> unlines
            $ a
    
    walkedPositions a p d = walkGuard a p 
            >>> map fst
            >>> Set.fromList
            $ d
    
    isLoop = isLoop' Set.empty
    isLoop' _ [] = False
    isLoop' s (l:ls)
            | l `Set.member` s = True
            | otherwise = isLoop' (Set.insert l s) ls
    
    part1 (a, p) = walkedPositions a p
            >>> length
            $ (-1, 0)
    part2 (a, p) = walkedPositions a p
            >>> Set.toList
            >>> map (, '#')
            >>> map (:[])
            >>> map (a Array.//)
            >>> map (\ a' -> walkGuard a' p (-1, 0))
            >>> filter (isLoop)
            >>> length
            $ (-1, 0)
    
    main = getContents >>= print . (part1 &&& part2) . parse
    
  • Pyro@programming.dev
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    18 days ago

    Python

    Part 1: Simulate the guard’s walk, keeping track of visited positions
    Part 2: Semi brute-force. Try to place an obstacle at every valid position in the guard’s original path and see if it leads to a loop.

    import os
    from collections import defaultdict
    
    # paths
    here = os.path.dirname(os.path.abspath(__file__))
    filepath = os.path.join(here, 'input.txt')
    
    # read input
    with open(filepath, mode='r', encoding='utf8') as f:
        data = f.read()
    rows = data.splitlines()
    
    # bounds
    m = len(rows)
    n = len(rows[0])
    
    # directions following 90 degree clockwise turns
    #   up, right, down, left
    DIRECTIONS = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # find position of guard
    guard_i, guard_j = -1, -1
    for i in range(m):
        for j in range(n):
            if rows[i][j] == '^':
                guard_i, guard_j = i, j
                break
        if guard_i != -1:
            break
    
    
    def part1(guard_i, guard_j):
        # keep track of visited positions
        visited = set()
        visited.add((guard_i, guard_j))
    
        dir_idx = 0     # current direction index
    
        # loop while guard is in map
        while True:
            delta_i, delta_j = DIRECTIONS[dir_idx]
            next_gi, next_gj = guard_i + delta_i, guard_j + delta_j   # next pos
            
            # if out of bounds, we are done
            if not (0 <= next_gi < m) or not (0 <= next_gj < n):
                break
            # change direction when obstacle encountered
            if rows[next_gi][next_gj] == "#":
                dir_idx = (dir_idx + 1) % 4
                continue
            # update position and visited
            guard_i, guard_j = next_gi, next_gj
            visited.add((guard_i, guard_j))
    
        print(f"{len(visited)=}")
    
    
    def part2(guard_i, guard_j):
        # keep track of visited positions
        visited = set()
        visited.add((guard_i, guard_j))
    
        dir_idx = 0 # current direction index
        loops = 0   # loops encountered
    
        # walk through the path
        while True:
            delta_i, delta_j = DIRECTIONS[dir_idx]
            next_gi, next_gj = guard_i + delta_i, guard_j + delta_j # next pos
            
            # if out of bounds, we are done
            if not (0 <= next_gi < m) or not (0 <= next_gj < n):
                break
            # change direction when obstacle encountered
            if rows[next_gi][next_gj] == "#":
                dir_idx = (dir_idx + 1) % 4
                continue
            # if a position is not already in path,
            # put a obstacle there and see if guard will loop
            if (next_gi, next_gj) not in visited and willLoop(guard_i, guard_j, dir_idx):
                loops += 1
            # update position and visited
            guard_i, guard_j = next_gi, next_gj
            visited.add((guard_i, guard_j))
        
        print(f"{loops=}")
    
    # used in part 2
    # returns whether placing an obstacle on next pos causes a loop or not
    def willLoop(guard_i, guard_j, dir_idx) -> bool:
        # obstacle pos
        obs_i, obs_j = guard_i + DIRECTIONS[dir_idx][0], guard_j + DIRECTIONS[dir_idx][1]
    
        # keep track of visited pos and the direction of travel
        visited: defaultdict[tuple[int, int], list[int]] = defaultdict(list)
        visited[(guard_i, guard_j)].append(dir_idx)
        
        # walk until guard exits map or loops
        while True:
            delta_i, delta_j = DIRECTIONS[dir_idx]
            next_gi, next_gj = guard_i + delta_i, guard_j + delta_j # next pos
            
            # if out of bounds, no loop
            if not (0 <= next_gi < m) or not (0 <= next_gj < n):
                return False
            # change direction when obstacle encountered
            if rows[next_gi][next_gj] == "#" or (next_gi == obs_i and next_gj == obs_j):
                dir_idx = (dir_idx + 1) % 4
                continue
            # we are looping if we encounter a visited pos in a visited direction
            if (next_gi, next_gj) in visited and dir_idx in visited[(next_gi, next_gj)]:
                return True
            
            # update position and visited
            guard_i, guard_j = next_gi, next_gj        
            visited[(guard_i, guard_j)].append(dir_idx)
    
    
    part1(guard_i, guard_j)
    part2(guard_i, guard_j)
    
    
      • Deebster@programming.dev
        link
        fedilink
        arrow-up
        3
        ·
        edit-2
        17 days ago

        My rust code ran in 6s on my phone (Samsung A35 running under Termux). When I’m back at a computer it’d be interesting to compare times properly.

        • CameronDev@programming.devOPM
          link
          fedilink
          arrow-up
          1
          ·
          edit-2
          17 days ago

          I got mine down to 3s, but it wasn’t a very smart loop detection. All I did was count steps and stop after 10000. The 9 second run was 100000 steps, which is obviously a bit excessive.

          Does save iterating over the list of past visits, so probably a good shortcut.

        • CameronDev@programming.devOPM
          link
          fedilink
          arrow-up
          2
          ·
          17 days ago

          How did you detect loops? I just ran for 100000 steps to see if I escaped, got my time down to 3s by doing only 10000 steps.

          • TunaCowboy@lemmy.world
            link
            fedilink
            arrow-up
            2
            ·
            edit-2
            17 days ago

            I added each visited position/direction to a set, and when a ‘state’ is reached again you have entered a loop:

            v = set()
            while t[g.r][g.c] != 'X':
                state = (g.r, g.c, g.d)
                if state in v:
                    acc += 1
                    break
                v.add(state)
                g.move(t)
            

            You can view my full solution here.

          • Leavingoldhabits@lemmy.world
            link
            fedilink
            arrow-up
            2
            ·
            17 days ago

            Not who you asked but: I save coordinates and direction into a vector each time the guard faces a #. Also every time the guard faces a #, I check if the position exists in the vector, if true, it’s an infinite loop. 78ms rust aolution.

            • CameronDev@programming.devOPM
              link
              fedilink
              arrow-up
              1
              ·
              17 days ago

              That’s probably quite optimal, compared with checking every state in the path, or running off a fixed number of steps

      • iAvicenna@lemmy.world
        link
        fedilink
        arrow-up
        1
        ·
        edit-2
        17 days ago

        I did a similar approach (place obstacles on guards path). Takes about 80s 10-15s in 11th Gen Intel® Core™ i7-11800H. Motivated by the code above, I also restricted the search to start right before the obstacle rather than the whole path which took it down from 80s to 10-15s

  • Gobbel2000@programming.dev
    link
    fedilink
    arrow-up
    4
    ·
    18 days ago

    Rust

    In part 2 it took me some time to figure out that I cannot immediately move after turning, but then it worked fairly well. As a slight optimization I check only the places that were visited without obstacles (the solution from part 1). With this, part 2 takes 52ms.

    Solution
    use euclid::default::{Point2D, Vector2D};
    use euclid::vec2;
    
    fn parse(input: String) -> (Vec<Vec<bool>>, Point2D<i32>) {
        let mut field = Vec::new();
        let mut start = Point2D::zero();
        for (y, line) in input.lines().enumerate() {
            let mut row = Vec::new();
            for (x, c) in line.chars().enumerate() {
                row.push(c == '#');
                if c == '^' {
                    start = Point2D::new(x, y).to_i32();
                }
            }
            field.push(row);
        }
        (field, start)
    }
    
    const DIRS: [Vector2D<i32>; 4] = [vec2(0, -1), vec2(1, 0), vec2(0, 1), vec2(-1, 0)];
    
    fn visited(field: &[Vec<bool>], start: Point2D<i32>) -> Vec<Vec<bool>> {
        let width = field[0].len();
        let height = field.len();
        let mut visited = vec![vec![false; width]; height];
        // Start up, then turn right
        let mut dir = 0;
        let mut pos = start;
        loop {
            visited[pos.y as usize][pos.x as usize] = true;
            let next = pos + DIRS[dir];
            // Guard leaves area
            if next.x < 0 || next.y < 0 || next.x >= width as i32 || next.y >= height as i32 {
                break;
            }
            // Path blocked
            if field[next.y as usize][next.x as usize] {
                dir = (dir + 1) % 4; // Turn right, don't move yet
            } else {
                pos = next
            }
        }
        visited
    }
    
    fn part1(input: String) {
        let (field, start) = parse(input);
        let count = visited(&field, start)
            .iter()
            .map(|r| r.iter().map(|b| u32::from(*b)).sum::<u32>())
            .sum::<u32>();
        println!("{count}")
    }
    
    fn is_loop(field: &[Vec<bool>], start: Point2D<i32>) -> bool {
        let width = field[0].len();
        let height = field.len();
        let mut visited = vec![vec![0; width]; height];
    
        // Start up, then turn right
        let mut dir = 0;
        let mut pos = start;
        loop {
            // Loop detected
            if visited[pos.y as usize][pos.x as usize] & (1 << dir) > 0 {
                break true;
            }
            // Record all walked directions at all fields
            visited[pos.y as usize][pos.x as usize] |= 1 << dir;
            let next = pos + DIRS[dir];
            // Guard leaves area
            if next.x < 0 || next.y < 0 || next.x >= width as i32 || next.y >= height as i32 {
                break false;
            }
            // Path blocked
            if field[next.y as usize][next.x as usize] {
                dir = (dir + 1) % 4 // Turn right, don't move yet
            } else {
                pos = next
            }
        }
    }
    
    fn part2(input: String) {
        let (mut field, start) = parse(input);
        let width = field[0].len();
        let height = field.len();
        let normal_visited = visited(&field, start); // Part 1 solution
        let mut count = 0;
        for x in 0..width {
            for y in 0..height {
                // Only check places that are visited without any obstacles, and don't check start
                if normal_visited[y][x] && !(x as i32 == start.x && y as i32 == start.y) {
                    field[y][x] = true; // Set obstacle
                    count += is_loop(&field, start) as u32;
                    field[y][x] = false; // Remove obstacle
                }
            }
        }
        println!("{count}");
    }
    
    util::aoc_main!();
    

    also on github

  • wer2@lemm.ee
    link
    fedilink
    arrow-up
    4
    ·
    17 days ago

    Lisp

    Brute forced part 2, but got a lot of reuse from part 1.

    Part 1 and 2
    
    (defvar *part1* "inputs/day06-part1")
    (defvar *part1-test* "inputs/day06-part1-test")
    
    (defstruct move x y direction)
    
    (defstruct guard direction x y (moves (make-hash-table :test 'equalp)))
    
    (defun convert-direction (g)
      (case g
        (^ 'up)
        (> 'right)
        (< 'left)
        (v 'down)))
    
    
    (defun find-guard (map)
      (destructuring-bind (rows cols) (array-dimensions map)
        (loop for j from 0 below rows
              do (loop for i from 0 below cols
                       for v = (aref  map j i)
                       when (not (or (eql '|.| v) (eql '|#| v)))
                         do (return-from find-guard (make-guard :direction (convert-direction v) :x i :y j ))))))
    
    (defun turn-guard (guard)
      (case (guard-direction guard)
        (UP (setf (guard-direction guard) 'RIGHT))
        (DOWN (setf (guard-direction guard) 'LEFT))
        (LEFT (setf (guard-direction guard) 'UP))
        (RIGHT (setf (guard-direction guard) 'DOWN))))
    
    (defun on-map (map x y)
      (destructuring-bind (rows cols) (array-dimensions map)
        (and (>= x 0) (>= y 0)
             (< y rows) (< x cols))))
    
    (defun mark-guard (map guard)
      (setf (aref map (guard-y guard) (guard-x guard)) 'X))
    
    (defun next-pos (guard)
      (case (guard-direction guard)
        (UP (list (guard-x guard) (1- (guard-y guard))))
        (DOWN (list (guard-x guard) (1+ (guard-y guard))))
        (LEFT (list (1- (guard-x guard)) (guard-y guard)))
        (RIGHT (list (1+ (guard-x guard)) (guard-y guard)))))
    
    (defun move-guard (map guard)
      (destructuring-bind (x y) (next-pos guard)
        (if (on-map map x y)
            (if (eql '|#| (aref map y x))
                (turn-guard guard)
                (progn (setf (guard-x guard) x)
                       (setf (guard-y guard) y))) 
            (setf (guard-direction guard) nil))))
    
    (defun run-p1 (file) 
      (let* ((map (list-to-2d-array (read-file file #'to-symbols)))
             (guard (find-guard map)))
        (mark-guard map guard)
        (loop while (guard-direction guard)
              do (mark-guard map guard)
              do (move-guard map guard))
        (destructuring-bind (rows cols) (array-dimensions map)
          (loop for y from 0 below rows sum (loop for x from 0 below cols count (eql (aref map y x) 'X))))))
    
    (defun save-move (guard move)
      (setf (gethash move (guard-moves guard)) t))
    
    (defun reset-moves (guard)
      (setf (guard-moves guard) nil))
    
    (defun is-loop (x y map original-guard)
      ;; can only set new blocks in blank spaces
      (unless (eql '|.| (aref map y x)) (return-from is-loop nil))
      (let ((guard (copy-guard original-guard)))
        ;; save the initial guard position
        (save-move guard (make-move :x (guard-x guard) :y (guard-y guard) :direction (guard-direction guard)))
        ;; set the "new" block
        (setf (aref map y x) '|#|)
        ;; loop and check for guard loops
        (let ((result
                (loop
                  while (move-guard map guard)
                  for move = (make-move :x (guard-x guard) :y (guard-y guard) :direction (guard-direction guard))
                  ;; if we have seen the move before, then it is a loop
                  if (gethash move (guard-moves guard))
                    return t
                  else
                    do (save-move guard move)
                  finally
                     (return nil))))
    
          ;; reset initial position
          (setf (aref map y x) '|.|)
          (clrhash (guard-moves guard))
          result)))
    
    
    (defun run-p2 (file) 
      (let* ((map (list-to-2d-array (read-file file #'to-symbols)))
             (guard (find-guard map)))
        
        (destructuring-bind (rows cols) (array-dimensions map)
          (loop for y from 0 below rows
                sum (loop for x from 0 below cols
                          count (is-loop x y map guard)))
          )))
    
    
  • hades@lemm.ee
    link
    fedilink
    arrow-up
    4
    ·
    18 days ago

    C#

    public class Day06 : Solver
    {
      private readonly (int, int)[] directions = [
        (0, -1), (1, 0), (0, 1), (-1, 0)
        ];
    
      private ImmutableArray<string> data;
      private int width, height;
      private ImmutableHashSet<(int, int)> guard_path;
      private int start_x, start_y;
    
      public void Presolve(string input) {
        data = input.Trim().Split("\n").ToImmutableArray();
        width = data[0].Length;
        height = data.Length;
        for (int i = 0; i < width; i++) {
          for (int j = 0; j < height; j++) {
            if (data[j][i] == '^') {
              start_x = i;
              start_y = j;
              break;
            }
          }
        }
        guard_path = Walk().Path.ToImmutableHashSet();
      }
    
      private bool IsWithinBounds(int x, int y) => x >= 0 && y >= 0 && x < width && y < height;
      
      private (HashSet<(int, int)> Path, bool IsLoop) Walk((int, int)? obstacle = null) {
        int obstacle_x = obstacle?.Item1 ?? -1;
        int obstacle_y = obstacle?.Item2 ?? -1;
        int direction = 0;
        int x = start_x;
        int y = start_y;
        bool loop = false;
        HashSet<(int, int, int)> positions = new();
        while (IsWithinBounds(x, y)) {
          if (positions.Contains((x, y, direction))) {
            loop = true;
            break;
          }
          positions.Add((x, y, direction));
          int nx = x + directions[direction].Item1;
          int ny = y + directions[direction].Item2;
    
          while (IsWithinBounds(nx, ny) && (data[ny][nx] == '#' || (nx == obstacle_x && ny == obstacle_y))) {
            direction = (direction + 1) % 4;
            nx = x + directions[direction].Item1;
            ny = y + directions[direction].Item2;
          }
          x = nx;
          y = ny;
        }
        return (positions.Select(position => (position.Item1, position.Item2)).ToHashSet(), loop);
      }
    
      public string SolveFirst() => guard_path.Count.ToString();
      public string SolveSecond() => guard_path
        .Where(position => position != (start_x, start_y))
        .Where(position => Walk(position).IsLoop)
        .Count().ToString();
    }
    
  • Deebster@programming.dev
    link
    fedilink
    arrow-up
    3
    ·
    edit-2
    17 days ago

    Rust

    Only part 1 because I’m meant to be leaving for a holiday in a few hours and haven’t packed yet. Part two looks simple enough to add:

    part 2 plan

    Change seen positions set to include direction, if pos+dir already seen then it’s a loop. Test all spaces.

    Edit: I did the change on my phone (which was painful).

    use std::{collections::HashSet, fs, str::FromStr};
    
    use color_eyre::eyre::{Report, Result};
    
    type GridPosition = usize;
    
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
    enum Direction {
        N,
        E,
        S,
        W,
    }
    
    impl Direction {
        fn clockwise(&self) -> Self {
            match self {
                Direction::N => Direction::E,
                Direction::E => Direction::S,
                Direction::S => Direction::W,
                Direction::W => Direction::N,
            }
        }
    }
    
    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
    enum Thing {
        Guard(Direction),
        Obstruction,
        Space,
    }
    
    #[derive(Debug, PartialEq, Eq)]
    struct LabMap {
        grid: Vec<Thing>,
        width: usize,
        height: usize,
    }
    
    impl FromStr for LabMap {
        type Err = Report;
    
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            let grid = s
                .chars()
                .filter_map(|ch| {
                    use Thing::*;
                    match ch {
                        '^' => Some(Guard(Direction::N)),
                        '>' => Some(Guard(Direction::E)),
                        'v' => Some(Guard(Direction::S)),
                        '<' => Some(Guard(Direction::W)),
                        '#' => Some(Obstruction),
                        '.' => Some(Space),
                        '\n' => None,
                        _ => unreachable!(),
                    }
                })
                .collect::<Vec<_>>();
            let width = s
                .chars()
                .position(|ch| ch == '\n')
                .ok_or_else(|| Report::msg("grid width cannot be zero, or one line"))?;
            let height = grid.len() / width;
            Ok(Self {
                grid,
                width,
                height,
            })
        }
    }
    
    impl LabMap {
        fn neighbour(&self, i: GridPosition, dir: Direction) -> Option<GridPosition> {
            let width = self.width;
            let length = self.grid.len();
            use Direction::*;
            match dir {
                N if i >= width => Some(i - width),
                E if i % width != width - 1 => Some(i + 1),
                S if i + width < length => Some(i + width),
                W if i % width != 0 => Some(i - 1),
                _ => None,
            }
        }
    
        fn guard_pos(&self) -> Option<(GridPosition, Direction)> {
            self.grid
                .iter()
                .enumerate()
                .filter_map(|(pos, &thing)| match thing {
                    Thing::Guard(dir) => Some((pos, dir)),
                    _ => None,
                })
                .next()
        }
    
        fn path_len(&self) -> usize {
            let mut positions = HashSet::new();
            let mut next = self.guard_pos();
            while let Some((pos, dir)) = next {
                positions.insert(pos);
    
                next = self.neighbour(pos, dir).map(|npos| match self.grid[npos] {
                    Thing::Space | Thing::Guard(_) => (npos, dir),
                    Thing::Obstruction => (pos, dir.clockwise()),
                });
            }
            positions.len()
        }
    
        fn num_loops(&self) -> usize {
            (0..self.grid.len())
                .filter(|&pos| matches!(self.grid[pos], Thing::Space))
                .map(|pos| {
                    let mut grid = self.grid.clone();
                    grid[pos] = Thing::Obstruction;
                    LabMap {
                        grid,
                        width: self.width,
                        height: self.height,
                    }
                })
                .filter(LabMap::is_loop)
                .count()
        }
    
        fn is_loop(&self) -> bool {
            let mut positions = HashSet::new();
            let mut next = self.guard_pos();
            while let Some((pos, dir)) = next {
                let is_new = positions.insert((pos, dir));
                if !is_new {
                    return true;
                }
    
                next = self.neighbour(pos, dir).map(|npos| match self.grid[npos] {
                    Thing::Space | Thing::Guard(_) => (npos, dir),
                    Thing::Obstruction => (pos, dir.clockwise()),
                });
            }
            false
        }
    }
    
    fn part1(filepath: &str) -> Result<usize> {
        let input = fs::read_to_string(filepath)?;
        let map = LabMap::from_str(&input)?;
        Ok(map.path_len())
    }
    
    fn part2(filepath: &str) -> Result<usize> {
        let input = fs::read_to_string(filepath)?;
        let map = LabMap::from_str(&input)?;
        Ok(map.num_loops())
    }
    
    fn main() -> Result<()> {
        color_eyre::install()?;
    
        println!("Part 1: {}", part1("input.txt")?);
        println!("Part 2: {}", part2("input.txt")?);
        Ok(())
    }
    
    
  • JRaccoon@discuss.tchncs.de
    link
    fedilink
    English
    arrow-up
    3
    ·
    18 days ago

    TypeScript

    The code
    import fs from "fs";
    
    enum GuardDirection {
        UP = "^",
        RIGHT = ">",
        DOWN = "v",
        LEFT = "<",
    };
    
    const originalGrid: string[][] = fs.readFileSync("./06/input.txt", "utf-8")
        .split(/[\r\n]+/)
        .filter(Boolean)
        .map(row => row.split(""))
        .map(row => row.map(char => char === "." ? "" : char));
    
    const gridWidth = originalGrid[0].length;
    const startingPosition = getStartPosition(originalGrid);
    const startingDirection = originalGrid[startingPosition.y][startingPosition.x] as GuardDirection;
    
    originalGrid[startingPosition.y][startingPosition.x] = "";
    
    // Part 1
    const grid = getGridCopy(originalGrid);
    doGuardMovement(grid);
    console.info("Part 1: " + grid.flatMap(row => row).filter(cell => cell.startsWith("X")).length);
    
    // Part 2
    let part2Result = 0;
    for (let y = 0; y < originalGrid.length; y++) {
        for (let x = 0; x < originalGrid.length; x++) {
            if (!originalGrid[y][x].length && grid[y][x].startsWith("X")) {
                // Cell is empty AND was visited during part 1 => Should place an obstacle here
                const gridCopy = getGridCopy(originalGrid);
                gridCopy[y][x] = "#";
                if (!doGuardMovement(gridCopy)) { part2Result++; }
            }
        }
    }
    console.info("Part 2: " + part2Result);
    
    function doGuardMovement(grid: string[][]): boolean { // Returns false if loop detected
        let [x, y, guard] = [startingPosition.x, startingPosition.y, startingDirection];
    
        while (y >= 0 && y < grid.length && x >= 0 && x < gridWidth) {
            // Check for loop
            if (grid[y][x].length > 3) { return false; }
            grid[y][x] += "X"; // Mark each visitation with X
            
            // If there is something directly in front of you, turn right 90 degrees
            if (guard === GuardDirection.UP && y > 0 && grid[y - 1][x] === "#") { guard = GuardDirection.RIGHT; }
            else if (guard === GuardDirection.RIGHT && x < gridWidth - 1 && grid[y][x + 1] === "#") { guard = GuardDirection.DOWN; }
            else if (guard === GuardDirection.DOWN && y < grid.length - 1 && grid[y + 1][x] === "#") { guard = GuardDirection.LEFT; }
            else if (guard === GuardDirection.LEFT && x > 0 && grid[y][x - 1] === "#") { guard = GuardDirection.UP; }
        
            // Otherwise, take a step forward
            else if (guard === GuardDirection.UP) { y--; }
            else if (guard === GuardDirection.RIGHT) { x++; }
            else if (guard === GuardDirection.DOWN) { y++; }
            else if (guard === GuardDirection.LEFT) { x--; }
            
            else { throw new Error("Something went wrong"); }
        }
    
        return true; // Exited the grid
    }
    
    function getGridCopy(grid: string[][]): string[][] {
        return grid.map(row => [...row]);
    }
    
    function getStartPosition(grid: string[][]): {x: number, y: number} {
        for (let y = 0; y < grid.length; y++) {
            for (let x = 0; x < grid.length; x++) {
                if (Object.values(GuardDirection).some(char => grid[y][x] === char)) {
                    return {x, y};
                }
            }
        }
    
        throw new Error("Could not find starting position");
    }
    
  • Leavingoldhabits@lemmy.world
    link
    fedilink
    arrow-up
    3
    ·
    edit-2
    17 days ago

    Rust

    This one was the first real think for this year, but I ended up brute forcing it, placing a ‘#’ in every position and checking. part 2 runs in about 380ms 78ms (after reducing the amount ‘#’-placements to only where the guard walks) on my 2011 core i-7, so I’m happy, even though it feels like I could have been smarter.

    Part 1 Part 2

    • ximtor@lemm.ee
      link
      fedilink
      arrow-up
      2
      ·
      edit-2
      17 days ago

      I am doing the same principle brute force but it takes ~7 seconds oO

      Is using a HashSet<(Pos, Dir)> for the loop detection so expensive? My CPU shouldn’t be THAT bad…

      Part one around 7ms.

      Also curious that i have not seen someone mention a more efficient approach, there gotta be one?

      • sjmulder@lemmy.sdf.org
        link
        fedilink
        arrow-up
        3
        ·
        edit-2
        17 days ago

        I draw ^>v< characters on the grid while walking, so then it’s a direct array lookup (instead of a hashtable). The representation could be better though, some kind of bitmask would beat checking against a bunch of characters.

        • ximtor@lemm.ee
          link
          fedilink
          arrow-up
          1
          ·
          17 days ago

          I dont change the map, i just record the steps in the hashtable. But maybe drawing on the map is indeed shaving some time off, thanks for the input :)

          • sjmulder@lemmy.sdf.org
            link
            fedilink
            arrow-up
            1
            ·
            16 days ago

            It probably won’t matter a whole deal but array indexing involves no comparisons or searches. And I found it convenient too!

      • Leavingoldhabits@lemmy.world
        link
        fedilink
        arrow-up
        2
        ·
        edit-2
        17 days ago

        I’d like to see your solution in total. I’m not too familiar with the nuts and bolts, but hash set is quite a bit more expensive than a simple vector, there’s a bunch of overhead incurred when executing the hashing and placing of the data, and when repeating a few thousand times it sure adds up. My part one hovers around 600 microseconds.

        • ximtor@lemm.ee
          link
          fedilink
          arrow-up
          2
          ·
          17 days ago

          I’d like to see your solution in total.

          I set it up a bit like a game, https://pastebin.com/FGA6E7fA

          My part one hovers around 600 microseconds.

          Ohhh, that says my part 1 is slow already, i was sure my approach for 2 was the problem. Good to know!

      • misty@lemmy.world
        link
        fedilink
        arrow-up
        2
        ·
        edit-2
        17 days ago

        I created rows and cols vecs that keep places of blocks. When moving, I binary search the row or col, find the block that stops me. So moving whole sections at once. Otherwise used HashSet of pos and dir like you. Also in part 2, place the new block only on the path I take in part1. Part 2 is 26ms.

        code

        • ximtor@lemm.ee
          link
          fedilink
          arrow-up
          2
          ·
          17 days ago

          The binary search sounds smart, would reduce the pathing quite a bit i guess :)

          Part 2 i approached quite the same i think, was only a couple lines of code additionally. But running 5ms 5000 times is also gonna take a while…

      • ximtor@lemm.ee
        link
        fedilink
        arrow-up
        1
        ·
        17 days ago

        Alright, I completely forgot about --release because i normally use just to run my stuff. That brings part 2 down to around 400ms, i am okay with that for now :D

  • Rin@lemm.ee
    link
    fedilink
    arrow-up
    2
    ·
    17 days ago

    TypeScript

    Solution
    import { AdventOfCodeSolutionFunction } from "./solutions";
    
    
    export const check_coords = (grid: Grid, x: number, y: number) => {
        return y >= grid.length ||
            y < 0 ||
            x >= grid[y].length ||
            x < 0
    }
    
    export enum Direction {
        UP,
        UP_RIGHT,
        RIGHT,
        BOTTOM_RIGHT,
        BOTTOM,
        BOTTOM_LEFT,
        LEFT,
        UP_LEFT,
    };
    
    /**
     * This function should return true if it wants the search function to continue
     */
    export type SearchFindFunction = (currChar: string, x: number, y: number) => boolean;
    
    export type Grid = Array<Array<string>>;
    
    export enum SearchExitReason {
        OUT_OF_BOUNDS,
        FUNCTION_FINISHED,
        INVALID_DIRECTION,
    }
    
    export const search_direction = (grid: Grid, x: number, y: number, direction: Direction, find: SearchFindFunction): SearchExitReason => {
        // invalid coords
        if (check_coords(grid, x, y))
            return SearchExitReason.OUT_OF_BOUNDS;
    
        // search failed
        if (!find(grid[y][x], x, y))
            return SearchExitReason.FUNCTION_FINISHED;
    
        switch (direction) {
            case Direction.UP:
                return search_direction(grid, x, y - 1, direction, find);
    
            case Direction.UP_RIGHT:
                return search_direction(grid, x + 1, y - 1, direction, find);
    
            case Direction.RIGHT:
                return search_direction(grid, x + 1, y, direction, find);
    
            case Direction.BOTTOM_RIGHT:
                return search_direction(grid, x + 1, y + 1, direction, find);
    
            case Direction.BOTTOM:
                return search_direction(grid, x, y + 1, direction, find);
    
            case Direction.BOTTOM_LEFT:
                return search_direction(grid, x - 1, y + 1, direction, find);
    
            case Direction.LEFT:
                return search_direction(grid, x - 1, y, direction, find);
    
            case Direction.UP_LEFT:
                return search_direction(grid, x - 1, y - 1, direction, find);
    
            default:
                return SearchExitReason.INVALID_DIRECTION;
        }
    }
    
    export const gridSearch = (grid: Grid, st: SearchFindFunction): [x: number, y: number] => {
        for (let y = 0; y < grid.length; y++) {
            const row = grid[y];
            for (let x = 0; x < row.length; x++) {
                const char = row[x];
                if (!st(char, x, y))
                    return [x, y];
            }
        }
    
        return [-1, -1];
    }
    
    export const makeGridFromMultilineString =
        (input: string) => input.split("\n").map(st => st.trim()).map(v => v.split(""));
    
    export const Duplicate2DArray = <T>(array: Array<Array<T>>) => {
        return [...array.map((item) => [...item])];
    }
    
    
    
    const NextDirection = (dir: Direction) => {
        switch (dir) {
            case Direction.UP:
                return Direction.RIGHT;
            case Direction.RIGHT:
                return Direction.BOTTOM;
            case Direction.BOTTOM:
                return Direction.LEFT;
            case Direction.LEFT:
                return Direction.UP;
            default:
                throw Error("Invalid direction");
        }
    }
    
    /**
     * @returns true if there are no loops
     */
    const NoLoops = (grid: Grid, x: number, y: number, dir: Direction) => {
        const visited = new Set<string>();
    
        /**
         * @returns True if not visited yet
         */
        const addToVisited = (x: number, y: number, dir: Direction) => {
            const log = `${x}:${y}:${dir}`;
    
            if (visited.has(log))
                return false;
    
            visited.add(log);
            return true;
        }
    
        let searchResult: SearchExitReason = SearchExitReason.FUNCTION_FINISHED;
        let res = true;
        let i = 0; // rate limited for API
        let [lastX, lastY] = [x, y];
        while (searchResult !== SearchExitReason.OUT_OF_BOUNDS && i++ < 10_000) {
            searchResult = search_direction(grid, lastX, lastY, dir, (ch, currX, currY) => {
                if (ch == "#")
                    return false;
    
                [lastX, lastY] = [currX, currY];
    
                res = addToVisited(currX, currY, dir);
                return res;
            });
    
            if (!res)
                break;
    
            dir = NextDirection(dir);
        }
    
        return res;
    }
    
    
    export const solution_6: AdventOfCodeSolutionFunction = (input) => {
        const grid = makeGridFromMultilineString(input);
        const visited = new Map<string, [x: number, y: number, dir: Direction, prevX: number, prevY: number]>();
        let [x, y] = gridSearch(grid, (ch) => ch !== "^");
        const [initialX, initialY] = [x, y];
        let dir: Direction = Direction.UP;
    
        const addToVisited = (visitedX: number, visitedY: number, dir: Direction) => {
            const loc = `${visitedX}:${visitedY}`;
            if (!visited.has(loc))
                visited.set(loc, [visitedX, visitedY, dir, x, y]);
        }
    
        addToVisited(x, y, dir);
    
        let res: SearchExitReason = SearchExitReason.FUNCTION_FINISHED;
        let i = 0; // rate limited for API
        while (res !== SearchExitReason.OUT_OF_BOUNDS && i++ < 10_000) {
            res = search_direction(grid, x, y, dir, (ch, currX, currY) => {
                if (ch == "#")
                    return false;
    
                addToVisited(currX, currY, dir);
                [x, y] = [currX, currY];
                return true;
            });
            dir = NextDirection(dir);
        }
    
        const part_1 = visited.size;
    
        // remove starting position for part 1
        visited.delete(`${initialX}:${initialY}`);
    
        let part_2 = 0;
        visited.forEach((v) => {
            const [visitedX, visitedY, visitedDirection, prevX, prevY] = v;
            const newGrid = Duplicate2DArray(grid);
            newGrid[visitedY][visitedX] = "#"; // add a block
    
            // look for loops
            if (!NoLoops(newGrid, prevX, prevY, visitedDirection))
                part_2++;
        });
    
        return {
            part_1, // 4656
            part_2, // 1575
        }
    }
    

    I’m so surprised this runs in ~3s, expected it to take like 60s (do I have supercomputer?). Solution was similar to Pyro’s in this thread as in it simulates the walk then places an obstacle in every possible position but I speed it up by starting just before the obstacle and looking towards it. Also, I reused some code from day 4 by tweaking it slightly. Thank you for the “S” tire Advent of Code puzzle. :)

  • janAkali@lemmy.one
    link
    fedilink
    English
    arrow-up
    2
    ·
    edit-2
    18 days ago

    Nim

    Not the prettiest code, but it runs in 3 seconds. For part 2 I just place an obstacle at every position guard visited in part 1.

    Edit: made step procedure more readable.

    type
      Vec2 = tuple[x,y: int]
      Dir = enum
        Up, Right, Down, Left
      Guard = object
        pos: Vec2
        dir: Dir
    
    proc step(guard: var Guard, map: seq[string]): bool =
      let next: Vec2 =
        case guard.dir
        of Up: (guard.pos.x, guard.pos.y-1)
        of Right: (guard.pos.x+1, guard.pos.y)
        of Down: (guard.pos.x, guard.pos.y+1)
        of Left: (guard.pos.x-1, guard.pos.y)
    
      if next.y < 0 or next.x < 0 or next.y > map.high or next.x > map[0].high:
        return false
      elif map[next.y][next.x] == '#':
        guard.dir = Dir((guard.dir.ord + 1) mod 4)
      else:
        guard.pos = next
      true
    
    proc solve(input: string): AOCSolution[int, int] =
      var map = input.splitLines()
      var guardStart: Vec2
      block findGuard:
        for y, line in map:
          for x, c in line:
            if c == '^':
              guardStart = (x, y)
              map[y][x] = '.'
              break findGuard
    
      var visited: HashSet[Vec2]
      block p1:
        var guard = Guard(pos: guardStart, dir: Up)
        while true:
          visited.incl guard.pos
          if not guard.step(map): break
        result.part1 = visited.len
    
      block p2:
        for (x, y) in visited - [guardStart].toHashSet:
          var loopCond: HashSet[Guard]
          var guard = Guard(pos: guardStart, dir: Up)
          var map = map
          map[y][x] = '#'
    
          while true:
            loopCond.incl guard
            if not guard.step(map): break
            if guard in loopCond:
              inc result.part2
              break
    

    Codeberg repo

  • proved_unglue@programming.dev
    link
    fedilink
    arrow-up
    2
    ·
    17 days ago

    Kotlin

    Not much inspiration. Brute forcing my way through today’s level.

    Solution
    typealias Grid = List<List<Char>>
    
    private val up: Char = '^'
    private val down: Char = 'v'
    private val left: Char = '<'
    private val right: Char = '>'
    private val obstacle: Char = '#'
    private val directions: Set<Char> = setOf(up, down, left, right)
    
    data class Position(
        var direction: Char,
        var row: Int,
        var col: Int,
        val visited: MutableSet<Pair<Int, Int>> = mutableSetOf(),
        val history: MutableSet<Triple<Char, Int, Int>> = mutableSetOf(),
    ) {
        override fun toString(): String = "Position(direction: $direction, position: ($row,$col))"
    }
    
    fun part1(input: String): Int {
        val grid: Grid = input.lines().map(String::toList)
        val position = findStartPosition(grid)
        while (!isEndPosition(position, grid)) {
            moveOrTurn(position, grid)
        }
        return position.visited.size
    }
    
    fun part2(input: String): Int {
        var loops = 0
        for (i in input.indices) {
            if (input[i] != '.') {
                continue
            }
            val sb = StringBuilder(input)
            sb.setCharAt(i, obstacle)
            val grid: Grid = sb.toString().lines().map(String::toList)
            val position = findStartPosition(grid)
            while (!isEndPosition(position, grid)) {
                moveOrTurn(position, grid)
                if (isLoop(position)) {
                    loops++
                    break
                }
            }
        }
        return loops
    }
    
    private fun findStartPosition(grid: Grid): Position {
        for (row in grid.indices) {
            for (col in grid[row].indices) {
                val c = grid[row][col]
                if (directions.contains(c)) {
                    val pos = Position(c, row, col)
                    pos.visited.add(Pair(row, col))
                    return pos
                }
            }
        }
        throw IllegalStateException("No start position found")
    }
    
    private fun isEndPosition(position: Position, grid: Grid): Boolean {
        return position.row == 0 || position.col == 0
                || position.row == grid.size - 1 || position.col == grid.size - 1
    }
    
    private fun isLoop(position: Position): Boolean {
        return position.history.contains(Triple(position.direction, position.row, position.col))
    }
    
    private fun moveOrTurn(position: Position, grid: Grid) {
        position.history.add(Triple(position.direction, position.row, position.col))
    
        when (position.direction) {
            up ->
                if (grid[position.row - 1][position.col] == obstacle)
                    position.direction = right
                else
                    position.row--
    
            right ->
                if (grid[position.row][position.col + 1] == obstacle)
                    position.direction = down
                else
                    position.col++
    
            down ->
                if (grid[position.row + 1][position.col] == obstacle)
                    position.direction = left
                else
                    position.row++
    
            left ->
                if (grid[position.row][position.col - 1] == obstacle)
                    position.direction = up
                else
                    position.col--
    
            else -> throw IllegalStateException("Invalid direction, cannot move")
        }
    
        position.visited.add(Pair(position.row, position.col))
    }
    
  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    17 days ago

    Dart

    Oof, simple rules can really trip you up if you don’t pay attention.

    This takes seconds to run so it’s clearly not the right approach, but it get the right answers, so…

    (edit) There’s an interesting range of times from others as well, so it probably only requires a little more attention to get the time down, but maybe not today…

    Click to reveal 60 lines of solution.
    import 'dart:math';
    import 'dart:math';
    import 'package:more/more.dart';
    
    var d4 = [Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0)];
    
    String safeGet(Point<int> p, List<List<String>> grid) =>
        (p.y.between(0, grid.length - 1) && p.x.between(0, grid.first.length - 1))
            ? grid[p.y][p.x]
            : '!';
    
    Point<int> findGuard(List<List<String>> grid) {
      for (var row in grid.indices()) {
        for (var col in grid.first.indices()) {
          if (grid[row][col] == '^') return Point(col, row);
        }
      }
      return Point(-1, -1); //!
    }
    
    Set<Point<int>> getTrack(Point<int> guard, List<List<String>> grid) =>
        checkPath(guard, grid).first.map((e) => e.first).toSet();
    
    // Check the path, returning ({(point, dir)}, did it end in a loop).
    (Set<(Point<int>, int)>, bool) checkPath(
        Point<int> guard0, List<List<String>> grid,
        {Point<int>? block}) {
      if (block != null) grid[block.y][block.x] = '#';
      var dir = 0;
      var guard = guard0;
      var track = <(Point<int>, int)>{};
      var isLoop = false;
      while (safeGet(guard, grid) != '!') {
        if (track.contains((guard, dir))) {
          isLoop = true;
          break;
        }
        track.add((guard, dir));
        var check = guard + d4[dir];
        if (safeGet(check, grid) == '#') {
          dir = (dir + 1) % 4;
        } else {
          guard += d4[dir];
        }
      }
      if (block != null) grid[block.y][block.x] = '.';
      return (track, isLoop);
    }
    
    part1(List<String> lines) {
      var grid = lines.map((e) => e.split('')).toList();
      return getTrack(findGuard(grid), grid).length;
    }
    
    part2(List<String> lines) {
      var grid = lines.map((e) => e.split('')).toList();
      var guard = findGuard(grid);
      return getTrack(guard, grid)
          .count((e) => checkPath(guard, grid, block: e).last);
    }
    
  • TunaCowboy@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    17 days ago

    python

    Takes around 10s on my machine. I came up 10 short at first for part two and then realized sometimes you have to turn multiple times to avoid an obstacle.

    solution
    from dataclasses import dataclass
    import aoc
    
    @dataclass
    class Guard():
        r: int = 0
        c: int = 0
        d: str = 'n'
    
        def move(self, lines):
            for _ in range(4):
                if self.d == 'n':
                    if lines[self.r - 1][self.c] == '#':
                        self.d = 'e'
                    else:
                        self.r -= 1
                        break
                elif self.d == 'e':
                    if lines[self.r][self.c + 1] == '#':
                        self.d = 's'
                    else:
                        self.c += 1
                        break
                elif self.d == 's':
                    if lines[self.r + 1][self.c] == '#':
                        self.d = 'w'
                    else:
                        self.r += 1
                        break
                elif self.d == 'w':
                    if lines[self.r][self.c - 1] == '#':
                        self.d = 'n'
                    else:
                        self.c -= 1
                        break
    
    def setup():
        lines = aoc.get_lines(6, padded=(True, 'X', 1))
        g = Guard()
        for row, l in enumerate(lines):
            for col, c in enumerate(l):
                if c == '^':
                    g.r, g.c = (row, col)
        s = (g.r, g.c)
        p = set()
        while lines[g.r][g.c] != 'X':
            p.add((g.r, g.c))
            g.move(lines)
        return (lines, g, s, p)
    
    def one():
        print(len(setup()[3]))
    
    def two():
        lines, g, s, p = setup()
        acc = 0
        for r, c in p:
            t = list(lines)
            ts = list(t[r])
            ts[c] = '#'
            t[r] = ''.join(ts)
            g.r, g.c, g.d = (s[0], s[1], 'n')
            v = set()
            while t[g.r][g.c] != 'X':
                st = (g.r, g.c, g.d)
                if st in v:
                    acc += 1
                    break
                v.add(st)
                g.move(t)
        print(acc)
    
    one()
    two()