Project Euler #566 "Cake Icing Puzzle" Performance Tuning

Question

I am rather new to python and wanted to use Project Euler to learn more about it. The task can be seen here, so I will skip any description of my own:

---

Project Euler Problem 566 (see Link for a nice simulation also)

Adam plays the following game with his birthday cake.

He cuts a piece forming a circular sector of 60 degrees and flips the piece upside down, with the icing on the bottom.
He then rotates the cake by 60 degrees counterclockwise, cuts an adjacent $60$ degree piece and flips it upside down.
He keeps repeating this, until after a total of twelve steps, all the icing is back on top.

Amazingly, this works for any piece size, even if the cutting angle is an irrational number: all the icing will be back on top after a finite number of steps.

Now, Adam tries something different: he alternates cutting pieces of size x=360/9 degrees, y=360/10 degrees and z=360/sqrt(11) degrees. The first piece he cuts has size x and he flips it. The second has size y and he flips it. The third has size z and he flips it. He repeats this with pieces of size x, y and z in that order until all the icing is back on top, and discovers he needs 60 flips altogether.

Let F(a,b,c) be the minimum number of piece flips needed to get all the icing back on top for pieces of size x=360/a degrees, y=360/b degrees and z=360/sqrt(c) degrees.
Let G(n) = SUM OVER 9

You are given that F(9, 10, 11) = 60, F(10, 14, 16) = 506, F(15, 16, 17) = 785232.
You are also given G(11) = 60, G(14) = 58020 and G(17) = 1269260.

Find G(53).

---

My approach is the following:

• the cake is always rotated so that the sliced are starts at 0
• i save all areas that are upsite down with tuples of ranges
• every new slice then checks for all areas, if they are inside the range of the slice
• all effected areas are joined and rotated around the middle of the piece of cake.

Here is my code which I hope is commented in a readable way :

from math import sqrt

def rotate_num(value:float, center:float):
    # function to rotate values around center, when a piece of cake is flipped.
    dist=center-value
    return center+dist

def get_pos_area(area:tuple, angle:float, angle_start:float=0.0):
    # get the positive area values beloning to a negative area
    center=(angle-angle_start)/2
    return (rotate_num(area[1],center),rotate_num(area[0],center))

def sort_pieces(piece):
    # function for sorting pieces based on second value (upper bound)
    return piece[1]

def F(a:int,b:int,c:int,max_counter:int=1269260,log_threshold:int=1e6):
    # 0 Initialize an empty vector to store negative areas
    areas=[]

    # angle length
    angles=(360/a,360/b,360/sqrt(c))

    # counter of the iterations. will also be used to change the angles applied at each step
    counter=0

    # start angle is always at 0, since the cake will be roatated. this drastically reduces complexity
    start_angle=0.0

    # termination for while loop
    cake_unfinished=True
    
    while cake_unfinished:
        # get current angle
        angle=angles[counter%3]

        # 1 identify all effected areas as well as uneffected areas and put into new arrays
        areas_eff=[]
        areas_new=[]

        for area in areas:

            ## 11 area completely in target space
            if start_angle<=area[0]<area[1]<=angle:
                areas_eff.append(area)
            
            ## 12 area with upperbound in target space
            elif start_angle<area[1]<=angle:
                ar_out,ar_in=(area[0],start_angle),(start_angle,area[1])
                areas_new.append(ar_out)
                areas_eff.append(ar_in)

            ## 13 area with lowerbound in target space
            elif start_angle<=area[0]<angle:
                ar_in,ar_out=(area[0],angle),(angle,area[1])
                areas_new.append(ar_out)
                areas_eff.append(ar_in)

            ## 14 area engulfing targetspace
            elif start_angle<angle<area[1]<area[0]:
                ar_in,ar_out_lower,ar_out_upper=(start_angle,angle),(area[0],start_angle),(angle,area[1])
                areas_new.append(ar_out_lower)
                areas_new.append(ar_out_upper)
                areas_eff.append(ar_in)

            ## 14 uneffected area
            else:
                areas_new.append(area)

        # 2 flip effected areas

        ## 21 get new positive areas
        area_eff_pos=[]

        # get all areas, that are not negative in the target area. 
        # these (to be precise their rotated values) are the ones that will become negative after being flipped 
        for ea in areas_eff:
            ar_pos=get_pos_area(area=ea,angle=angle,angle_start=start_angle)
            area_eff_pos.insert(0,ar_pos)
            
        ## 22 get negative areas from positives -- if no areas, all negative
        area_eff_neg=[]
        pos=start_angle

        for ap in area_eff_pos:
            ar_neg=(pos,ap[0])
            area_eff_neg.append(ar_neg)
            pos=ap[1]

        try: 
            ar_neg=(area_eff_pos[-1][1],angle)

            area_eff_neg.append(ar_neg)

            ## 23 deleting negative areas
            area_eff_neg=[an for an in area_eff_neg if an[0]!=an[1]]

            # 3 join effected and uneffected areas
            for an in area_eff_neg:
                areas_new.append(an)

        except:
            pass

        # if there were no negative areas, the whole effected are becomes negative
        if len(areas_eff)==0:
            areas_new.append((start_angle,angle))

        # 4 rotate cake (north the cake)

        ## 41 add degrees (cake needs to be rotated the amount of the next angle)
        angle_rotate=angles[(counter+1)%3]
        areas_new=[((a[0]+angle_rotate)%360,(a[1]+angle_rotate)%360) for a in areas_new]

        ## 42 sort for next iteration
        areas_new.sort(key=sort_pieces)


        # 5 update for next iteration
        areas=[]
        
        ## throw out "tiny" areas, as they occur due to rounding issues
        for ar in areas_new:            
            if not -1e-10<(ar[1]-ar[0])<1e-10:
                areas.append(ar)

        ## count up for next iteration
        counter+=1

        ## give periodical logs to confirm program is still running
        if (counter%log_threshold)==0:
            print(f"cake {a,b,c} at counter {counter}")
            pass

        # checkout when cake is finished
        if len(areas)==0:
            cake_unfinished=False
            print(f"cake {a,b,c} finalized after {counter} iterations!")
            return counter
        # checkout in case cake does not finish in time
        elif counter>max_counter: 
            cake_unfinished=False
            print(f"cake not finilized after {counter} iterations!")
            return 0

