trjhtr

I've recently solved Project Euler's 15th problem stating:

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

This is my dynamic approach in C++

#include <cstdio>

const unsigned short n = 20;

int main() 
 unsigned long long p[n][n];
 for (unsigned short i = 2; i <= n; i++)
 p[n - i][n - 1] = i + 1;
 for (unsigned short i = n - 2; i >= 1; i--) 
 p[i][i] = 2 * p[i][i + 1];
 for (unsigned short k = i; k >= 1; k--)
 p[k - 1][i] = p[k][i] + p[k - 1][i + 1];
 
 printf("%llu", 2 * p[0][1]);

I am aware that this problem could be solved way more efficiently and faster by simply calculating $(2n)!/(n!)^2$, however I decided to look at this problem from a programmer's point of view, rather than a mathematician's.

Why are you using unsigned short?

I presume the answer is somewhere along the lines of worrying about memory usage. There isn't a problem with that, but given that p will consume almost all of the memory used by this routine, it would be more productive checking whether you need the whole grid or can get away with just a few rows at once.

Consider using constexpr rather than const when defining n. That is slightly more explicit that the value is known at compile time and is therefore legal for use in setting array sizes.

It is generally considered a better habit to use ++i rather than i++ if you're going to discard the result. This has no practical difference with the primitive integral types you're using, but for more complex objects can be more efficient.

It is generally considered safer to always include the braces after flow control statements like for and if.

Finally, a quick note about your closing sentence. I appreciate the desire to explore other ways of doing things, but doing calculations that bypass a whole load of loops is often the mark of a very good programmer! (For that matter, it doesn't necessarily make for easy programming either: 40! wouldn't fit in your variable types so implementing something that handled that case would be a worthwhile challenge on its own.)

#include <cstdio>

If your goal is to write C++, you're really off to a bad start using the C standard I/O library.

const unsigned short n = 20;

The modern way to do compile time constants is with constexpr.

But I don't understand why you chose to use unsigned short for all your indexing calculations. Any operations you try to do on it will automatically promote it to unsigned int. You're not really gaining anything.

for (unsigned short i = 2; i <= n; i++)

Once again, once you've bought into unsigned short, you keep using it everywhere. But aside from the assignment, every single operation in this statement is promoting all your unsigned shorts to unsigned ints. Even the comparison. You might as well have just used unsigned from the start to save yourself a lot of typing:

constexpr auto n = 20u; // unsigned int

for (auto i = 2u; i <= n; ++i)

And so on.

If you want to be technically correct, indexes should be std::size_t. But unsigned works well enough if you know you're not going any higher than 20. unsigned short is useless except for storage, because any operations you do on it get promoted.

printf("%llu", 2 * p[0][1]);

First, you're missing the std:: here.

But more importantly, you should be using C++ I/O:

std::cout << (2 * p[0][1]);

Other than that, the most important element you're missing here would be comments, I'd say.

Package your code into meaningful operations as carefully named functions.

There will be a day that you or someone else is going to maintain some code, they'll open the file, and they'll see something like your code. You can't unit-test main(). Whatever you have main() doing should be kept simple. Delegate to other functions and objects you can unit-test.

Names are important and you should call things what they are. Select names that provide context, denote relationships, and/or promotes understanding. What is p?

Always initialize variables. When you declare p, the values within ps extents are all indeterminate values until they are set.

Use int when you need an integer type. Use std::size_t/ptrdiff_t for sizes and indices. If you need an integer type of fixed-size, use the appropriate type from <cstdint>. In every expression evaluated in the context of operator, the result of the expression is converted to std::size_t for C-Arrays and the C++ containers.

template <std::size_t length, std::size_t width>
std::uint64_t matrix_count_routes() 
 std::uint64_t path_counts[length][width] = ;
 // your code here


void euler_15() 
 constexpr int matrix_width = 20;
 std::cout << matrix_count_routes<matrix_width, matrix_width>() << 'n';


int main() 
 euler_15();

I am aware that this problem could be solved way more efficiently and faster by simply calculating $frac(2n)!(n!)^2$, however I decided to look at this problem from a programmer's point of view, rather than a mathematician's.

The programmer would implement both and measure.

Here are some things that may help you improve your code.

Prefer iostreams to printf

The printf function needs to evaluate the format string at runtime and then apply the result, while something like std::cout << n; already knows at compile time what kind of thing that n is. The result is that the C++ version can be faster. It's a common misconception that C++ iostream operations are slower than printf (measuring is the way to go!) but in this case, it's only used once, so it probably doesn't matter.

Prefer constexpr to const

In modern C++, constexpr implies that the value can be derived at compile time, so anything that can be constexpr reduces to essentially zero runtime overhead. That's a huge "win" for performance, so it should be something you strive for.

Understand integer promotion rules

The effect of declaring short everywhere its used in this program is ... absolutely nothing! The reason is that there are integral numeric promotions being applied to promote from a short to an int.

Use objects

Since you're writing in C++, let's use objects! In this case, we might wrap everything up into a Grid object and have a const function that returns the answer. My rewrite on a 64-bit Linux machine has this for main:

int main() 
 Grid<22> g;
 std::cout << g.answer(20) << 'n';

Reduce memory use by choosing a better data structure

If we think about the algorithm carefully, it's possible to do everything in a single array of length n rather than using an n x n grid. Here's one way to do it in the constructor of the Grid class:

Grid() 
 for (unsigned i = 0; i < n; ++i) 
 p[i] = i + 2;
 
 for (unsigned i = 1; i < n; ++i) 
 p[i] *= 2;
 for (unsigned j = i+1; j < n; ++j) 
 p[j] += p[j-1];
 
 

This is essentially the same algorithm, but reduced to a single in-place array. More on that in the next suggestion.

Prefer std::array to plain C-style arrays

The std::array is just as efficient as a plain C-style array, but has the considerable advantage that it can be used with all of the standard library algorithms. In this case, it seems prudent to make a templated class, so the first few lines of the Grid class are these:

template <unsigned n>
class Grid 
 std::array<unsigned long long,n> p;
 // rest of the class
;

Carefully consider usage

Note that as the array is constructed, each successive entry in the final version of the array is the answer for that size grid. So we can use that by writing the answer function like so:

unsigned long long answer(int i) const return p.at(i-1); 

The at function will throw an exception if the index is out of bounds, so that that's one less consideration that we need to write code to handle (except perhaps at the caller's end).

Further optimizations

With this same basic algorithm, we can move almost all of the calculation to compile-time. The way we can do that is to use constexpr and recursive templates to calculate values for all sizes at compile time and then the entire program reduces, effectively, to a runtime lookup in a static table. I'll leave this final optimization step to you, but this compile-time sieve of Eratosthenes might inspire you and give you ideas on how to do that.