Day 6: Guard Gallivant
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
5 points
*
Haskell
This was a fun one! Infinite loops, performance concerns and so on. Part 2 could be made a bit faster with a recursive approach (I think), but this is good enough for me. Lost quite a bit of time with an incorrect walk function that passed the test data and part 1 but not part 2.
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
4 points
Rust
In part 2 it took me some time to figure out that I cannot immediately move after turning, but then it worked fairly well. As a slight optimization I check only the places that were visited without obstacles (the solution from part 1). With this, part 2 takes 52ms.
Solution
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!();
also on github
4 points
C#
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();
}
4 points
Lisp
Brute forced part 2, but got a lot of reuse from part 1.
Part 1 and 2
(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)))
)))
4 points
*
Haskell
This one was fun, I think I wrote my first lazy infinite loop I cancel out at runtime, lost some time because I had misread the requirements on turning right.
Runs in 45 seconds on my Laptop in power-saver mode, which isn’t very fast I fear.
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
