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

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

Change seen positions set to include direction, if pos+dir already seen then it’s a loop. Test all spaces.

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

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

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

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