6
\$\begingroup\$

This question is part of a series solving the Rosalind challenges. For the previous question in this series, see Mendelian inheritance. The repository with all my up-to-date solutions so far can be found here.


The next part of the Rosalind challenges is basically asking for a Fibonacci solver, with a twist.

Problem: FIB

A sequence is an ordered collection of objects (usually numbers), which are allowed to repeat. Sequences can be finite or infinite. Two examples are the finite sequence \$(π,−2√,0,π)\$ and the infinite sequence of odd numbers \$(1,3,5,7,9,…)\$. We use the notation \$a_n\$ to represent the \$n\$-th term of a sequence.

A recurrence relation is a way of defining the terms of a sequence with respect to the values of previous terms. In the case of Fibonacci's rabbits from the introduction, any given month will contain the rabbits that were alive the previous month, plus any new offspring. A key observation is that the number of offspring in any month is equal to the number of rabbits that were alive two months prior. As a result, if \$F_n\$ represents the number of rabbit pairs alive after the \$n\$-th month, then we obtain the Fibonacci sequence having terms \$F_n\$ that are defined by the recurrence relation \$F_n=F_{n−1}+F_{n−2}\$ (with \$F_1=F_2=1\$ to initiate the sequence). Although the sequence bears Fibonacci's name, it was known to Indian mathematicians over two millennia ago.

When finding the \$n\$-th term of a sequence defined by a recurrence relation, we can simply use the recurrence relation to generate terms for progressively larger values of n. This problem introduces us to the computational technique of dynamic programming, which successively builds up solutions by using the answers to smaller cases.

Given:

Positive integers \$n≤40\$ and \$k≤5\$.

Return:

The total number of rabbit pairs that will be present after \$n\$ months if we begin with 1 pair and in each generation, every pair of reproduction-age rabbits produces a litter of \$k\$ rabbit pairs (instead of only 1 pair).

Sample Dataset:

5 3

Sample Output:

19

My solution solves the sample dataset and the actual dataset given:

Dataset:

33 5

Output:

112316396483406

FIB.rb:

def wabbits(n, k)
    fibs = 1, 1, k + 1
    4.upto n do |x|
        fibs[0] = fibs[1]
        fibs[1] = fibs[2]
        fibs[2] = fibs[0] * k + fibs[1]
    end
    return fibs[2]
end

user_input = gets.chomp
split_input = user_input.split().map { |number| number.to_i() }
puts wabbits(split_input[0], split_input[1])

I've tried to do this recursive, but I failed to successfully implement the additional work involved for \$k\$. This solution shouldn't be too, except it doesn't look idiomatic to me.

I couldn't find a way around the return fibs[2], but I suspect it isn't required if the program is restructured. I'm also not too fond of the hacky way of starting my loop with 4.upto. 4 is a magic number here.

\$\endgroup\$
6
\$\begingroup\$

A few housekeeping things:

  • The Ruby conventions is 2 spaces of indentation. Not not 4 spaces, not tabs.
  • return is implicit, so you don't have to write it.
  • () is implicit too, so .split() is just split, and .to_i() just .to_i
  • However, if you just want to call the same method of an array's elements, you can just a shortcut. Here, for the map operation, it'd be .map(&:to_i).

You can also just "splats" to destructure an array into separate arguments. So you do:

input = gets.chomp.split.map(&:to_i)
puts wabbits(*input)

Of course, this assumes there really are two values - and only two - in the input, but I'll leave such concerns alone for now.

You could also be extra descriptive, by using a little array destructuring:

n, k = gets.chomp.split.map(&:to_i)

As for the method itself: You're using a 3-element array, which gives you one element to use for "swap space". But in Ruby, there's a shortcut for swapping two numbers, again using array destructuring like above:

a, b = [b, a]

So you can define your method using just the previous generation total, and the current generation total instead:

def wabbits(n, k)
  previous = 1
  current = 1

  3.upto(n) do
    previous, current = [current, previous * k + current]
  end

  current
end

A little cleaner, in my view.

You can get rid of magic numbers entirely, however. The above doesn't do any input validation, but obviously the sequence is only works for n >= 0, where n values of 0, 1, and 2 have predefined results. I'd file that under "That's just how it is", and maybe add a check for the n (and k) arguments, raising exceptions or returning predefined values as necessary.


Edit: Alternatively, you can use a range and reduce (aka inject)

def wabbits(n, k)
  (3..n).reduce([1, 1]) do |(previous, current), _|
    [current, previous * k + current]
  end.last
