5
\$\begingroup\$

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

Additional information

When r=2: OEIS A006355.

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Abr001am May 1 '16 at 12:27
  • \$\begingroup\$ @Jakube Yes you can. \$\endgroup\$ – Leaky Nun May 1 '16 at 13:01
  • \$\begingroup\$ 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. \$\endgroup\$ – Neil May 1 '16 at 13:41
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – proud haskeller May 1 '16 at 15:40
  • 1
    \$\begingroup\$ @proudhaskeller Colloquially, "less than O(something)" means "has an upper bound of less than something". As the meaning is understood, extra qualifications are unnecessary. \$\endgroup\$ – Fund Monica's Lawsuit May 1 '16 at 16:12
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Explanation please? :) \$\endgroup\$ – Leaky Nun May 1 '16 at 12:46
  • \$\begingroup\$ Very nice indeed! \$\endgroup\$ – Leaky Nun May 1 '16 at 13:24
  • \$\begingroup\$ @jakube how much a detailed explanation costs ? (joking but i m very excited for the algorithm behind this) \$\endgroup\$ – Abr001am May 1 '16 at 13:36
1
\$\begingroup\$

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!

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

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Isn't the above solution O(e^n)? \$\endgroup\$ – Leaky Nun May 1 '16 at 15:32
  • \$\begingroup\$ @KennyLau Pretty much like the javascript answer, this is less than 2^n, and phi^n calls, and phi<2<e \$\endgroup\$ – proud haskeller May 1 '16 at 15:34
  • \$\begingroup\$ According to Wikipedia, every thing of the form O(k^n) where k>1 counts as O(e^n)... \$\endgroup\$ – Leaky Nun May 1 '16 at 15:44
  • \$\begingroup\$ Its not about the exact value of base, but the form of the time complexity. So for practical purposes, this is exponential. \$\endgroup\$ – Optimizer May 1 '16 at 15:45
  • \$\begingroup\$ @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. \$\endgroup\$ – proud haskeller May 1 '16 at 15:48

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.