Multiplication: Finding the Greatest Product
fawnnguyen.com
Multiplication: Finding the Greatest Product
1–10 of 16 posts
Re: Multiplication: Finding the Greatest Product
#2It should be noticed that the title refers to a mathematical product, which is an important distinction especially on Hacker News. :P
Re: Multiplication: Finding the Greatest Product
#3The real gem, for me, was the final quote from one of the children. Any math teacher than can achieve this mindset in the students, is worthy of great praise.
Re: Multiplication: Finding the Greatest Product
#4I see that the challenge to the students in this exercise comes from randomizing the numbers involved. I should do this as a review for my math students, who usually are working on harder problems. This is a good way to reality-check whether students really understand place-value numerals or not.
Re: Multiplication: Finding the Greatest Product
#5Nice problem! I tried to find an algorithm that would solve the general case with arbitrarily many digits, some of them equal. Here's what I ended up with:
def maximize_product(m, n, digits):
if m n
if flipped:
m, n = n, m
digits = sorted(digits)
a, b = [], []
while len(a) Re: Multiplication: Finding the Greatest Product
#6Nice problem! I tried to find an algorithm that would solve the general case with arbitrarily many digits, some of them equal. Here's what I ended up with: def maximize_product(m, n, digits): if m n if flipped: m, n = n, m digits = sorted(digits) a, b = [], [] while len(a) I think I have a proof that it gives the right answer, but won't spell it out here.
You can cut a lot of the boilerplate in your code by using existing functions (apologies if I get the argument orders wrong):
def best_digit_choice_to_maximize_product(n, digits):
numer = lambda d: reduce(
sorted(d, reverse=True),
0,
lambda a, e: a*10 + e)
return max(
itertools.combinations(digits, n),
key = lambda e: numer(e) * numer(set(digits) - set(e)))Re: Multiplication: Finding the Greatest Product
#7Nice problem! I tried to find an algorithm that would solve the general case with arbitrarily many digits, some of them equal. Here's what I ended up with: def maximize_product(m, n, digits): if m n if flipped: m, n = n, m digits = sorted(digits) a, b = [], [] while len(a) I think I have a proof that it gives the right answer, but won't spell it out here.
You can cut a lot of the boilerplate in your code by using existing functions (apologies if I get the argument orders wrong): def best_digit_choice_to_maximize_product(n, digits): numer = lambda d: reduce( sorted(d, reverse=True), 0, lambda a, e: a*10 + e) return max( itertools.combinations(digits, n), key = lambda e: numer(e) * numer(set(digits) - set(e)))
I don't mean this as a criticism -- as you are absolutely correct, your code does cut out a lot of the boilerplate and makes for a more compact function -- but I vastly prefer @cousin_it's function to yours in terms of readability. I think Python is a very pretty language but I always have a hard time reading Python code when it's heavy on the functional paradigms.
Re: Multiplication: Finding the Greatest Product
#8Nice problem! I tried to find an algorithm that would solve the general case with arbitrarily many digits, some of them equal. Here's what I ended up with: def maximize_product(m, n, digits): if m n if flipped: m, n = n, m digits = sorted(digits) a, b = [], [] while len(a) I think I have a proof that it gives the right answer, but won't spell it out here.
You can cut a lot of the boilerplate in your code by using existing functions (apologies if I get the argument orders wrong): def best_digit_choice_to_maximize_product(n, digits): numer = lambda d: reduce( sorted(d, reverse=True), 0, lambda a, e: a*10 + e) return max( itertools.combinations(digits, n), key = lambda e: numer(e) * numer(set(digits) - set(e)))
My code runs in O(n log n) time and can deal with repeated digits. You converted it to something that takes exponential time and chokes on repeated digits.
(BTW, I just realized that my code can be made O(n), by replacing the default sort with a counting sort :-))
Re: Multiplication: Finding the Greatest Product
#9Earlier quoted context omitted.
You can cut a lot of the boilerplate in your code by using existing functions (apologies if I get the argument orders wrong): def best_digit_choice_to_maximize_product(n, digits): numer = lambda d: reduce( sorted(d, reverse=True), 0, lambda a, e: a*10 + e) return max( itertools.combinations(digits, n), key = lambda e: numer(e) * numer(set(digits) - set(e)))
My code runs in O(n log n) time and can deal with repeated digits. You converted it to something that takes exponential time and chokes on repeated digits. (BTW, I just realized that my code can be made O(n), by replacing the default sort with a counting sort :-))
Hm, embarrassing, I just assumed you were doing the naive brute force. You're de-interleaving the digits with an order swap when the digits first start to differ.
Re: Multiplication: Finding the Greatest Product
#10Earlier quoted context omitted.
My code runs in O(n log n) time and can deal with repeated digits. You converted it to something that takes exponential time and chokes on repeated digits. (BTW, I just realized that my code can be made O(n), by replacing the default sort with a counting sort :-))
Hm, embarrassing, I just assumed you were doing the naive brute force. You're de-interleaving the digits with an order swap when the digits first start to differ.
Yeah, that's pretty much it.