Find the number of ways to choose `n` objects from `r` objects with repetition so that every object has a matching neighbour

Question

For example, if n is 5 and r is 2, it would mean the number of lists below:

[1,1,1,1,1]
[1,1,1,2,2]
[1,1,2,2,2]
[2,2,1,1,1]
[2,2,2,1,1]
[2,2,2,2,2]

which is 6.

If n is 4 and r is 3:

[1,1,1,1]
[1,1,2,2]
[1,1,3,3]
[2,2,1,1]
...
[3,3,3,3]

which is 9.

where each item has a neighbour whose value is the same.

For example, [1,2,1,1,2] is not counted, because both 2 are alone.

Goal

Your task is to write a program/function which takes two inputs in any order, and which produces the required output.

Detail

You can assume that r≥2.

Scoring

This is code-golf. Shortest solution in bytes wins.

Bonus

Multiply your score by 0.3 if the complexity of your program is below O(e^n).

For example, 10 bytes becomes 3 bytes.

Testcases

Can be generated from this Pyth test suite.

Usage: two lines per testcase, n on top, r below.

n r output
2 5 5
4 4 16
6 3 33
8 2 26

Additional information

When r=2: OEIS A006355.

Answer 1

Pyth, 14 bytes * 0.3 = 4.2 bytes

*Quh*~+ZGtQtE0

Try it online: Demonstration. Input r on the first line and n on the second line.

Complexity is O(n).

Explanation:

Let f(n, r) be the number of ways to create such a list with the last number being 0. Obviously it doesn't matter if we take 0 or any other number.

It's easy to see, that the following recursion holds:

f(n, r) = 0                                  ... if n < 2
f(n, r) = sum(f(i, r), i <= n-2) * (r-1) + 1 ... otherwise

If n == 0, than the list cannot end with the number 0. If n == 1, than the only number in the list has no neighbor. Therefore both cases have the value zero.

If n >= 2, than it could end in 2, 3, ... n zeros. The digit before the last zero can be any of the number 1, 2, ..., r-1. These are r-1 possibilities. Therefore I'll add up all f(i,n) and multiply by r-1. At the end I'll have to add 1 (for the case that all digits are zeros).

The result to the question than is: r * f(n, r), since the list can end in any of the r numbers.

In my code I make use of the predefined variable Z = 0. It will contain the last computed sum so far.

*Quh*~+ZGtQtE0   implicit: Q = first input number (r)
  u        tE0   start with G=0, do the following input-1 (n-1) times:
     ~+ZG           add G to Z
   h*~ Z tQ         and update G to the value Z*(Q-1) + 1 
                    (using the old value of Z)
*Q               multiply the result with Q

Answer 2

JavaScript (ES6), 64 (70 * 0.3 = 21) bytes

(n,r)=>[...Array(n)].map((m,i,a)=>a[i+2]=(s=s+m|0)*~-r+r).slice(-2)[0]

Now runs in linear time!

Answer 3

Haskell, 16.5 (55 bytes)

r#n=l!!(n-1)where l=0:r:r:w l;w(x:y:s)=r*(x+y)-x:w(y:s)

It uses this recursive definition:

f(n,r) = r*f(n-2,r) + (r-1)*f(n-3,r)

and uses O(n) time. Usage: evaluate r#n