Brainteaser++, my first crack at Ruby

by

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

Tags: ,

2 Responses to “Brainteaser++, my first crack at Ruby”

  1. leon oosterwijk Says:

    perhaps the Ruby matrix class can let you cut down on your code.

    http://www.ensta.fr/~diam/ruby/online/ruby-doc-stdlib/libdoc/matrix/rdoc/classes/Matrix.html

  2. Mr. S Says:

    Yep. I did something similar for that infernal TextTwist game. Kinda needed an anagram solver routine. Just found a ~400000 word spellcheck dictionary, sucked it in to SQL Server. The app just required that I enter the available letters, and it would spit out a list of valid words that could be spelled using the available letters.

    My wife didn’t understand…sometimes you don’t want to win the game, you want to beat it…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: