undefined

    
import Data.Array.Unboxed (UArray)
import Data.Array.Unboxed qualified as Array
import Data.List
import Data.Maybe
import Data.Set (Set)
import Data.Set qualified as Set

readInput :: String -> UArray (Int, Int) Char
readInput s =
  let rows = lines s
   in Array.listArray ((1, 1), (length rows, length $ head rows)) $ concat rows

startPos = fst . fromJust . find ((== '^') . snd) . Array.assocs

walk grid = go (startPos grid) (-1, 0)
  where
    go pos@(i, j) dir@(di, dj) =
      (pos, dir)
        : let pos' = (i + di, j + dj)
           in if Array.inRange (Array.bounds grid) pos'
                then case grid Array.! pos' of
                  '#' -> go pos (dj, -di)
                  _ -> go pos' dir
                else []

path = Set.fromList . map fst . walk

part1 = Set.size . path

part2 grid = Set.size $ Set.filter (isLoop . walk . addO) $ Set.delete (startPos grid) $ path grid
  where
    addO pos = grid Array.// [(pos, '#')]
    isLoop xs = or $ zipWith Set.member xs $ scanl' (flip Set.insert) Set.empty xs

main = do
  input <- readInput <$> readFile "input06"
  print $ part1 input
  print $ part2 input

  

 undefined

    
public class Day06 : Solver
{
  private readonly (int, int)[] directions = [
    (0, -1), (1, 0), (0, 1), (-1, 0)
    ];

  private ImmutableArray<string> data;
  private int width, height;
  private ImmutableHashSet<(int, int)> guard_path;
  private int start_x, start_y;

  public void Presolve(string input) {
    data = input.Trim().Split("\n").ToImmutableArray();
    width = data[0].Length;
    height = data.Length;
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if (data[j][i] == '^') {
          start_x = i;
          start_y = j;
          break;
        }
      }
    }
    guard_path = Walk().Path.ToImmutableHashSet();
  }

  private bool IsWithinBounds(int x, int y) => x >= 0 && y >= 0 && x < width && y < height;
  
  private (HashSet<(int, int)> Path, bool IsLoop) Walk((int, int)? obstacle = null) {
    int obstacle_x = obstacle?.Item1 ?? -1;
    int obstacle_y = obstacle?.Item2 ?? -1;
    int direction = 0;
    int x = start_x;
    int y = start_y;
    bool loop = false;
    HashSet<(int, int, int)> positions = new();
    while (IsWithinBounds(x, y)) {
      if (positions.Contains((x, y, direction))) {
        loop = true;
        break;
      }
      positions.Add((x, y, direction));
      int nx = x + directions[direction].Item1;
      int ny = y + directions[direction].Item2;

      while (IsWithinBounds(nx, ny) && (data[ny][nx] == '#' || (nx == obstacle_x && ny == obstacle_y))) {
        direction = (direction + 1) % 4;
        nx = x + directions[direction].Item1;
        ny = y + directions[direction].Item2;
      }
      x = nx;
      y = ny;
    }
    return (positions.Select(position => (position.Item1, position.Item2)).ToHashSet(), loop);
  }

  public string SolveFirst() => guard_path.Count.ToString();
  public string SolveSecond() => guard_path
    .Where(position => position != (start_x, start_y))
    .Where(position => Walk(position).IsLoop)
    .Count().ToString();
}

  

 haskell

    
import Control.Arrow hiding (first, second)

import Data.Map (Map)
import Data.Set (Set)
import Data.Bifunctor

import qualified Data.Array.Unboxed as Array
import qualified Data.List as List
import qualified Data.Set as Set
import Data.Array.Unboxed (UArray)

parse :: String -> (UArray (Int, Int) Char, (Int, Int))
parse s = (a, p)
        where
                p = Array.indices 
                        >>> filter ((a Array.!) >>> (== '^'))
                        >>> head
                        $ a
                a = Array.listArray ((1, 1), (n, m)) . filter (/= '\n') $ s
                l = lines s
                (n, m) = (length . head &&& pred . length) l

rotate90 d@(-1, 0) = (0, 1)
rotate90 d@(0,  1) = (1, 0)
rotate90 d@(1,  0) = (0, -1)
rotate90 d@(0, -1) = (-1, 0)

