Day 6: Guard Gallivant

def compute_p1(input)
  map = Grid.new(input)
  guard_pos = map.coords_where { |ch| ch == "^" }.first
  map.set(guard_pos[0], guard_pos[1], ".")
  direction = :up
  visited = Set.new([guard_pos])
  while map.in_bounds?(guard_pos[0],guard_pos[1])
    guard_pos, direction = step(map, guard_pos, direction)
    visited.add(guard_pos) if map.in_bounds?(guard_pos[0], guard_pos[1])
  end
  return visited.count
end

def step(grid, guard_pos, direction)
  facing_coords = case direction
           when :up
             [guard_pos[0],guard_pos[1]-1]
           when :down
             [guard_pos[0],guard_pos[1]+1]
           when :left
             [guard_pos[0]-1,guard_pos[1]]
           when :right
             [guard_pos[0]+1,guard_pos[1]]
           end
  facing = grid.get(facing_coords[0], facing_coords[1])
  case facing
  when ".", nil
    guard_pos = facing_coords
  when "#", "O"
    direction = case direction
                when :up
                  :right
                when :right
                  :down
                when :down
                  :left
                when :left
                  :up
                end
  end
  return [guard_pos, direction]
end

def loops?(map, start_pos)
  guard_pos = start_pos
  direction = :up
  visited = Set.new([guard_pos])
  while map.in_bounds?(guard_pos[0],guard_pos[1])
    guard_pos, direction = step(map, guard_pos, direction)
    if visited.include?([guard_pos, direction])
      return true
    end
    visited.add([guard_pos, direction])
  end
  return false
end

def compute_p2(input)
  map = Grid.new(input)
  start_pos = map.coords_where { |ch| ch == "^" }.first
  map.set(start_pos[0], start_pos[1], ".")
  count = 0
  map.each_index do |x, y|
    next if map.get(x,y) == "#"
    map.set(x,y, "O")
    count += 1 if loops?(map, start_pos)
    map.set(x,y, ".")
  end
  return count
end

/* Advent of Code 2024
 * Day 06: Guard Gallivant
 */

#import "Basic";
#import "File";
#import "Hash";
#import "String";

using Hash_Table :: #import "Hash_Table";
#poke_name Hash_Table operator ==;

Vector2_Int :: struct {
    x, y: int;
}

// Maybe the guard doesn't have to be a struct, but it makes the program more
// readable and doesn't have any performance impact. It's also possible
// "direction" could be an enum, but then the simulation code would be a little
// less clean...
Guard :: struct {
    position, direction: Vector2_Int;
}

// Inlining all these procedures makes the bruteforcing faster. Maybe.
operator == :: inline (a: Vector2_Int, b: Vector2_Int) -> bool {
    return a.x == b.x && a.y == b.y;
}

Vector2_Int_Table :: Table(Vector2_Int, void, (vector: Vector2_Int) -> u32 {
    return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
});

