DEV Community

Caleb Weeks
Caleb Weeks

Posted on

Advent of Code #6 (in Gleam)

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
    }
  })
}
Enter fullscreen mode Exit fullscreen mode

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay