I program stuff.

Tuesday, February 27, 2007

Here's a dandy in Ruby, that I just wrote up.

Rather than go the direct approach (like "'remove my spaces'.tr(' ','')") this will do the same thing but in the process will,

- Find all the combinations of characters than can be removed.
- Then removes them for each combination.
- Then takes those removed characters from each combination and finds which one removed the most spaces without removing any other character and picks that solution.

Man, it's hard to write code this convoluted, but fun!


# remove_spaces.rb

def do_combos(range, pos, combos)
  if range.last - range.first == 0 then return combos end
  split = range.first + ((range.last - range.first) / 2)
  range.each { |i| combos[i][pos] = i>split }
  combos = do_combos(range.first..split.to_i, pos+1, combos)
  do_combos(split.to_i+1..range.last, pos+1, combos)
end

class String
def remove_spaces
  # make map of possible combinations
  combos = (0..2**length-1).map { [] }
  combos = do_combos(0..2**length-1, 0, combos)

  # make map of possible solutions
  solutions = combos.map do |combo|
    i = -1
    combo.inject(['','']) do |solution, do_it|
      i += 1
      if do_it then
        [solution[0]+self[i..i], solution[1]]
      else
        [solution[0], solution[1]+self[i..i]]
      end
    end
  end

  # find best solution, the one that removed the most spaces without other characters in there
  solutions.inject(['',self]) { |best, sol| (sol[0].match(/^ +$/) and sol[0].length >= best[0].length) ? sol : best }[1]
  end
end

p ARGV.shift.remove_spaces

A typical example,


mike@dedeX ruby $ time ruby remove_spaces.rb "test this string ! "
"testthisstring!"

real 12m3.352s
user 11m27.059s
sys 0m35.102s


But be sure to have a good machine to run this on if you are removing spaces from a string with more than like 20 some odd characters. It quickly gets out of hand and gets killed on my iron.

mike@dedeX ruby $ time ruby remove_spaces.rb "test this string ! "
Killed

real 3m31.015s
user 1m20.429s
sys 0m19.149s

I originally posted this here in WTF?!

Man I hate posting code in blogger, grrr.

No comments: