Multiplication: Finding the Greatest Product | Hacker News Reader

Multiplication: Finding the Greatest Product

fawnnguyen.com

125 pointsorin_hanner15 comments

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

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 < 1 or n < 1 or m + n != len(digits):
        raise Exception
      flipped = m > n
      if flipped:
        m, n = n, m
      digits = sorted(digits)
      a, b = [], []
      while len(a) < m:
        a.append(digits.pop())
        b.append(digits.pop())
        if a[-1] != b[-1]:
          break
      while len(a) < m:
        b.append(digits.pop())
        a.append(digits.pop())
      while len(b) < n:
        b.append(digits.pop())
      if flipped:
        a, b = b, a
      return a, b
    
    print maximize_product(3, 2, [8, 4, 2, 7, 5])

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.

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.

It's nice to have this version for testing the faster, more complicated one from OP. I can attest that they indeed produce the same answers.

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 :)

Proof please :)

Use this lemma: If 1 <= a < b < c < d < 10 and b-a = d-c, then log(b) - log(a) > log(d) - log(c).

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 multiplying "ACE" * "BD", you are multiplying "ACE" * "BD0" = ("ACE" * "BD") * 10:

      A C E
    * B D 0

Now, to figure out which of the two greatest digits are A and B, and which of the next two greatest are C and D, you can apply the identity (x + y) * (x - y) = x^2 - y^2 to this. Since "ABC" * "BD0" = (x + y) * (x - y), then equating "ABC" = x + y and "BD0" = x - y, you can solve to get x = ("ACE" + "BD0") / 2, which is the same number no matter the order between A and B, or between C and D. Then maximizing (x + y) * (x - y) means minimizing y^2; or, making the two numbers "ACE" and "BD0" as close together as possible, which leads to the given solution.

Well done. (You have a couple of typos in your last paragraph, where you say "ABC", when you mean "ACE", but your logic makes it clear they are just typos.)

It should be noticed that the title refers to a mathematical product, which is an important distinction especially on Hacker News. :P

Agreed, but this is funny: I am now a product manager so I clicked on it thinking it's going to be interesting in that way. But I work at an education nonprofit and it kicked butt in that way :-).

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

Reply on news.ycombinator.com