Wascally Wabbits

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 rabbi

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.

StackExchange Code Review Q#127287, answer score: 6