Skip Navigation
Advent Of Code @programming.dev CameronDev @programming.dev

💂 - 2024 DAY 6 SOLUTIONS - 💂

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

40
40 comments

  • 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)

  • 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

  • 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

  • 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);
}

  • 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

  • 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();
}

  • 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

  • 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(())
}

  • 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");
}

  • 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)))
      )))

  • 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))
}

  • C

    Got super stumped on part 2. I'd add an obstacle for every tile on the path of part 1 but I kept getting wrong results, even after fixing some edge cases. Spent too much time looking at terminal dumps and mp4 visualisations.

    Eventually I gave up and wrote a for(y) for(x) loop, trying an obstacle in every possible tile, and that gave the correct answer. Even that brute force took only 2.5 ish seconds on my 2015 PC! But having that solution allowed me to narrow it down again to a reasonably efficient version similar to what I had before. Still I don't know where I went wrong the first time.

    Code 
    #include "common.h"

#define GZ 134

struct world { char g[GZ][GZ]; int x,y, dir; };

static const char carets[] = "^>v<";
static const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};

static inline char *ahead(struct world *w) {
    return &w->g[w->y+dy[w->dir]][w->x+dx[w->dir]]; }
static inline int visited(char t) { return t && strchr(carets, t); }
static inline int traversible(char t) { return t=='.' || visited(t); }

/* new tile, previously visited tile, in a loop, out of bounds */
enum { ST_NEW, ST_SEEN, ST_LOOP, ST_END };

static int
step(struct world *w)
{
	char *cell;
	int is_new;

	assert(w->x >= 0); assert(w->x < GZ);
	assert(w->y >= 0); assert(w->y < GZ);

	cell = &w->g[w->y][w->x];

	if (!traversible(*cell))	/* out of bounds? */
		return ST_END;
	while (*ahead(w) == '#')	/* turn if needed */
		w->dir = (w->dir +1) %4;
	if (*cell == carets[w->dir])	/* walked here same dir? */
		return ST_LOOP;

	is_new = *cell == '.';
	*cell = carets[w->dir];
	w->x += dx[w->dir];
	w->y += dy[w->dir];

	return is_new ? ST_NEW : ST_SEEN;
}

int
main(int argc, char **argv)
{
	static struct world w0,w1,w2;
	int p1=0,p2=0, x,y, r,i;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	for (y=1; y<GZ && fgets(w0.g[y]+1, GZ-1, stdin); y++)
		;

	for (y=0; y<GZ; y++)
	for (x=0; x<GZ; x++)
	for (i=0; i<4; i++)
		if (w0.g[y][x] == carets[i])
			{ w0.x=x; w0.y=y; w0.dir=i; goto found_start; }
found_start:
	w0.g[y][x] = '.';

	/* keep the clean copy of the grid (needed for part 2) */
	memcpy(&w1, &w0, sizeof(w1));

	/* part 1: trace the path and count unseen tiles */
	while ((r = step(&w1)) <= ST_SEEN)
		p1 += r == ST_NEW;

	/* part 2: try putting obstacles on each tile seen in p1 */
	for (y=0; y<GZ; y++)
	for (x=0; x<GZ; x++)
		if (visited(w1.g[y][x])) {
			memcpy(&w2, &w0, sizeof(w2));
			w2.g[y][x] = '#';
			while ((r = step(&w2)) <= ST_SEEN) ;
			p2 += r == ST_LOOP;
		}

	printf("06: %d %d\n", p1, p2);
	return 0;
}

    https://github.com/sjmulder/aoc/blob/master/2024/c/day06.c

  • 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. :)

  • 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

  • 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()

  • 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);
}

  • I'm not proud of it.

    I have a conjecture though, that any looping solution, obtained by adding one obstacle, would eventually lead to a rectangular loop. That may lead to a non brute-force solution. It's quite hard to prove rigorously though. (Maybe proving, that the loop has to be convex, which is an equivalent statement here, is easier? You can also find matrix representations of the guard's state changes, if that helps.)

    Maybe some of the more mathematically inclined people here can try proving or disproving that.

    Anyways, here is my current solution in **Kotlin**: 
    fun main() {
    fun part1(input: List<String>): Int {
        val puzzleMap = PuzzleMap.fromPuzzleInput(input)
        puzzleMap.simulateGuardPath()
        return puzzleMap.asIterable().indicesWhere { it is MapObject.Visited }.count()
    }

    fun part2(input: List<String>): Int {
        val puzzleMap = PuzzleMap.fromPuzzleInput(input)
        puzzleMap.simulateGuardPath()

        return puzzleMap.asIterable().indicesWhere { it is MapObject.Visited }.count {
            val alteredPuzzleMap = PuzzleMap.fromPuzzleInput(input)
            alteredPuzzleMap[VecNReal(it)] = MapObject.Obstacle()
            alteredPuzzleMap.simulateGuardPath()
        }
    }

    val testInput = readInput("Day06_test")
    check(part1(testInput) == 41)
    check(part2(testInput) == 6)

    val input = readInput("Day06")
    part1(input).println()
    part2(input).println()
}

enum class Orientation {
    NORTH, SOUTH, WEST, EAST;

    fun rotateClockwise(): Orientation {
        return when (this) {
            NORTH -> EAST
            EAST -> SOUTH
            SOUTH -> WEST
            WEST -> NORTH
        }
    }
    
    fun asVector(): VecNReal {
        return when (this) {
            NORTH -> VecNReal(listOf(0.0, 1.0))
            SOUTH -> VecNReal(listOf(0.0, -1.0))
            WEST -> VecNReal(listOf(-1.0, 0.0))
            EAST -> VecNReal(listOf(1.0, 0.0))
        }
    }
}

class PuzzleMap(objectElements: List<List<MapObject>>): Grid2D<MapObject>(objectElements) {
    private val guard = Grid2D(objectElements).asIterable().first { it is MapObject.Guard } as MapObject.Guard

    companion object {
        fun fromPuzzleInput(input: List<String>): PuzzleMap = PuzzleMap(
            input.reversed().mapIndexed { y, row -> row.mapIndexed { x, cell ->  MapObject.fromCharAndIndex(cell, x to y) } }
        ).also { it.transpose() }
    }

    fun guardStep() {
        if (guardScout() is MapObject.Obstacle) guard.orientation = guard.orientation.rotateClockwise()
        else {
            guard.position += guard.orientation.asVector()
        }
    }

    fun simulateGuardPath(): Boolean {
        while (true) {
            markVisited()
            val scouted = guardScout()
            if (scouted is MapObject.Visited && guard.orientation in scouted.inOrientation) return true
            else if (scouted is MapObject.OutOfBounds) return false
            guardStep()
        }
    }

    fun guardScout(): MapObject = runCatching { this[guard.position + guard.orientation.asVector()] }.getOrElse { MapObject.OutOfBounds }

    fun markVisited() {
        val previousMapObject = this[guard.position]
        if (previousMapObject is MapObject.Visited) this[guard.position] = previousMapObject.copy(previousMapObject.inOrientation.plus(guard.orientation))
        else this[guard.position] = MapObject.Visited(listOf(guard.orientation))
    }
}

sealed class MapObject {
    class Empty: MapObject()
    class Obstacle: MapObject()
    object OutOfBounds: MapObject()

    data class Visited(val inOrientation: List<Orientation>): MapObject()
    data class Guard(var position: VecNReal, var orientation: Orientation = Orientation.NORTH): MapObject()

    companion object {
        fun fromCharAndIndex(c: Char, index: Pair<Int, Int>): MapObject {
            return when (c) {
                '.' -> Empty()
                '#' -> Obstacle()
                '^' -> Guard(VecNReal(index))
                else -> throw IllegalArgumentException("Unknown map object $c")
            }
        }
    }
}

    I also have a repo.

  • Uiua

    Part one was simple enough. Part two nearly made me give up.
    Part two has the most ugly and least performant code I've made in uiua so far but it gets the job done and that's all I care about for now.

    Run with example input here

    RotateClock ← (
  ⊙⊙(⍉⇌)
  ⊙(⇌⍜(⊡0)(-⊙(⧻⊡0.)+1))
  ↻¯1
)

RotateCounter ← (
  ⊙⊙(⇌⍉)
  ⊙(⍜(⊡0)(-⊙(⧻.)+1)⇌)
  ↻1
)

