[PYTHON] Zero-based code wars kata yield and Fibonacci sequence

At codewars kata you can learn programming and practical English at the same time. If you have a github account, you can get started in 30 seconds If you are interested, start here now

By the way, you can challenge in many languages other than python.

Q1.https://www.codewars.com/kata/54d512e62a5e54c96200019e/train/python

Given a positive number n > 1 find the prime factor decomposition of n. The result will be a string with the following form :

 "(p1**n1)(p2**n2)...(pk**nk)"
with the p(i) in increasing order and n(i) empty if n(i) is 1.

Example: n = 86240 should return "(2**5)(5)(7**2)(11)"

Given a positive integer n, return the prime numbers that make up it

my A.


def primeFactors(b ):

    ps = []
    ns = []
    i = 1
    while  not b==1:
        i += 1
        j = 0
        while not b % i:
            b = b / (i)
            j += 1
        if not j == 0:        
            ps.append(i)
            ns.append(j)
            
    return ''.join([ '({})'.format(p) if  n == 1 else '({}**{})'.format(p,n) for p,n in zip(ps,ns)])

3000ms

First successful attempt


def primeFactors(b ):

    k = 100000000000000
    ps = []
    ns = []
    
    for i in range(2,k):
        mod = 0    
        j = 0
        if b ==1:
            break
        while mod == 0:
            div,mod = divmod(b,i)
            if mod == 0:
                b = b / (i)
                j += 1
        if not j == 0:        
            ps.append(i)
            ns.append(j)
            
    return ''.join([ '({})'.format(p) if  n == 1 else '({}**{})'.format(p,n) for p,n in zip(ps,ns)])

5500ms

Best Answer


def primeFactors(n):
    ret = ''
    for i in range(2, n + 1):
        num = 0
        while(n % i == 0):
            num += 1
            n /= i
        if num > 0:
            ret += '({}{})'.format(i, '**%d' % num if num > 1 else '')
        if n == 1:
            return ret

3000ms I save the result as a list → for strings This is a character string from the beginning The execution time is almost the same, but which one is better?

Q2.https://www.codewars.com/kata/559a28007caad2ac4e000083/solutions/python

The drawing shows 6 squares the sides of which have a length of 1, 1, 2, 3, 5, 8. It's easy to see that the sum of the perimeters of these squares is : 4 * (1 + 1 + 2 + 3 + 5 + 8) = 4 * 20 = 80

Could you give the sum of the perimeters of all the squares in a rectangle when there are n + 1 squares disposed in the same manner as in the drawing:

Find four times the sum of the Fibonacci sequences

my A.https://www.codewars.com/kata/559a28007caad2ac4e000083/train/python


def perimeter(n):
    # your code
    fibo = [1,1]
    for i in range(n-1):
        fibo.append(fibo[-1] + fibo[-2] )
    return sum(fibo)*4

best A1.

def fib(n):
    a, b = 0, 1

    for i in range(n+1):
        if i == 0:
            yield b 
        else:
            a, b = b, a+b
            yield b
        

def perimeter(n):
    return sum(fib(n)) * 4

Yield is a statement that has the function of temporarily stopping the execution of a function. By using yield instead of return, you can return elements one by one without storing them in a list etc. What does that mean

length = 5
generator  =fib(length)
for i in range(length):
    print(next(generator),end=', ')

out

1, 1, 2, 3, 5,

In this way, the for loop in the function can be stopped halfway and the value can be returned. It seems that this sum is being taken. For details, see Commentary site etc.

best A2.


def perimeter(n):
    a, b = 1, 2
    while n:
        a, b, n = b, a + b, n - 1
    return 4 * (b - 1)

What this means is that it seems to use this formula

\sum a_n = a_{n+2} - a_{1}

I will try to derive The only formula I use most is $ a_ {k} = a_ {k-1} + a_ {k-2} $ ... Let's think based on $ a_ {n + 2} $. $a_{n+2} = a_{n+1} + a_{n}$ $a_{n+2} = (a_{n} + a_{n-1}) + a_{n}$ $a_{n+2} = a_{n} + 2a_{n-1} + a_{n-2}$ After that, when the term whose coefficient is 2 is expanded so that the coefficient becomes 1. $a_{n+2} = a_{n} + a_{n-1} + 2a_{n-2}+ a_{n-3}$ $…$

a_{n+2} = a_{n} + a_{n-1} + a_{n-2}+…+a_{3}+2a_{1} + a_{0}

Next to the transition $a_{n+2} - a_{1} = \sum a_n $ It will be.