Day 4 - Advent of Code 2024
Mix.install([:kino, :benchee])Links
Prompt
— Day 4: Ceres Search —
“Looks like the Chief’s not here. Next!” One of The Historians pulls out a device and pushes the only button on it. After a brief flash, you recognize the interior of the Ceres monitoring station!
As the search for the Chief continues, a small Elf who lives on the station tugs on your shirt; she’d like to know if you could help her with her word search (your puzzle input). She only has to find one word: XMAS.
This word search allows words to be horizontal, vertical, diagonal, written backwards, or even overlapping other words. It’s a little unusual, though, as you don’t merely need to find one instance of XMAS - you need to find all of them. Here are a few ways XMAS might appear, where irrelevant characters have been replaced with .:
..X...
.SAMX.
.A..A.
XMAS.S
.X....The actual word search will be full of letters instead. For example:
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX
In this word search, XMAS occurs a total of 18 times; here’s the same word search again, but where letters not involved in any XMAS have been replaced with .:
....XXMAS.
.SAMXMS...
...S..A...
..A.A.MS.X
XMASAMX.MM
X.....XA.A
S.S.S.S.SS
.A.A.A.A.A
..M.M.M.MM
.X.X.XMASXTake a look at the little Elf’s word search. How many times does XMAS appear?
To begin, get your puzzle input.
— Part Two —
The Elf looks quizzically at you. Did you misunderstand the assignment?
Looking for the instructions, you flip over the word search to find that this isn’t actually an XMAS puzzle; it’s an X-MAS puzzle in which you’re supposed to find two MAS in the shape of an X. One way to achieve that is like this:
M.S
.A.
M.SIrrelevant characters have again been replaced with . in the above diagram. Within the X, each MAS can be written forwards or backwards.
Here’s the same example from before, but this time all of the X-MASes have been kept instead:
.M.S......
..A..MSMS.
.M.S.MAA..
..A.ASMSM.
.M.S.M....
..........
S.S.S.S.S.
.A.A.A.A..
M.M.M.M.M.
..........In this example, an X-MAS appears 9 times.
Flip the word search from the instructions back over to the word search side and try again. How many times does an X-MAS appear?
Although it hasn’t changed, you can still get your puzzle input.
Input
input = Kino.Input.textarea("Please paste your input file:")input = input |> Kino.Input.read()
# input = AdventOfCode.Input.get!(1, 2024)"AAMXMASASMXSAMXXSAMSAMXXSXMMSMMSXSASXSXSSSXSAMXXXSXMASXMAMMASAMXAXAXMXMSSMMSXSASXSAMXXMASMXSMMMMMXXMAXXSXXXAXMSAMXSMXMSXSAMXMXMSXMMXSMXMXSMS\nAXMASXMAASAMMMSMSAMSAMXMAXMAAAMXMASAAMMMAAAMMXMASMAMAMASMSAASXMAXMMXASAMXAAAMSAMMMAMMMXMASASAXXASMMMMSAMMMXMASXMASMSMMMAMMMMMAXXAMXAXMAMSAAA\nXMSMMAMXMMSMAAAAMAMSAMXAMAMSSSMXAMMMSMAMMMMMSASXAXAMASXMAAMXXMSMXSAMXSMMSMMSMMAMASAMMAAXSMMSAMSMMAAAMMAMAASMMMXMMXMASAMAMSMSSSSSSMMXSXMXAMXM\nSAMXSAMSXMASMSSMSMMMMMMAMMMMAMASMXSAAMSMMAMXSASMSSXSASMMSMMMSMAAAXAAAXAAMAMXASMMMSASXSMSMMXMXMAXMSMSSSSMSMXAASMMAASAMXSASAAXAAMXAASMMASAMXAX\nASAASXMMAXAXMAXXAXAXASAMXAAXMMMMMAMXSXMASXSMMMMAAMXMASAAMXSAAMMAMSSMSMMMSSMSMMXMXSXMAXXAAXMMSSMSXMAMAAAAXMSSMXASXXMMSMSMSMSMMMMSSMMASAMAXSSS\nMMMMSAXSAMMXSASMMSMSAXMASMSMXAXAMXMXXASAMXAMXXXMAXAMXSMMMXMXSMXAXMAAXXSAAXMAMXXMMSAMXMSSXMAAMAAAMMAMMMMMMMAMAMXMXAXXAASAMXAAXXXXMAMMMMSXMAAX\nXMAMXMXMASXAMMSAXAAMAMSASMXXSXSXSAMXMAMSMSAMXSMSASXSAMXSMASAXASMMSMMMAMMSSSMSMSMASXMAMMAMSMMSMMMMSASXXAAAMAXXMXASMMMMSMAMSMSMMMXMMMSXMSMSMAM\nSSMSAXSMASMMMASMMMMMXMMASAMASAAMSASAMXMAMMAXXAAAAMASXSASMXMASAXXAAAAMAMAAAMXAASMAMASMSMAMXAAMXSXASASASXSSSSMSXMASXAAXAXSMSMAAAMMASASAAXAXXAX\nAAAMXMXMAXAXMXXXXXXXXXMMMXMAMXMXMASXMXSASMSMXMSMSMXMAMASAMMMMXMMSSSMSXSXMMSXMSSXMSMMMAMMSMMMSAMMMMAMAMAAAAXAXMXAXMSMSAMXAMMSSMAAXMASXMMSMSAS\nMMMMSSXMASMXMASMMMXSXMMMAXMSMSXAMMMXMASASMMMAAAMXMXMXMXMMMXAMASXMAMAXMMMXMAASAXXXAXASASMSXSAMMSAXMAMAMMMMAMMMAMMMXAXMMMMAMAAAMXSXMXMAMAXXSSM\nXMAAMAAMAMMAXAAAAXAMMAAMAMMMAXMXSAAAMAMMMAAXXMMMAMAXMASMMSMASAMMMMMMMAAAMMSSMASMSMSXSAMAMSMASXSMSSSSSMSAMXMXASAMXMSMMSASASMMXXMMMXAXAMMSMMAS\nMSMSSSSMMSXMMMSSXMMSASXSSMSMMMMMMMSMMASASMMSSMXSASXXSASAAXSXMMXMAAMXSSSXSAXXMAMXAAAXMAMMMASMMMXAXAMAAASXSMXASXXAAAAAXSXSASAMSAAAAMMSXXXAAXAM\nXAAAAAXXAAMSXMAMXXMAMMAAAAAAAAAAXAXAXXXXMAAAAAASAMAAMASMMXAMXSASMMSAAAAAMXMXMXSSMSMXMAMAMAMMAMMMMAMXMMMMMAMXXMSSMSSSMSMMAMAAASXMSXMAASMSSMXS\nSMSMMMMSMXMXAMASMMSSMMMMMMMXMSSSMSSMMSSSSMMMMMMSAMMMMAMAXSAMXSASAAMMMMMMMMMXMAAAAAXSSMXSMSSSMMAAMAMXXAAAMXXAMXAAMMAAXXAMXMMMMMXMAASMMMAAXXXX\nSAMXMAMSMSMXAMAMAAXASAAXXXSAAAAAAAXMAXAAMXXXXAXMASXAMASXMMASXMAMMMMSASXMAAXAMXXMSMSAAXAMXMAAASXMSMSASMSMSAMSSMSSMMSMMSSMAXXAXXAMSXMAAMMMMMSM\nSAMXSASXASAASMSMMMMMSXXSAASMMMSMMMSMSMMMMXMMSMSXAXXXSAMXASAMAXSXXXASMSASXSSSXSXXAXMMMMMSAMMMMSAAXAAXAAMAMMSAAAAXAXAXAXMMSMSAXSMMMMSSMSXSXAAA\nMAMXSSSMXMAMMAAXSXMXXXXMXMMASAXXSXAAXMMMXMXXAMXMMSSMMMMSXMASMMMMMMAMASXMXAAAASXXXXXAMAMMAMXSASMMMXMSMMMAMSMXSMMSSMMMSSSXMASXMXMAAMAAAXAXMASM\nSSMMMAXAMXMMMMMMMAXAXSSMMXSAMXMMSSMMMAAXAXXSSSSXSAMXSAAMMXAMMXMAMMSMAMXSSMMMMMAXSMSSSSXSASXMASAMSAMXAASMSSXMMAXXMAAAMAMAMXMMMASXSSSMXMXMAMXM\nMASXMMMXAAMAXMASMMMXSAAAAXMAMXMAMAXXSXMXMXMXMAMSMASAMMSMAMSMSAMMSAAMAMAXAAXXXMSMAAAAAAASAMXMXMAMSXSSXMASAXAAXMXSSSMSMASXMAXAMXSAMAMXSMMSXMAX\nSAMXMXMXSXSAMAAAAAAXAMMMMXAXMAMSSSSMXAMASAMAMAMAXSMXSAXMAXMASXSAMXSMMMSSMSXSMMASMXMMMMMMAMMSASAMXAAMMSMMMSMMXMAMAXMXXMMMXMMSMMMAMXMASXAAAMXM\nMASASASMMASMSMMXSMMXMXMMMMMMMXSXAAXMAXSASASASXSMMMAXMAMSSSMAMAMMSAMAXAXXXXAAASASXSXAAXXMAAMSXSASMSMMMMMAMMAMXMASMSMSMSMSASMXAASAMAXMXSXSAMXA\nMXSASAMAXAXXAXMXMAMXMAXSAAXAXMMMMMMMXXMASXAASAAXAMXMXAXXAXMAMAMXMAMSMMXSAMMMMMMSASXSXSXMASXMASXMXAMXAAMAXSAMXSASXAAAAAXXAMASMMMASMSXAMMAMSSS\nXXMMMMSSMMSSMXXAXMAXXAXXXMXMSAMMMXMSXAMAXXMSMMMMXXMASMXXMASMSXSASXAMAMAMASMSMAXMXMXMXMAXAMAMAMXMASXSSSMSXSXSXSXSXMSMSMMMAMAMAASMAMMMASAMXAAM\nXMASAMXMAXAAAAMSMSMSMSXSASAXSAMAXSAMSXMASMXAASXMXSXXAXSXXXMASASASAMSAMXSAMXASMSMXMASXMXSASXMMXMXAMXMAAAMASMSXXAMMXAXXAXSMMMSXMMSXAMMMSXSMMXM\nXSAMXSASMMMSMMMXAAAXAAAXASMXXSMAMMAMXXXXXAMMXMASAMXSXMASXXXXSXMXMAXSAMAMASXMMMAMAMAAAAASAMXXSASXSSSMMMMMASAMMMMMMXAMXMMXAAASASMMSXASASASASAS\nMMASXMASXAXAXXAMSMSMSMAMXMXXMXMMSSSMSSSMXMAXASMMXXMXAMMMMMSASXSASAMXAMSXMMAAASASXMASMMMMAXAXXASXAAXXXMXMAMMMAXMAMMSMXMAMMMXXAMAAASMMASASAMAA\nAXAMAMAMMSXMSMSMAXXAXXMAXMMMXXAMAMAMAAAXSXXSAMAMSMSAMMXSAAMMMAXASAXXSAXAXSSMMSMSASXXMASXSMMSMSMMMMMMAXAMAXMXSXMAMMXAAMMMSMSMASXMMAXMMMAMMMSM\nSMSSMMASXMAXXAAXMSMXMAMSMXAASMSMASMMMSMMXAAXASMMAAAAMSXMMMXAMAMXMXSAMASAMXXAAXASAMXMSASMXAAAXAAXMAAXXSXSASMMMASMSSMMMSXAAAMSAMASXMASMMSMSAMX\nXMAAASXSASAMMSMXSAXAXXMAXSMSMAASAMAAAAXMMSMSAMASMXMSMXAMASXMMASAAXMXMMMMMMSMMSXMMMAAMASXSSSMSSSMMMSMXXAXAAAASAMXAAXSAMXXMMMMXSAMXXAMAMMAMASA\nMMMSMMX" <> ...Solution
defmodule Day04 do
def part1(input) do
check_part(Day04.Part1, input)
end
def part2(input) do
check_part(Day04.Part2, input)
end
defp check_part(module, input) do
grid = Day04.Input.parse(input)
1..grid.max_y
|> Enum.flat_map(fn y ->
1..grid.max_x
|> Enum.flat_map(fn x ->
module.check_coord({x, y}, grid)
end)
end)
|> Enum.sum()
end
def next_char(dir, xy, grid), do: grid[next_xy(dir, xy)]
def next_xy(:NW, {x, y}), do: {x - 1, y - 1}
def next_xy(:N, {x, y}), do: {x, y - 1}
def next_xy(:NE, {x, y}), do: {x + 1, y - 1}
def next_xy(:E, {x, y}), do: {x + 1, y}
def next_xy(:SE, {x, y}), do: {x + 1, y + 1}
def next_xy(:S, {x, y}), do: {x, y + 1}
def next_xy(:SW, {x, y}), do: {x - 1, y + 1}
def next_xy(:W, {x, y}), do: {x - 1, y}
defmodule Part1 do
def check_coord(xy, grid) do
check_coord(grid[xy], xy, grid)
end
defp check_coord(?X, xy, grid) do
[
next_coord(:NW, ?M, xy, grid),
next_coord(:N, ?M, xy, grid),
next_coord(:NE, ?M, xy, grid),
next_coord(:E, ?M, xy, grid),
next_coord(:SE, ?M, xy, grid),
next_coord(:S, ?M, xy, grid),
next_coord(:SW, ?M, xy, grid),
next_coord(:W, ?M, xy, grid)
]
end
defp check_coord(_, _, _), do: [0]
defp next_coord(dir, char, xy, grid) do
xy = Day04.next_xy(dir, xy)
case grid[xy] do
^char when char == ?S -> 1
^char -> next_coord(dir, next_char(char), xy, grid)
_ -> 0
end
end
defp next_char(?M), do: ?A
defp next_char(?A), do: ?S
end
defmodule Part2 do
defdelegate next_char(dir, xy, grid), to: Day04
def check_coord(xy, grid) do
check_coord(grid[xy], xy, grid)
end
defp check_coord(?A, xy, grid) do
d1 = {next_char(:NW, xy, grid), next_char(:SE, xy, grid)}
d2 = {next_char(:NE, xy, grid), next_char(:SW, xy, grid)}
if valid_diagonal?(d1) and valid_diagonal?(d2), do: [1], else: [0]
end
defp check_coord(_, _, _), do: [0]
defp valid_diagonal?({?M, ?S}), do: true
defp valid_diagonal?({?S, ?M}), do: true
defp valid_diagonal?(_), do: false
end
defmodule Input do
def parse(input) when is_binary(input) do
input
|> String.split("\n", trim: true)
|> parse()
end
def parse(input) do
grid = %{
max_y: length(input),
max_x: input |> List.first() |> String.length()
}
input
|> Enum.with_index(1)
|> Enum.reduce(grid, &parse_line/2)
end
def parse_line({line, y}, grid) do
line
|> String.to_charlist()
|> Enum.with_index(1)
|> Enum.reduce(grid, fn {c, x}, acc ->
Map.put(acc, {x, y}, c)
end)
end
end
end{:module, Day04, <<70, 79, 82, 49, 0, 0, 14, ...>>,
{:module, Day04.Input, <<70, 79, 82, ...>>, {:parse_line, 2}}}Take a look at the little Elf’s word search. How many times does XMAS appear?
Your puzzle answer was 2613.
Day04.part1(input)2613Flip the word search from the instructions back over to the word search side and try again. How many times does an X-MAS appear?
Your puzzle answer was 1905.
Day04.part2(input)1905Both parts of this puzzle are complete! They provide two gold stars: **
At this point, you should return to your Advent calendar and try another puzzle.
If you still want to see it, you can get your puzzle input.
Tests
ExUnit.start(auto_run: false)
defmodule Day04Test do
use ExUnit.Case, async: false
setup_all do
[
input:
"MMMSXXMASM\nMSAMXMSMSA\nAMXSXMAAMM\nMSAMASMSMX\nXMASAMXAMM\nXXAMMXXAMA\nSMSMSASXSS\nSAXAMASAAA\nMAMMMXMMMM\nMXMXAXMASX"
]
end
describe "part1/1" do
test "returns expected value", %{input: input} do
assert Day04.part1(input) == 18
end
end
describe "part2/1" do
test "returns expected value", %{input: input} do
assert Day04.part2(input) == 9
end
end
end
ExUnit.run()..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures
Randomized with seed 766654%{total: 2, failures: 0, excluded: 0, skipped: 0}Benchmarking
defmodule Benchmarking do
# https://github.com/bencheeorg/benchee
def run(input) do
Benchee.run(
%{
"Part 1" => fn -> Day04.part1(input) end,
"Part 2" => fn -> Day04.part2(input) end
},
memory_time: 2,
reduction_time: 2
)
nil
end
end{:module, Benchmarking, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:run, 1}}Benchmarking.run(input)Operating System: macOS
CPU Information: Apple M1
Number of Available Cores: 8
Available memory: 8 GB
Elixir 1.15.7
Erlang 26.1.1
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 2 s
reduction time: 2 s
parallel: 1
inputs: none specified
Estimated total run time: 22 s
Benchmarking Part 1 ...
Benchmarking Part 2 ...
Name ips average deviation median 99th %
Part 2 161.42 6.19 ms ±9.01% 6.02 ms 7.41 ms
Part 1 113.80 8.79 ms ±8.88% 8.53 ms 10.56 ms
Comparison:
Part 2 161.42
Part 1 113.80 - 1.42x slower +2.59 ms
Memory usage statistics:
Name Memory usage
Part 2 11.55 MB
Part 1 13.21 MB - 1.14x memory usage +1.66 MB
**All measurements for memory usage were the same**
Reduction count statistics:
Name average deviation median 99th %
Part 2 569.41 K ±0.01% 569.40 K 569.60 K
Part 1 793.88 K ±0.01% 793.87 K 794.05 K
Comparison:
Part 2 569.40 K
Part 1 793.88 K - 1.39x reduction count +224.46 Knil
