• + 0 comments

    I started out thinking I could simply go through each good cell and compute the biggest plus I could make with that cell as its center. While doing this, I tracked the largest two areas seen, then finally returned the product of those two values.

    This doesn't work for two reasons:

    1. We cannot count two pluses if they have overlapping cells
    2. We have to consider not only the LARGEST plus you can make from a given center, but any possible smaller sized plus.

    The second case might happen if you have a 9-area plus and a 13-area plus that overlap. But inside the 13-area plus is a smaller 9-area plus that doesn't overlap with the other 9-area plus. Those two pluses might turn out to be the two largest ones in the grid.

    So the approach looks more like this:

    1. Create a pluses array to hold all of the pluses you find.
    2. For each good cell, try to make pluses of size 1, 5, 9, 13, 17, ... etc. using that cell as the center. Each time you find a plus, copy its cell coordinates into a set and save that set in pluses.
    3. You now have a large array of pluses, each one represented as a set of coordinates.
    4. Set a value for the maximum product found so far to zero.
    5. Iterate through every possible pair of pluses. If the product of their lengths is greater than the maximum found so far, check if the pluses are overlapping. (In Python, you can check if two sets overlap by finding their intersection; if they overlap, len(set1 & set2) > 0.) If they don't overlap, update the maximum product found so far.