From 8362e80cbdda472c2a92d9566e511cbce5a9ecf5 Mon Sep 17 00:00:00 2001 From: Alexandre Jesus Date: Sat, 7 Dec 2024 13:34:49 +0000 Subject: Day 6 --- flake.lock | 17 +++--- flake.nix | 9 +++- src/day06.exs | 171 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 188 insertions(+), 9 deletions(-) create mode 100644 src/day06.exs diff --git a/flake.lock b/flake.lock index 7e3bd39..9067273 100644 --- a/flake.lock +++ b/flake.lock @@ -20,15 +20,18 @@ }, "nixpkgs": { "locked": { - "lastModified": 1730327045, - "narHash": "sha256-xKel5kd1AbExymxoIfQ7pgcX6hjw9jCgbiBjiUfSVJ8=", - "path": "/nix/store/ylrrz211xgjzkcpyiafpq9y2yws7fyah-source", - "rev": "080166c15633801df010977d9d7474b4a6c549d7", - "type": "path" + "lastModified": 1733392399, + "narHash": "sha256-kEsTJTUQfQFIJOcLYFt/RvNxIK653ZkTBIs4DG+cBns=", + "owner": "nixos", + "repo": "nixpkgs", + "rev": "d0797a04b81caeae77bcff10a9dde78bc17f5661", + "type": "github" }, "original": { - "id": "nixpkgs", - "type": "indirect" + "owner": "nixos", + "ref": "nixos-unstable", + "repo": "nixpkgs", + "type": "github" } }, "root": { diff --git a/flake.nix b/flake.nix index 3e5ccdd..096769e 100644 --- a/flake.nix +++ b/flake.nix @@ -2,8 +2,13 @@ description = "Development shell for aoc2024"; inputs = { + nixpkgs = { + url = "github:nixos/nixpkgs/nixos-unstable"; + }; + flake-utils = { url = "github:numtide/flake-utils"; + inputs.nixpkgs.follows = "nixpkgs"; }; }; @@ -11,11 +16,11 @@ flake-utils.lib.eachDefaultSystem (system: let pkgs = import nixpkgs { inherit system; }; + beamPkgs = with pkgs.beam_minimal; packagesWith interpreters.erlang_27; in { devShells.default = pkgs.mkShell { buildInputs = [ - pkgs.elixir - pkgs.elixir-ls + beamPkgs.elixir_1_17 ]; }; }); diff --git a/src/day06.exs b/src/day06.exs new file mode 100644 index 0000000..09a1604 --- /dev/null +++ b/src/day06.exs @@ -0,0 +1,171 @@ +defmodule Day06 do + def parse_data(data) do + grid = data + |> String.split("\n", trim: true) + + guard = grid + |> map_elements("^") + |> hd() + + obstacles = grid + |> map_elements("#") + + obstacles_vert = obstacles + |> Enum.group_by(fn {i, _} -> i end, fn {_, j} -> j end) + |> Enum.map(fn {k, v} -> {k, v |> :gb_sets.from_list()} end) + |> Map.new() + + obstacles_hori = obstacles + |> Enum.group_by(fn {_, j} -> j end, fn {i, _} -> i end) + |> Enum.map(fn {k, v} -> {k, v |> :gb_sets.from_list()} end) + |> Map.new() + + grid = grid + |> Enum.map(& :array.from_list(String.codepoints(&1))) + |> :array.from_list() + + {guard, grid, obstacles_vert, obstacles_hori} + end + + def map_elements(grid, element) do + for {line, i} <- Enum.with_index(grid), + {v, j} <- Enum.with_index(String.codepoints(line)) do + if v == element do + {i, j} + else + nil + end + end + |> Enum.filter(& &1 != nil) + end + + def part1({i, j}, grid) do + path({i, j}, :up, grid) + |> Enum.map(fn {i, j, _} -> {i, j} end) + |> Enum.uniq() + |> Enum.count() + end + + def path(acc \\ [], {i, j}, dir, grid) do + acc = [{i, j, dir} | acc] + + {ni, nj, ndir} = next(i, j, dir) + + case check(ni, nj, grid) do + :invalid -> + acc + :obstacle -> + path(tl(acc), {i, j}, ndir, grid) + :valid -> + path(acc, {ni, nj}, dir, grid) + end + end + + def next(i, j, dir) do + case dir do + :up -> + {i-1, j, :right} + :right -> + {i, j+1, :down} + :down -> + {i+1, j, :left} + :left -> + {i, j-1, :up} + end + end + + def check(i, j, grid, extra \\ nil) do + cond do + i < 0 + or i == :array.size(grid) + or j < 0 + or j == :array.get(i, grid) |> :array.size() -> + :invalid + :array.get(j, :array.get(i, grid)) == "#" + or {i, j} == extra -> + :obstacle + true -> + :valid + end + end + + def part2(guard, grid, overt, ohori) do + path(guard, :up, grid) + |> Enum.map(fn {i, j, _} -> {i, j} end) + |> Enum.uniq() + |> Enum.filter(& &1 != guard) + |> Enum.map(fn {i, j} -> + is_loop?(guard, :up, grid, update(overt, i, j), update(ohori, j, i)) + end) + |> Enum.count(& &1) + end + + def update(m, k, v) do + Map.get_and_update(m, k, fn set -> + case set do + nil -> + {set, :gb_sets.from_list([v])} + set -> + {set, :gb_sets.add(v, set)} + end + end) + |> elem(1) + end + + def next(i, j, dir, overt, ohori) do + case dir do + :up -> + case :gb_sets.smaller(i, Map.get(ohori, j, :gb_sets.empty())) do + :none -> + :out + {_, v} -> + {v+1, j, :right} + end + :right -> + case :gb_sets.larger(j, Map.get(overt, i, :gb_sets.empty())) do + :none -> + :out + {_, v} -> + {i, v-1, :down} + end + :down -> + case :gb_sets.larger(i, Map.get(ohori, j, :gb_sets.empty())) do + :none -> + :out + {_, v} -> + {v-1, j, :left} + end + :left -> + case :gb_sets.smaller(j, Map.get(overt, i, :gb_sets.empty())) do + :none -> + :out + {_, v} -> + {i, v+1, :up} + end + end + end + + def is_loop?(cache \\ MapSet.new(), {i, j}, dir, grid, overt, ohori) do + key = {i, j, dir} + if MapSet.member?(cache, key) do + true + else + case next(i, j, dir, overt, ohori) do + :out -> + false + {ni, nj, ndir} -> + is_loop?(MapSet.put(cache, key), {ni, nj}, ndir, grid, overt, ohori) + end + end + end +end + +{guard, grid, overt, ohori} = IO.read(:stdio, :eof) |> Day06.parse_data() + +{time1 , ans1} = :timer.tc(fn -> Day06.part1(guard, grid) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") + +{time2 , ans2} = :timer.tc(fn -> Day06.part2(guard, grid, overt, ohori) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") -- cgit v1.2.3