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

Advertisements