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

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 . 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


When r=2: OEIS A006355.

• what about ranking complexities from O(n^k) to O(n), craming all approaches below O(r^n) in one jar isnt that judicious (in addition that i dont claim this knowingly of any solution-shortcut) – Abr001am May 1 '16 at 12:27
• @Jakube Yes you can. – Leaky Nun May 1 '16 at 13:01
• I don't understand those test cases. In particular, if n=2, then there can only be r solutions i.e. two of the same object. – Neil May 1 '16 at 13:41
• Also, you're using the O notation wrong - being O(e^n) means being not asymptotically greater than e^n - so n is O(e^n), and being "less than O(e^n)" doesn't make much sense. – proud haskeller May 1 '16 at 15:40
• @proudhaskeller Colloquially, "less than O(something)" means "has an upper bound of less than something". As the meaning is understood, extra qualifications are unnecessary. – Fund Monica's Lawsuit May 1 '16 at 16:12

# 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)
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

• Explanation please? :) – Leaky Nun May 1 '16 at 12:46
• Very nice indeed! – Leaky Nun May 1 '16 at 13:24
• @jakube how much a detailed explanation costs ? (joking but i m very excited for the algorithm behind this) – Abr001am May 1 '16 at 13:36

## 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!

• How does it not qualify for the bonus? – Leaky Nun May 1 '16 at 13:44
• @KennyLau The number of calls required is the nth Fibonacci number. – Neil May 1 '16 at 13:50
• I see. Not memoized... – Leaky Nun May 1 '16 at 13:51
• Well, you could just translate the Pyth algorithm? – Leaky Nun May 1 '16 at 13:52

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

• Isn't the above solution O(e^n)? – Leaky Nun May 1 '16 at 15:32
• @KennyLau Pretty much like the javascript answer, this is less than 2^n, and phi^n calls, and phi<2<e – proud haskeller May 1 '16 at 15:34
• According to Wikipedia, every thing of the form O(k^n) where k>1 counts as O(e^n)... – Leaky Nun May 1 '16 at 15:44
• Its not about the exact value of base, but the form of the time complexity. So for practical purposes, this is exponential. – Optimizer May 1 '16 at 15:45
• @KennyLau that may be the notation some people use for "exponential", I do not know, but if you would actually look up the definition of big O notation, you would see that if 0<x<y then O(x^n) is asymptotically smaller than O(y^n), so O(2^n) applies for the bonus. If you would like the bonus to apply when the program uses less than exponential time, please write so in the challenge. – proud haskeller May 1 '16 at 15:48