Saturday, August 7, 2010

Code Kata Eight: Conflicting Objectives, Part 1

   Kata number seven is a non-coding kata, so let's move on to kata number eight.  This one is about conflicting objectives.  To quote the original:

Write the program three times.
  • The first time, make program as readable as you can make it.
  • The second time, optimize the program to run fast fast as you can make it.
  • The third time, write as extendible a program as you can.

   Even that, though, leaves a lot of room for interpretation.  For instance, "readable" to whom?  I decided to divide this into two audiences.  The first is people entirely new to the language (in this case, Ruby) and possibly to programming in general.  Ruby has quite an advantage here, being so expressive and easy to pick up.  The second is people who do know the language, including common idioms, and presumably programming in general.

   Since the two are so radically different, at least the way I did them, I'll give you them both at once.  First the one for complete newbies:

#! /usr/bin/ruby

# Dave Thomas Code Kata #8: Conflicting Objectives
# See http://codekata.pragprog.com/2007/01/kata_eight_conf.html
# Solution by Dave Aronson
# version 1: make it readable
# part A: make it readable to a ruby newbie, possibly non-programmer


def make_word_lists file_name

  word_lists = []

  for len in 1 .. 6 do
    word_lists[len] = []
  end

  puts "Reading #{file_name}..."
  dict = File.new file_name, 'r'
  for line in dict do
    word = line.chomp
    if    word.length == 1 then word_lists[1] << word
    elsif word.length == 2 then word_lists[2] << word
    elsif word.length == 3 then word_lists[3] << word
    elsif word.length == 4 then word_lists[4] << word
    elsif word.length == 5 then word_lists[5] << word
    elsif word.length == 6 then word_lists[6] << word
    end
  end
  dict.close

  return word_lists

end



def find_combinations word_lists

  puts 'Finding combinations....'
  
  combinations = 0
  
  for word in word_lists[6] do
  
    part_1 = word[0 .. 0]
    part_2 = word[1 .. 5]
    if word_lists[1].include? part_1 and word_lists[5].include? part_2
      puts "#{part_1} + #{part_2} = #{word}"
      combinations = combinations + 1
    end
  
    part_1 = word[0 .. 1]
    part_2 = word[2 .. 5]
    if word_lists[2].include? part_1 and word_lists[4].include? part_2
      puts "#{part_1} + #{part_2} = #{word}"
      combinations = combinations + 1
    end
  
    part_1 = word[0 .. 2]
    part_2 = word[3 .. 5]
    if word_lists[3].include? part_1 and word_lists[3].include? part_2
      puts "#{part_1} + #{part_2} = #{word}"
      combinations = combinations + 1
    end
  
    part_1 = word[0 .. 3]
    part_2 = word[4 .. 5]
    if word_lists[4].include? part_1 and word_lists[2].include? part_2
      puts "#{part_1} + #{part_2} = #{word}"
      combinations = combinations + 1
    end
  
    part_1 = word[0 .. 4]
    part_2 = word[5 .. 5]
    if word_lists[5].include? part_1 and word_lists[1].include? part_2
      puts "#{part_1} + #{part_2} = #{word}"
      combinations = combinations + 1
    end
  
  end
  
  return combinations

end


start_time = Time.now
word_lists = make_word_lists ARGV[0]
combinations = find_combinations word_lists
puts "We found a total of #{combinations} combinations"

end_time = Time.now
run_time = end_time - start_time

puts "Running time: #{run_time} seconds"

   Yes, it's incredibly slow, due to use of simple arrays rather than hashes, since Ruby-newbies, or even more so, programming-newbies, would not be familiar with hashes or other such semi-advanced data structures.  I could make it faster by using a binary search function, but that would also have to be in there and count against the readability!  Besides, speed is for Part 2.  And now the one for Ruby programmers (who are presumably familiar with hashes):

#! /usr/bin/ruby

# Dave Thomas Code Kata #8: Conflicting Objectives
# See http://codekata.pragprog.com/2007/01/kata_eight_conf.html
# Solution by Dave Aronson
# version 1: make it readable
# part B: make it readable to someone who knows Ruby


def make_word_lists file_name

  word_lists = []
  
  for len in 1 .. 6 do word_lists[len] = {} end
  
  dict = File.open file_name, 'r'
  dict.each_line do |line|
    word = line.chomp
    len = word.length
    word_lists[len][word] = nil if len <= 6
  end
  dict.close

  word_lists
end
  

def find_combinations word_lists
  combinations = 0
  for word in word_lists[6].keys.sort do
    for first_part_len in 1 .. 5 do
      part_1 = word[0 .. first_part_len - 1]
      part_2 = word[first_part_len .. 5]
      if word_lists[first_part_len].include? part_1 and
         word_lists[6-first_part_len].include? part_2
        puts "#{part_1} + #{part_2} = #{word}"
        combinations += 1
      end
    end
  end
  combinations
end


start_time = Time.now
word_lists = make_word_lists ARGV[0]
combinations = find_combinations word_lists
puts "We found a total of #{combinations} combinations"
puts "Running time: #{Time.now - start_time} seconds"

   So, dear readers, let's hear your input.  Did you find any of that poorly readable?  What do you think would have been more readable?  Should I have coded up a binary search, to make Part A tolerably fast?  Or going the other way, do you think I went overboard?  (Especially in the horribly verbose Part A, with the inner loop unrolled?)