AOC 2024, Day 06: Guard Gallivant

Day 6 of Advent of Code 2024, Guard Gallivant, brings us toNorth Pole prototype suit manufacturing lab... in the year 1518, where we are challenged to track the movement of a guard in a maze-like environment full of obstacles.

Elf Shenanigans

Part 1: Simulating the Guard's Patrol Path

In the first part, we are given a map and asked to simulate the movement of the guard. The guard starts at a specific position and moves forward in a direction unless obstructed. When encountering an obstacle (#), the guard rotates to the right and continues moving.

The solution involves simulating this process and counting the number of distinct positions the guard visits before returning to a previously visited position.

Part 2: Introducing Obstacles to Create Patrol Loops

In the second part, the task becomes more complex. We must update the map by replacing some open spaces (.) with obstacles (#) and check if that causes the guard to revisit any previously visited positions. The goal is to determine how many such changes can create a loop in the patrol route.

Santa's Ingenious Solutions

C#F#Python

using AdventOfCode.Lib;
using PatrolMap = System.Collections.Generic.Dictionary<AdventOfCode.Lib.Point, char>;

namespace AdventOfCode.Y2024;

[AocPuzzle(2024, 6, "Guard Gallivant", "C#")]
public sealed class Day06 : IAocDay<int>
{
    public static int Part1(AocInput input) =>
        input.AllLines
            .Pipe(lines =>
            {
                var map = ParsePatrolMap(lines);
                var start = LocateGuardStart(map, '^');
                return TrackGuardRoute(map, start);
            })
            .Pipe(route => route.Positions.Count);

    public static int Part2(AocInput input) =>
        input.AllLines
            .Pipe(lines =>
            {
                var map = ParsePatrolMap(lines);
                var start = LocateGuardStart(map, '^');
                return TrackGuardRoute(map, start).Positions.Where(p => map[p] is '.')
                    .Sum(open =>
                    {
                        var updatedMap = UpdateMap(map, '#', open);
                        var (_, loop) = TrackGuardRoute(updatedMap, start);
                        return loop ? 1 : 0;
                    });
            });

    private static PatrolMap UpdateMap(PatrolMap map, char obstacle, Point position) =>
        map.ToDictionary(kvp => kvp.Key, kvp => kvp.Key == position ? obstacle : kvp.Value);

    private static GuardRoute TrackGuardRoute(PatrolMap map, Point start)
    {
        var position = start;
        var patrol = new PatrolState(start, Point.North);
        var visited = new HashSet<PatrolState>();
        while (map.ContainsKey(patrol.Position) && visited.Add(patrol))
        {
            patrol = map.GetValueOrDefault(patrol.Position + patrol.Direction) switch
            {
                '#' => patrol with { Direction = Point.RotateRight(patrol.Direction) },
                _ => patrol with { Position = position += patrol.Direction }
            };
        }

        return new GuardRoute(visited.Select(s => s.Position).ToHashSet(), visited.Contains(patrol));
    }

    private static Point LocateGuardStart(PatrolMap map, char c) =>
        map.Single(p => p.Value == c).Key;

    private static PatrolMap ParsePatrolMap(string[] lines) => (
        from y in Enumerable.Range(0, lines.Length)
        from x in Enumerable.Range(0, lines[0].Length)
        select KeyValuePair.Create(new Point(x, y), lines[y][x])
    ).ToDictionary();

    private readonly record struct PatrolState(Point Position, Point Direction);

    private readonly record struct GuardRoute(HashSet<Point> Positions, bool Loop);
}

open AdventOfCode.Lib

[<AocPuzzle(2024, 6, "Guard Gallivant", "F#")>]
module Fay06 =

    open Lib

    type PatrolMap = Map<Point, char>
    type Positions = Set<Point>
    type PatrolState = { Position: Point; Direction: Point }
    type GuardRoute = { Positions: Positions; Loop: bool }

    let parsePatrolMap (lines: string array) =
        lines
        |> Array.indexed
        |> Array.collect (fun (y, line) -> [|
            for x, c in line |> Seq.toArray |> Array.indexed -> { X = x; Y = y }, c
        |])
        |> Map.ofArray

    let locateGuardStart (map: PatrolMap) (c: char) =
        map |> Seq.find (fun kvp -> kvp.Value = c) |> _.Key

    [<TailCall>]
    let trackGuardRoute (map: PatrolMap) (start: Point) =
        let rec track (visited: Set<PatrolState>) (patrol: PatrolState) =
            if map.ContainsKey patrol.Position && not (visited.Contains patrol) then
                let visited = visited.Add patrol

                match map.TryFind(patrol.Position + patrol.Direction) |> Option.defaultValue ' ' with
                | '#' ->
                    track visited {
                        patrol with
                            Direction = Point.rotateRight patrol.Direction
                    }

                | _ ->
                    track visited {
                        patrol with
                            Position = patrol.Position + patrol.Direction
                    }

            else
                {
                    Positions = visited |> Seq.map _.Position |> Set.ofSeq
                    Loop = visited.Contains patrol
                }

        track Set.empty { Position = start; Direction = Point.North }

    let updateMap (map: PatrolMap) (obstacle: char) (position: Point) =
        map |> Map.map (fun k v -> if k = position then obstacle else v)

    let part1 (input: AocInput) =
        input.AllLines
        |> parsePatrolMap
        |> (fun map -> (map, locateGuardStart map '^'))
        |> (fun (map, start) -> trackGuardRoute map start)
        |> _.Positions
        |> Set.count

    let part2 (input: AocInput) =
        let map = parsePatrolMap input.AllLines
        let start = locateGuardStart map '^'
        let route = trackGuardRoute map start

        route
        |> _.Positions
        |> Set.filter (fun p -> map[p] = '.')
        |> Seq.sumBy (fun obstacle ->
            let updatedMap = updateMap map '#' obstacle
            let route = trackGuardRoute updatedMap start
            route |> _.Loop |> (fun loop -> if loop then 1 else 0))

from aoc.core import AocInput

Santa's & Elves' Reflections

Day 6 of Advent of Code 2024 presented a challenging maze-like puzzle where we had to track the guard's movements and determine whether the guard revisited a position or got stuck in a loop.

Check out the repository for solutions: AdventOfCode & AdventOfCode.Lib.