diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/day16.exs | 194 | ||||
| -rw-r--r-- | src/day17.exs | 127 | ||||
| -rw-r--r-- | src/day18.exs | 94 | ||||
| -rw-r--r-- | src/day19.exs | 104 | ||||
| -rw-r--r-- | src/day20.exs | 122 | ||||
| -rw-r--r-- | src/day21.exs | 147 | ||||
| -rw-r--r-- | src/day22.exs | 65 | ||||
| -rw-r--r-- | src/day23.exs | 118 |
8 files changed, 971 insertions, 0 deletions
diff --git a/src/day16.exs b/src/day16.exs new file mode 100644 index 0000000..827dc25 --- /dev/null +++ b/src/day16.exs @@ -0,0 +1,194 @@ +defmodule Day16 do + defmodule State do + @enforce_keys [:pqueue, :map, :path, :dist] + defstruct [:pqueue, :map, :path, :dist] + + def new(game) do + pqueue = :gb_sets.from_list([{0, game.start}]) + map = :gb_trees.insert(game.start, 0, :gb_trees.empty()) + path = Map.new([{game.start, []}]) + dist = Map.new([{game.start, 0}]) + %State{pqueue: pqueue, map: map, path: path, dist: dist} + end + + def upsert(state, posdir, dist, prev) do + case :gb_trees.lookup(posdir, state.map) do + :none -> + pqueue = :gb_sets.insert({dist, posdir}, state.pqueue) + map = :gb_trees.insert(posdir, dist, state.map) + path = Map.put(state.path, posdir, [prev]) + distmap = Map.update(state.dist, posdir, dist, &min(&1, dist)) + %State{pqueue: pqueue, map: map, path: path, dist: distmap} + {_, odist} -> + distmap = Map.update!(state.dist, posdir, &min(&1, dist)) + cond do + dist > odist -> + %State{state | dist: distmap} + dist == odist -> + path = Map.update!(state.path, posdir, &[prev | &1]) + %State{state | path: path, dist: distmap} + true -> + pqueue = :gb_sets.delete({odist, posdir}, state.pqueue) + pqueue = :gb_sets.insert({dist, posdir}, pqueue) + map = :gb_trees.update(posdir, dist, state.map) + path = Map.put(state.path, posdir, [prev]) + %State{pqueue: pqueue, map: map, path: path, dist: distmap} + end + end + end + + def empty?(state) do + :gb_sets.is_empty(state.pqueue) + end + + def pop(state) do + {v, pqueue} = :gb_sets.take_smallest(state.pqueue) + {v, %State{state | pqueue: pqueue}} + end + + def optimal_dist(state, node) do + state.dist + |> Enum.filter(fn {{pos, _}, _} -> pos == node end) + |> Enum.map(fn {_, v} -> v end) + |> Enum.min() + end + + def optimal_path_nodes(state, node) do + nodes = state.dist + |> Enum.filter(fn {{pos, _}, _} -> pos == node end) + + mindist = nodes + |> Enum.map(fn {_, v} -> v end) + |> Enum.min() + + nodes = nodes + |> Enum.filter(fn {_, v} -> v == mindist end) + |> Enum.map(fn {posdir, _} -> posdir end) + + optimal_path_nodes(state, nodes, []) + end + + defp optimal_path_nodes(state, queue, acc) do + case queue do + [] -> + acc + |> Enum.map(fn {pos, _} -> pos end) + |> Enum.uniq() + [h | t] -> + acc = [h | acc] + queue = Map.fetch!(state.path, h) ++ t + optimal_path_nodes(state, queue, acc) + end + end + end + + defmodule Game do + @derive Inspect + defstruct [:grid, :start, :end] + + def from_data(data) do + grid = data + |> String.split("\n", trim: true) + |> Enum.with_index() + |> Enum.flat_map(fn {s, i} -> + String.codepoints(s) + |> Enum.with_index() + |> Enum.map(fn {c, j} -> {{i, j}, c} end) + end) + |> Map.new() + + start = grid + |> Enum.find_value(fn {pos, c} -> c == "S" and pos end) + |> then(& {&1, :right}) + + endpos = grid + |> Enum.find_value(fn {pos, c} -> c == "E" and pos end) + + %Game{grid: grid, start: start, end: endpos} + end + + def shortest(game) do + game + |> shortest(State.new(game)) + |> State.optimal_dist(game.end) + end + + def shortest_path_nodes(game) do + game + |> shortest(State.new(game)) + |> State.optimal_path_nodes(game.end) + end + + defp shortest(game, state) do + if State.empty?(state) do + state + else + {{dist, {pos, dir}}, state} = State.pop(state) + if pos == game.end do + shortest(game, state) + else + neighbors(game, {dist, {pos, dir}}) + for {ndist, nposdir} <- neighbors(game, {dist, {pos, dir}}), reduce: state do + state -> State.upsert(state, nposdir, ndist, {pos, dir}) + end + |> then(& shortest(game, &1)) + end + end + end + + defp neighbors(game, {dist, {{i, j}, dir}}) do + case dir do + :right -> + [{dist+1, {{i, j+1}, :right}}, + {dist+1001, {{i-1, j}, :up}}, + {dist+1001, {{i+1, j}, :down}}, + {dist+2001, {{i, j-1}, :left}}] + :left -> + [{dist+1, {{i, j-1}, :left}}, + {dist+1001, {{i-1, j}, :up}}, + {dist+1001, {{i+1, j}, :down}}, + {dist+2001, {{i, j+1}, :right}}] + :up -> + [{dist+1, {{i-1, j}, :up}}, + {dist+1001, {{i, j-1}, :left}}, + {dist+1001, {{i, j+1}, :right}}, + {dist+2001, {{i+1, j}, :down}}] + :down -> + [{dist+1, {{i+1, j}, :down}}, + {dist+1001, {{i, j-1}, :left}}, + {dist+1001, {{i, j+1}, :right}}, + {dist+2001, {{i-1, j}, :up}}] + end + |> Enum.filter(fn {_, {p, _}} -> + case Map.fetch(game.grid, p) do + :error -> false + {:ok, "#"} -> false + _ -> true + end + end) + end + end + + def part1(data) do + data + |> Game.from_data() + |> Game.shortest() + end + + def part2(data) do + data + |> Game.from_data() + |> Game.shortest_path_nodes() + |> Enum.count() + end +end + +data = IO.read(:stdio, :eof) + +{time1, ans1} = :timer.tc(fn -> Day16.part1(data) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") + +{time2, ans2} = :timer.tc(fn -> Day16.part2(data) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") diff --git a/src/day17.exs b/src/day17.exs new file mode 100644 index 0000000..9f9db29 --- /dev/null +++ b/src/day17.exs @@ -0,0 +1,127 @@ +defmodule Day17 do + defmodule Computer do + @derive Inspect + @enforce_keys [:a, :b, :c, :out, :instructions, :pointer] + defstruct @enforce_keys + + def from_data(data) do + [a, b, c | instructions] = Regex.scan(~r/\d+/, data) + |> Enum.map(&String.to_integer(hd(&1))) + + %Computer{a: a, b: b, c: c, out: [], instructions: instructions, pointer: 0} + end + + def run(comp) do + case instruction(comp) do + {:halt, comp} -> + comp + {:ok, comp} -> + run(comp) + end + end + + defp instruction(comp) do + case comp.instructions |> Enum.drop(comp.pointer) do + [] -> + {:halt, comp} + [0, r | _] -> + cr = combo(comp, r) + {:ok, %Computer{comp | a: Bitwise.bsr(comp.a, cr), pointer: comp.pointer+2}} + [1, r | _] -> + {:ok, %Computer{comp | b: Bitwise.bxor(comp.b, r), pointer: comp.pointer+2}} + [2, r | _] -> + cr = combo(comp, r) + {:ok, %Computer{comp | b: rem(cr, 8), pointer: comp.pointer+2}} + [3, r | _] -> + if comp.a == 0 do + {:ok, %Computer{comp | pointer: comp.pointer+2}} + else + {:ok, %Computer{comp | pointer: r}} + end + [4, _ | _] -> + {:ok, %Computer{comp | b: Bitwise.bxor(comp.b, comp.c), pointer: comp.pointer+2}} + [5, r | _] -> + cr = combo(comp, r) + {:ok, %Computer{comp | out: [rem(cr, 8) | comp.out], pointer: comp.pointer+2}} + [6, r | _] -> + cr = combo(comp, r) + {:ok, %Computer{comp | b: Bitwise.bsr(comp.a, cr), pointer: comp.pointer+2}} + [7, r | _] -> + cr = combo(comp, r) + {:ok, %Computer{comp | c: Bitwise.bsr(comp.a, cr), pointer: comp.pointer+2}} + end + end + + defp combo(comp, v) do + case v do + 0 -> 0 + 1 -> 1 + 2 -> 2 + 3 -> 3 + 4 -> comp.a + 5 -> comp.b + 6 -> comp.c + 7 -> raise "Invalid combo operand (7)" + end + end + end + + def part1(data) do + data + |> Computer.from_data() + |> Computer.run() + |> then(& &1.out) + |> Enum.reverse() + |> Enum.join(",") + end + + def part2(data) do + data + |> Computer.from_data() + |> then(& &1.instructions) + |> Enum.reverse() + |> solve2(0) + end + + defp solve2(rout, a) do + case rout do + [] -> + a + [h | t] -> + # I deduced the following by hand for my input, but maybe it could + # have been done programatically. An important takeway is that + # (for my input, and probably for all) `a` incerases by 3 bits for each + # iteration of the program. AS such, we can only need to check the + # possibilities over the last 3 bits (a..a+7) in each iteration ourselves + a = Bitwise.bsl(a, 3) + possible = a..a+7 + |> Enum.filter(fn a -> + Bitwise.band(a, 7) + |> Bitwise.bxor(5) + |> Bitwise.bxor(6) + |> Bitwise.bxor(Bitwise.bsr(a, Bitwise.band(a, 7) |> Bitwise.bxor(5))) + |> Bitwise.band(7) == h + end) + + case possible do + [] -> + :none + possible -> + possible + |> Enum.map(& solve2(t, &1)) + |> Enum.find(& &1 != :none) + || :none + end + end + end +end + +data = IO.read(:stdio, :eof) + +{time1, ans1} = :timer.tc(fn -> Day17.part1(data) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") + +{time2, ans2} = :timer.tc(fn -> Day17.part2(data) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") diff --git a/src/day18.exs b/src/day18.exs new file mode 100644 index 0000000..e97da36 --- /dev/null +++ b/src/day18.exs @@ -0,0 +1,94 @@ +defmodule Day18 do + defmodule Game do + @derive Inspect + @enforce_keys [:obj, :source, :target, :w, :h] + defstruct @enforce_keys + + def from_data(data, source, target) do + obj = data + |> String.split("\n", trim: true) + |> Enum.map(&integer_list/1) + |> Enum.map(&List.to_tuple/1) + + {w, h} = target + + %Game{obj: obj, source: source, target: target, w: w, h: h} + end + + defp integer_list(s), do: String.split(s, ",") |> Enum.map(&String.to_integer/1) + + def shortest(game, count_obj \\ nil) do + obj = + if count_obj == nil do + game.obj + else + Enum.take(game.obj, count_obj) + end + + %Game{game | obj: MapSet.new(obj)} + |> shortest(0, [game.source], MapSet.new([game.source])) + end + + defp shortest(game, i, q, v) do + case q do + [] -> + :none + q -> + if Enum.member?(q, game.target) do + i + else + for n <- q, reduce: {[], v} do + {q, v} -> + neighbors(game, n) + |> Enum.reject(&MapSet.member?(v, &1)) + |> Enum.reduce({q, v}, fn n, {q, v} -> {[n | q], MapSet.put(v, n)} end) + end + |> then(fn {q, v} -> shortest(game, i+1, q, v) end) + end + end + end + + defp neighbors(game, {x, y}) do + [{x+1, y}, {x-1, y}, {x, y+1}, {x, y-1}] + |> Enum.filter(fn {x, y} -> x >= 0 and x <= game.w and y >= 0 and y <= game.h end) + |> Enum.reject(&MapSet.member?(game.obj, &1)) + end + end + + def part1(data) do + data + |> Game.from_data({0, 0}, {70, 70}) + |> Game.shortest(1024) + end + + def part2(data) do + game = data + |> Game.from_data({0, 0}, {70, 70}) + + part2(game, 1, Enum.count(game.obj)) + end + + defp part2(game, l, r) do + if l == r do + Enum.at(game.obj, l-1) + |> then(fn {x, y} -> "#{x},#{y}" end) + else + m = div(l + r, 2) + if Game.shortest(game, m) != :none do + part2(game, m+1, r) + else + part2(game, l, m) + end + end + end +end + +data = IO.read(:stdio, :eof) + +{time1, ans1} = :timer.tc(fn -> Day18.part1(data) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") + +{time2, ans2} = :timer.tc(fn -> Day18.part2(data) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") diff --git a/src/day19.exs b/src/day19.exs new file mode 100644 index 0000000..9c9a1e2 --- /dev/null +++ b/src/day19.exs @@ -0,0 +1,104 @@ +defmodule Day19 do + defmodule Onsen do + @derive Inspect + @enforce_keys [:patterns, :designs] + defstruct @enforce_keys + + def from_data(data) do + [patterns, designs] = data + |> String.split("\n\n", trim: true) + + patterns = patterns + |> String.split(", ", trim: true) + + designs = designs + |> String.split("\n", trim: true) + + %Onsen{patterns: patterns, designs: designs} + end + + def count_feasible_designs(onsen) do + onsen.designs + |> Enum.filter(& feasible?(&1, onsen.patterns) |> elem(0)) + |> Enum.count() + end + + defp feasible?(design, patterns, vis \\ MapSet.new()) do + cond do + MapSet.member?(vis, design) -> + {false, vis} + design == "" -> + {true, vis} + true -> + for pat <- patterns, reduce: {false, MapSet.put(vis, design)} do + {acc, vis} -> + cond do + acc == true -> + {acc, vis} + String.starts_with?(design, pat) -> + design + |> String.split_at(String.length(pat)) + |> elem(1) + |> feasible?(patterns, vis) + true -> + {acc, vis} + end + end + end + end + + def count_feasible_ways(onsen) do + onsen.designs + |> Enum.map(& ways(&1, onsen.patterns) |> elem(0)) + |> Enum.sum() + end + + defp ways(design, patterns, vis \\ Map.new()) do + case Map.fetch(vis, design) do + {:ok, count} -> + {count, vis} + :error -> + if design == "" do + {1, vis} + else + for pat <- patterns, reduce: {0, vis} do + {acc, vis} -> + cond do + String.starts_with?(design, pat) -> + design + |> String.split_at(String.length(pat)) + |> elem(1) + |> ways(patterns, vis) + |> then(fn {acc2, vis} -> {acc + acc2, vis} end) + true -> + {acc, vis} + end + end + |> then(fn {acc, vis} -> {acc, Map.put(vis, design, acc)} end) + end + end + end + end + + def part1(data) do + data + |> Onsen.from_data() + |> Onsen.count_feasible_designs() + end + + def part2(data) do + data + |> Onsen.from_data() + |> Onsen.count_feasible_ways() + end +end + +data = IO.read(:stdio, :eof) + +{time1, ans1} = :timer.tc(fn -> Day19.part1(data) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") + +{time2, ans2} = :timer.tc(fn -> Day19.part2(data) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") diff --git a/src/day20.exs b/src/day20.exs new file mode 100644 index 0000000..8299199 --- /dev/null +++ b/src/day20.exs @@ -0,0 +1,122 @@ +defmodule Day20 do + defmodule Maze do + @derive Inspect + @enforce_keys [:positions, :walls, :source, :target] + defstruct @enforce_keys + + def from_data(data) do + positions = data + |> String.split("\n", trim: true) + |> Enum.with_index() + |> Enum.map(fn {l, i} -> + l + |> String.codepoints() + |> Enum.with_index() + |> Enum.map(fn {v, j} -> {{i, j}, v} end) + end) + |> List.flatten() + + source = Enum.find(positions, fn {_, v} -> v == "S" end) |> elem(0) + target = Enum.find(positions, fn {_, v} -> v == "E" end) |> elem(0) + + walls = positions + |> Enum.filter(fn {_, v} -> v == "#" end) + |> Enum.map(fn {p, _} -> p end) + + positions = positions + |> Enum.filter(fn {_, v} -> v != "#" end) + |> Enum.map(fn {p, _} -> p end) + |> MapSet.new() + + %Maze{positions: positions, walls: walls, source: source, target: target} + end + + def cheats(maze, seconds) do + # Get shortest distances for all nodes + dist = rev_shortest(maze) + + # Get cheats + for n1 <- maze.positions, n2 <- neighbors(maze, n1, seconds) do + {n1, n2, Map.get(dist, n1) - Map.get(dist, n2) - dist(n1, n2)} + end + end + + defp dist({x1, y1}, {x2, y2}), do: abs(x1-x2) + abs(y1-y2) + + defp rev_shortest(maze) do + maze.target + |> then(&rev_shortest(maze, :queue.from_list([{&1, 0}]), MapSet.new([&1]), Map.new())) + end + + defp rev_shortest(maze, q, inq, dist) do + case :queue.peek(q) do + :empty -> + dist + {_, {v, d}} -> + for n <- neighbors(maze, v), reduce: {:queue.drop(q), inq} do + {q, inq} -> + if MapSet.member?(inq, n) do + {q, inq} + else + {:queue.in({n, d+1}, q), MapSet.put(inq, n)} + end + end + |> then(fn {q, inq} -> rev_shortest(maze, q, inq, Map.put(dist, v, d)) end) + end + end + + defp neighbors(maze, {x, y}) do + [{x+1, y}, + {x-1, y}, + {x, y+1}, + {x, y-1}] + |> Enum.filter(&MapSet.member?(maze.positions, &1)) + end + + defp neighbors(maze, {x, y}, d) do + for i <- 0..d, j <- 0..d-i do + cond do + i == 0 and j == 0 -> + [] + i == 0 -> + [{x, y+j}, + {x, y-j}] + j == 0 -> + [{x+i, y}, + {x-i, y}] + true -> + [{x+i, y+j}, + {x-i, y+j}, + {x+i, y-j}, + {x-i, y-j}] + end + end + |> List.flatten() + |> Enum.filter(&MapSet.member?(maze.positions, &1)) + end + end + + def part1(data) do + data + |> Maze.from_data() + |> Maze.cheats(2) + |> Enum.count(& elem(&1, 2) >= 100) + end + + def part2(data) do + data + |> Maze.from_data() + |> Maze.cheats(20) + |> Enum.count(& elem(&1, 2) >= 100) + end +end + +data = IO.read(:stdio, :eof) + +{time1, ans1} = :timer.tc(fn -> Day20.part1(data) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") + +{time2, ans2} = :timer.tc(fn -> Day20.part2(data) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") diff --git a/src/day21.exs b/src/day21.exs new file mode 100644 index 0000000..8c2e0ce --- /dev/null +++ b/src/day21.exs @@ -0,0 +1,147 @@ +defmodule Day21 do + defmodule Keypad do + @derive Inspect + @enforce_keys [:type] + defstruct @enforce_keys + + def new(type) do + %Keypad{type: type} + end + + def shortest_paths(keypad, from, to) do + bfs([[{:nil, from}]], to, keypad) + end + + defp bfs(paths, to, keypad) do + finished = Enum.any?(paths, &(elem(hd(&1), 1) == to)) + + if finished do + Enum.filter(paths, &(elem(hd(&1), 1) == to)) + else + for path <- paths, neighbor <- neighbors(keypad, elem(hd(path), 1)) do + [neighbor | path] + end + |> bfs(to, keypad) + end + end + + defp neighbors(keypad, from) do + case keypad.type do + :numeric -> neighbors_numeric(from) + :directional -> neighbors_directional(from) + end + end + + defp neighbors_numeric(from) do + case from do + "A" -> %{left: "0", up: "3"} + "0" -> %{right: "A", up: "2"} + "1" -> %{right: "2", up: "4"} + "2" -> %{down: "0", left: "1", right: "3", up: "5"} + "3" -> %{down: "A", left: "2", up: "6"} + "4" -> %{down: "1", right: "5", up: "7"} + "5" -> %{down: "2", left: "4", right: "6", up: "8"} + "6" -> %{down: "3", left: "5", up: "9"} + "7" -> %{down: "4", right: "8"} + "8" -> %{down: "5", left: "7", right: "9"} + "9" -> %{down: "6", left: "8"} + end + end + + defp neighbors_directional(from) do + case from do + :A -> %{left: :up, down: :right} + :up -> %{right: :A, down: :down} + :left -> %{right: :down} + :down -> %{left: :left, up: :up, right: :right} + :right -> %{left: :down, up: :A} + end + end + end + + def part1(data, n \\ 2) do + data + |> String.split("\n", trim: true) + |> Enum.map(fn code -> + { + String.split(code, "A") |> hd() |> String.to_integer(), + shortest_dist(String.codepoints(code), "A", n, %{}) |> elem(0) + } + end) + # |> IO.inspect(charlists: :as_lists) + |> Enum.map(fn {a, b} -> a*b end) + |> Enum.sum() + end + + defp shortest_dist(code, start, n, state) do + chunks = [start | code] + |> Enum.chunk_every(2, 1, :discard) + + kpadtype = if start == "A" do :numeric else :directional end + + {values, nstate} = + for [from, to] <- chunks, reduce: {[], state} do + {values, state} -> + shortest_dist(from, to, n, kpadtype, state) + |> then(fn {v, state} -> {[v | values], state} end) + end + + {Enum.sum(values), nstate} + end + + defp shortest_dist(from, to, n, keypadtype, state) do + key = {from, to, n, keypadtype} + case Map.get(state, key) do + :nil -> + {values, nstate} = + for path <- paths(from, to, keypadtype), reduce: {[], state} do + {values, state} -> shortest_dist(path, n, state) + |> then(fn {v, s} -> {[v | values], s} end) + end + value = Enum.min(values) + {value, Map.put(nstate, key, value)} + value -> + {value, state} + end + end + + defp paths(from, to, keypad) do + case keypad do + :numeric -> + Keypad.new(:numeric) + :directional -> + Keypad.new(:directional) + end + |> Keypad.shortest_paths(from, to) + end + + defp shortest_dist(path, n, state) do + if n == 0 do + {Enum.count(path), state} + else + path + |> Enum.map(&(elem(&1, 0))) + |> then(&([:A | &1])) + |> Enum.reverse() + |> tl() + |> shortest_dist(:A, n-1, state) + end + end + + def part2(data) do + part1(data, 25) + end +end + +data = IO.read(:stdio, :eof) + +{time1, ans1} = :timer.tc(fn -> Day21.part1(data) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") # 184718 + +{time2, ans2} = :timer.tc(fn -> Day21.part2(data) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") # 228800606998554 + + + diff --git a/src/day22.exs b/src/day22.exs new file mode 100644 index 0000000..418631f --- /dev/null +++ b/src/day22.exs @@ -0,0 +1,65 @@ +defmodule Day22 do + def part1(data, n \\ 2000) do + data + |> String.split("\n", trim: true) + |> Enum.map(&String.to_integer/1) + |> Enum.map(&(secret_numbers(&1, n))) + |> Enum.map(&hd/1) + |> Enum.sum() + end + + defp secret_numbers(v, n) do + for _ <- 1..n, reduce: [v] do + v -> + [(v |> hd() |> change_value(6) |> change_value(-5) |> change_value(11)) | v] + end + end + + defp change_value(v, shift) do + v + |> Bitwise.bsl(shift) + |> Bitwise.bxor(v) + |> Integer.mod(16777216) + end + + def part2(data, n \\ 2000) do + data + |> String.split("\n", trim: true) + |> Enum.map(&String.to_integer/1) + |> Enum.map(&(secret_numbers(&1, n))) + |> Enum.map(&(sequences(&1, 10))) + |> Enum.reduce(%{}, fn s, acc -> + Map.merge(acc, s, fn _k, v1, v2 -> v1 + v2 end) + end) + |> Map.values() + |> Enum.max() + end + + defp sequences(vs, m) do + vs + |> Enum.map(&Integer.mod(&1, m)) + |> Enum.chunk_every(5, 1, :discard) # performance here could be improved + |> Enum.map(fn chunk -> {diffs(chunk), hd(chunk)} end) + |> Map.new() + end + + defp diffs(vs) do + vs + |> Enum.chunk_every(2, 1, :discard) + |> Enum.map(fn [a, b] -> a - b end) + |> List.to_tuple() + end +end + +data = IO.read(:stdio, :eof) + +{time1, ans1} = :timer.tc(fn -> Day22.part1(data) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") # 19822877190 + +{time2, ans2} = :timer.tc(fn -> Day22.part2(data) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") # 2277 + + + diff --git a/src/day23.exs b/src/day23.exs new file mode 100644 index 0000000..04d60ce --- /dev/null +++ b/src/day23.exs @@ -0,0 +1,118 @@ +defmodule Day23 do + defmodule Graph do + @derive Inspect + @enforce_keys [:nodes, :edges, :adj, :deg] + defstruct @enforce_keys + + def from_data(data) do + edges = data + |> String.split("\n", trim: true) + |> Enum.map(&String.split(&1, "-", trim: true)) + |> Enum.map(fn [a,b] -> if a < b do [a, b] else [b, a] end end) + + nodes = edges + |> List.flatten() + |> Enum.sort() + |> Enum.dedup() + + adj = + for [a, b] <- edges, reduce: %{} do + acc -> + add_adj(acc, a, b) + |> add_adj(b, a) + end + |> Enum.map(fn {k, v} -> {k, MapSet.new(v)} end) + |> Map.new() + + deg = Enum.map(adj, fn {k, v} -> {k, Enum.count(v)} end) |> Map.new() + + %Graph{edges: edges, nodes: nodes, adj: adj, deg: deg} + end + + defp add_adj(adj, a, b) do + Map.get_and_update(adj, a, fn v -> + case v do + nil -> {v, [b]} + lst -> {v, [b | lst]} + end + end) + |> elem(1) + end + + def cliques(graph, n) do + cliques([], graph.adj, [], MapSet.new(graph.nodes), n) + |> Enum.map(&Enum.sort/1) + |> Enum.sort() + |> Enum.dedup() + end + + # Could be improved, but this is fast enough + defp cliques(acc, adj, nodes, possible, n) do + if n == 0 do + [nodes | acc] + else + for v <- possible, reduce: acc do + acc -> + cliques(acc, adj, [v | nodes], MapSet.intersection(Map.get(adj, v), possible), n-1) + end + end + end + + def maxclique(graph) do + bk([], graph.adj, graph.deg, [], MapSet.new(graph.nodes), MapSet.new()) + |> Enum.max_by(&Enum.count/1) + end + + defp bk(acc, adj, deg, r, p, x) do + if Enum.empty?(p) && Enum.empty?(x) do + [r | acc] + else + u = Enum.max_by(MapSet.union(p, x), fn u -> Map.get(deg, u) end) + nu = Map.get(adj, u) + np = MapSet.difference(p, nu) + for v <- np, reduce: {acc, p, x} do + {acc, p, x} -> + { + bk( + acc, + adj, + deg, + [v | r], + MapSet.intersection(p, Map.get(adj, v)), + MapSet.intersection(x, Map.get(adj, v)) + ), + MapSet.delete(p, v), + MapSet.put(x, v) + } + end + |> elem(0) + end + end + end + + def part1(data) do + data + |> Graph.from_data() + |> Graph.cliques(3) + |> Enum.filter(fn nodes -> Enum.any?(nodes, fn v -> String.starts_with?(v, "t") end) end) + |> Enum.count() + end + + def part2(data) do + data + |> Graph.from_data() + |> Graph.maxclique() + |> Enum.sort() + |> Enum.join(",") + end +end + +data = IO.read(:stdio, :eof) + +{time1, ans1} = :timer.tc(fn -> Day23.part1(data) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") # 1046 + +{time2, ans2} = :timer.tc(fn -> Day23.part2(data) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") # de,id,ke,ls,po,sn,tf,tl,tm,uj,un,xw,yz |