Python Code Improvements?

homework
python

#1

Hi,

This is my solution to ECOO(2005) - Fractorials.

Is there any place where I can improve my code? Any advice would be appreciated. Thanks! :slight_smile:

prime_list = [2]
fractorial = {}


def prime_factor(n):
    prime_factorization = {}
    for j in range(len(prime_list)):
        while n % prime_list[j] == 0:
            n = n // prime_list[j]
            update_dict(prime_factorization, prime_list[j])
    if len(prime_factorization) == 0:
        update_dict(prime_factorization, n)
        prime_list.append(n)

    return prime_factorization


def update_dict(dict, n):
    if n in dict:
        dict[n] += 1
    else:
        dict[n] = 1


def main():
    number = int(input())
    if number == 1:
        print("Fractorial(1) = 1")
    else:
        for i in range(2, number + 1):
            prime_factorization = prime_factor(i)
            for key in prime_factorization:
                if key in fractorial:
                    if prime_factorization[key] > fractorial[key]:
                        fractorial[key] = prime_factorization[key]
                else:
                    fractorial[key] = prime_factorization[key]

        fractorial_value = 1
        for key in fractorial:
            fractorial_value *= key ** fractorial[key]
        print(f"Fractorial({number}) = {fractorial_value}")


main()

#3

Use defaultdict instead, it already has this behaviour

This much nesting is difficult to track, it contains a large number of possible paths making it all kinds of difficult to deal with and error prone.

You are creating an iterable and iterating through it to iterate through your iterable.
Iterate through your iterable instead.

I gave up on trying to follow along in what happens in that code, it is all very intertwined, and the behaviour of prime_factor may change.
I’d like to see things being carried out one at a time if at all possible
Without digging too much into it myself, I imagine you would do something like creating a function to factorize a number (doesn’t need to be efficient because your numbers are 22 or less I believe)
Then apply it to each of your numbers
Then figure out which of those you are keeping
Then multiply them together
…emphasis on then, they’re separate steps, in sequence, not being done simultaneously which is what you currently do (which is why you “need” global variables to track your state, causing your factorization function to change its behaviour between calls, this is not a good thing). I may very well have gotten the algorithm wrong.

I would also be tempted to go with a much more naive solution considering that the largest number is only around 200 million, and the results could be hard-coded into the program since there are only 22 of them

The way you keep down complexity (and you have to, because it doesn’t take much more than this to start running into human limits) is by splitting things up into small tasks which are easy to understand by themselves. Then you increasingly combine those together in higher-level tasks which are also understandable because the other parts don’t need to be understood at the same time

I’d want the main function to look something like this:

get input, convert
stuff = create list of 1-x
stuff = get factors(stuff)
stuff = decide what to keep(stuff)
stuff = multiply together(stuff)
write stuff to screen

#4

Wow. Thanks for your advice. I’m on it. So basically, you want it to be modular so that it is easy to understand and check for errors. Just one question, what do you mean by

…emphasis on then , they’re separate steps, in sequence, not being done simultaneously which is what you currently do (which is why you “need” global variables to track your state, causing your factorization function to change its behaviour between calls, this is not a good thing). I may very well have gotten the algorithm wrong.

What do you mean by behaviour between calls? Sorry for the dumb question, I’m new to programming.


#5

You have a global variable which affects how it behaves. It also changes that variable, it’s really difficult to figure out what it does, and I imagine if you called it with other arguments in a different order it wouldn’t behave right at all.

Modular is such a big difficult word. I’m just looking for doing one thing at a time. Right now you have control jumping all over the place. Lots of nesting is a pretty good indication that something should be written differently, though the interaction with that function which changes its own behaviour makes it all a lot worse.

If you look at my mock-up of what i want your main function to look like, those are completely separate steps that don’t interact with each other and happen in sequence


#6

Also, for clarification, this was basically my algorithm.

Say i want fractorial(6).

Then I will loop through the numbers from 2 to 6 (I don’t consider 1).
So I prime factor each number and update the fractorial dictionary, which is initially empty. So…

Prime factor 2 -> 2 ^ 1
Fractorial dict becomes {2:1}

Prime factor 3 -> 3 ^ 1
Fractorial Dict becomes {2:1, 3:1}

Prime factor 4 -> 2 ^ 2
Since 2 is an existing key in fractorial dictionary and the power (2) is greater than the current power of 2 in fractorial dictionary(1). Fractorial Dict becomes {2:2, 3, 1}.

Prime factor 5 -> 5 ^ 1
Fractorial Dict becomes {2^2, 3:1, 5:1}

