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

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

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

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

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

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

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