Project Euler Solutions
Here you can see a few examples of my solutions to the problems listed over at ProjectEuler.net
These solutions are coded in C++. You can find more of my code over on my github page
These solutions are coded in C++. You can find more of my code over on my github page
The above code finds the largest palindrome product of two 3-digit numbers. It does so by looping through all numbers from 100-999 (all 3-digit numbers), checks if the product is the largest we've found so far, and if so, checks to see if it is a palindrome.
In order to check if a number is a palindrome, it reverses is by isolating the last digit and adding it to the reverse. Each time it isolates a new digit it moves all previously added digits over one, and adds the new digit. If the reverse and the original number are the same, it is a palindrome and we remember this result.
In order to check if a number is a palindrome, it reverses is by isolating the last digit and adding it to the reverse. Each time it isolates a new digit it moves all previously added digits over one, and adds the new digit. If the reverse and the original number are the same, it is a palindrome and we remember this result.
The above code finds the pythagorean triplet for which A+B+C = 1000. Once found, it will output the product of this triplet.
When looking for this triplet, there are a few given rules. First of all, A<B<C, so we can limit the values of A, B and C accordingly.
Second, A + B + C = 1000, so the value of C is determined by the values of A and B.
Once we have our limits, we loop through the remaining possibilities and see if they form a pythagorean triplet. If so, we've found our target and output A, B and C as well as the product.
When looking for this triplet, there are a few given rules. First of all, A<B<C, so we can limit the values of A, B and C accordingly.
Second, A + B + C = 1000, so the value of C is determined by the values of A and B.
Once we have our limits, we loop through the remaining possibilities and see if they form a pythagorean triplet. If so, we've found our target and output A, B and C as well as the product.
This code finds the number of paths through a square grid, while only being allowed to move right or down.
In order to find this number of paths for our target grid size, we recursively call the Lattice function. This function can return 3 things:
It can return 1, if we have have been given a grid with only 1 path. This is the deepest recursion we can encounter.
It can return a stored result, if it is a grid of dimensions we've aready calculated the amount of paths for.
Or it can return the combined values of a recursive call with parameters of this grid with reduced width, and this grid with reduced height. It will then store the result for future use and return the new value.
After recursion runs its course, we will be returned the total amount of paths through the grid.
In order to find this number of paths for our target grid size, we recursively call the Lattice function. This function can return 3 things:
It can return 1, if we have have been given a grid with only 1 path. This is the deepest recursion we can encounter.
It can return a stored result, if it is a grid of dimensions we've aready calculated the amount of paths for.
Or it can return the combined values of a recursive call with parameters of this grid with reduced width, and this grid with reduced height. It will then store the result for future use and return the new value.
After recursion runs its course, we will be returned the total amount of paths through the grid.
A little different, this code finds the total amount of letters used to write out the numbers 1-1000 as words in the english language.
In order to find this we first have to store some data, namely the amount of letters in each unique number we can encounter up to 1000. The unique numbers are all numbers from one to twenty, as well as the multiples of ten, the combiner word "and" as used in "One hundred and twenty", the word "hundred" and the word "thousand".
Then we need to check every number from 1 to our target, in this case 1000.
If our number has a 1000 in it, we add the number of letters in "thousand" to our total, in addition to the number of letters in the thousand-count (e.g. "two thousand"). The same goes true for hundred, where we also check if we need to add the combiner word "and". We then check if our remainder is larger than 20, since the numbers 20 and below are unique numbers. If not, we add the the number of letters in the remaining two digits, otherwise we add the number of letters in the unique number (e.g. fourteen).
In order to find this we first have to store some data, namely the amount of letters in each unique number we can encounter up to 1000. The unique numbers are all numbers from one to twenty, as well as the multiples of ten, the combiner word "and" as used in "One hundred and twenty", the word "hundred" and the word "thousand".
Then we need to check every number from 1 to our target, in this case 1000.
If our number has a 1000 in it, we add the number of letters in "thousand" to our total, in addition to the number of letters in the thousand-count (e.g. "two thousand"). The same goes true for hundred, where we also check if we need to add the combiner word "and". We then check if our remainder is larger than 20, since the numbers 20 and below are unique numbers. If not, we add the the number of letters in the remaining two digits, otherwise we add the number of letters in the unique number (e.g. fourteen).
Here we try to find the path with the highest resulting sum when moving through a triangle. We represent the triangle in array form, with zero being entered in the "empty" elements.
In order to find the best path, we collapse upwards layer by layer, each time picking the best of two numbers to occupy the number above. For instance, the 3 numbers in the bottom left are 63, 4 and 62. When collapsing upward, we add 62 to 63 and have the resulting number (125) take the place of the original 63. We do this for every number on that layer, then move on to collapse the next layer upward.
In the end this leaves us with the largest possible sum in our highest array element, triangle[0][0].
In order to find the best path, we collapse upwards layer by layer, each time picking the best of two numbers to occupy the number above. For instance, the 3 numbers in the bottom left are 63, 4 and 62. When collapsing upward, we add 62 to 63 and have the resulting number (125) take the place of the original 63. We do this for every number on that layer, then move on to collapse the next layer upward.
In the end this leaves us with the largest possible sum in our highest array element, triangle[0][0].