Here is my solution for day 4:
2 Likes
Today looked more intimidating than it actually was. General strategy is to bruteforce all directions. We can minimize bruteforce area by only searching when āXā (for part 1) or āAā (for part 2):
defmodule AOC.Y2024.Day4 do
@moduledoc false
use AOC.Solution
@dirs [
{-1, 0},
{1, 0},
{0, -1},
{0, 1},
{-1, -1},
{-1, 1},
{1, -1},
{1, 1}
]
@impl true
def load_data() do
Data.load_day_as_grid(2024, 4)
end
@impl true
def part_one({grid, _, _}) do
grid
|> Enum.filter(fn {_, v} -> v == "X" end)
|> General.map_sum(fn {coord, _} -> count_xmas(grid, coord) end)
end
@impl true
def part_two({grid, _, _}) do
grid
|> Enum.filter(fn {_, v} -> v == "A" end)
|> Enum.count(fn {coord, _} -> has_x_mas(grid, coord) end)
end
defp has_x_mas(grid, {r, c}) do
[tl, tr, bl, br] =
@dirs
|> Enum.slice(4..-1//1)
|> Enum.map(fn {dr, dc} -> {r + dr, c + dc} end)
|> Enum.map(fn coord -> Map.get(grid, coord, ".") end)
([tl, br] == ["M", "S"] or [tl, br] == ["S", "M"]) and
([tr, bl] == ["M", "S"] or [tr, bl] == ["S", "M"])
end
defp count_xmas(grid, {r, c}) do
for {dr, dc} <- @dirs do
0..3
|> Enum.map(fn j -> {r + dr * j, c + dc * j} end)
|> Enum.map_join(fn coord -> Map.get(grid, coord, ".") end)
end
|> Enum.count(fn v -> v == "XMAS" end)
end
end
2 Likes
Bruteforcing is fun, indeed!
I feel part 2 is actually easier.
defmodule AoC2024.Day04 do
def part_1(grid) do
directions =
for di <- -1..1,
dj <- -1..1,
di != 0 or dj != 0,
do: {di, dj}
directions
|> Enum.map(fn {di, dj} ->
Enum.count(Map.keys(grid), fn coord ->
coord
|> Stream.iterate(fn {i, j} -> {i + di, j + dj} end)
|> Stream.take(4)
|> Enum.map(&grid[&1])
|> Kernel.==(~c"XMAS")
end)
end)
|> Enum.sum()
end
def part_2(grid) do
Enum.count(grid, fn
{{i, j}, ?A} ->
[grid[{i - 1, j - 1}], grid[{i + 1, j + 1}]] in [~c"MS", ~c"SM"] and
[grid[{i - 1, j + 1}], grid[{i + 1, j - 1}]] in [~c"MS", ~c"SM"]
_ ->
false
end)
end
end
where grid is built like this:
charlists = puzzle_input |> String.split() |> Enum.map(&String.to_charlist/1)
grid =
for {row, i} <- Enum.with_index(charlists),
{char, j} <- Enum.with_index(row),
into: %{},
do: {{i, j}, char}
2 Likes
I think thereās a subtle bug in your part 2 though - what if:
# this is "MS"
[grid[{i - 1, j - 1}], grid[{i + 1, j + 1}]] in [~c"MS", ~c"SM"]
# and this is "SM"?
[grid[{i - 1, j + 1}], grid[{i + 1, j - 1}]] in [~c"MS", ~c"SM"]
Or I may have misunderstood your algorithm here!
Actually, the line before and checks the cases like
M S
A A
S M
And the line after and checks
M S
A A
S M
My solution relies on my Grid module so it may not be very clear.
But I can see you guys have very short and contained solutions!
defmodule AdventOfCode.Solutions.Y24.Day04 do
alias AdventOfCode.Grid
alias AoC.Input
def parse(input, _part) do
input
|> Input.stream!(trim: true)
|> Grid.parse_stream(fn <<c>> -> {:ok, c} end)
end
def part_one(grid) do
grid
|> Enum.filter(fn {_, c} -> c == ?X end)
|> Enum.map(&elem(&1, 0))
|> Enum.map(&count_xmas(&1, grid))
|> Enum.sum()
end
defp count_xmas(pos, grid) do
for dir <- Grid.directions(8), step <- 0..3 do
Grid.translate(pos, dir, step)
end
|> Enum.chunk_every(4)
|> Enum.map(&to_word(&1, grid))
|> Enum.filter(&(&1 == ~c"XMAS"))
|> length()
end
defp to_word(coords, grid) do
Enum.map(coords, &Map.get(grid, &1))
end
def part_two(grid) do
grid
|> Enum.filter(fn {_, c} -> c == ?A end)
|> Enum.map(&elem(&1, 0))
|> Enum.count(&is_cross(&1, grid))
end
defp is_cross(pos, grid) do
nw = Map.get(grid, Grid.translate(pos, :nw))
se = Map.get(grid, Grid.translate(pos, :se))
sw = Map.get(grid, Grid.translate(pos, :sw))
ne = Map.get(grid, Grid.translate(pos, :ne))
((nw == ?M and se == ?S) or (nw == ?S and se == ?M)) and
((ne == ?M and sw == ?S) or (ne == ?S and sw == ?M))
end
end
Edit: filtering on start == X for part 1 for speed, thank you 
Oh I really like the idea of having helpers in the grid for moving in different directions! Much less magic -1 and 1 everywhere 
2 Likes
#!/usr/bin/env elixir
# Aoc 2024. day 4.
defmodule Part1 do
@spec xmas(map(), non_neg_integer(), non_neg_integer()) :: non_neg_integer()
def xmas(m, r, c) do
b2i(unquote(:"xmasā")(m, r, c)) +
b2i(unquote(:"xmasā")(m, r, c)) +
b2i(unquote(:"xmasā")(m, r, c)) +
b2i(unquote(:"xmasā")(m, r, c)) +
b2i(unquote(:"xmasā")(m, r, c)) +
b2i(unquote(:"xmasā")(m, r, c)) +
b2i(unquote(:"xmasā")(m, r, c)) +
b2i(unquote(:"xmasā")(m, r, c))
end
defp unquote(:"xmasā")(m, r, c),
do: m[{r,c}] == "X" && m[{r-1,c}] == "M" && m[{r-2,c}] == "A" && m[{r-3,c}] == "S"
defp unquote(:"xmasā")(m, r, c),
do: m[{r,c}] == "X" && m[{r-1,c+1}] == "M" && m[{r-2,c+2}] == "A" && m[{r-3,c+3}] == "S"
defp unquote(:"xmasā")(m, r, c),
do: m[{r,c}] == "X" && m[{r,c+1}] == "M" && m[{r,c+2}] == "A" && m[{r,c+3}] == "S"
defp unquote(:"xmasā")(m, r, c),
do: m[{r,c}] == "X" && m[{r+1,c+1}] == "M" && m[{r+2,c+2}] == "A" && m[{r+3,c+3}] == "S"
defp unquote(:"xmasā")(m, r, c),
do: m[{r,c}] == "X" && m[{r+1,c}] == "M" && m[{r+2,c}] == "A" && m[{r+3,c}] == "S"
defp unquote(:"xmasā")(m, r, c),
do: m[{r,c}] == "X" && m[{r+1,c-1}] == "M" && m[{r+2,c-2}] == "A" && m[{r+3,c-3}] == "S"
defp unquote(:"xmasā")(m, r, c),
do: m[{r,c}] == "X" && m[{r,c-1}] == "M" && m[{r,c-2}] == "A" && m[{r,c-3}] == "S"
defp unquote(:"xmasā")(m, r, c),
do: m[{r,c}] == "X" && m[{r-1,c-1}] == "M" && m[{r-2,c-2}] == "A" && m[{r-3,c-3}] == "S"
def b2i(true), do: 1
def b2i(false), do: 0
end
map = File.stream!("../day04.txt")
|> Stream.with_index()
|> Enum.reduce(%{}, fn {line, row}, map ->
line
|> String.trim_trailing()
|> String.codepoints()
|> Enum.with_index()
|> Enum.reduce(map, fn {c, col}, map -> Map.put(map, {row, col}, c) end)
end)
# part 1
Enum.reduce(map, 0, fn {{r,c},_char}, n -> n+Part1.xmas(map, r, c) end)
|> IO.inspect(label: "part 1")
defmodule Part2 do
@spec xmas(map(), non_neg_integer(), non_neg_integer()) :: boolean()
def xmas(m, r, c) do
unquote(:"xmasāā")(m, r, c) && unquote(:"xmasāā")(m, r, c)
end
defp unquote(:"xmasāā")(m, r, c),
do: m[{r,c}] == "A" && ((m[{r+1,c-1}] == "M" && m[{r-1,c+1}] == "S") || (m[{r+1,c-1}] == "S" && m[{r-1,c+1}] == "M"))
defp unquote(:"xmasāā")(m, r, c),
do: m[{r,c}] == "A" && ((m[{r+1,c+1}] == "M" && m[{r-1,c-1}] == "S") || (m[{r+1,c+1}] == "S" && m[{r-1,c-1}] == "M"))
end
# part 2
Enum.reduce(map, 0, fn {{r,c},_char}, n -> n+Part1.b2i(Part2.xmas(map, r, c)) end)
|> IO.inspect(label: "part 2")
2 Likes
Part1
defmodule Advent.Y2024.Day04.Part1 do
def run(puzzle) do
grid = parse(puzzle)
grid
|> find_char("X")
|> Enum.map(fn pos ->
pos |> directions() |> Enum.count(&(multiple_get(grid, &1) == "MAS"))
end)
|> Enum.sum()
end
def parse(puzzle) do
for {row, y} <- puzzle |> String.split("\n") |> Enum.with_index(),
{char, x} <- row |> String.graphemes() |> Enum.with_index(),
into: %{},
do: {{x, y}, char}
end
def find_char(grid, match) do
grid |> Enum.filter(fn {_, c} -> c == match end) |> Enum.map(&elem(&1, 0))
end
def directions({x, y}) do
[
[{x + 1, y}, {x + 2, y}, {x + 3, y}],
[{x - 1, y}, {x - 2, y}, {x - 3, y}],
[{x, y + 1}, {x, y + 2}, {x, y + 3}],
[{x, y - 1}, {x, y - 2}, {x, y - 3}],
[{x + 1, y + 1}, {x + 2, y + 2}, {x + 3, y + 3}],
[{x - 1, y - 1}, {x - 2, y - 2}, {x - 3, y - 3}],
[{x - 1, y + 1}, {x - 2, y + 2}, {x - 3, y + 3}],
[{x + 1, y - 1}, {x + 2, y - 2}, {x + 3, y - 3}]
]
end
def multiple_get(grid, positions) do
Enum.map_join(positions, &Map.get(grid, &1))
end
end
Part2
defmodule Advent.Y2024.Day04.Part2 do
alias Advent.Y2024.Day04.Part1
def run(puzzle) do
grid = Part1.parse(puzzle)
a_positions = Part1.find_char(grid, "A")
Enum.count(a_positions, &xmas?(grid, &1))
end
def xmas?(grid, {x, y}) do
grid
|> Part1.multiple_get([{x - 1, y - 1}, {x + 1, y - 1}, {x + 1, y + 1}, {x - 1, y + 1}])
|> Kernel.in(["MMSS", "MSSM", "MSSM", "SSMM", "SMMS"])
end
end
Using NIFs for the fun of it Using macOS 14.7.1 and Homebrew.
Compilation.
export ERL_INCLUDE_PATH=/opt/homebrew/lib/erlang/usr/include
cc -fPIC -I $ERL_INCLUDE_PATH -dynamiclib -undefined dynamic_lookup -o day04_array.so day04_array.c
elixirc day04_array.ex
First timing with the map is pure Elixir (cfr. above my solution) and the other ones using the array is with C code. Since the array is stateful, we do not need to reduce using it as an accumulator. But I copy/pasted the Elixir solution and left it as is.
$ ./day04.exs
Set up the map in 7205 Āµs
Part 1 (map): 2427. Job done in 4360 Āµs
Part 2 (map): 1900. Job done in 2867 Āµs
Number of rows/cols: 140
Set up the array in 821 Āµs
Part 1 (array): 2427. Job done in 576 Āµs
Part 2 (array): 1900. Job done in 502 Āµs
Using C to solve day 4. The file is day04.ex.
# setting up the array
%File.Stat{size: size} = File.stat!("../day04.txt")
# same number of rows and columns + 1 \n per row
rows = trunc((-1 + :math.sqrt(1+4*size)) / 2) # positive solution of quadratic equation
IO.puts "Number of rows/cols: #{rows}"
start = System.monotonic_time(:microsecond)
array = File.stream!("../day04.txt")
|> Stream.with_index()
|> Enum.reduce(Day04Array.new(rows, rows), fn {line, row}, array ->
line
|> String.trim_trailing()
|> String.to_charlist()
|> Enum.with_index()
|> Enum.reduce(array, fn {c, col}, array -> Day04Array.set(array, row, col, c) end)
end)
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Set up the array in #{elapsed} Āµs"
# part 1. array
start = System.monotonic_time(:microsecond)
n = for r <- 0..rows-1, c <- 0..rows-1, reduce: 0 do
n -> n + Day04Array.count_xmas(array, r, c)
end
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Part 1 (array): #{n}. Job done in #{elapsed} Āµs"
# part 2. array
start = System.monotonic_time(:microsecond)
n = for r <- 0..rows-1, c <- 0..rows-1, reduce: 0 do
n -> n + Day04Array.is_xmas(array, r, c)
end
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Part 2 (array): #{n}. Job done in #{elapsed} Āµs"
day04_array.ex
defmodule Day04Array do
@on_load :load_nifs
def load_nifs do
:erlang.load_nif(~c"./day04_array", 0)
end
def new(_size1, _size2) do
raise "NIF new/2 not implemented"
end
def new(_size1, _size2, _value) do
raise "NIF new/3 not implemented"
end
def get(_array, _index1, _index2) do
raise "NIF get/3 not implemented"
end
def set(_array, _index1, _index2, _value) do
raise "NIF set/4 not implemented"
end
def count_xmas(_array, _row, _col) do
raise "NIF count_xmas/3 not implemented"
end
def is_xmas(_array, _row, _col) do
raise "NIF is_xmas/3 not implemented"
end
end
day04_array.c
#include "erl_nif.h"
#include <limits.h>
ErlNifResourceType* RES_TYPE;
typedef struct {
int* array;
unsigned int size1;
unsigned int size2;
} array_t;
void array_destructor(ErlNifEnv* env, void* res) { free(((array_t*)res)->array); }
int load(ErlNifEnv* env, void** priv_data, ERL_NIF_TERM load_info) {
int flags = ERL_NIF_RT_CREATE | ERL_NIF_RT_TAKEOVER;
RES_TYPE = enif_open_resource_type(env, NULL, "day04_array", array_destructor, flags, NULL);
if (RES_TYPE == NULL) return -1;
return 0;
}
static ERL_NIF_TERM new(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) {
if (argc != 2) return enif_make_badarg(env);
unsigned int size1, size2;
if (!enif_get_uint(env, argv[0], &size1)) return enif_make_badarg(env);
if (!enif_get_uint(env, argv[1], &size2)) return enif_make_badarg(env);
array_t* res = enif_alloc_resource(RES_TYPE, sizeof(array_t));
res->size1 = size1;
res->size2 = size2;
res->array = malloc(size1*size2*sizeof(int));
if (res->array == NULL) return enif_make_badarg(env);
ERL_NIF_TERM term = enif_make_resource(env, res);
enif_release_resource(res);
return term;
}
static ERL_NIF_TERM get(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) {
if (argc != 3) return enif_make_badarg(env);
unsigned int idx1, idx2;
if (!enif_get_uint(env, argv[1], &idx1)) return enif_make_badarg(env);
if (!enif_get_uint(env, argv[2], &idx2)) return enif_make_badarg(env);
array_t* res;
if (!enif_get_resource(env, argv[0], RES_TYPE, (void**) &res)) return enif_make_badarg(env);
if (idx1 < 0 || idx1 >= res->size1 || idx2 < 0 || idx2 >= res->size2 ) return enif_make_badarg(env);
return enif_make_int(env, *(res->array + idx1*res->size2 + idx2));
}
static ERL_NIF_TERM set(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) {
if (argc != 4) return enif_make_badarg(env);
unsigned int idx1, idx2;
if (!enif_get_uint(env, argv[1], &idx1)) return enif_make_badarg(env);
if (!enif_get_uint(env, argv[2], &idx2)) return enif_make_badarg(env);
int value;
if (!enif_get_int(env, argv[3], &value)) return enif_make_badarg(env);
array_t* res;
if (!enif_get_resource(env, argv[0], RES_TYPE, (void**) &res)) return enif_make_badarg(env);
if (idx1 < 0 || idx1 >= res->size1 || idx2 < 0 || idx2 >= res->size2 ) return enif_make_badarg(env);
*(res->array + idx1*res->size2 + idx2) = value;
return argv[0];
}
static ERL_NIF_TERM count_xmas(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) {
if (argc != 3) return enif_make_badarg(env);
int r, c;
if (!enif_get_int(env, argv[1], &r)) return enif_make_badarg(env);
if (!enif_get_int(env, argv[2], &c)) return enif_make_badarg(env);
array_t* res;
if (!enif_get_resource(env, argv[0], RES_TYPE, (void**) &res)) return enif_make_badarg(env);
if (*(res->array + r*res->size2 + c) != 'X') return enif_make_int(env, 0);
int count = 0;
if (r - 3 >= 0) count += *(res->array + (r-1)*res->size2 + c) == 'M' && *(res->array + (r-2)*res->size2 + c) == 'A' && *(res->array + (r-3)*res->size2 + c) == 'S';
if (r - 3 >= 0 && c + 3 < res->size2) count += *(res->array + (r-1)*res->size2 + c+1) == 'M' && *(res->array + (r-2)*res->size2 + c+2) == 'A' && *(res->array + (r-3)*res->size2 + c+3) == 'S';
if (c + 3 < res->size2) count += *(res->array + r*res->size2 + c+1) == 'M' && *(res->array + r*res->size2 + c+2) == 'A' && *(res->array + r*res->size2 + c+3) == 'S';
if (r + 3 < res->size1 && c + 3 < res->size2) count += *(res->array + (r+1)*res->size2 + c+1) == 'M' && *(res->array + (r+2)*res->size2 + c+2) == 'A' && *(res->array + (r+3)*res->size2 + c+3) == 'S';
if (r + 3 < res->size1) count += *(res->array + (r+1)*res->size2 + c) == 'M' && *(res->array + (r+2)*res->size2 + c) == 'A' && *(res->array + (r+3)*res->size2 + c) == 'S';
if (r + 3 < res->size1 && c - 3 >= 0) count += *(res->array + (r+1)*res->size2 + c-1) == 'M' && *(res->array + (r+2)*res->size2 + c-2) == 'A' && *(res->array + (r+3)*res->size2 + c-3) == 'S';
if (c - 3 >= 0) count += *(res->array + r*res->size2 + c-1) == 'M' && *(res->array + r*res->size2 + c-2) == 'A' && *(res->array + r*res->size2 + c-3) == 'S';
if (r - 3 >= 0 && c - 3 >= 0) count += *(res->array + (r-1)*res->size2 + c-1) == 'M' && *(res->array + (r-2)*res->size2 + c-2) == 'A' && *(res->array + (r-3)*res->size2 + c-3) == 'S';
return enif_make_int(env, count);
}
static ERL_NIF_TERM is_xmas(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) {
if (argc != 3) return enif_make_badarg(env);
int r, c;
if (!enif_get_int(env, argv[1], &r)) return enif_make_badarg(env);
if (!enif_get_int(env, argv[2], &c)) return enif_make_badarg(env);
array_t* res;
if (!enif_get_resource(env, argv[0], RES_TYPE, (void**) &res)) return enif_make_badarg(env);
if (*(res->array + r*res->size2 + c) != 'A') return enif_make_int(env, 0);
int b = 0;
if (r-1>=0 && r+1<res->size1 && c-1>=0 && c+1<res->size2) {
b = ((*(res->array + (r+1)*res->size2 + c-1) == 'M' && *(res->array + (r-1)*res->size2 + c+1) == 'S') ||
(*(res->array + (r+1)*res->size2 + c-1) == 'S' && *(res->array + (r-1)*res->size2 + c+1) == 'M')) &&
((*(res->array + (r+1)*res->size2 + c+1) == 'M' && *(res->array + (r-1)*res->size2 + c-1) == 'S') ||
(*(res->array + (r+1)*res->size2 + c+1) == 'S' && *(res->array + (r-1)*res->size2 + c-1) == 'M'));
}
return enif_make_int(env, b);
}
static ErlNifFunc nif_funcs[] =
{
{"new", 2, new},
{"new", 3, new},
{"get", 3, get},
{"set", 4, set},
{"count_xmas", 3, count_xmas},
{"is_xmas", 3, is_xmas}
};
ERL_NIF_INIT(Elixir.Day04Array, nif_funcs, load, NULL, NULL, NULL);
EDIT: changed the Elixir code to check for X or A first and avoid doing extra work if absent. It is more fair regarding the timing comparison with C.
2 Likes
Nothing too fancy. I did some basic optimizations like checking only from X (in p1) and A (in p2), plus reduce_while in p1 to stop early if thereās no matches.
Added some padding and made sub matrixes. Not optimal at all. 
defmodule Aoc2024.Solutions.Y24.Day04 do
alias AoC.Input
def parse(input, part) do
input =
input
|> Input.stream!(trim: true)
|> Enum.map(&String.codepoints(&1 <> "YYY"))
|> (fn input -> input ++ padding(length(hd(input))) end).()
n = if part == :part_one, do: 4, else: 3
for x <- 0..(length(input) - n), y <- 0..(length(hd(input)) - n) do
{_, rest_x} = Enum.split(input, x)
rest_rows = Enum.take(rest_x, n)
Enum.map(rest_rows, fn rest_row ->
{_, rest_y} = Enum.split(rest_row, y)
Enum.take(rest_y, n)
end)
end
end
def part_one(problem), do: Enum.reduce(problem, 0, &(&2 + count_xmas(&1)))
def part_two(problem), do: Enum.reduce(problem, 0, &(&2 + count_mas(&1)))
defp count_xmas([[a1, a2, a3, a4], [b1, b2, b3, _b4], [c1, c2, c3, _c4], [d1, _d2, _d3, d4]]) do
list = [
a1 <> a2 <> a3 <> a4,
a1 <> b1 <> c1 <> d1,
a1 <> b2 <> c3 <> d4,
a4 <> b3 <> c2 <> d1
]
Enum.reduce(list, 0, fn e, acc ->
case e do
"XMAS" -> acc + 1
"SAMX" -> acc + 1
_ -> acc
end
end)
end
defp count_mas([[a1, _a2, a3], [_b1, b2, _b3], [c1, _c3, c3]]) do
case b2 <> a1 <> a3 <> c1 <> c3 do
"AMMSS" -> 1
"ASSMM" -> 1
"ASMSM" -> 1
"AMSMS" -> 1
_ -> 0
end
end
defp padding(n) do
for _ <- 0..2 do
for _ <- 0..(n - 1) do
"Y"
end
end
end
end
Solution for 2024 day 4
part_one: 2427 in 82.75ms
part_two: 1900 in 49.76ms
I could try nx now that I thought about itā¦ 
Ugh. Grids. Just grunt work.
I decided to use :array to represent the grid as I know the O(log n) lookup of maps are not ideal. Combined with for, itās not very elixir-like. I agree with @lkuty that native code is probably the way to go for this kind of thing. I might come back to this when I have more free time next year to try it with Zigler.
Four of these for part 1:
for y <- 0..(n - 1), x <- 0..(n - 4), reduce: 0 do
count ->
for x_offset <- 0..(4 - 1), into: "" do
:array.get(x + x_offset, :array.get(y, grid))
end
|> consider(count)
end
and some similar stuff in part 2.
On my M1 the times were 15ms and 4ms. Not sure how that compares to the Map solutions.
It took me some time to get to the solution today. I solved part 2 by counting the diagonal occurrences of āMASā in the 3x3 grid around the current position. If there are more than one then it is a valid X. I wondered if it was possible to have more than two āMASā occurrences, but it is not because if two edges start with āMā then the other two edges must end with āSā obviously 
For both solutions, I construct the full word / sequence before comparing it with āMASā or "XMAS. An optimization would be to stop earlier, e.g., if the word doesnāt start with X or M at allā¦
Source Code:
It looks like Erlang arrays use a tree (trie maybe?) data structure and have O(log n) time complexity. See otp/lib/stdlib/src/array.erl at 44ffe8811dfcf3d2fe04d530c6e8fac5ca384e02 Ā· erlang/otp Ā· GitHub
I ācheatedā a little bit because the C implementation is not just for 2D arrays of ints but it is specifically made for that problem. It allows to avoid many round-trips between Elixir and C as we check if we have an XMAS candidate. I could have gone all-in with C but then the Elixir code would have just been some sort of a driver for the C code. Would have been faster for sure.
Haha, oh well. I wonder why that info hidden in a comment instead of being in the moduledocs (which I read before starting, but didnāt find any information about performanceā¦)
1 Like
Yes, it should be in the doc of the arrays module. This is an important info.
For part 1 I rotates the matrix instead of looking in differente directions.
And for part 2, I went with a sliding window using Enum,chunks =)
defmodule Smaoc.Solution.Day4 do
def solve(:part1, input) do
matrix = parse_input(input)
[
[],
[:reverse],
[:transpose],
[:transpose, :reverse],
[:rotate45],
[:rotate45, :reverse],
[:reverse, :rotate45],
[:reverse, :rotate45, :reverse]
]
|> Enum.map(
&(matrix
|> apply_operations(&1)
|> count_XMAS)
)
|> Enum.sum()
end
def solve(:part2, input) do
valid_patterns = [
~r/M.M.A.S.S/,
~r/M.S.A.M.S/,
~r/S.M.A.S.M/,
~r/S.S.A.M.M/
]
input
|> parse_input()
|> Enum.chunk_every(3, 1, :discard)
|> Enum.map(fn row ->
row
|> transpose()
|> Enum.chunk_every(3, 1, :discard)
|> Enum.count(fn chunk ->
Enum.any?(valid_patterns, &Regex.match?(&1, to_string(chunk)))
end)
end)
|> Enum.sum()
end
defp parse_input(input) do
input
|> String.split("\n", trim: true)
|> Enum.map(&String.split(&1, "", trim: true))
end
def reverse(matrix), do: Enum.map(matrix, &Enum.reverse/1)
def transpose(matrix) do
matrix
|> Enum.zip()
|> Enum.map(&Tuple.to_list/1)
end
def rotate45(matrix) do
for(
{row, i} <- Enum.with_index(matrix),
{v, j} <- Enum.with_index(row),
do: {i + j, v}
)
|> Enum.group_by(&elem(&1, 0), &elem(&1, 1))
|> Enum.sort()
|> Enum.map(&elem(&1, 1))
end
def count_XMAS(matrix) do
matrix
|> Enum.map(fn l ->
~r/XMAS/
|> Regex.scan(to_string(l))
|> Enum.count()
end)
|> Enum.sum()
end
defp apply_operations(matrix, ops) do
Enum.reduce(ops, matrix, fn op, m -> apply(__MODULE__, op, [m]) end)
end
end
Hereās mine for today, itās a bit verbose, so could be tidied up significantly, agreed with others that Part 2 seemed easier than Part 1 in some ways, really waiting for the hammer to drop as the first 4 days have seemed worryingly easy compared to last year.
defmodule Aoc2024.Solutions.Y24.Day04 do
alias AoC.Input
def parse(input, _part) do
Input.read!(input) |> String.split("\n", trim: true) |> pad_grid()
end
def part_one(problem) do
matrix = problem |> build_matrix()
matrix |> Enum.to_list() |> Enum.filter(fn {_, v} -> v == "X" end) |> find_xmas(matrix)
end
def find_xmas(xs, matrix) do
Enum.reduce(xs, [], fn {x_coords, _}, acc ->
acc ++
[
find_next(x_coords, :up, ["M", "A", "S"], matrix),
find_next(x_coords, :down, ["M", "A", "S"], matrix),
find_next(x_coords, :left, ["M", "A", "S"], matrix),
find_next(x_coords, :right, ["M", "A", "S"], matrix),
find_next(x_coords, :diag_up_right, ["M", "A", "S"], matrix),
find_next(x_coords, :diag_down_right, ["M", "A", "S"], matrix),
find_next(x_coords, :diag_up_left, ["M", "A", "S"], matrix),
find_next(x_coords, :diag_down_left, ["M", "A", "S"], matrix)
]
end)
|> Enum.filter(&(&1 == 1))
|> Enum.count()
end
def find_next(_, _, [], _), do: 1
def find_next({current_x, current_y}, direction, [next_letter | tail], matrix) do
next_coords = get_next_coord({current_x, current_y}, direction)
next_match = Map.get(matrix, next_coords)
if next_letter == next_match do
find_next(next_coords, direction, tail, matrix)
else
0
end
end
def pad_grid(problem) do
[first | _] = problem
width = String.length(first)
pad_row = 1..width |> Enum.map(fn _ -> "." end) |> Enum.join()
[pad_row] ++ Enum.map(problem, &".#{&1}.") ++ [pad_row]
end
#
def build_matrix(grid) do
Enum.with_index(grid)
|> Enum.reduce(%{}, fn row, acc ->
build_matrix_row(row, acc)
end)
end
def build_matrix_row({row, row_index}, acc) do
row
|> String.graphemes()
|> Enum.with_index()
|> Enum.reduce(acc, fn {char, col_index}, acc ->
Map.put(acc, {col_index, row_index}, char)
end)
end
def get_next_coord({current_x, current_y}, direction) do
case direction do
:up -> {current_x, current_y - 1}
:down -> {current_x, current_y + 1}
:left -> {current_x - 1, current_y}
:right -> {current_x + 1, current_y}
:diag_up_right -> {current_x + 1, current_y - 1}
:diag_down_right -> {current_x + 1, current_y + 1}
:diag_up_left -> {current_x - 1, current_y - 1}
:diag_down_left -> {current_x - 1, current_y + 1}
end
end
def part_two(problem) do
matrix = problem |> build_matrix()
matrix |> Enum.to_list() |> Enum.filter(fn {_, v} -> v == "A" end) |> find_x_mases(matrix)
end
def find_x_mases(as, matrix) do
Enum.reduce(as, [], fn a, acc ->
acc ++ [find_x_mas(a, matrix)]
end)
|> Enum.filter(& &1)
|> Enum.count()
end
def find_x_mas({{coord_x, coord_y}, _}, matrix) do
cross_1 =
[
Map.get(matrix, {coord_x - 1, coord_y - 1}),
Map.get(matrix, {coord_x, coord_y}),
Map.get(matrix, {coord_x + 1, coord_y + 1})
]
|> List.to_string()
cross_2 =
[
Map.get(matrix, {coord_x + 1, coord_y - 1}),
Map.get(matrix, {coord_x, coord_y}),
Map.get(matrix, {coord_x - 1, coord_y + 1})
]
|> List.to_string()
cross_1 in ["MAS", "SAM"] && cross_2 in ["MAS", "SAM"]
end
end
Solution for 2024 day 4
part_one: 2370 in 143.32ms
part_two: 1908 in 26.88ms
