Solution to King Kohima problem in Python

Question

King Kohima problem:

King Kohima has reserved a new exclusive street for his executive class employees where they can build their homes. He has assigned you to plan that street. You have to decide on which plots along the street are new building allowed to be built. In order to this, you first want to calculate the number of possible ways of assigning free plots to buildings while keeping in mind this restriction – No two consecutive plots can have buildings on them. This is done to ensure a sense of free space in the arena. The street is divided in M sections. Each section corresponds to 2 plots, one on each side of the street. Find the number of possible assignments.

Input

In the first line you’re given M ( M ≤ 1000 ). Output In the first and only line output the result/ Example Input: 3 Output: 25 Example explanation: If we just look at the one street side and mark X as a plot where building is allowed and Y as a free plot, we have: XYX, YXY, YYX, XYY, YYY. Since the same number exists on the other side, we have 5*5 = 25 combinations.

For example, if the input is 3, then only five layouts (YYY, YYX, YXY, XYY, XYX) of the eight possible combinations (YYY, YYX, YXX, YXY, XYY, XYX, XXY, XXX) are valid. For both sides of the street, it's 5*5=25.

Please critique this solution.

def binary(i):
 r=str(0)
 while(i):
 x=str(i%2)
 if(x=='1' and r[-1]=='1'): #two consecutive X are not possible 
 return None
 else:
 r=r+str(x)
 i=i/2
 return r 
m=3 #input
l=[]
for i in range(0,2**m):
 l.append(binary(i)) #converted the number to binary
print(l)
c=0 #count possible plot available
for i in l:
 if i:
 c=c+1
print(c*c) #both side of the lane

• Ravinder Baid: This is the same question as: stackoverflow.com/questions/19343509/…
• 200_success: Umm... do you realize that M can be as large as 1000, and that 2**1000 is a very large number (300 decimal digits)? I'm putting the time-limit-exceeded tag on for you.
• Krishnasagar Subhedarpage: Solution: Follow this link, enjoy

Answer 1

There is a much faster solution to this problem. If the ending character is Y, two strings can be created. But if the ending character is X, only one valid string can be created: XY. This results in the following equation, complexity O(n):

def king_kohima(number: int) -> int:
 x = [0, 1, 1]
 y = [0, 1, 2]
 for i in range(3, number + 1): # Start at 3 so we skip results already stored.
 x += [y[i - 1]]
 y += [x[i - 1] + y[i - 1]]
 result = x[number] + y[number]
 return result * result

After benchmarking, this code is substantially faster than your original code.

Benchmarks:

Iterations king_kohima_op: 100 1.52433s
Iterations king_kohima: 100 0.00154s
Iterations king_kohima_op: 200 2.80376s
Iterations king_kohima: 200 0.00617s
Iterations king_kohima_op: 300 4.28752s
Iterations king_kohima: 300 0.01403s
Iterations king_kohima_op: 400 5.65897s
Iterations king_kohima: 400 0.02699s
Iterations king_kohima_op: 500 7.35554s
Iterations king_kohima: 500 0.04244s
Iterations king_kohima_op: 600 8.48669s
Iterations king_kohima: 600 0.06066s
Iterations king_kohima_op: 700 9.78000s
Iterations king_kohima: 700 0.08022s
Iterations king_kohima_op: 800 10.87804s
Iterations king_kohima: 800 0.10385s
Iterations king_kohima_op: 900 12.21734s
Iterations king_kohima: 900 0.13148s
Iterations king_kohima_op: 1000 13.80984s
Iterations king_kohima: 1000 0.16195s

Answer 2

The approach is too slow, further analysis is required.

Let's call the number of possibilities for a single sided road F(n).

If n < 0, this should be zero. Clearly F(0) = 1, since there is a single way to plan an empty street. Also, F(1) = 2, because a street with a single spot is either occupied or not.

For n >= 2, the first spot is either occupied or not. If it is occupied, the one next to it is empty and we have no restrictions on the following n-2 spots. If it is not occupied, then we have no restrictions on the following n-1 spots. This yields the recursion

F(n) = F(n-2) + F(n-1).

Therefore, the solution should be the square of the Fibonacci numbers (shifted appropriately).

Now there are plenty of ways to calculate these. The following is clean and works for the parameter range of the problem.

from functools import lru_cache
@lru_cache
def fib(n):
 if n <= 0: return 0
 if n == 1: return 1
 return fib(n-1) + fib(n-2)
def king_kohima_fib(n):
 return fib(n+2)**2