// This function behaves differently depending on which part of the puzzle it is
// supposed to be solving. This is important to avoid unnecessarily wasting time
// on recording the unique positions visited by the guard during part 2, which
// slows the bruteforcing down considerably. While this procedure returns
// multiple values (the set of unique positions, and whether the guard entered a
// loop), the first one will always be an empty set during part 2.
simulate_guard :: inline (
    map: [..][..] bool,
    width: int,
    height: int,
    initial_guard: Guard,
    part: int
) -> Vector2_Int_Table, bool {
    unique_positions: Vector2_Int_Table;

    // This is _much_ faster than using a set. I'm keeping this as a flat array
    // to avoid unnecessary allocations - I tried using a flat array for the map
    // itself too, but the overhead of calculating the index constantly seemed
    // to slow the program down very slightly (by milliseconds - I'm splitting
    // hairs here!).
    previous_guard_states := NewArray(width * height, [4] bool);
    defer array_free(previous_guard_states);

    guard := initial_guard;
    while true {
        // It looks a little weird, but using #run {} allows you to add keys to
        // a table with void as the value type (which is useful to lower memory
        // usage when using a table as a set).
        if part == 1 {
            if !table_contains(*unique_positions, guard.position) {
                table_add(*unique_positions, guard.position, #run {});
            }
        } else {
            position_index := guard.position.x * width + guard.position.y;

            direction_index: int;
            if      guard.direction == .{1, 0}  direction_index = 0;
            else if guard.direction == .{0, 1}  direction_index = 1;
            else if guard.direction == .{-1, 0} direction_index = 2;
            else if guard.direction == .{0, -1} direction_index = 3;

            if previous_guard_states[position_index][direction_index] {
                return unique_positions, true;
            } else {
                previous_guard_states[position_index][direction_index] = true;
            }
        }

        guard.position.x += guard.direction.x;
        guard.position.y += guard.direction.y;

        if
            guard.position.x < 0 || guard.position.x >= width
            || guard.position.y < 0 || guard.position.y >= height
        {
            break;
        }

        if map[guard.position.y][guard.position.x] {
            guard.position.x -= guard.direction.x;
            guard.position.y -= guard.direction.y;
            guard.direction = .{-guard.direction.y, guard.direction.x};
        }
    }

    return unique_positions, false;
}

main :: () {
    input, success := read_entire_file("inputs/day_06.txt");
    assert(success);

    map: [..][..] bool;
    guard: Guard;
    guard.direction = .{0, -1};

    for line, y: split(input, "\n") {
        if line == "" {
            continue;
        }

        row: [..] bool;
        for char, x: line {
            array_add(*row, ifx char == #char "#" then true else false);

            if char == #char "^" {
                guard.position = .{x, y};
            }
        }

        array_add(*map, row);
    }

    width := map[0].count;
    height := map.count;

    unique_positions, _ := simulate_guard(map, width, height, guard, 1);
    print("Part 1: %\n", unique_positions.count);

    loop_causing_obstructions := 0;
    for unique_positions {
        map[it_index.y][it_index.x] = true;

        _, entered_loop := simulate_guard(map, width, height, guard, 2);
        if entered_loop {
            loop_causing_obstructions += 1;
        }

        map[it_index.y][it_index.x] = false;
    }

    print("Part 2: %\n", loop_causing_obstructions);
}

import "utils" as utils;

let input = utils::get_input(6, false);

// AUXILIARY
fn next_dir(dir) {
    switch dir {
        "up" => "right",
        "right" => "down",
        "down" => "left",
        "left" => "up",
    }
}

fn dir_offset(dir) {
    switch dir {
        "up" => new_point(0, -1),
        "down" => new_point(0, 1),
        "left" => new_point(-1, 0),
        "right" => new_point(1, 0),
    }
}

// PART 1
let grid = new_grid(input.split("\n").map(|line| line.to_chars()));

let guard_pos = ();
let guard_dir = ();
for item in grid.cells().zip(grid.cell_positions()) {
    if item[0] == '^' {
        guard_dir = "up";
    } if item[0] == 'v' {
        guard_dir = "down";
    } if item[0] == '<' {
        guard_dir = "left";
    } else if item[0] == '>' {
        guard_dir = "right";
    }
    if guard_dir != () {
        guard_pos = item[1];
        grid.set_cell(guard_pos, 'X');
        break;
    }
}

while grid.is_valid(guard_pos) {
    let offset = dir_offset(guard_dir);

    if grid.cell(guard_pos + offset) != '#' {
        guard_pos = guard_pos + offset;
        grid.set_cell(guard_pos, 'X');
    } else {
        guard_dir = next_dir(guard_dir);
    }
}

let total = 0;
for cell in grid.cells() {
    if cell == 'X' {
        total += 1;
    }
}

print(`part 1: ${total}`);

// PART 2
let prev_grid = grid;
let grid = new_grid(input.split("\n").map(|line| line.to_chars()));

let guard_pos = ();
let guard_dir = ();
for item in grid.cells().zip(grid.cell_positions()) {
    if item[0] == '^' {
        guard_dir = "up";
    } if item[0] == 'v' {
        guard_dir = "down";
    } if item[0] == '<' {
        guard_dir = "left";
    } else if item[0] == '>' {
        guard_dir = "right";
    }
    if guard_dir != () {
        guard_pos = item[1];
        grid.set_cell(guard_pos, '.');
        break;
    }
}

let total = 0;
let original_guard_pos = guard_pos;
let original_guard_dir = guard_dir;
for pos in grid.cell_positions() {
    if (pos.x == original_guard_pos.x && pos.y == original_guard_pos.y) || prev_grid.cell(pos) != 'X' {
        continue;
    }

    guard_pos = original_guard_pos;
    guard_dir = original_guard_dir;

    let graph = new_graph();
    let point_to_node = #{};
    point_to_node[`${guard_pos}-${guard_dir}`] = graph.add_node(0.0);

    grid.set_cell(pos, '#');

    let found = false;
    let prev_node = point_to_node[`${guard_pos}-${guard_dir}`];
    let curr_node = ();
    while grid.is_valid(guard_pos) {
        let offset = dir_offset(guard_dir);

        if grid.cell(guard_pos + offset) != '#' {
            guard_pos = guard_pos + offset;
        } else {
            guard_dir = next_dir(guard_dir);
        }

        curr_node = point_to_node[`${guard_pos}-${guard_dir}`];
        if curr_node == () {
            curr_node = graph.add_node(0.0);
            point_to_node[`${guard_pos}-${guard_dir}`] = curr_node;
        }

        if !graph.contains_edge(prev_node, curr_node) {
            graph.add_edge(prev_node, curr_node, 0.0);
        }
        if graph.is_cyclic_directed() {
            found = true;
            break;
        }
        prev_node = curr_node;
    }

    if found {
        total += 1;
    }

    grid.set_cell(pos, '.');
}

print(`part 2: ${total}`);

Quick note that since every turn is 90° clockwise, I was able to set up a rotate() convenience function and just call that whenever the guard hit an obstacle.

I hate code duplication so my solution to both parts lives in a single function, and one of the args is just a flag indicating what you want it to return (either the count of distinct guard positions, or the count of valid obstacle positions).

The first thing it does is figure out the starting position and direction, then it replaces that tile in the map with a . so it matches all the other non-obstacle tiles. This is important, because in the next phase (the walk) the guard will paint the tile she's on to track where she has been and what direction she was facing the first time she was there. We can use this to validate that a position is distinct before counting it, and also use it to detect infinite loops in Part 2 without wasting cycles on simulating them. The idea being, that if the guard enters a tile already marked with the direction she's currently facing, we know she MUST be in a loop.

A few other small optimizations like breaking early out of loops helped a bit too; both parts together complete in 2795ms on my machine. I kind of hate the flag argument pattern I landed on here in my pursuit of DRYness but it's good enough for AoC.

type InputData = string[][];

type DirectionSymbol = '^' | '>' | 'v' | '<';
type Direction = [number, number];

enum Target {
  GuardPositions,
  ObstaclePositions,
}

function formatInput(input: string): InputData {
  return input
    .trim()
    .split('\n')
    .map(line => line.split(''));
}

const directions: Record<DirectionSymbol, Direction> = {
  '>': [0, 1],
  '^': [-1, 0],
  v: [1, 0],
  '<': [0, -1],
};

// directions in order, rotating clockwise
const rotationCW: DirectionSymbol[] = ['^', '>', 'v', '<'];

const rotate = (currentDirection: DirectionSymbol) => {
  return rotationCW[(rotationCW.indexOf(currentDirection) + 1) % rotationCW.length];
};

const checkBounds = ([row, col]: [number, number], map: InputData) => {
  if (row < map.length && row >= 0) {
    if (col < map[0].length && col >= 0) {
      return true;
    }
  }
  return false;
};

export function run(input: string): string[] {
  const data = formatInput(input);

  const countPositions = (originalMap: InputData, target: Target): number => {
    const map: InputData = [...originalMap.map(row => [...row])];
    let startingPosition: [number, number];
    let startingDirection: DirectionSymbol;
    let count = 0;
    // initial map setup is the same for both parts: find start position and direction
    outerLoop: for (let row = 0; row < map.length; row++) {
      for (let col = 0; col < map[row].length; col++) {
        // when the info is found, note it and mark that position unvisited (".")
        if (Object.prototype.hasOwnProperty.call(directions, map[row][col])) {
          startingPosition = [row, col];
          startingDirection = map[row][col] as DirectionSymbol;
          map[row][col] = '.';
          break outerLoop;
        }
      }
    }
    // if looking for guard positions (Part 1) just do a single walk
    // but if looking for obstacle positions (Part 2) walk once for each possibility
    const rowIterations = target === Target.GuardPositions ? 1 : map.length;
    const colIterations = target === Target.GuardPositions ? 1 : map[0].length;
    for (let obstacleRow = 0; obstacleRow < rowIterations; obstacleRow++) {
      for (let obstacleCol = 0; obstacleCol < colIterations; obstacleCol++) {
        let currentPosition = startingPosition;
        let currentDirection = startingDirection;
        // clone the map for use in this iteration without modifying the original one
        const currentMap: InputData = [...map.map(row => [...row])];
        if (target === Target.ObstaclePositions) {
          // don't bother placing an obstacle in a position if there's already one there
          if (currentMap[obstacleRow][obstacleCol] === 'X') {
            continue;
          }
          currentMap[obstacleRow][obstacleCol] = '#';
        }
        while (true) {
          const [row, col] = currentPosition;
          if (currentMap[row][col] === currentDirection) {
            // identified: stuck in a loop
            if (target === Target.ObstaclePositions) {
              count++;
            }
            break;
          }
          if (currentMap[row][col] === '.') {
            if (target === Target.GuardPositions) {
              count++;
            }
            currentMap[row][col] = currentDirection;
          }
          const [rowChange, colChange] = directions[currentDirection];
          const nextPosition: [number, number] = [row + rowChange, col + colChange];
          const [nextRow, nextCol] = nextPosition;
          if (!checkBounds(nextPosition, currentMap)) {
            break;
          }
          if (currentMap[nextRow][nextCol] === '#') {
            currentDirection = rotate(currentDirection);
          } else {
            currentPosition = [nextRow, nextCol];
          }
        }
      }
    }

    return count;
  };

  const countGuardPositions = (map: InputData): number => {
    return countPositions(map, Target.GuardPositions);
  };

  const countObstaclePositions = (map: InputData): number => {
    return countPositions(map, Target.ObstaclePositions);
  };

  return [`${countGuardPositions(data)}`, `${countObstaclePositions(data)}`];
}

I used my existing Grid module to parse the input. I might create a companion Heading module soon as well, because I keep treating headings as a special case of points/coordinates, when they're kind of a whole different thing.

defmodule AdventOfCode.Solution.Year2024.Day06 do
  use AdventOfCode.Solution.SharedParse

  alias AdventOfCode.Grid, as: G

  @impl true
  def parse(input) do
    grid = G.from_input(input)
    [{guard_start, ?^}] = G.filter_cells(grid, &match?({_, ?^}, &1))

    # Replace ^ with .
    grid = G.replace(grid, guard_start, ?.)

    {grid, guard_start}
  end

  def part1({grid, guard_start}) do
    grid
    |> stream_steps(guard_start)
    |> MapSet.new(fn {coords, _heading} -> coords end)
    |> MapSet.size()
  end

  def part2({grid, guard_start}) do
    path = grid |> stream_steps(guard_start) |> Enum.to_list()

    # Try placing walls along the guard's original path, one at a time
    path
    |> Stream.with_index(fn {coords, _heading}, i -> {coords, i} end)
    # If the path crosses over itself, we don't need to try placing a wall there again
    |> Stream.uniq_by(fn {coords, _i} -> coords end)
    # Can't place a wall on top of the guard
    |> Stream.drop(1)
    |> Enum.count(fn {coords, i} ->
      wall_causes_loop?(grid, coords, i, path)
    end)
  end

  defp wall_causes_loop?(grid, wall_coords, wall_step_idx, path) do
    # Place the wall
    grid = G.replace(grid, wall_coords, ?#)

    # Fast-forward to the step just before the new wall
    step_before_wall = Enum.at(path, wall_step_idx - 1)
    {coords, heading} = step_before_wall
    visited_before_wall = MapSet.new(Enum.take(path, max(0, wall_step_idx - 2)))

    # See if the guard repeats a step from there
    grid
    |> stream_steps(coords, heading)
    |> Enum.reduce_while(visited_before_wall, fn step, visited ->
      if step in visited do
        {:halt, :loop}
      else
        {:cont, MapSet.put(visited, step)}
      end
    end)
    |> Kernel.==(:loop)
  end

  @spec stream_steps(G.t(), G.coordinates()) :: Enumerable.t({G.coordinates(), G.heading()})
  @spec stream_steps(G.t(), G.coordinates(), G.heading()) ::
          Enumerable.t({G.coordinates(), G.heading()})
  defp stream_steps(grid, coords, heading \\ {0, -1}) do
    Stream.unfold({coords, heading}, fn
      nil ->
        nil

      {coords, heading} ->
        next_coords = G.sum_coordinates(coords, heading)

        case G.at(grid, next_coords) do
          nil -> {{coords, heading}, nil}
          ?. -> {{coords, heading}, {next_coords, heading}}
          ?# -> {{coords, heading}, {coords, turn_right(heading)}}
        end
    end)
  end

  defp turn_right({x, y}), do: {-y, x}
end

Name             ips        average  deviation         median         99th %
Part 1       1238.78      0.00081 s     ±3.68%      0.00082 s      0.00086 s
Parse         428.80      0.00233 s     ±5.56%      0.00230 s      0.00275 s
Part 2          0.55         1.80 s     ±1.86%         1.79 s         1.84 s

Comparison: 
Part 1       1238.78
Parse         428.80 - 2.89x slower +0.00152 s
Part 2          0.55 - 2234.52x slower +1.80 s

import sys

def move_guard(lab: dict[complex, str], pos: complex, heading: complex) -> tuple[complex, complex]:
    if lab[pos + heading] == '#':
        heading *= -1j
    else:
        pos += heading
        lab[pos] = 'X'
    return pos, heading

lab = {}
for b, line in enumerate(sys.stdin):
    for a, char in enumerate(line.strip()):
        if char == '^':
            startpos = complex(a, -b)
            char = 'X'
        lab[complex(a, -b)] = char

pos = startpos
heading = 1j
while pos + heading in lab:
    pos, heading = move_guard(lab, pos, heading)

print(sum(char == 'X' for char in lab.values()))

from collections.abc import Iterator
import sys

def move_guard(lab: dict[complex, str], pos: complex, heading: complex) -> tuple[complex, complex]:
    if lab[pos + heading] == '#':
        heading *= -1j
    else:
        pos += heading
        lab[pos] = 'X'
    return pos, heading

def obstruction_candidates(_lab: dict[complex, str], pos: complex, heading: complex) -> Iterator[complex]:
    lab = _lab.copy()
    while pos + heading in lab:
        oldchar = lab[pos + heading]
        pos, heading = move_guard(lab, pos, heading)
        if oldchar == '.':
            yield pos

def would_loop(_lab: dict[complex, str], pos: complex, heading: complex, obstruction: complex) -> bool:
    lab = _lab.copy()
    lab[obstruction] = '#'
    history = set()
    while pos + heading in lab:
        if (pos, heading) in history:
            return True
        history.add((pos, heading))
        pos, heading = move_guard(lab, pos, heading)
    return False

lab = {}
for b, line in enumerate(sys.stdin):
    for a, char in enumerate(line.strip()):
        if char == '^':
            startpos = complex(a, -b)
            char = 'X'
        lab[complex(a, -b)] = char

print(sum(would_loop(lab, startpos, 1j, candidate)
          for candidate in obstruction_candidates(lab, startpos, 1j)))

pub fn part1(input: &PuzzleInput) -> String {
    let coord = guard_starting_position(&input.grid);
    let mut visited = Vec::new();

    let mut state = GuardState {
        coordinate: coord,
        direction: Direction::Up,
    };

    visited.push((state.coordinate, state.direction));

    while let Some(next_state) = state.next_state(&input.grid) {
        visited.push((next_state.coordinate, next_state.direction));
        state = next_state;
    }

    let mut v = visited.iter().map(|(c, _)| c).collect::<Vec<_>>();
    v.sort();
    v.dedup();

    v.len().to_string()
}

#[derive(Debug)]
pub struct GuardState {
    pub coordinate: Coordinate,
    pub direction: Direction,
}

impl GuardState {
    pub fn next_state(&self, grid: &Grid2D<char>) -> Option<GuardState> {
        let next_coord = self.coordinate + self.direction.into();

        if let Some(c) = grid.get(next_coord) {
            if *c == '#' {
                let new_direction = self.direction.turn_right_90();

                return Some(GuardState {
                    coordinate: self.coordinate,
                    direction: new_direction,
                });
            }

            return Some(GuardState {
                coordinate: next_coord,
                direction: self.direction,
            });
        }

        None
    }
}

pub fn guard_starting_position(grid: &Grid2D<char>) -> Coordinate {
    grid.iter()
        .find(|(c, x)| **x == '^')
        .map(|(c, x)| c)
        .unwrap()
}

pub fn part2(input: &PuzzleInput) -> String {
    let coord = guard_starting_position(&input.grid);

    let mut state = GuardState {
        coordinate: coord,
        direction: Direction::Up,
    };

    let mut visited = Vec::new();

    visited.push((state.coordinate, state.direction));

    while let Some(next_state) = state.next_state(&input.grid) {
        visited.push((next_state.coordinate, next_state.direction));
        state = next_state;
    }

    let mut loops_found = HashSet::new();
    let mut obstacles = HashSet::new();

    for (pos, dir) in visited.iter() {
        let obstacle = *pos + (*dir).into();

        if obstacle == coord {
            continue;
        }

        if input.grid.get(obstacle).is_none() {
            continue;
        }

        if input.grid.get(obstacle).unwrap() == &'#' {
            continue;
        }

        obstacles.insert(obstacle);
    }

    for obstacle in obstacles.iter() {
        let mut g2 = input.grid.clone();
        g2.set(*obstacle, '#');

        let mut state = GuardState {
            coordinate: coord,
            direction: Direction::Up,
        };

        let mut visited = HashSet::new();

        while let Some(next_state) = state.next_state(&g2) {
            state = next_state;

            if !visited.insert((state.coordinate, state.direction)) {
                break;
            }
        }

        if g2.get(state.coordinate + state.direction.into()).is_some() {
            loops_found.insert(obstacle);
        }
    }

    loops_found.len().to_string()
}

#! /usr/bin/env racket
#lang racket

(require "common.rkt" rackunit)

;; XXX: Might want to move a lot of these procedures to common.rkt

;; returns #t if i or j are out-of-bounds of in-map
;; else returns #f
(define (out-of-bounds? in-map i j)
  (cond
    [(or (negative? i)
         (negative? j)
         (>= i (length in-map))
         (>= j (length (list-ref in-map i)))) #t]
    [else #f]))

;; get the coordinates of the next step
(define (next-step-coords coords dir)
  (cond
    [(eq? dir 'up) (cons (sub1 (car coords)) (cdr coords))]
    [(eq? dir 'down) (cons (add1 (car coords)) (cdr coords))]
    [(eq? dir 'left) (cons (car coords) (sub1 (cdr coords)))]
    [(eq? dir 'right) (cons (car coords) (add1 (cdr coords)))]
    [else 'invalid-dir]))

;; get the value at (i, j) else #f
(define (map-ref in-map i j)
  (cond
    [(out-of-bounds? in-map i j) #f]
    [else (list-ref (list-ref in-map i) j)]))

;; get the value at the next step
(define (map-ref-next-step in-map coords dir)
  (let* ([next-step-crds (next-step-coords coords dir)]
         [i (car next-step-crds)]
         [j (cdr next-step-crds)])
    (map-ref in-map i j)))

(define (replace-at-index lst i new-value)
  (cond
    [(empty? lst) '()]
    [(zero? i) (cons new-value (cdr lst))]
    [else (cons (car lst) (replace-at-index (cdr lst) (sub1 i) new-value))]))

(define (replace-at-coords in-map coords new-value)
  (cond
    [(empty? in-map) '()]
    [(zero? (car coords)) (cons (replace-at-index (car in-map) (cdr coords) new-value) (cdr in-map))]
    [else (cons (car in-map) (replace-at-coords (cdr in-map) (cons (sub1 (car coords)) (cdr coords)) new-value))]))

;; returns the coordinates of the ^ on the map
(define (find-start in-map)
  (let helper ((i 0) (j 0))
    (cond
      ;; we went past the bottom right corner and somehow didn't find the start
      [(eq? i (length in-map)) 'no-start]
      ;; end of a row, go to start of the next row
      [(eq? j (length (list-ref in-map i))) (helper (add1 i) 0)]
      ;; these *should* never happen
      ;; but let's handle it just in case
      [(out-of-bounds? in-map i j) empty]
      ;; valid coordinates, check for #\^
      [(eq? #\^ (list-ref (list-ref in-map i) j)) (cons i j)]
      ;; go to next column in the same row
      [else (helper i (add1 j))])))

(define (turn-right dir)
  (cond
    [(eq? dir 'up) 'right]
    [(eq? dir 'right) 'down]
    [(eq? dir 'down) 'left]
    [(eq? dir 'left) 'up]
    [else 'invalid-dir]))

(define (looping? visited coords dir)
  (member (cons coords dir) visited))

;; if there's an obstacle, turn 90-degrees right;
;; else, walk one step forwards.
(define (walk in-map coords dir [visited '()])
  (let ([next-step-val (map-ref-next-step in-map coords dir)])
    (cond
      ;; we finish when we go out of bounds
      [(not next-step-val) (cons (cons coords dir) visited)]
      ;; easy way to "detect" a cycle; probably not very reliable but it works...
      [(looping? visited coords dir) (cons (cons coords dir) visited)]
      ;; obstacle, turn right
      [(eq? next-step-val #\#) (walk in-map coords (turn-right dir) visited)]
      ;; walk forward
      [else (walk in-map
                  (next-step-coords coords dir)
                  dir
                  (cons (cons coords dir) visited))])))

(define (day06/run-part01 in-map)
  (let ([start-coords (find-start in-map)])
    (set-count (list->set (map car (walk in-map start-coords 'up))))))

;; TODO: Loop through visited and then walk again
(define (day06/run-part02 in-map)
  (let* ([start-coords (find-start in-map)])
    (for*/sum ([i (length in-map)]
               [j (length (list-ref in-map i))])
      (cond
        [(and (not (eq? #\# (map-ref in-map i j)))
              (not (eq? #\^ (map-ref in-map i j))))
         ; (printf "~a,~a\n" i j)
         (let* ([modded-map (replace-at-coords in-map (cons i j) #\#)]
                [visited (walk modded-map start-coords 'up)]
                [coords (car (car visited))]
                [dir (cdr (car visited))])
           ; (printf "modded at (~a,~a): ~a\n" i j modded-map)
           (if (looping? (cdr visited) coords dir)
               1
               0))]
        [else 0]))))

(check-equal? (day06/run-part01 (input->list (open-input-file "examples/day06.in"))) 41 "Test part 1")
(check-equal? (day06/run-part02 (input->list (open-input-file "examples/day06.in"))) 6 "Test part 2")

(check-equal? (day06/run-part01 (input->list (open-input-file "inputs/day06.in"))) 5453 "Test part 1")

(let* ([in-map (input->list (open-input-file "inputs/day06.in"))]
       [part1 (day06/run-part01 in-map)])
       ; [part2 (day06/run-part02 in-map)])
  (printf "Part 1: ~a, Part 2: ~a\n" part1 'part2))

I think most of the time is because I used a list of lists for the map instead of a vector of vectors, so trying to replace a single value is O(ij) instead of O(1). Honestly though, I think my part 1 is decent enough.