walkGuard :: (UArray (Int, Int) Char) -> (Int, Int) -> (Int, Int) -> [((Int, Int), (Int, Int))]
walkGuard a p d@(dy, dx)
        | not isInBounds                  = []
        | (maybe ' ' id tileAhead) == '#' = (p, d) : walkGuard a p rotatedDirection
        | otherwise                       = (p, d) : walkGuard a updatedPosition d
        where
                isInBounds = Array.inRange (Array.bounds a) p
                updatedPosition = bimap (+dy) (+dx) p
                tileAhead = a Array.!? updatedPosition
                rotatedDirection = rotate90 d

ruleGroup :: Eq a => (a, b) -> (a, b') -> Bool
ruleGroup = curry (uncurry (==) <<< fst *** fst)
                
arrayDisplay a = Array.indices
        >>> List.groupBy ruleGroup
        >>> map (map (a Array.!))
        >>> unlines
        $ a

walkedPositions a p d = walkGuard a p 
        >>> map fst
        >>> Set.fromList
        $ d

isLoop = isLoop' Set.empty
isLoop' _ [] = False
isLoop' s (l:ls)
        | l `Set.member` s = True
        | otherwise = isLoop' (Set.insert l s) ls

part1 (a, p) = walkedPositions a p
        >>> length
        $ (-1, 0)
part2 (a, p) = walkedPositions a p
        >>> Set.toList
        >>> map (, '#')
        >>> map (:[])
        >>> map (a Array.//)
        >>> map (\ a' -> walkGuard a' p (-1, 0))
        >>> filter (isLoop)
        >>> length
        $ (-1, 0)

main = getContents >>= print . (part1 &&& part2) . parse

  

 undefined

    
import os
from collections import defaultdict

# paths
here = os.path.dirname(os.path.abspath(__file__))
filepath = os.path.join(here, 'input.txt')

# read input
with open(filepath, mode='r', encoding='utf8') as f:
    data = f.read()
rows = data.splitlines()

# bounds
m = len(rows)
n = len(rows[0])

# directions following 90 degree clockwise turns
#   up, right, down, left
DIRECTIONS = [(-1, 0), (0, 1), (1, 0), (0, -1)]

# find position of guard
guard_i, guard_j = -1, -1
for i in range(m):
    for j in range(n):
        if rows[i][j] == '^':
            guard_i, guard_j = i, j
            break
    if guard_i != -1:
        break


def part1(guard_i, guard_j):
    # keep track of visited positions
    visited = set()
    visited.add((guard_i, guard_j))

    dir_idx = 0     # current direction index

    # loop while guard is in map
    while True:
        delta_i, delta_j = DIRECTIONS[dir_idx]
        next_gi, next_gj = guard_i + delta_i, guard_j + delta_j   # next pos
        
        # if out of bounds, we are done
        if not (0 <= next_gi < m) or not (0 <= next_gj < n):
            break
        # change direction when obstacle encountered
        if rows[next_gi][next_gj] == "#":
            dir_idx = (dir_idx + 1) % 4
            continue
        # update position and visited
        guard_i, guard_j = next_gi, next_gj
        visited.add((guard_i, guard_j))

    print(f"{len(visited)=}")


def part2(guard_i, guard_j):
    # keep track of visited positions
    visited = set()
    visited.add((guard_i, guard_j))

    dir_idx = 0 # current direction index
    loops = 0   # loops encountered

    # walk through the path
    while True:
        delta_i, delta_j = DIRECTIONS[dir_idx]
        next_gi, next_gj = guard_i + delta_i, guard_j + delta_j # next pos
        
        # if out of bounds, we are done
        if not (0 <= next_gi < m) or not (0 <= next_gj < n):
            break
        # change direction when obstacle encountered
        if rows[next_gi][next_gj] == "#":
            dir_idx = (dir_idx + 1) % 4
            continue
        # if a position is not already in path,
        # put a obstacle there and see if guard will loop
        if (next_gi, next_gj) not in visited and willLoop(guard_i, guard_j, dir_idx):
            loops += 1
        # update position and visited
        guard_i, guard_j = next_gi, next_gj
        visited.add((guard_i, guard_j))
    
    print(f"{loops=}")

# used in part 2
# returns whether placing an obstacle on next pos causes a loop or not
def willLoop(guard_i, guard_j, dir_idx) -> bool:
    # obstacle pos
    obs_i, obs_j = guard_i + DIRECTIONS[dir_idx][0], guard_j + DIRECTIONS[dir_idx][1]

    # keep track of visited pos and the direction of travel
    visited: defaultdict[tuple[int, int], list[int]] = defaultdict(list)
    visited[(guard_i, guard_j)].append(dir_idx)
    
    # walk until guard exits map or loops
    while True:
        delta_i, delta_j = DIRECTIONS[dir_idx]
        next_gi, next_gj = guard_i + delta_i, guard_j + delta_j # next pos
        
        # if out of bounds, no loop
        if not (0 <= next_gi < m) or not (0 <= next_gj < n):
            return False
        # change direction when obstacle encountered
        if rows[next_gi][next_gj] == "#" or (next_gi == obs_i and next_gj == obs_j):
            dir_idx = (dir_idx + 1) % 4
            continue
        # we are looping if we encounter a visited pos in a visited direction
        if (next_gi, next_gj) in visited and dir_idx in visited[(next_gi, next_gj)]:
            return True
        
        # update position and visited
        guard_i, guard_j = next_gi, next_gj        
        visited[(guard_i, guard_j)].append(dir_idx)


part1(guard_i, guard_j)
part2(guard_i, guard_j)


  

 rust

    
use std::{collections::HashSet, fs, str::FromStr};

use color_eyre::eyre::{Report, Result};

type GridPosition = usize;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Direction {
    N,
    E,
    S,
    W,
}

impl Direction {
    fn clockwise(&self) -> Self {
        match self {
            Direction::N => Direction::E,
            Direction::E => Direction::S,
            Direction::S => Direction::W,
            Direction::W => Direction::N,
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Thing {
    Guard(Direction),
    Obstruction,
    Space,
}

#[derive(Debug, PartialEq, Eq)]
struct LabMap {
    grid: Vec<Thing>,
    width: usize,
    height: usize,
}

impl FromStr for LabMap {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let grid = s
            .chars()
            .filter_map(|ch| {
                use Thing::*;
                match ch {
                    '^' => Some(Guard(Direction::N)),
                    '>' => Some(Guard(Direction::E)),
                    'v' => Some(Guard(Direction::S)),
                    '<' => Some(Guard(Direction::W)),
                    '#' => Some(Obstruction),
                    '.' => Some(Space),
                    '\n' => None,
                    _ => unreachable!(),
                }
            })
            .collect::<Vec<_>>();
        let width = s
            .chars()
            .position(|ch| ch == '\n')
            .ok_or_else(|| Report::msg("grid width cannot be zero, or one line"))?;
        let height = grid.len() / width;
        Ok(Self {
            grid,
            width,
            height,
        })
    }
}

impl LabMap {
    fn neighbour(&self, i: GridPosition, dir: Direction) -> Option<GridPosition> {
        let width = self.width;
        let length = self.grid.len();
        use Direction::*;
        match dir {
            N if i >= width => Some(i - width),
            E if i % width != width - 1 => Some(i + 1),
            S if i + width < length => Some(i + width),
            W if i % width != 0 => Some(i - 1),
            _ => None,
        }
    }

    fn guard_pos(&self) -> Option<(GridPosition, Direction)> {
        self.grid
            .iter()
            .enumerate()
            .filter_map(|(pos, &thing)| match thing {
                Thing::Guard(dir) => Some((pos, dir)),
                _ => None,
            })
            .next()
    }

    fn path_len(&self) -> usize {
        let mut positions = HashSet::new();
        let mut next = self.guard_pos();
        while let Some((pos, dir)) = next {
            positions.insert(pos);

            next = self.neighbour(pos, dir).map(|npos| match self.grid[npos] {
                Thing::Space | Thing::Guard(_) => (npos, dir),
                Thing::Obstruction => (pos, dir.clockwise()),
            });
        }
        positions.len()
    }

    fn num_loops(&self) -> usize {
        (0..self.grid.len())
            .filter(|&pos| matches!(self.grid[pos], Thing::Space))
            .map(|pos| {
                let mut grid = self.grid.clone();
                grid[pos] = Thing::Obstruction;
                LabMap {
                    grid,
                    width: self.width,
                    height: self.height,
                }
            })
            .filter(LabMap::is_loop)
            .count()
    }

    fn is_loop(&self) -> bool {
        let mut positions = HashSet::new();
        let mut next = self.guard_pos();
        while let Some((pos, dir)) = next {
            let is_new = positions.insert((pos, dir));
            if !is_new {
                return true;
            }

            next = self.neighbour(pos, dir).map(|npos| match self.grid[npos] {
                Thing::Space | Thing::Guard(_) => (npos, dir),
                Thing::Obstruction => (pos, dir.clockwise()),
            });
        }
        false
    }
}

fn part1(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let map = LabMap::from_str(&input)?;
    Ok(map.path_len())
}

fn part2(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let map = LabMap::from_str(&input)?;
    Ok(map.num_loops())
}

fn main() -> Result<()> {
    color_eyre::install()?;

    println!("Part 1: {}", part1("input.txt")?);
    println!("Part 2: {}", part2("input.txt")?);
    Ok(())
}


  

 nim

    
type
  Vec2 = tuple[x,y: int]
  Dir = enum
    Up, Right, Down, Left
  Guard = object
    pos: Vec2
    dir: Dir

proc step(guard: var Guard, map: seq[string]): bool =
  let next: Vec2 =
    case guard.dir
    of Up: (guard.pos.x, guard.pos.y-1)
    of Right: (guard.pos.x+1, guard.pos.y)
    of Down: (guard.pos.x, guard.pos.y+1)
    of Left: (guard.pos.x-1, guard.pos.y)

  if next.y < 0 or next.x < 0 or next.y > map.high or next.x > map[0].high:
    return false
  elif map[next.y][next.x] == '#':
    guard.dir = Dir((guard.dir.ord + 1) mod 4)
  else:
    guard.pos = next
  true

proc solve(input: string): AOCSolution[int, int] =
  var map = input.splitLines()
  var guardStart: Vec2
  block findGuard:
    for y, line in map:
      for x, c in line:
        if c == '^':
          guardStart = (x, y)
          map[y][x] = '.'
          break findGuard

  var visited: HashSet[Vec2]
  block p1:
    var guard = Guard(pos: guardStart, dir: Up)
    while true:
      visited.incl guard.pos
      if not guard.step(map): break
    result.part1 = visited.len

  block p2:
    for (x, y) in visited - [guardStart].toHashSet:
      var loopCond: HashSet[Guard]
      var guard = Guard(pos: guardStart, dir: Up)
      var map = map
      map[y][x] = '#'

      while true:
        loopCond.incl guard
        if not guard.step(map): break
        if guard in loopCond:
          inc result.part2
          break


  

 undefined

    
RotateClock ← (
  ⊙⊙(⍉⇌)
  ⊙(⇌⍜(⊡0)(-⊙(⧻⊡0.)+1))
  ↻¯1
)

RotateCounter ← (
  ⊙⊙(⇌⍉)
  ⊙(⍜(⊡0)(-⊙(⧻.)+1)⇌)
  ↻1
)

NewPos ← (
  ⊙⍜(⊙⊡:)(-1+⊙(⊗@#)⟜↘⊙.)⟜°⊟
  ⍜(⊡1)⋅
)

MarkPath ← (
  RotateClock
  ⍢( # replace characters up til next '#'
    ⊙(⊙⍜(↘⊙⊡:)(⍜(↙)(▽:@^⧻)⊗@#.)⟜°⊟
      NewPos
    )
    RotateCounter
  | ⋅(≠0⊡0))
  ◌◌
)

PartOne ← (
  &rs ∞ &fo "input-6.txt"
  ⊜∘≠@\n.
  # maybe make compatible with
  # non-up facing inputs
  ♭⊚=@^.
  [0 1 2 3]
  MarkPath
  &fwa "test.txt" json.
  /+/+=@^
)

PartTwo ← (
  &rs ∞ &fo "input-6.txt"
  ⊜∘≠@\n.
  # maybe make compatible with
  # non-up facing inputs
  ♭⊚=@^.
  [0 1 2 3]
  ◡MarkPath
  ⊙::
  # rotate the field to match the intital state
  ⊙⊙(
    ⊙(⊚=@#)
    ⍢(⇌⍉|¬≍⊚=@#)
    ⊙◌
  )
  ⊙⊙(⊚=@^.)
  ⊙⊙⊙¤∩¤
  ⊞(⊙⊙(⍜⊡⋅@#)
    RotateClock
    ⊙NewPos
    ¤¯1_¯1_¯1
    ⍢(⊙◡(⊂⊢)
      ⊂
      ⊙(RotateCounter
        ⊙NewPos
      )
    | =1+⊙(∈↘1⇌)◡⋅(≠129⊡2)⊙(⊂⊢))
    # 129 = length of input array. Hardcoded because
    # the condition block doesn't seem to get the
    # input array passed to it so the length can't
    # be read dynamically
    ⊙(⊂⊢)
    ∈
    ⊙◌
  )
  /+♭
)

&p "Day 6:"
&pf "Part 1: "
&p PartOne
&pf "Part 2: "
&p PartTwo

  

 gleam

    
import gleam/dict
import gleam/io
import gleam/list
import gleam/option.{None, Some}
import gleam/result
import gleam/set.{type Set}
import gleam/string
import simplifile

pub type Point =
  #(Int, Int)

pub type Grid(a) =
  dict.Dict(Point, a)

pub type Direction {
  North
  East
  South
  West
}

pub type Loops {
  DoesLoop
  DoesNotLoop
}

pub type Guard {
  Guard(position: Point, direction: Direction)
}

fn get_guard(grid: Grid(String)) -> Guard {
  let pos = dict.filter(grid, fn(_pos, char) { char == "^" })
  let assert Ok(pos) = case dict.size(pos) {
    1 -> list.first(dict.keys(pos))
    0 -> panic as "No guard found in input!"
    _ -> panic as "More than one guard found in input!"
  }
  Guard(pos, North)
}

fn move_guard(guard: Guard) -> Guard {
  let new_pos = case guard.direction {
    North -> #(-1, 0)
    East -> #(0, 1)
    South -> #(1, 0)
    West -> #(0, -1)
  }
  Guard(
    #(guard.position.0 + new_pos.0, guard.position.1 + new_pos.1),
    guard.direction,
  )
}

fn turn_guard(guard: Guard) -> Guard {
  let new_dir = case guard.direction {
    North -> East
    East -> South
    South -> West
    West -> North
  }
  Guard(guard.position, new_dir)
}

fn get_obstacles(grid: Grid(String)) -> List(Point) {
  dict.filter(grid, fn(_pos, char) { char == "#" })
  |> dict.keys()
}

fn recurse_grid(
  grid: Grid(String),
  guard: Guard,
  obstacles: List(#(Int, Int)),
  visited: Set(#(#(Int, Int), Direction)),
) -> #(Set(#(#(Int, Int), Direction)), Loops) {
  let new_guard = move_guard(guard)
  let position = new_guard.position
  let dir = new_guard.direction
  case dict.has_key(grid, position) {
    False -> #(visited, DoesNotLoop)
    True -> {
      case set.contains(visited, #(position, dir)) {
        True -> {
          #(visited, DoesLoop)
        }
        False -> {
          case list.contains(obstacles, position) {
            True -> recurse_grid(grid, turn_guard(guard), obstacles, visited)
            False ->
              recurse_grid(
                grid,
                new_guard,
                obstacles,
                set.insert(visited, #(position, dir)),
              )
          }
        }
      }
    }
  }
}

fn get_grid_input(filename: String) -> Grid(String) {
  let lines =
    filename
    |> simplifile.read()
    |> result.unwrap("")
    |> string.trim()
    |> string.split("\n")
  use grid, row, row_idx <- list.index_fold(lines, dict.new())
  use grid, col, col_idx <- list.index_fold(string.to_graphemes(row), grid)
  dict.insert(grid, #(row_idx, col_idx), col)
}

fn part_one(
  grid: Grid(String),
) -> #(#(Set(#(#(Int, Int), Direction)), Loops), Int) {
  let guard = get_guard(grid)
  let obstacles = get_obstacles(grid)
  let visited = set.new() |> set.insert(#(guard.position, guard.direction))
  let visited = recurse_grid(grid, guard, obstacles, visited)
  let visited_without_dir =
    set.fold(visited.0, set.new(), fn(acc, x) { set.insert(acc, x.0) })
  #(visited, visited_without_dir |> set.size())
}

fn check_loop(grid: Grid(String), blocker: Point) -> Loops {
  let blocked_grid =
    dict.upsert(grid, blocker, fn(x) {
      case x {
        Some("^") -> "^"
        Some(_) -> "#"
        None -> "#"
      }
    })
  let visited = part_one(blocked_grid).0
  visited.1
}

fn part_two(grid: Grid(String), visited: Set(#(#(Int, Int), Direction))) {
  let visited =
    set.fold(visited, set.new(), fn(acc, x) { set.insert(acc, x.0) })
  use counter, position <- set.fold(visited, 0)
  case check_loop(grid, position) {
    DoesLoop -> counter + 1
    DoesNotLoop -> counter
  }
}

pub fn main() {
  let input = "input.in"
  let p1 = input |> get_grid_input() |> part_one
  let visited = p1.0.0
  io.debug(p1.1)
  input |> get_grid_input |> part_two(visited) |> io.debug()
}