Today, I'll just be using Ruby. You know Ruby; it takes a very Smalltalk-inspired, message-passing object system and grafts it onto a clean scripting language which takes a lot of syntax niceties from Perl.
For this task, we will receive a 2D grid of characters, and return the number of ways to spell "XMAS" horizontally, vertically, or diagonally, where it can be spelt forwards or backwards.
A straightforward approach works fine. We can just iterate over each character in order, and look for the word in all 8 directions. We could cut down on the amount of work it takes to check each position, but it's still O(n), so let's not worry about it.
We can keep most of our code in a WordFinder class that we
initialise with a target word and a letter grid. The attr_reader
method defines simple getters for the named properties that map to an
instance variable. We also define getters for the number of rows and
columns, and use them in our main entrypoint, count. count just
loops over every x and y and calls another method,
count_from_pos, whose job will be to look for the word in each
direction:
class WordFinder
attr_reader :word, :grid
def initialize(word, grid)
@word = word
@grid = grid
end
def num_rows
grid[0].size
end
def num_columns
grid.size
end
def count
num_rows.times.sum do |x|
num_columns.times.sum do |y|
count_from_pos(x, y)
end
end
end
end
To implement count_from_pos, we'll use a function to return a list
of directions, all_directions, and another helper function,
find_word, whose job is to look for a word in a given direction;
we'll define both of these later. If the letter we're currently
looking at isn't the first letter in the word, we can just return 0,
otherwise we'll sum all the matches we find in any direction.
find_word will chew through the target string one letter at a time,
so since we already checked for the first letter, we can just pass in
the tail:
def count_from_pos(x, y)
return 0 unless grid[y][x] == word[0]
all_directions.sum do |direction|
find_word(x, y, word[1..-1], direction)
end
end
Directions can be represented as lists of symbols; we use lists so
that we can handle diagonals as a combination of an x and y direction,
so that find_word can process them in a loop and only worry about
moving up, down, left, or right. We'll adjust the coordinates first so
that we can group the return statements all together.
def find_word(x, y, target, directions)
directions.each do |direction|
case direction
when :left; x -= 1
when :right; x += 1
when :up; y -= 1
when :down; y += 1
end
end
return 1 if target.empty?
return 0 if x < 0 || x >= num_rows
return 0 if y < 0 || y >= num_columns
return 0 if grid[y][x] != target[0]
find_word(x, y, target[1..-1], directions)
end
Now we can put everything together, defining the all_directions
method, and adding some simple main code to initialise and run our
WordFinder:
class WordFinder
attr_reader :word, :grid
def initialize(word, grid)
@word = word
@grid = grid
end
def num_rows
grid[0].size
end
def num_columns
grid.size
end
def count
num_rows.times.sum do |x|
num_columns.times.sum do |y|
count_from_pos(x, y)
end
end
end
def count_from_pos(x, y)
return 0 unless grid[y][x] == word[0]
all_directions.sum do |direction|
find_word(x, y, word[1..-1], direction)
end
end
def find_word(x, y, target, directions)
directions.each do |direction|
case direction
when :left; x -= 1
when :right; x += 1
when :up; y -= 1
when :down; y += 1
end
end
return 1 if target.empty?
return 0 if x < 0 || x >= num_rows
return 0 if y < 0 || y >= num_columns
return 0 if grid[y][x] != target[0]
find_word(x, y, target[1..-1], directions)
end
def all_directions
[
%i[up],
%i[left],
%i[down],
%i[right],
%i[up left],
%i[up right],
%i[down left],
%i[down right],
]
end
end
lines = File.readlines('input.txt', chomp: true)
grid = lines.map { _1.split('') }
puts WordFinder.new('XMAS', grid).count
Just a couple things to note here:
%i[foo bar baz] is the same as [:foo, :bar, :baz].chomp: true says to remove trailing newlines, like chomp in
Perl.{ ... } denote a block like do/end._1 inside a block is the first argument passed to that block.For the second task, we need to modify the program so that it finds pairs of diagonal "MAS"s which overlap on the A, forming an X. Using the straightforward approach we started with, this is actually easier to implement than the first task, as we don't need to worry about following in a direction.
First, we need to add readers for center and target, and then
initialise them in the constructor. center holds the centre letter
that we're looking for in count_from_pos, and target holds the
other two letters. The letters in target are sorted so that we can
ignore the direction we find a MAS written in. We also don't need to
store word in an instance variable anymore, because it's only used
for initialising center and target.
Our new count_from_pos is pretty simple: return 0 if we're not
looking at an A or if we're on the edge of the grid. Otherwise, grab
both diagonals and sort each, then check whether both are equal to
target and return 1 or 0 appropriately. Here's the complete
code:
class WordFinder
attr_reader :grid, :center, :target
def initialize(word, grid)
@grid = grid
@center = word[1]
@target = [word[0], word[2]].sort
end
def num_rows
grid[0].size
end
def num_columns
grid.size
end
def count
num_rows.times.sum do |x|
num_columns.times.sum do |y|
count_from_pos(x, y)
end
end
end
def count_from_pos(x, y)
return 0 unless grid[y][x] == center
return 0 if x < 1 || x >= num_rows - 1
return 0 if y < 1 || y >= num_columns - 1
diagonals = [
[grid[y + 1][x + 1], grid[y - 1][x - 1]].sort,
[grid[y + 1][x - 1], grid[y - 1][x + 1]].sort,
]
if diagonals.count(target) == 2
1
else
0
end
end
end
lines = File.readlines('input.txt', chomp: true)
grid = lines.map { _1.split('') }
puts WordFinder.new('MAS', grid).count