NewPos ← (
  ⊙⍜(⊙⊡:)(-1+⊙(⊗@#)⟜↘⊙.)⟜°⊟
  ⍜(⊡1)⋅
)

MarkPath ← (
  RotateClock
  ⍢( # replace characters up til next '#'
    ⊙(⊙⍜(↘⊙⊡:)(⍜(↙)(▽:@^⧻)⊗@#.)⟜°⊟
      NewPos
    )
    RotateCounter
  | ⋅(≠0⊡0))
  ◌◌
)

PartOne ← (
  &rs ∞ &fo "input-6.txt"
  ⊜∘≠@\n.
  # maybe make compatible with
  # non-up facing inputs
  ♭⊚=@^.
  [0 1 2 3]
  MarkPath
  &fwa "test.txt" json.
  /+/+=@^
)

PartTwo ← (
  &rs ∞ &fo "input-6.txt"
  ⊜∘≠@\n.
  # maybe make compatible with
  # non-up facing inputs
  ♭⊚=@^.
  [0 1 2 3]
  ◡MarkPath
  ⊙::
  # rotate the field to match the intital state
  ⊙⊙(
    ⊙(⊚=@#)
    ⍢(⇌⍉|¬≍⊚=@#)
    ⊙◌
  )
  ⊙⊙(⊚=@^.)
  ⊙⊙⊙¤∩¤
  ⊞(⊙⊙(⍜⊡⋅@#)
    RotateClock
    ⊙NewPos
    ¤¯1_¯1_¯1
    ⍢(⊙◡(⊂⊢)
      ⊂
      ⊙(RotateCounter
        ⊙NewPos
      )
    | =1+⊙(∈↘1⇌)◡⋅(≠129⊡2)⊙(⊂⊢))
    # 129 = length of input array. Hardcoded because
    # the condition block doesn't seem to get the
    # input array passed to it so the length can't
    # be read dynamically
    ⊙(⊂⊢)
    ∈
    ⊙◌
  )
  /+♭
)

&p "Day 6:"
&pf "Part 1: "
&p PartOne
&pf "Part 2: "
&p PartTwo

  • Gleam

    Late as usual. This one challenged me. Functional programming is a lot of fun, but it's kicking my ass.

    import gleam/dict
import gleam/io
import gleam/list
import gleam/option.{None, Some}
import gleam/result
import gleam/set.{type Set}
import gleam/string
import simplifile

pub type Point =
  #(Int, Int)

pub type Grid(a) =
  dict.Dict(Point, a)

pub type Direction {
  North
  East
  South
  West
}

pub type Loops {
  DoesLoop
  DoesNotLoop
}

pub type Guard {
  Guard(position: Point, direction: Direction)
}

fn get_guard(grid: Grid(String)) -> Guard {
  let pos = dict.filter(grid, fn(_pos, char) { char == "^" })
  let assert Ok(pos) = case dict.size(pos) {
    1 -> list.first(dict.keys(pos))
    0 -> panic as "No guard found in input!"
    _ -> panic as "More than one guard found in input!"
  }
  Guard(pos, North)
}

fn move_guard(guard: Guard) -> Guard {
  let new_pos = case guard.direction {
    North -> #(-1, 0)
    East -> #(0, 1)
    South -> #(1, 0)
    West -> #(0, -1)
  }
  Guard(
    #(guard.position.0 + new_pos.0, guard.position.1 + new_pos.1),
    guard.direction,
  )
}

fn turn_guard(guard: Guard) -> Guard {
  let new_dir = case guard.direction {
    North -> East
    East -> South
    South -> West
    West -> North
  }
  Guard(guard.position, new_dir)
}

fn get_obstacles(grid: Grid(String)) -> List(Point) {
  dict.filter(grid, fn(_pos, char) { char == "#" })
  |> dict.keys()
}

fn recurse_grid(
  grid: Grid(String),
  guard: Guard,
  obstacles: List(#(Int, Int)),
  visited: Set(#(#(Int, Int), Direction)),
) -> #(Set(#(#(Int, Int), Direction)), Loops) {
  let new_guard = move_guard(guard)
  let position = new_guard.position
  let dir = new_guard.direction
  case dict.has_key(grid, position) {
    False -> #(visited, DoesNotLoop)
    True -> {
      case set.contains(visited, #(position, dir)) {
        True -> {
          #(visited, DoesLoop)
        }
        False -> {
          case list.contains(obstacles, position) {
            True -> recurse_grid(grid, turn_guard(guard), obstacles, visited)
            False ->
              recurse_grid(
                grid,
                new_guard,
                obstacles,
                set.insert(visited, #(position, dir)),
              )
          }
        }
      }
    }
  }
}

fn get_grid_input(filename: String) -> Grid(String) {
  let lines =
    filename
    |> simplifile.read()
    |> result.unwrap("")
    |> string.trim()
    |> string.split("\n")
  use grid, row, row_idx <- list.index_fold(lines, dict.new())
  use grid, col, col_idx <- list.index_fold(string.to_graphemes(row), grid)
  dict.insert(grid, #(row_idx, col_idx), col)
}

fn part_one(
  grid: Grid(String),
) -> #(#(Set(#(#(Int, Int), Direction)), Loops), Int) {
  let guard = get_guard(grid)
  let obstacles = get_obstacles(grid)
  let visited = set.new() |> set.insert(#(guard.position, guard.direction))
  let visited = recurse_grid(grid, guard, obstacles, visited)
  let visited_without_dir =
    set.fold(visited.0, set.new(), fn(acc, x) { set.insert(acc, x.0) })
  #(visited, visited_without_dir |> set.size())
}

fn check_loop(grid: Grid(String), blocker: Point) -> Loops {
  let blocked_grid =
    dict.upsert(grid, blocker, fn(x) {
      case x {
        Some("^") -> "^"
        Some(_) -> "#"
        None -> "#"
      }
    })
  let visited = part_one(blocked_grid).0
  visited.1
}

fn part_two(grid: Grid(String), visited: Set(#(#(Int, Int), Direction))) {
  let visited =
    set.fold(visited, set.new(), fn(acc, x) { set.insert(acc, x.0) })
  use counter, position <- set.fold(visited, 0)
  case check_loop(grid, position) {
    DoesLoop -> counter + 1
    DoesNotLoop -> counter
  }
}

pub fn main() {
  let input = "input.in"
  let p1 = input |> get_grid_input() |> part_one
  let visited = p1.0.0
  io.debug(p1.1)
  input |> get_grid_input |> part_two(visited) |> io.debug()
}

  • Factor

    spoiler 
    : get-input ( -- rows )
  "vocab:aoc-2024/06/input.txt" utf8 file-lines ;

: all-locations ( rows -- pairs )
  dimension <coordinate-matrix> concat ;

: guard-location ( rows -- pair )
  [ all-locations ] keep
  '[ _ matrix-nth "<>^v" in? ] find nip ;

TUPLE: state location char ;
C: <state> state

: guard-state ( rows -- state )
  [ guard-location ]
  [ dupd matrix-nth ] bi <state> ;

: faced-location ( state -- pair )
  [ char>> H{
    { CHAR: > { 0 1 } }
    { CHAR: v { 1 0 } }
    { CHAR: < { 0 -1 } }
    { CHAR: ^ { -1 0 } }
  } at ] [ location>> ] bi v+ ;

: off-grid? ( rows location -- ? )
  [ dimension ] dip
  [ v<= vany? ] keep
  { 0 0 } v< vany? or ;

: turn ( state -- state' )
  [ location>> ] [ char>> ] bi
  H{
    { CHAR: > CHAR: v }
    { CHAR: v CHAR: < }
    { CHAR: < CHAR: ^ }
    { CHAR: ^ CHAR: > }
  } at <state> ;

: obstacle? ( rows location -- ? )
  swap matrix-nth CHAR: # = ;

: guard-step ( rows state -- state' )
  swap over faced-location
  {
    { [ 2dup off-grid? ] [ 2nip f <state> ] }
    { [ [ obstacle? ] keep-under ] [ drop turn ] }
    [ swap char>> <state> ]
  } cond ;

: walk-out ( rows state -- trail )
  [
    [ 2dup location>> off-grid? ] [
      dup location>> ,
      dupd guard-step
    ] until
  ] { } make 2nip ;

: part1 ( -- n )
  get-input dup guard-state walk-out cardinality ;

: (walk-loops?) ( visited rows state -- looped? )
  dupd guard-step
  2dup location>> off-grid? [ 3drop f ] [
    pick dupd in? [ 3drop t ] [
      pick dupd adjoin (walk-loops?)
    ] if
  ] if ;

: walk-loops? ( rows -- looped? )
  dup guard-state
  [ HS{ } clone ] 2dip
  pick dupd adjoin (walk-loops?) ;

: obstacle-candidates ( rows -- pairs )
  [ guard-location ]
  [ dup guard-state walk-out members ] bi remove ;

: part2 ( -- n )
  get-input dup obstacle-candidates
  [ CHAR: # spin deep-clone [ matrix-set-nth ] keep walk-loops? ] with count ;

    • Nothing smart to see here. I may revisit this when I give up on future days.

40 comments