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 } }) } 
Top comments (0)