## Archive for February, 2011

### Brainteaser++, my first crack at Ruby

February 3, 2011

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

1. Read the data from stdin line-by-line and build a collection of character arrays or strings including the columns and the two diagonals.
2. Sort each string alphabetically. Then, I can use string comparison to see if two ‘sets’ contain the same elements.
3. 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
buildLines
puts findMatch or "no matches found"
end

private

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?)