end

This avoids the dangling return value (discussed in the comments), and also avoids the block depending on and modifying closed-over variables.

\$\endgroup\$
  • \$\begingroup\$ Try what happens in the original code if you don't write the return. It doesn't work the same. Good reminder on the indentation, I'm so used to Python I keep forgetting the standard in Ruby is only 2. I learned some neat things from your answer, thanks a lot! \$\endgroup\$ – Mast May 2 '16 at 16:23
  • \$\begingroup\$ @Mast You still need to write fibs[2] in your code, but you just don't need to write return in front of it. If you leave the entire line off, yeah, it won't work, since the result of 4.upto ... will be implicitly returned. But idiomatically, you don't want to write return x at the end of a method, when x will do the same. \$\endgroup\$ – Flambino May 2 '16 at 16:57
  • \$\begingroup\$ To be more specific, ruby (always) automatically returns the result of the last evaluation in a function. The return keyword is usually only used if you are returning early. \$\endgroup\$ – Zack May 2 '16 at 17:09
  • \$\begingroup\$ Oh, of-course, and just calling the variable is enough to make sure it is counted as last evaluation. Just loosely mentioning a variable without a keyword at the end feels a bit off, but if it's the Ruby way I'll just have to adapt. \$\endgroup\$ – Mast May 2 '16 at 19:11
  • \$\begingroup\$ it's your code; you can follow whatever convention you want. Personally I sometimes stick a return in just to make the text look more balanced. \$\endgroup\$ – Zack May 2 '16 at 19:21
5
\$\begingroup\$

As I did the same exercise some time ago, I used a different approach, using hashes. It takes advantage of the ability to define a default for hashes when accessing a not present element. So, in general:

x=Hash.new
x[1]
#=> nil

but

x=Hash.new{12}
x[1]
#=>12

Now... what happens if I define the default as being a function of the previous values - which may or may not be defined?

def fibonacci_with_offspring number_of_months, offspring_number
  fib_generator=Hash.new {|hash,month| month<=2 ? 1 : hash[month-1] + offspring_number*hash[month-2]}
  fib_generator[number_of_months]
end

fibonacci_with_offspring(33,5)
#=> 112316396483406

What happens is that now the hash generates on the fly its values to give me the correct result :)

Basically, the function is not recursive per se but uses defaults to generate a recursive solution ;) I hope you'll like this solution, in theory it could be converted as a oneliner as well

\$\endgroup\$
  • 2
    \$\begingroup\$ That's a cool way to do memorization! \$\endgroup\$ – 200_success May 20 '16 at 16:13
  • \$\begingroup\$ Seconded, that is definitely cool \$\endgroup\$ – Zack May 20 '16 at 21:39
4
\$\begingroup\$

Just because you mentioned recursion it in your post, here is an example, and also an example of implementing this as an infinite sequence.

Pure Recursive

Note that pure recursive functions in ruby have to be used carefully as ruby has a limited stack. Recursing more than a few thousand times tends to cause a stack overflow. Also note that this implementation does not include support for memoization, so it does a lot of redundant work. It is, however, a pure function.

def wabbits(n, k)
  case n
    when 1 then 1
    when 2 then 1
    else w(n-2, k)*k + w(n-1, k)
  end
end

Sequence

Also, just because ruby is awesome, here is an iterator that generates a sequence of Fibonacci numbers for additional functional programming tricks.

def wabbit_factory(k)
  Enumerator.new do |yielder|
    f2 = 1
    f1 = 1
    yielder.yield f2
    yielder.yield f1
    loop do
      wabbit = f2*k + f1
      yielder.yield wabbit
      f2, f1 = [f1, wabbit]
    end
  end
end

Testing:

factory = wabbit_factory(3)
puts factory.take(10).to_s
# [1, 1, 4, 7, 19, 40, 97, 217, 508, 1159]

herd = factory
  .lazy
  .take_while { |w| w < 1000 }
  .map { |w| "#{w} wabbits! " }
  .to_a
  .join("\n")
puts herd
# 1 wabbits!
# 1 wabbits!
# 4 wabbits!
# 7 wabbits!
# 19 wabbits!
# 40 wabbits!
# 97 wabbits!
# 217 wabbits!
# 508 wabbits!
\$\endgroup\$
  • \$\begingroup\$ Good to know, this will definitely help in my toolbox with tackling the remaining challenges. \$\endgroup\$ – Mast May 2 '16 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.