11–16 of 16 posts
It should be noticed that the title refers to a mathematical product, which is an important distinction especially on Hacker News. :P
Nice 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)))
Two fixes: - If you use `(Counter(digits)-Counter(e)).elements()` in the last line, you can support repeated digits. - Reduce is `reduce(function, sequence[, initial]) -> value` so you should move the lambda to the first argument.
All in all I think this is a very nice, succinct use of Python. The combinatorial parts of `itertools` are extreamly handy :)
Nice 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.
Once you figure out that the most significant digits should be the largest ones, and the 3rd and 4th largest digits should be in the 2nd most significant place, you end up with a situation like this:
A C E
* B D
A C E
* B D 0
Nice 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.
Proof please :)
I think this also makes a good tie-in for teaching algebra. Once you figure out that the most significant digits should be the largest ones, and the 3rd and 4th largest digits should be in the 2nd most significant place, you end up with a situation like this: A C E * B D To make it more clear what to do next, you can just append a zero onto the number "BD" and still solve the same problem, because instead of multiply…