Related to this question I am still looking for a solution to 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=\frac{360}{9}\$ degrees, \$\frac{y=360}{10}\$ degrees and \$z=\frac{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=\frac{360}{a}\$ degrees, \$y=\frac{360}{b}\$ degrees and \$z=\frac{360}{\sqrt{c}}\$ degrees.
Let \$G(n) = \sum\limits_{9<=a<b<c<=n} F(a,b,c)\$, for integers a, b and c.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 slices start at 0
- I save all areas that are upside down with tuples of ranges
- every new slice then checks for all areas, if they are inside the range of the slice
- all affected areas are joined and rotated around the middle of the piece of cake.
The code seems to be working fine (passing all unit tests), however the performance is so slow that it would take an astronomical amount of time to solve the actual problem.
from math import sqrt
def get_affected_areas(areas:list,angle:float,start_angle:float=0.0)->tuple:
"""function that from a list of areas splits into affected and unaffected areas"""
areas_affected=[]
areas_new=[]
for area in areas:
## 11 area completely in target space
if start_angle<=area[0]<area[1]<=angle:
areas_affected.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_affected.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_affected.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_affected.append(ar_in)
## 15 uneffected area
else:
areas_new.append(area)
return areas_affected,areas_new
def rotate_num(value:float, center:float)->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)->tuple:
"""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 flip_affected_areas(areas_affected:list,angle:float,start_angle:float=0.0)->list:
"""
function that takes a list of negative areas.
eturns the negative areas after the region has been flipped.
"""
## 21 get new positive areas
area_affected_positive=[]
# 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_affected:
ar_pos=get_pos_area(area=ea,angle=angle,angle_start=start_angle)
area_affected_positive.insert(0,ar_pos)
## 22 get negative areas from positives -- if no areas, all negative
areas_affected_flipped=[]
pos=start_angle
for ap in area_affected_positive:
ar_neg=(pos,ap[0])
areas_affected_flipped.append(ar_neg)
pos=ap[1]
try:
ar_neg=(area_affected_positive[-1][1],angle)
areas_affected_flipped.append(ar_neg)
## 23 deleting empty areas
areas_affected_flipped=[an for an in areas_affected_flipped if an[0]!=an[1]]
except (IndexError):
# this error happens if area_affected_positive is empty sinc there exist no positive areas.
# this is not problematic, as in this case no areas are appended to areas_new.
areas_affected_flipped.append((start_angle,angle))
return areas_affected_flipped
def sort_pieces(piece)->float:
"""function for sorting pieces based on second value (upper bound)"""
return piece[1]
def f(
a:int,
b:int,
c:int,
max_counter:int=1_269_260,
log_threshold:int=1e6,
epsilon:float=1e-10
)->int:
""""
function to run a while loop of rotating cake pieces of sizes a,b,c cyclically
returns number of steps needed until the upperside of the cake is on top again
max_counter set by default to 1.2M as this is the expected result of g(17)
"""
# 0 Initialize an empty vector to store negative areas.
# all negative areas will be collected and deducted based on cake piece rotation
# when the list areas is empty this means there exist no negative areas
# hence then the cake is perfectly upside up
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 rotated. this drastically reduces complexity
start_angle=0.0
# termination criteria for while loop
cake_unfinished=True
while cake_unfinished:
# get current angle
angle=angles[counter%3]
# # 1 identify all affected areas as well as uneffected areas and put into new arrays
areas_affected,areas_new=get_affected_areas(
areas=areas,
angle=angle,
start_angle=start_angle
)
# 2 flip affected areas
areas_affected_flipped=flip_affected_areas(
areas_affected=areas_affected,
angle=angle,
start_angle=start_angle
)
# 3 join effected and uneffected areas
areas_new+=areas_affected_flipped
# 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
## 51 throw out "tiny" areas, as they occur due to rounding issues
areas=[a for a in areas_new if abs(a[0]-a[1])>epsilon]
## 52 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)==785_232
def g(
upper_bound:int,
lower_bound:int=9,
max_counter:int=1269260,
log_threshold:int=1e6,
epsilon:float=1e-10
)->int:
"""function iterating over all possible combinations of f() within specified upper_bound """
print(f"\n---------------------------------\nStarting g with upper bound of {upper_bound}\n---------------------------------\n")
sum=0
# generate all possibilities for f(a,b,c) and sum the results into sum.
for a in range(lower_bound,upper_bound-1):
print(f"\n-----------\na now at {a}\n-----------\n")
for b in range(a+1,upper_bound):
for c in range(b+1,upper_bound+1):
res=f(a=a,b=b,c=c,max_counter=max_counter,log_threshold=log_threshold,epsilon=epsilon)
# 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"\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\nFinished g with upper_bound {upper_bound}! Resulting sum = {sum}\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n")
return sum
# tests for g
assert g(upper_bound=11)==60
assert g(upper_bound=14)==58_020
assert g(upper_bound=17)==1_269_260
How can I change (areas of) my code to make it run more efficiently?
What else I've 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,epsilon:float=1e-10)->list:
"""given a list of tuples joins tuples when applicable"""
max_idx=len(area)
for i1 in range(0,max_idx-1):
for i2 in range(i1+1,max_idx):
if -epsilon<(area[i1][0]-area[i2][1])<epsilon:
area.append((area[i2][0],area[i1][1]))
del area[i1],area[i2-1]
return True
if -epsilon<(area[i1][1]-area[i2][0])<epsilon:
area.append((area[i1][0],area[i2][1]))
del area[i1],area[i2-1]
return True
return False
