CODEWITHSUNDEEP
rubyoptimizationpuzzle
darkone
darkone

Reputation: 11

How can I make this Ruby puzzle solution faster?

One reason I hate puzzle sites is because they tell you when you fail but you can't learn how to improve. I typically don't like posting these kinds of questions, but I wasted so much time trying to figure out why this fails I MUST KNOW the answer!

Here is my code:

ARGF.each do |line|
  if ARGF.lineno > 1
    string_a = line.strip
    string_b = line.strip
    sum = string_a.size
    (0...string_a.size).each do |i|
      string_b[0] = '' 
      (0...string_b.size).each do |j|
        break if string_a[j] != string_b[j]
        sum = sum + 1 
      end 
    end
    puts sum
  end
end

Here is the problem (if your curious): http://pastie.org/3044657

It passes most tests but then fails afterward due to optimization reasons. I would LOVE to know how to optimize this. I don't know how to go about "identifying and learning" how to optimize.

PS. This is the most entry-level puzzle so I highly doubt it is hurting anyone by walking through this.

Upvotes: 0

Views: 249

Answers (1)

undur_gongor
undur_gongor

Reputation: 15954

Your algorithm is O(n²). There is not much you can do about this by just optimizing the code.

Some ideas to slightly improve the performance for the given algorithm:

  • Split the string into an array.
  • Once you have found a j with string_a[j] != string_b[j], increment sum by that j instead of counting each equal pair.

This code is about twice as fast as your's on my machine for my test cases:

ary = line.strip.chars.to_a
n = ary.count
sum = (1...n).inject(n) do | sum, i |
  sum + (n-i).times { | j | break j if ary[j] != ary[j + i] }
end

Upvotes: 1

Related Questions