I started out with the Rosalind problems a while back. Turns out it's a great way to learn a new language. I'm still trying to learn Ruby, and while I haven't managed to use regular expressions as much as I wanted to (learning those being one of the reasons I started learning Ruby in the first place), I put together a repository of whatever challenges I have solved so far.
I learned how easy it is to benchmark with Ruby, so I put that to the test as well. While the resulting solution is good, it's quite possible there's a better one out there.
Problem: IPRB
Probability is the mathematical study of randomly occurring phenomena. We will model such a phenomenon with a random variable, which is simply a variable that can take a number of different distinct outcomes depending on the result of an underlying random process.
For example, say that we have a bag containing 3 red balls and 2 blue balls. If we let \$X\$ represent the random variable corresponding to the color of a drawn ball, then the probability of each of the two outcomes is given by \$Pr[X=red]=35\$ and \$Pr[X=blue]=25\$.
Random variables can be combined to yield new random variables. Returning to the ball example, let \$Y\$ model the color of a second ball drawn from the bag (without replacing the first ball). The probability of \$Y\$ being red depends on whether the first ball was red or blue. To represent all outcomes of \$X\$ and \$Y\$, we therefore use a probability tree diagram. This branching diagram represents all possible individual probabilities for \$X\$ and \$Y\$, with outcomes at the endpoints ("leaves") of the tree.
Given:
Three positive integers \$k, m,\$ and \$n\$, representing a population containing \$k+m+n\$ organisms: \$k\$ individuals are homozygous dominant for a factor, \$m\$ are heterozygous, and \$n\$ are homozygous recessive.
Return:
The probability that two randomly selected mating organisms will produce an individual possessing a dominant allele (and thus displaying the dominant phenotype). Assume that any two organisms can mate.
Sample dataset:
2 2 2
Sample output:
0.78333
My solution solves the sample dataset and the actual dataset given:
Dataset:
22 26 27
Solution:
0.71775
IPRB.rb:
def probability_dominant(k, m, n)
(k * k + k * (2 * m + 2* n - 1) + m * (0.75 * m + n - 0.75)) / ((k + m + n - 1) * (k + m + n))
end
user_input = gets.chomp
split_input = user_input.split().map { |number| number.to_i() }
puts probability_dominant(split_input[0], split_input[1], split_input[2]).round(5)
The math involved appears to be the performance bottleneck.
IPRB_benchmark.rb:
def probability_dominant_1(k, m, n)
((k * k - k) + 2 * (k * m) + 2 * (k * n) + (0.75 * (m * m - m)) + 2 * (0.5 * m * n))/((k + m + n)*(k + m + n -1))
end
def probability_dominant_2(k, m, n)
(k * k + k * (2 * m + 2* n - 1) + m * (0.75 * m + n - 0.75)) / ((k + m + n - 1) * (k + m + n))
end
def probability_dominant_3(k, m, n)
(k * k + k * m + k + 0.25 * m * m + 0.75 * m)/(k + m + n) - (k * k + k * m - k + 0.25 * m * m - 0.25 * m) / (k + m + n - 1)
end
require 'benchmark'
n = 500000
Benchmark.bm(6) do |x|
x.report("first:") { for i in 1..n; probability_dominant_1(n, n, n); end }
x.report("second:") { for i in 1..n; probability_dominant_2(n, n, n); end }
x.report("third:") { for i in 1..n; probability_dominant_3(n, n, n); end }
end
Output:
user system total real first: 0.594000 0.000000 0.594000 ( 0.597825) second: 0.328000 0.000000 0.328000 ( 0.316578) third: 0.500000 0.000000 0.500000 ( 0.517067)
I optimized the math the best I could, but optimizing for a computer is a lot sketchier than optimizing for a human. It's quite hard to keep it fast for the machine and readable for a human at the same time. I foresee the upcoming challenges to be more and more mathematically inclined, so I better tackle this here and now.
Any and all advice about how to math in Ruby is appreciated. Nitpicks are welcome too.