Skip to content

Instantly share code, notes, and snippets.

@davoscollective davoscollective/lds.py
Last active Apr 18, 2018

Embed
What would you like to do?
List versus generator for a code interview question - find largest sum of digits for some range of exponential expressions
"""
lds - large digit sum
"""
from itertools import product
from timeit import timeit
import tracemalloc
import matplotlib.pyplot as plt
def original_lds():
x = 80
y = 80
a = list(str(pow(x, y)))
d = sum([int(i) for i in a])
range1 = range(1, 100)
range2 = range(1, 100)
for i in range1:
for j in range2:
p = list(str(pow(int(i), int(j))))
k = [int(x) for x in p]
m = sum(k)
if m > d:
d = m
return d
# itertools.product "Roughly equivalent to nested for-loops in a generator expression"
def lds():
for base, exponent in product(range(1,100), repeat=2):
yield sum(int(x) for x in str(base ** exponent)), base, exponent
def max_lds():
"""
lds returns a tuple, this finds the max of the first value in the tuple, sum_of_digits
"""
return max(lds())[0]
if __name__ == '__main__':
# check equivalency
print('Do the functions return the same value?')
print(f'Is {original_lds()} equal to {max_lds()} ? : {original_lds() == max_lds()}')
# Which exponential expression yields the highest sum of digits?
# lds returns a tuple of the (sum_of_digits, base, exponent)
max_sum_of_digits, base, exponent = max(lds())
expression_label = str(base)+"**"+str(exponent)+" = "+str(max_sum_of_digits)
print(f"The expression that yields the highest sum of digits: {max_sum_of_digits} is {expression_label}")
# Takes the memory measurement on just the functions
tracemalloc.start(10)
time1 = tracemalloc.take_snapshot()
original_lds()
max_lds()
time2 = tracemalloc.take_snapshot()
# Show results of memory measurements
print("[ Memory Comparison between snapshots ]")
stats = time2.compare_to(time1, 'lineno')
for stat in stats[:10]:
print(stat)
print ('[Highest memory usage]')
stat = stats[0]
print(f"{stat.count} blocks: {stat.size / 1024} KiB")
print('\n'.join(stat.traceback.format()))
tracemalloc.stop()
# Takes & shows timing measurements averaged over 'number' iterations
"""
print(timeit('original_lds()',setup='from __main__ import original_lds', number=100))
print(timeit('max_lds()',setup='from __main__ import max_lds', number=100))
"""
max_x_index = {b[0]:i for i,b in enumerate(lds())}[max_sum_of_digits]
# plot the output of the generator
# matplotlib needs the full list to render, not a generator
plt.plot([val for val, base, exponent in lds()])
plt.title('Sum of digits for exponentials 1**1 to 99*99')
plt.xlabel('1**1 through 99**99')
plt.ylabel('Sum of digits')
plt.annotate(expression_label, xy=(max_x_index, max_sum_of_digits),xytext=(max_x_index-300, max_sum_of_digits))
plt.show()
@davoscollective

This comment has been minimized.

Copy link
Owner Author

commented Apr 18, 2018

Run like this:
python lds.py

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.