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

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

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!();

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

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

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

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

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

#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;
}

: 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 ;

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