3

I need to write a python script that counts the number of times these operations: +, -, *, //, %, >, <, ==, <=, >= are performed in a piece of python code relative to the input of N.

Python Code:

def bar(k):
    score = 0
    for i in range(2, k + 1):
        j = i - 1
        while j > 0:
            if i % j == 0:
                score = score // 2
            else:
                score = score + 10
            j = j - 1
    return score

mod = 10**9 + 7

def foo(n):
    m = n % 3
    if n == 0:
        return 1
    elif m == 0:
        v = foo(n // 3)
        t = 0
        for i in range(1, n+1):
            t = t + bar(4 * i)
        return v + t
    elif m == 1:
        v = foo(n - 1)
        return v + bar(n * n * n)
    else:
        v = foo(n - 2)
        r = 1
        for a in range(2, n):
            r = r * a % mod
            r = r + bar(n)
        return v + r

My Script:

def count_operations(n):
    if n == 0:
        return 1  # Base case: 1 operation for returning 1
    elif n % 3 == 0:
        return count_operations(n // 3) + 4
    elif n % 3 == 1:
        return 6 + count_operations(n - 1) + 4
    else:
        return 9 + 2 * count_operations(n - 2)

I wrote the script with the understanding of when N=1,calculating m=1 % 3 takes 1 operation, and the value of m is 1. Then the code executes 3 tests of the == operation before finding one to be true, when it encounters elif m == 1:. Up to that point, 4 operations have been performed.

Then it performs a recursive call with foo(n-1) which means that 5 operations have now been performed before the recursive call (the last for the -). The recursive call now has n=0, so 2 more operations occur (n%3 and n==0), before it returns with its result of 1. That makes a total of 7 basic operations that have now been performed to the point of returning from the recursive call to foo.

The code next encounters return v + bar(nnn), which means that 2 more operations (both *) occur before the call to bar followed by 1 more (+) afterwards, to bring the total 10, not counting the number done in bar. Simulating the call to bar(1), 1 more operation (k+1) is performed when the top end of the range of the for loop is calculated, bringing the total to 11. The for loop terminates immediately since the range of its iteration is empty, and the score of 0 is returned to complete the (already counted) + operation and return statement in foo. So, that means a total of 11 basic operations were performed, and we return 11 as the answer for when N=1.

So, my script only works correctly when n=1 anyone can help me fixed my script to get an understanding of how to do the proper counting when N>1?

My inefficient code what produces the correct answer:

class Integer(int):
    n_ops = 0

def new_patch(name):
    def patch(self, *args):
        Integer.n_ops += 1
        value = getattr(int, name)(self, *args)
        if isinstance(value, int) and not (value is True or value is False):
            value = Integer(value)
        return value
    patch.__name__ = name
    return patch

methods = {
    '__le__': '\u2264',
    '__lt__': '<',
    '__ge__': '\u2265',
    '__gt__': '>',
    '__eq__': '==',
    '__add__': '+',
    '__sub__': '-',
    '__mul__': '*',
    '__floordiv__': '//',
    '__mod__': '%',
}

for name in methods:
    setattr(Integer, name, new_patch(name))
    
def bar(k):
    score = 0
    for i in range(2, k + 1):
        j = i - 1
        while j > 0:
            if i % j == 0:
                score = score // 2
            else:
                score = score + 10
            j = j - 1
    return score

mod = 10**9 + 7
Integer.n_ops+=1

def foo(n):
    m = n % 3
    if n == 0:
        return 1
    elif m == 0:
        v = foo(n // 3)
        t = 0
        for i in range(1, n+1):
            t = t + bar(4 * i)
        return v + t
    elif m == 1:
        v = foo(n - 1)
        return v + bar(n * n * n)
    else:
        v = foo(n - 2)
        r = 1
        for a in range(2, n):
            r = r * a % mod
            r = r + bar(n)
        return v + r

    def countOps(n):
       print(f'Number of operations when n={n}: {Integer.n_ops}')
Improve this question
16
  • After this modulo assignment m=n%3, m will be either 0, 1, or 2. Why are you then performing further modulo operations on m? It's not necessarily wrong, but it is confusing and wasteful. Commented Feb 22 at 3:03
  • @JohnGordon that was a mistake i put the wrong code, i put the correct code now. Commented Feb 22 at 3:22
  • @aaa nope well kinda but not like that. Commented Feb 22 at 3:25
  • @aaa it should just return in total how many times those operations are called, not individually count them. Commented Feb 22 at 3:37
  • ok for when n = 1 it should return 11 as explained as the last part of my question, and when n=2 it should return how many times the basic operations are used. Commented Feb 22 at 5:07

3 Answers 3

Reset to default
3

First of all, as you want to count both % and == as operations, the first base case should be return 2 instead of return 1. Also the constant terms you add in the other return statements seem all wrong. For instance, the second return statement should count 6 instead of 4 as its constant term: there are n % 3, n == 0, m == 0, n // 3, n+1, v+t. It seems you have not counted the comparisons.

Here is an analysis to get the correct counts:

Analysis

First look at bar.

  • The number of operations in the body of the while loop is 4: a %, ==, either // or +, and -.

  • The number of executions of the while loop body is 𝑗, and the operation in the while condition is executed one more time, so that gives 5𝑗+1 operations for the while, not considering the outer loop yet.

  • The body of the for loop has one more operation (a -) so that body executes 5𝑗+2 operations.

  • The for loop makes 𝑖 vary from 2 to 𝑘 (inclusive), and thus 𝑗 varies from 1 to 𝑘−1 (inclusive), so we have this count of operations:

            ∑𝑗=1..𝑘−1(5𝑗+2)

        = 5∑𝑗=1..k−1(𝑗) + 2(𝑘−1)

    The sum term is a triangular number. We can substitute it:

            5(𝑘²−𝑘)/2 + 2(𝑘−1)

        = (5𝑘² − 𝑘 − 4) / 2

  • Add to that the operation in the range argument, and we get as final number of operations for bar(k):

            (5𝑘² − 𝑘 − 2) / 2

Now look at foo.

  • For the case where 𝑚 is 0:

    • One iteration of the for loop body executes 2 operations and those from the bar call, i.e.

              2 + (5(4𝑖)² − 4𝑖 − 2) / 2

          = 40𝑖² − 2𝑖 + 1.

    • As 𝑖 iterates from 1 to 𝑛 (inclusive), we have this sum:

              ∑𝑖=1..𝑛(40𝑖² − 2𝑖 + 1)

          = 40∑𝑖=1..𝑛(𝑖²) − 2∑𝑖=1..𝑛(𝑖) + 𝑛

      The second sum is again a triangular number, while the first is a square pyramidal number, for which there also is a closed formula, and so we can write the above as:

              40(2𝑛³+3𝑛²+𝑛)/6 − 2(𝑛²+𝑛)/2 + 𝑛

          = 20(2𝑛³+3𝑛²+𝑛)/3 − 𝑛² − 𝑛 + 𝑛

          = (40𝑛³ + 57𝑛² + 20𝑛)/3

    • There are 6 more operations to add to this (n % 3, n == 0, m == 0, n // 3, n+1, v+t), excluding the recursive call (which apparently you want to maintain), so we arrive at this count for when 𝑚 is 0:

              (40𝑛³ + 57𝑛² + 20𝑛 + 18) / 3

  • For the case where 𝑚 is 1:

    • We have one call of bar with argument 𝑛³, so that represents (5(𝑛³)² − 𝑛³ − 2) / 2 operations.

    • There are 8 more operations to add to this (n % 3, n == 0, m == 0, m == 1, n - 1, n * n * n (2), v + bar()), so we arrive at

              (5𝑛6 − 𝑛³ + 14) / 2

  • For the case where 𝑚 is 2:

    • One iteration of the for loop body executes 3 operations and those from the bar call, i.e.

              3 + (5𝑛² − 𝑛 − 2) / 2

          = (5𝑛² − 𝑛 + 4) / 2.

    • As 𝑎 iterates from 2 to 𝑛−1 (inclusive), we have 𝑛−2 of those iterations, where the number of operations don't depend on 𝑎, and so we get:

              (𝑛 − 2)(5𝑛² − 𝑛 + 4) / 2

          = (5𝑛³ − 11𝑛² + 6𝑛 − 8) / 2

    • There are 6 more operations to add to this (n % 3, n == 0, m == 0, m == 1, n - 2, v + r), so we arrive at

              (5𝑛³ − 11𝑛² + 6𝑛 + 4) / 2

Code

The above analysis leads to the following code for count_operations:

def count_operations(n):
    if n == 0:
        return 2
    elif n % 3 == 0:
        return count_operations(n // 3) + (40*n**3 + 57*n*n + 20*n + 18) // 3
    elif n % 3 == 1:
        return count_operations(n - 1) + (5*n**6 - n**3 + 14) // 2
    else:
        return count_operations(n - 2) + (5*n**3 - 11*n*n + 6*n + 4) // 2
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

This code does calculate it efficiently but its just like mine it does not calculate it correctly, your code returns 10 for when N=1 and 7 for when N=2 and its way off with numbers greater than 2.
I had already left a comment below your question, asking about n=3 and why you think it should be 16. That just cannot be right. Please clarify my comments below your original post to explain exactly how you arrive at 16, since executing each operation for n=3 is surely much much more. The loops in bar execute a lot!!
the comment section is not enough for me to explain it can i email you? @trincot
Just extend your original post with the information needed. Note that even btilly's answer will return a score of 37 for when calling bar(4), and this is what foo(3) calls. So how can you say that for n=3 the outcome should be 16? This point really needs to be clarified. This information should be available to anyone visiting the question.
Does the acceptance mark mean that the expected output you mentioned in comments was not correct? Are your comments here obsolete now? Not sure how to interpret this ;-)
1

Just add a counter to the code. Be sure not to miss any operations. For example.

def bar(k):
    score = 0
    c = 1 # for the k+1
    for i in range(2, k + 1):
        j = i - 1
        c += 1 # for -
        while j > 0:
            if i % j == 0:
                score = score // 2
            else:
                score = score + 10
            j = j - 1
            c += 5 # for >, %, ==, // or +, -
        c += 1 # for the final > in the loop test.
    return score, c

But now when you call it you have to take the extra argument into account. So

r = r + bar(n)

becomes:

score, c_tmp = bar(n)
r = r + score
c += c_tmp + 1

And now the logic of your counting matches the logic of your code.

Improve this answer

3 Comments

the code itself shouldn't be ran.
the python code itself shouldn't be ran it's supposed to be solved by solved by a counting_operations function and not just by running foo or bar.
@Geddez That makes it a math problem, not a programming problem. I guess that someone else did the math for you though.
0

As far as I understand, your code doesn't work for n = 2, and you don't know why.

It should be simple to check. Here are some ideas:

  • Put a breakpoint on Integer.n_ops += 1 in your new_patch function; run your code for n = 2; each time you get to the breakpoint, try to think what the code is doing
  • Make several functions like new_patch — one per operator; print the name of the operator instead of counting; try to think about the order of the operators and understand which ones you missed
  • Instead of relying on operator overloading, modify your foo and bar code to increase a global counter or print some message right next to each usage of any arithmetic operator

Once you fix your counting code for n = 2, proceed to next case, n > 2. It should be harder, but you will already have debugging tools, so it should be possible.

It's basic debugging really; use the principles of "from simple to complex" and "learn how to fish instead of asking people for fishes".

Improve this answer

2 Comments

The first code does not work for any number(N) greater than 1, but the very last code in my question does work for all numbers(N) given but it is very slow., if N is greater than 100 it takes like 5 minutes to calculate the answer.
Wow, that's very slow for your last piece of code! I hope you can fix your fast code to produce the correct result.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.