Advent of Code 2024 in SQLite: Day 4

On Day 4 the input was a grid of characters, like this one:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM

The first problem was to find the number of occurrences of the string XMAS in the grid. We needed to count horizontal, vertical as well as diagonal occurrences, both forwards and backwards.

I started by creating separate tables containing the coordinates for each of the letters. I use materialized here to force SQLite to fully generate the tables in memory instead of using lazy evaluation.

create table T (row text) strict;
.import 04_input.txt T
.load ./regex0.so

with

P(x, y, v) as materialized (
	select
		start,
		T.rowid - 1,
		match
	from regex_find_all('.', T.row)
	join T
),
X as materialized (select x, y from P where v = 'X'),
M as materialized (select x, y from P where v = 'M'),
A as materialized (select x, y from P where v = 'A'),
S as materialized (select x, y from P where v = 'S'),

Using these tables the solution was quite straightforward to express, it was simply a join between the tables for the individual letters and a new table containing direction vectors for the searches.

D(x, y) as (
	values
		-- horizontal/vertical
		( 1,  0),
		(-1,  0),
		( 0,  1),
		( 0, -1),
		-- diagonal
		( 1,  1),
		( 1, -1),
		(-1,  1),
		(-1, -1)
)

select count(*)
	from X
	join M
	join A
	join S
	join D
where (
	M.x = X.x + 1 * D.x and M.y = X.y + 1 * D.y and
	A.x = X.x + 2 * D.x and A.y = X.y + 2 * D.y and
	S.x = X.x + 3 * D.x and S.y = X.y + 3 * D.y
)

The second problem was to find occurences of 3x3 X-shapes containing the letters "MAS" on both diagonals. The solution was pretty similar to the solution for part 1:

D(a, b) as (
	values
		( 1,  1),
		( 1, -1),
		(-1, -1),
		(-1,  1)
)

select count(*)
	from A
	join M as M1
	join M as M2
	join S as S1
	join S as S2
	join D
where (
	M1.x = A.x + a and M1.y = A.y + a and
	S1.x = A.x - a and S1.y = A.y - a and

	M2.x = A.x + b and M2.y = A.y - b and
	S2.x = A.x - b and S2.y = A.y + b
)

The runnable scripts can be found on GitHub.