Tetrahedral Numbers

Here's another one from Programming Praxis this one on tetrahedral numbers. I'll leave you to read the description and just jump straight into the ruby solution. The interesting thing here is to use a lambda to create a method that we can pass around. Here's the entire program ...

def linear(target, f)
    n = 1
    while ( f.call(n) != target)
        n = n + 1
    end
    n
end

def binary(target, f)
    low, high = 1, 2
    while (f.call(high) < target) do high = high*2 end
    mid = (high + low) / 2
    while (fmid = f.call(mid)) != target do
        fmid < target ?  (low, mid = mid, (mid + high) / 2) : (high, mid = mid, (low + mid) / 2)
    end
    mid
end


tetrahedral = lambda { |n| n * (n + 1) * (n + 2) / 6 }

1.upto(10) { |i| puts tetrahedral.call(i) }

puts linear(169179692512835000, tetrahedral)
puts binary(169179692512835000, tetrahedral)

We start out with two methods linear and binary which are pretty straightforward with the exception that both take a function (in this case f) as a parameter. For linear, we start at 1 and continue calling f until the value of f(n) is the same as target. binary is similar, but here we keep doubling the high value until we're above the target and then we calculate the fmid and use it as a high or low value until we converge.

The tetrahedral function itself is created with a lambda so that we can pass it to the other two methods. The next lines are simply tests. Note how much longer the linear method takes than the binary.

As always, let me know if you have questions or comments.

Two String Exercise via Programming Praxis

Here's another one (or two rather) from Programming Praxis. Let's take a look at the second one first as it's trivial in ruby. If we're given a string, how do we replace multiple spaces with single spaces. F/or example the string "a b c" would become "a b c". For both of these, we're going to monkey patch the string class. Here's the code ...

class String

    def remove_consecutive_spaces

        self.gsub(/ +/, " ")

    end

end

All we do is do a global substitution of one or more spaces with a single space. This would be quite a bit trickier in C say which is why it ends up in interview questions.

The second (or first) problem is to remove duplicate characters from a string. For example, "aaaabbbb" becomes "ab" and "abcbd" becomes "abcd". This one is a bit trickier but shows another good example of how useful inject() can be. Here's the code ...

class String

    def remove_duplicate_characters

        self.split(//).inject([]) { |a, c| a << c if !a.include?(c); a }.join

    end

end

Going through it from left to right, we have first the split(//) which will turn the array into a string of characters. With that string of characters we do an inject([]) which a) initializes a new empty array (sometimes called the "memo") and then runs through the character array adding a character "c" to the array "a" if it's not already there include?. The ; a returns the current array back to the inject. Finally, we recreate the string by doing a join on the character string array.

Let me know if you have questions or comments.