Today was the first day I decided not to stay up to solve the puzzles right as they come out. Where I live, the puzzles come out at midnight, and for the first few days, I'm usually pretty confident that I can knock out a solution in about half an hour to an hour.
This puzzle was definitely a step up, particularly for part 2. It was the first time this year where I submitted a wrong answer and the first time I had to wait more than a second for the code to run. But I haven't had to reach for any advanced techniques yet. My solution is still pretty much the most straightforward approach.
Typically, these sorts of puzzles where you have to check a lot of things will start to benefit from divide and conquer techniques, caching strategies, or analytical approaches. The one 'optimization' I applied is I only tried placing new barriers along the standard route, but this is only a reduction of about 75% of the search space, which isn't really the defining dimension of the problem.
The other thing I did differently in this solution compared to previous solutions is using types and records. This helped me keep track in my head of the different pieces of data, and provides a nicer interface for pattern matching and accessing record fields. Here's my solution:
import gleam/int
import gleam/io
import gleam/list
import gleam/string
import gleam/result
import gleam/option
import gleam/set.{type Set}
import gleam/dict.{type Dict, insert}
import simplifile as file
const example = "
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
"
pub fn main() {
let assert Ok(input) = file.read("input")
let assert 41 = part1(example)
let assert 6 = part2(example)
part1(input) |> int.to_string |> io.println
part2(input) |> int.to_string |> io.println
}
type Coord = #(Int, Int)
type Direction {
Up
Down
Left
Right
}
type Guard {
Guard(position: Coord, direction: Direction)
}
type Space {
Blank
Barrier
}
type Map = Dict(Coord, Space)
fn parse_input(input: String) -> #(Map, Guard) {
input
|> string.trim
|> string.split("\n")
|> list.index_fold(#(dict.new(), Guard(#(0, 0), Up)), fn(init, line, x) {
line
|> string.to_graphemes
|> list.index_fold(init, fn(init, char, y) {
let #(map, start) = init
case char {
"." -> #(insert(map, #(x, y), Blank), start)
"#" -> #(insert(map, #(x, y), Barrier), start)
"^" -> #(insert(map, #(x, y), Blank), Guard(#(x, y), Up))
"v" -> #(insert(map, #(x, y), Blank), Guard(#(x, y), Down))
">" -> #(insert(map, #(x, y), Blank), Guard(#(x, y), Right))
"<" -> #(insert(map, #(x, y), Blank), Guard(#(x, y), Left))
_ -> init
}
})
})
}
fn rotate(guard: Guard) -> Guard {
case guard {
Guard(position, Up) -> Guard(position, Right)
Guard(position, Right) -> Guard(position, Down)
Guard(position, Down) -> Guard(position, Left)
Guard(position, Left) -> Guard(position, Up)
}
}
fn move(map: Map, guard: Guard) -> Result(Guard, Nil) {
let Guard(#(x, y), direction) = guard
let next_position = case direction {
Up -> #(x - 1, y)
Down -> #(x + 1, y)
Left -> #(x, y - 1)
Right -> #(x, y + 1)
}
map
|> dict.get(next_position)
|> result.map(fn(space) {
case space {
Blank -> Guard(next_position, direction)
Barrier -> rotate(guard)
}
})
}
fn standard_route(visited: Set(Coord), map: Map, guard: Guard) -> Set(Coord) {
case move(map, guard) {
Ok(guard) -> standard_route(set.insert(visited, guard.position), map, guard)
_ -> visited
}
}
fn part1(input: String) -> Int {
let #(map, start) = parse_input(input)
set.new()
|> set.insert(start.position)
|> standard_route(map, start)
|> set.size
}
type Route {
Exit
Loop
}
fn route(visited: Set(Guard), map: Map, guard: Guard) -> Route {
case move(map, guard) {
Ok(guard) ->
case set.contains(visited, guard) {
True -> Loop
False -> route(set.insert(visited, guard), map, guard)
}
_ -> Exit
}
}
fn part2(input: String) -> Int {
let #(map, start) = parse_input(input)
set.new()
|> set.delete(start.position)
|> standard_route(map, start)
|> set.fold(0, fn(count, coord) {
let new_map =
map
|> dict.upsert(coord, fn(space) {
space
|> option.map(fn(_) { Barrier })
|> option.unwrap(Blank)
})
case route(set.new(), new_map, start) {
Loop -> count + 1
Exit -> count
}
})
}
SOCIAL SHARE CARD GENERATOR