# Project Euler #566 "Cake Icing Puzzle" Performance Tuning

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

• @toolic the second one includes a function for joining tuples. it is slightly different since you can get areas like (40,5) which need a new case in the area classification. Furthermore, since you will get two negative areas (for 60 degrees in this example (0,5) and (40,60)you need some sorting right after "#2", in case you also have another area like (20,25), for the loop under "## 22" to work). Also the order in "#4" is adjusted slightly Commented May 2 at 13:28
• You should edit the question with this new information, instead of adding it in the comments. In any case, I find this confusing, and others may as well. I recommend only posting one version of your code. After you receive feedback, you can always post another question. Commented May 2 at 13:32
• Include the text of the Problem Statement in your Question, please. Sometimes sites will bit-rot, even Project Euler. // Your G(ub=11) "test" is not an automated unit test, as it does not "know the right answer" and so cannot display a Green bar. Please include self.assertEqual() or assert ... == ... so we can read the source code to understand what result is expected.
– J_H
Commented May 2 at 17:28
• What's with all the numbers at the start of your code? And I love to hear why you decided to leave comments such as # counter before counter=0 while comments in the places where it would actually make a difference are missing.
– Mast
Commented May 2 at 18:47
• Looks good! I feel the submission is ready for review at this point.
– J_H
Commented May 3 at 8:06

# 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.

• since this is my first time posting to code review: should i update the code in my question accordingly so that other suggestions are not redundant and suggestions on performance can benefit? Commented May 3 at 9:20
• @DuesserBaest No. If you would like the updated code reviewed you should post a new question. Commented May 3 at 11:28