Ad
  • Custom User Avatar
  • Custom User Avatar

    Can you explain, please, what does "|" mean in this solution?

  • Default User Avatar

    For python there is a NATO dictionary already.
    Can I suggest you print it out in the demo program, it'll save people typing out the whole dictionary.

  • Custom User Avatar

    "No additional keys" test checks that the input and output of partial_keys are equal.

  • Default User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Default User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Custom User Avatar

    the feature was already implemented in 3.6, but as implementation detail and wasn't official, effectively. But it was there.

  • Custom User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Default User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Default User Avatar

    The description is not correct.
    they have fib(0) = 1
    and there code doesn't calculate the fibonnaci series.

    Here is my alternative expansion.

    The function is recursively defined by:

    0.    fib(0) = 0
    1.    fib(1) = 1
    2.    fib(2) = 1
    3.    fib(n + 2) = fib(n) + fib(n + 1), if n + 2 > 1
    If one translates the above definition directly into a recursive function, the result is not very efficient. One can try memoization, but that requires lots of space and is not necessary. So, first step is to try and find a tail recursive definition. In order to do that we try to write both sides of equation 3) on the same form. Currently, the left side of the equation contains a single term, whereas the right side is the sum of two terms. A first attempt is to add fib(n + 1) to both sides of the equation:

    3.    fib(n + 1) + fib(n + 2) = fib(n) + 2 * fib(n + 1)

    The two sides of the equation look much more alike, but there is still an essential difference, which is the coefficient of the second term of each side. On the left side of the equation, it is 1 and, on the right, it is 2. To remedy this, we can introduce a variable b:

    3.     b * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (b + b) * fib(n + 1)

    We then subtract both sides by b * fib(n+1)

    3.     b * fib(n + 2) = b * fib(n) + (b + b)

    To try and return the tail to the function we add both sides by a * fib(n+1) to each side:

    3.     a * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (a + b) * fib(n + 1)

    Now the two sides have the same form (call it F), this function has the form:

    3.     F(c, d, e) = F(a, b, n+1) = F(a, a+b, n) = c * fib(e) + d * fib(e + 1)

    (Note if your confused by the above equation substitute the values into the furthest right function and you get)

    3.     a * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (a + b) * fib(n + 1) = c * fib(n) + d * fib(n + 1)

    Which we can simplify to:

    3.     F(a, b, n + 1) = F(b, a + b, n)

    We also have, by definition of F and fib:

    4.     F(a, b, 0) = a * fib(0) + b * fib(1) = b

    (Proove this with general equation)
    F(a, b, n + 1) with n = 0
    c * fib(n) + d * fib(n + 1)
    a * fib(0) + b * fib(0 + 1) as fib(0) = 0, fib(1) = 1
    b
    Also, by definition of F:
    5\.     fib(n) = F(1, 0, n) with a = 1, b = 0
    (Proove this with general equation)
    c * fib(e) + d * fib(e + 1)
    1 * fib(n) + 0 * fib(n + 1)
    1 * fib(n)
    6\.     F(a, b, 1) = a * fib(1) + b * fib(2) = a + b
    (Proove this with general equation)
    F(a, b, n + 1) with n = 1
    c * fib(n) + d * fib(n + 1)
    a * fib(1) + b * fib(1 + 1) as fib(1) = fib(2) = 1
    a + b
    The next step is to translate the above into code:
    def fib(n):
        if n == 0: return 0    # see 6. above
        def F(a, b, n):
            if n == 1: return a + b    # see 6. above
            return F(b, a + b, n - 1)  # see 3. above (F(a, b, n + 1) = F(b, a + b, n)) use n = n - 1
        return F(1, 0, n)              # see 5. above
    

    The final step (optional for languages that support tail call optimization) is to replace the tail recursive function F with a loop:

    def fib(n):
        if n == 0: return 0            # see 4. above
        a, b = 1, 0                    # see 5. above
        while n > 1:		
            a, b, n = b, a + b, n - 1  # see 3. above
        # n = 1 at this point
        return a + b<>                   # see 6. above 
    
  • Default User Avatar

    Your fibonacci description is very wrong, and the code at the end doesn't work:
    A big flaw in your description starts here:
    1. fib(0) = 1

    I did the algebra in a bit more detail trying to work out what went wrong.
    So here is my description, based on what you had:

    The function is recursively defined by:

    0.    fib(0) = 0
    1.    fib(1) = 1
    2.    fib(2) = 1
    3.    fib(n + 2) = fib(n) + fib(n + 1), if n + 2 > 1
    If one translates the above definition directly into a recursive function, the result is not very efficient. One can try memoization, but that requires lots of space and is not necessary. So, first step is to try and find a tail recursive definition. In order to do that we try to write both sides of equation 3) on the same form. Currently, the left side of the equation contains a single term, whereas the right side is the sum of two terms. A first attempt is to add fib(n + 1) to both sides of the equation:

    3.    fib(n + 1) + fib(n + 2) = fib(n) + 2 * fib(n + 1)

    The two sides of the equation look much more alike, but there is still an essential difference, which is the coefficient of the second term of each side. On the left side of the equation, it is 1 and, on the right, it is 2. To remedy this, we can introduce a variable b:

    3.     b * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (b + b) * fib(n + 1)

    We then subtract both sides by b * fib(n+1)

    3.     b * fib(n + 2) = b * fib(n) + (b + b)

    To try and return the tail to the function we add both sides by a * fib(n+1) to each side:

    3.     a * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (a + b) * fib(n + 1)

    Now the two sides have the same form (call it F), this function has the form:

    3.     F(c, d, e) = F(a, b, n+1) = F(a, a+b, n) = c * fib(e) + d * fib(e + 1)

    (Note if your confused by the above equation substitute the values into the furthest right function and you get)

    3.     a * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (a + b) * fib(n + 1) = c * fib(n) + d * fib(n + 1)

    Which we can simplify to:

    3.     F(a, b, n + 1) = F(b, a + b, n)

    We also have, by definition of F and fib:

    4.     F(a, b, 0) = a * fib(0) + b * fib(1) = b

    (Proove this with general equation)
    F(a, b, n + 1) with n = 0
    c * fib(n) + d * fib(n + 1)
    a * fib(0) + b * fib(0 + 1) as fib(0) = 0, fib(1) = 1
    b
    Also, by definition of F:
    5\.     fib(n) = F(1, 0, n) with a = 1, b = 0
    (Proove this with general equation)
    c * fib(e) + d * fib(e + 1)
    1 * fib(n) + 0 * fib(n + 1)
    1 * fib(n)
    6\.     F(a, b, 1) = a * fib(1) + b * fib(2) = a + b
    (Proove this with general equation)
    F(a, b, n + 1) with n = 1
    c * fib(n) + d * fib(n + 1)
    a * fib(1) + b * fib(1 + 1) as fib(1) = fib(2) = 1
    a + b
    The next step is to translate the above into code:
    def fib(n):
        if n == 0: return 0    # see 6. above
        def F(a, b, n):
            if n == 1: return a + b    # see 6. above
            return F(b, a + b, n - 1)  # see 3. above (F(a, b, n + 1) = F(b, a + b, n)) use n = n - 1
        return F(1, 0, n)              # see 5. above
    

    The final step (optional for languages that support tail call optimization) is to replace the tail recursive function F with a loop:

    def fib(n):
        if n == 0: return 0            # see 4. above
        a, b = 1, 0                    # see 5. above
        while n > 1:		
            a, b, n = b, a + b, n - 1  # see 3. above
        # n = 1 at this point
        return a + b<>                   # see 6. above