Prime factor 6 -> 2 ^ 1 x 3 ^ 1
Since 2 and 3 are existing keys in fractorial, but their powers (1 and 1) are less than or equal to the existing powers in fractorial dictionary for 2 and 3 (2 and 1). Then I will not update fractorial dictionary.

Therfore fractorial dictionary is {2:2, 3:1, 5:1} and I multiply all that to get the final value.


#7

That’s the same algorithm I’m describing, I believe.


#8

Oh and apparently Counter (like defaultdict, this is also a version of a dict) has a sweet operation where it can keep the max count of each item when merging Counters:

from collections import Counter

a = Counter([2, 3, 3, 3, 5])
b = Counter([2, 2, 3, 7, 7, 7])
print(a)
print(b)
c = a | b  # <-- union
print(c)

output:

Counter({3: 3, 2: 1, 5: 1})
Counter({7: 3, 2: 2, 3: 1})
Counter({3: 3, 7: 3, 2: 2, 5: 1})

But. Even though it’s super neat it has the cost of figuring out what exactly it does, and most readers probably wouldn’t know what it does either. I learned about it now

Gets worse yet when wanting to apply that operation on an arbitrary amount of such Counters. You could put it in a loop. The really neat way though is with reduce:

from functools import reduce
from collections import Counter
from operator import or_

counters = [a, b, c, d]  # let's pretend those exist
maxcounts = reduce(or_, counters)

Super neat. Neat here mostly meaning there’s a lot to understand… So don’t bother. Yet.


#9

How’s this?

def main():
    number = int(input())
    fractorial = {}
    for i in range(2, number + 1):
        prime_factorization = prime_factor(i)
        update_fractorial(prime_factorization, fractorial)

    print(compute_fractorial_value(fractorial))


def prime_factor(number):
    primes = [2, 3, 5, 7, 11, 13, 17, 19]
    dict = {}
    i = 0
    while i < len(primes):
        p = 0
        while number % primes[i] == 0:
            number = number // primes[i]
            p += 1

        if p != 0:
            dict[primes[i]] = p

        i += 1

    return dict


def update_fractorial(prime_factorization, fractorial):
    for key in prime_factorization:
        if key in fractorial:
            if prime_factorization[key] > fractorial[key]:
                fractorial[key] = prime_factorization[key]
        else:
            fractorial[key] = prime_factorization[key]
            
        # Or should I replace the if/else statements with:
        #
        # if key in fractorial:
        #   if prime_factorization[key] < fractorial[key]:
        #      break
        #
        # fractorial[key] = prime_factorization[key]
        #
        # since it has less code.


def compute_fractorial_value(fractorial):
    value = 1
    for key in fractorial:
        value *= key ** fractorial[key]

    return value


main()

#10

Not done looking, but surely, rather than passing in an empty dict, create one inside that function instead, and return it?

…Oh you’re doing it multiple times.
I’d rather you returned multiple results, and consolidate them later
So your factorisation function would return a list of factors.
And then you would have several such lists, which you then, in a separate step figure out what to keep

It’s doing two things at once. And I’m not a fan, because it’s easy to separate that

…oh they are two steps. but. they’re like… taking turns. I want ALL the factors before doing anything else

Anyway. It’s better. And it’s starting to be more of an opinion than an obvious problem


#11

This is what I came up with:

from collections import Counter
from functools import reduce
from operator import or_, mul


def main():
    x = int(input())
    xs = range(1, x+1)
    factors = [Counter(prime_factors(x)) for x in xs]
    consolidated = reduce(or_, factors)
    multiplied = reduce(mul, consolidated.elements())
    print(multiplied)


def prime_factors(n):
    if n == 1:
        return [1]
    divisor = 2
    result = []
    while divisor <= n:
        if n % divisor == 0:
            result.append(divisor)
            n //= divisor
        else:
            divisor += 1
    return result


if __name__ == '__main__':
    main()

I suppose that it illustrates that past getting the factors, it’s all just massaging the data into the format you want. Think assembly lines. You put your data on one assembly line. Then that feeds into the next. At the end you have the result.
What you don’t do is switch assembly lines back and forth.


#12

That’s where I want a defaultdict, if you’re going to do it that way. You can make it default to 0.

from collections import defaultdict
fractorial = defaultdict(int)
print(fractorial[3])  # 0 (default)

#13

Oh and I like this. // instead of / is the correct way to do it. Otherwise you’re using floats for no reason at all.


#14

I noticed you imported various modules that I have not come across anywhere in the the text I read “Introduction to Python Programming” by Daniel Liang. Could you list some useful and commonly used modules that one should know.

Thanks for all your help. :slight_smile:


#15

When you need some particular behaviour, google it and see if it already exists. The common stuff is in the builtins module (that’s what you don’t need to import, always there), most of the rest is situational


#16

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.