Another harder problem. The first part was pretty simple and didn’t take me too much time to solve, but adapting for the second part of the problem took a lot more time.
I originally solved the first part by using a simple matrix of integers and calculating all the possible 3x3 squares in there. This was done with a procedural style (no objects, just functions).
When I got to the second part of the problem, I tried adapting that procedural solution to the new problem, but it required way too much time to find the solution. So I switched to an object-oriented approach with the following classes:
- Cell: containing the power level for a cell and the method to compute it. I realized afterwards that this was not necessary and transformed into a static class with a single computation method.
- CellGrid: containing the position of the top left cell in the grid, the size of the grid and it’s power level. It also contains a method to create a new CellGrid at the same position which has a size of one more than the current CellGrid, this was added to reduce computation time by using the existing computed cell grids to compute the next size of cell grids. There are also methods to easily compare these by power level.
- PowerGrid: containing the complete power grid which the cell grids use to compute their sum. It also has a method to find the most powerful CellGrid of a given size (which is used to solve the first part of the problem).
- SplitPowerGrid: containing all the cell grids computed for a given size. This class also contains a method to compute the next level of cell grids and a method to find the most powerful CellGrid for any size by incrementally increasing it’s size and finding the most powerful CellGrid for the current size until all sizes are checked. This gives the solution to the second part of the problem.
Even with the optimization of calculating the next size of cell grids with current size, the solution takes around 30 seconds to be computed. I’m starting to give myself a 1-minute maximum computing time, so this still fits, but I’m guessing the next problems might become harder to fit into that time frame.
Even though I solved this using C#, and I think I will continue using C# for the remainder of the problems so that all the solutions are together, this problem would have been a lot easier to solve using a language that has better support for matrices like MatLab/Octave or Python.