Codesignal Solution: monkeyBars

Original Problem

You are at the International Monkey Bars Climbing Competition 2017! Each contestant must climb various stretches of monkey bars during each round. The rules are that you may not more move than 3 bars at a time. Find the number of distinct ways to climb a given section.

Example
For n = 4, the output should be
monkeyBars(n) = 7.
There are 7 distinct ways to climb the bars - 3 + 1, 1 + 3, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 1 + 1 + 1 + 1, 2 + 2.

Input/Output

• [time limit] 4000ms (py3)

• [input] integer n

  Number of bars.

  Guaranteed constraints:
  1 ≤ n ≤ 60.

• [output] integer64

  Number of distinct ways to climb.

Solution

When investigating the series, we can see that the emerging pattern is known as the tribonacci number sequence - a generalization of fibonacci numbers. The definition is

\[T_n = T_{n-1} + T_{n-2} + T_{n-3}\]

for \(n\geq 4\) and \(T_1=T_2=1, T_3=2\). This recurrence relation can be implemented with Python like this:

def monkeyBars(n):
  a = b = 1
  c = 2
  while n:
    a, b, c = b, c, a + b + c
    n-= 1
  return a

« Back to problem overview