In my solution code for project euler problem 11, I got the following functions. Max_consecutive_prod is a class which calculates the max product of consecutive input()ed numbers, generalised from problem 8. The six functions calculate max product in different series of different directions and start from different edges of the grid.
The only difference in these functions is indexes in for statements, how to elimilate the obvious duplication? The situation here is somehow the opposite to the typical application of template method pattern: the operation is identical but the control framework is different, is there another design pattern for this?
Edit: all the modifications specified in comments are to the (two) for statements, and the loop body in each function is identical to the first.
template <size_t size> unsigned process_row(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int i = 0; i < size; ++i)
{
Max_consecutive_prod mcp;
for (int j = 0; j < size; ++j)
{
mcp.input(grid[i][j]);
}
if (mcp.result() > prodMax)
{
prodMax = mcp.result();
}
}
return prodMax;
}
// exchange i, j in process_row
template <size_t size> unsigned process_col(const unsigned (&grid)[size][size])
{
// ...
}
template <size_t size> unsigned process_diag_lower(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int init = 0; init < size; ++init)
{
Max_consecutive_prod mcp;
for (int i = init, j = 0; i < size && j < size; ++i, ++j)
// ...
// ...
}
return prodMax;
}
// exchange i, j in process_diag_lower
template <size_t size> unsigned process_diag_upper(const unsigned (&grid)[size][size])
{
// ...
}
// flip j in process_diag_lower
template <size_t size> unsigned process_rev_diag_lower(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int init = 0; init < size; ++init)
{
Max_consecutive_prod mcp;
for (int i = init, j = size-1; i < size && j >= 0; ++i, --j)
// ...
// ...
}
return prodMax;
}
// change ++j in process_diag_upper to --j
template <size_t size> unsigned process_rev_diag_upper(const unsigned (&grid)[size][size])
{
unsigned prodMax = 0;
for (int init = 0; init < size; ++init)
{
Max_consecutive_prod mcp;
for (int j = init, i = 0; j >=0 && i < size; ++i, --j)
// ...
// ...
}
return prodMax;
}
Based on random-hacker's code, which shows the real commonality and variability in control flows of the six function, I wrote my version and made the code more self-explaining and C++ idiomatic, using a stragegy class, defining local variables to clarify the code and improve effiency. I define a non-template version of process(), to avoid binary code bloat when instantizing for different size (see 'Effective C++', Item 44).
If you still get confused, please read random-hacker's answer for explanation. :)
namespace Grid_search
{
enum Step { neg = -1, nul, pos };
enum Index_t { i, j };
struct Strategy
{
Step direction[2];
Index_t varOuter;
};
const size_t typeCount = 6;
const Strategy strategy[typeCount] = { {{pos, nul}, i}, {{nul, pos}, j}, {{pos, pos}, i}, {{pos, pos}, j}, {{pos, neg}, i}, {{pos, neg}, j} };
};
template <size_t size> inline unsigned process(const Grid_search::Strategy& strategy, const unsigned (&grid)[size][size])
{
return process(strategy, reinterpret_cast<const unsigned*>(&grid), size);
}
unsigned process(const Grid_search::Strategy& strategy, const unsigned* grid, size_t size)
{
using namespace Grid_search;
const Index_t varOuter = strategy.varOuter, varInner = static_cast<Index_t>(!varOuter);
const Step di = strategy.direction[i], dj = strategy.direction[j];
const unsigned initInner = strategy.direction[varInner] == pos ? 0 : size -1;
unsigned prodMax = 0;
unsigned index[2];
unsigned &indexI = index[i], &indexJ = index[j];
for (unsigned initOuter = 0; initOuter < size; ++initOuter)
{
Max_consecutive_prod mcp;
for (index[varOuter] = initOuter, index[varInner] = initInner;
0 <= indexI && indexI < size && 0 <= indexJ && indexJ < size;
indexI += di, indexJ += dj)
{
mcp.input(grid[indexI*size + indexJ]);
if (mcp.result() > prodMax)
{
prodMax = mcp.result();
}
}
}
return prodMax;
}
int main()
{
static const size_t N = 20;
unsigned grid[N][N];
std::ifstream input("d:/pro11.txt");
for (int count = 0; input >> grid[count/N][count%N]; ++count)
{
}
unsigned prodMax = 0;
for (int i = 0; i < Grid_search::typeCount; ++i)
{
unsigned prod = process(Grid_search::strategy[i], grid);
if (prod > prodMax)
{
prodMax = prod;
}
}
}