# tests for F
assert F(a=9,b=10,c=11)==60
assert F(a=10,b=14,c=16)==506
assert F(a=15,b=16,c=17)==785232

def G(ub:int,lb:int=9,max_counter:int=1269260,log_threshold:int=1e6):
    print(f"---------------------------------\nStarting G with upper bound of {ub}\n---------------------------------\n")

    sum=0

    # generate all possibilities for F(a,b,c) and sum the results into sum.
    for a in range(lb,ub-1):
        print(f"----------\na now at {a}\n----------\n")
        for b in range(a+1,ub):
            for c in range(b+1,ub+1):
                
                res=F(a=a,b=b,c=c,max_counter=max_counter,log_threshold=log_threshold)
                # if F() aborts due to reaching max_counter, it returns 0
                if res==0:
                    print(f"Error for F({(a,b,c)}) - max_counter {max_counter} reached")
                    return res
                else:
                    sum+=res

    print(f"G({ub})={sum}")
    return sum

# tests for G
assert G(ub=11)==60
assert G(ub=14)==58020
assert G(ub=17)==1269260

As can be tested, my code returns the desired results for all tests of F() and G(). However, when running on G(53) it just runs forever. I know that the code is not really efficient, however I lack the knowledge of what can be improved.

---

WHAT ELSE I TRIED

One possible improvement would be joining two areas like (0,1) and (1,5) into (0,5), to reduce the time it takes to iterate over all the areas (by reducing the areas). For this I wrote a function rationalize_areas() that can be seen below. It runs inside a while loop but it is just making the code run much longer. Some other adjustments need to be made to the code if the function should be included.

def rationalize_areas(area:list):
    max_idx=len(area)

    for i1 in range(0,max_idx-1):
        for i2 in range(i1+1,max_idx):

            if -1e-10<(area[i1][0]-area[i2][1])<1e-10:
                area.append((area[i2][0],area[i1][1]))
                del area[i1],area[i2-1]
                return True
            if -1e-10<(area[i1][1]-area[i2][0])<1e-10:
                area.append((area[i1][0],area[i2][1]))
                del area[i1],area[i2-1]
                return True
    
    return False

Answer 1

docstrings

def rotate_num( ... ):
    # function to rotate values around center, when a piece of cake is flipped.
    ...
def get_pos_area( ... ):
    # get the positive area values beloning to a negative area
    ...
def sort_pieces( ... ):
    # function for sorting pieces based on second value (upper bound)

Thank you for these helpful comments.

But, they should be """docstrings""", spelling out the single responsibility of each function.

Kudos for the optional type annotations. Consider mentioning the -> return type of each function.

lower case

The Problem Statement speaks of "F()" and "G()".

When translating from those English sentences into executable python code, pep-8 explains that it would be appropriate to turn them into f() and g(). No biggie.

magic number

..., max_counter: int = 1_269_260, ...

That is 20 × 63_463. I have no idea what significance that holds. It merits a # comment. Also, feel free to use an _ underscore every three characters, in order to improve legibility. The 1e6 threshold of a million, for example, was very legible.

nit, typo: "roatated"

Bigger typo: "identify all AFFECTED areas as well as UNAFFECTED areas and ..."
areas_eff = [] --> areas_affected = []

areas

The OP code introduces a central datastructure with this:

    # 0 Initialize an empty vector to store negative areas
    areas=[]

It would have been more helpful to describe the meaning of entries in that list, to help us reason about its relationship to the Problem Statement, and to reason about termination of the {while, for} loops.

extract helper

The function F is entirely Too Long. We cannot view all of it without vertically scrolling. It would benefit from evicting some of the logic into one or more helper routines.

bare except

        except:
            pass

No.

We don't write a bare except, not ever, as it disables important functionality such as CTRL/C handling.

Prefer except Exception:.

Even better, tell us what kind of exception you're worried about, either in the code or at least in a # comment.

Consider logging a given exception e when it occurs.

epsilon

        # throw out "tiny" areas, as they occur due to rounding issues
        for ar in areas_new:            
            if not -1e-10 < (ar[1] - ar[0]) < 1e-10:

Thank you for the helpful comment, which explains the why rather than the how -- very good.

We still have a magic number to deal with. Consider putting ... , eps=1e-10): in the signature. Then we could write if not -eps < ... < eps:. Or we could compare abs(...) < eps.

commas

assert F(a=15, b=16, c=17) == 785232

Consider writing that last constant as 785_232, so at a glance it's immediately clear we're dealing with a quantity less than a million. Unlike, for example, 1_269_260.

design of Public API

def G(ub: int, lb: int = 9, ...

These are some pretty OK identifiers for the input parameters. But they could be better.

"lb" and "ub" are not exactly cryptic ways of describing lower- and upper- bound; they are fairly clear. Though they would be more naturally described in that order in the signature.

Minimally I would expect to see mention of such bounds in a """docstring""".

Absent that, as we have here, it would be appropriate to use lower_bound and upper_bound as the parameter names. And then immediately assign them to lb and ub local vars within the function, for convenience. Parameter names are part of the Public API that you design for callers, and the documentation burden is a little bit higher than it is for local vars.