I got a new desk calendar with daily brain teasers. The advertised purpose is to give my mind a little exercise for a few minutes every morning. January 5th’s puzzle inspired me. What would be better than solving this puzzle? Writing a program to solve it for me! Even better, I’ll use a new language I’ve been meaning to pick up. Now we’re flexing the brain.
Here’s the puzzle:
In the table of letters, find the two ‘lines’ that contain the same set of letters. Lines can go horizontal, vertical, or diagonal and in any direction.
M P A F H E L C G E H O A F F A C M T L K E B H F M C O G H M L E O A A L F O G K C H C P T A G G
This definitely lends itself to a computerized, brute-force approach. ‘Line’ and ‘in any direction’ are misdirection. Really we’re looking for two unordered sets that contain the same elements.
The approach
- Read the data from stdin line-by-line and build a collection of character arrays or strings including the columns and the two diagonals.
- Sort each string alphabetically. Then, I can use string comparison to see if two ‘sets’ contain the same elements.
- Iterate over the collection of strings, looking for two that match. It will have to be an ordered collection just so that I can output an indicator of which rows, columns, or diagonals matched.
Here’s my stab at it in Ruby.
class Puzzle
def initialize
# table of characters from input
@char_table = []
# the horizontal, vertical, and diagonal lines from @char_table
@lines = {}
end
def main
readPuzzle
buildLines
puts findMatch or "no matches found"
end
private
def readPuzzle
while line = gets
lineAsArray = []
line.chomp.each_char {|c| lineAsArray << c}
@char_table << lineAsArray
end
end
def buildLines
counter = 0
#horizontal lines
@char_table.each { |line|
@lines[ counter ] = line.sort.to_s
counter += 1
}
#vertical lines
#FIXME: assumes square 2D array; ought to validate that
for i in 0..@char_table.length() - 1
@lines[ counter ] = []
for j in 0..@char_table[i].length() -1
@lines[ counter ] << @char_table[j][i]
end
@lines[ counter ] = @lines[ counter ].sort.to_s
counter += 1
end
#diagonal lines
@lines[ counter ] = []
@lines[ counter + 1 ] = []
for i in 0..@char_table.length() -1
@lines[ counter ] << @char_table[i][i]
@lines[ counter + 1 ] << @char_table[i][@char_table.length - i - 1 ]
end
@lines[ counter ] = @lines[ counter ].sort.to_s
@lines[ counter + 1 ] = @lines[ counter + 1 ].sort.to_s
end
def findMatch
until @lines.length == 0
key, val = @lines.shift
@lines.each{ |key2,val2|
if val==val2 then
return "matches found at line #{key} and line #{key2}"
end
}
end
end
end
p = Puzzle.new
p.main
I really enjoyed the exercise. The puzzle was supposed to take about 2 minutes. This took hours (hey, it’s my first time with Ruby, cut me some slack). However, it can solve these puzzles in well under 2 minutes, so I think I still hit the mark.
My solution is not particularly Ruby-esque. There’s a lot of explicit iteration with indices. That may just be the nature of trying to extract strings from a two-dimensional character table. Once I got past the data-loading, things seemed to get closer to the Ruby way.
What would you improve? (Especially to all you Ruby coders on the Web, how can I make this more Ruby-like?)