Code Challenge: Map out moves on a matrix to spell words
This is a really cool challenge that could even be a part of a ruby job interview.
You have a matrix of letters, like this, sort of like an on screen keyboard like the one you use to login to Netflix on your TV.
a b c d e f g h i j k l m n o p q r s t u v w x y z
The goal here, is to write some code that will take a word and calculate the “moves” required to spell the given word. For example in the grid above, my name would be “RDDDX”,”RUUX”, “LLDX” – that would spell “Tim”, assuming that:
R = Right
L = Left
U = Up
D = Down
X = Enter / Accept
Here are a few more rules:
- the word is an argument to your script
- the number of columns is configurable
- A is the starting position
- For two consecutive letters, you can just hit “X” twice.
So, to write the word “dog”, using the same above matrix, you’d get a result like this (in array form):
["RRRX","DDLX", "ULLX"]
How I solved this puzzle
I knew that we needed two arguments to gather info for the word itself and how many columns the grid was supposed to be.
WORD = ARGV[0] COLUMNS = ARGV[1].to_i
Then, I knew this would probably be a class with a few methods, so I assumed a class that needed to know how to build the grid, and figure out the word path. Also, I wanted a little debug output, so that’s in here too. It only has one external method, get_moves.
wp = WordPath.new(WORD, COLUMNS);
puts "For the word #{WORD}"
wp.get_moves.each do |move|
puts move.inspect
end
Then, I started thinking about the things that this code is going to need to do. It needed to know its current position, its next position, and how to get to the next position from the current position. Also, we needed that class and constructor, so I started there.
The minute you instantiate this class, it does all the work, and then you’re just calling get_moves to get the list of moves. Depending on the application, you may or may not want to do it this way. It resulted in a pretty fat constructor here.
class WordPath
def initialize(word, columns)
@matrix_columns = columns
@word = word.upcase #upcase it so .ord works predictably
@positions = []
@moves = []
@last_position = []
@position_counter = 0
#create an array of positions
@word.split("").each do |letter|
@positions << self.get_position(letter)
end
#iterate the positions and generate a move.
@positions.each do |position|
if @last_position.count < 1
@last_position = [1,1]
else
@last_position = @positions[@position_counter - 1 ]
end
@position_counter = @position_counter + 1
@moves << self.get_next_move(position, @last_position)
end
end
# more stuff here, eventually.
end
So basically, the above will create an array of “positions” for the word in question. Think of these like placeholders. For “dog”, for example, we need 3 positions. So we need to get the position of each letter in the word, on the current grid setup. That’s what get_position(letter) does.
def get_position(letter)
#returns the position of a letter in the current matrix
alpha_position = (letter.ord) - 64
row = (alpha_position / @matrix_columns.to_f) + 1
column = (alpha_position % @matrix_columns)
row = row - 1 if column == 0
column = @matrix_columns if column == 0 # no modulus means the last position in a row
return [row.floor, column]
end
You’ll notice it gets an ord for each letter. This is to assign a value to that letter that we can do math on. Thats why we did the .upcaseon it earlier, because an ord of “A” is not the same as “a”. ord gives us a number for each letter, and amongst the capitals in this case, a reference of order.
For example, check out these ord examples I did in irb.
2.4.0 :003 > "a".ord => 97 2.4.0 :004 > "A".ord => 65 2.4.0 :005 > "B".ord => 66
The first thing we see here, is that “a” is not equal to “A” – thus the upcasing. Also, we see that indeed, “B” is 1 greater than “A”. Cool, now we can reference the letters mathematically.
So, back to get_position(letter) – It does a few other things. It subtracts 64 from the ord value, so that A becomes 1, B becomes 2, etc. Also, it determines the row that the letter is on by dividing the position of the letter we got from ord by the @matrix_columns. The column is determined by getting the modulus of the same – alpha_position % @matrix_columns.
And finally, we know two things. If the column ended up being 0 from the modulus calculation – we’re on a previous row, and we know we’re on the last position in a row, so we set it to the value of @matrix_columns.
This is because a modulus of 0 basically means no remainder, so the position of the current letter is the same as the length of the row, or the last character in the row. However, that being the case, we need to back off to the previous row.
After all this, we arrive with an array of positions, one for each letter in our word. It ends up looking like this, if you were to echo it to the screen. It’s just an array, with the coordinates of our word, assuming 6 columns as above and the word “dog”:
[[1, 4], [3, 3], [2, 1]]
Now, looking back up at that constructor, we want to iterate that array of positions, store a copy of the last position, and get the next move to get to the next position.
If the last position is less than 1, we know this is the first trip around, so we are at 1,1. If not, the last position is the current position minus 1.
We increment the position counter, and generate the next “move”. We build an array of moves using get_next_move(position, @last_position), basically generating the path between the current position and the last position. So lets look at that method and see what it’s doing.
def get_next_move(curpos, lastpos)
#assembles and returns the next complete move
# just to make things clearer ...
cur_row = curpos[0]
cur_col = curpos[1]
last_row = lastpos[0]
last_col = lastpos[1]
submoves = position_mover(last_row, cur_row, "v") + position_mover(last_col, cur_col, "h") + ["X"]
end
Obviously, this could be a lot shorter. I didn’t need to use those friendlier variables in there, but I did it that way for readability, since cur_pos[0] and last_pos[1] etc don’t tell you much.
So this method has one job, to figure out just one move, and get that into the right format. It calls position_mover()once for the vertical moves (if any) and once for the horizontal moves (if any), and packs them all into a string and returns them. But what’s this magical position_mover()? It seems like it’s really doing all the work. Let’s find out.
def position_mover(from, to, direction)
# given two positions, and a "v" or "h" to indicate direction
# will return a sub-move
move = []
direction_indicator = from - to
positions_to_move = direction_indicator.abs
# sloppy, theres likely better way to do this
if direction == "v"
move << "D" * positions_to_move if direction_indicator < 0
move << "U" * positions_to_move if direction_indicator > 0
end
if direction == "h"
move << "R" * positions_to_move if direction_indicator < 0
move << "L" * positions_to_move if direction_indicator > 0
end
return move
end
At this point, we’re dealing with a sub move. It’ll be n number of positions in one direction. We need a direction to move in, as well, so we take where we’re coming from and subtract where we’re going to, and that will give us either a positive or negative result. If its less than 0 and we’re doing a vertical move, that means we’re going down. If its greater than 0, we’re moving up. Same for left and right, if its a horizontal move.
After this quick calculation, it shoves all of this in that move array and returns it, then as you remember, get_next_move() will assemble that into an actual move.
Then finally we can get the @moves array at any time. which as you’ll remember, we do outside of the class – see the top of this page.
So that is it. I’ll link this to a github gist so you can see the whole thing.
