What is Project Euler?
A website where you are introduced to several mathematical problems which require a coded solution to be solved. Each problem has been produced so that the most efficient solution should take no more than 1 minute to execute which is often challenging to accomplish as I have had solutions which can take hours to return a solution.
In this article we will take a look at Problem 4 on Project Euler and I will talk through my thoughts when tackling this problem as well as show you guys a coded solution on Python 3.5.1. Here is the problem:
When I generally tackle a problem and I am sure when most people tackle problems they go through a process called computational thinking. Computational thinking consists of decomposing a problem and abstracting parts of the problem. Decomposition is where the problem is broken down into several smaller problems making it far easier to solve. And abstraction is where each of these 'sub-problems' are understood by simplifying them and ignoring characteristics which are irrelevant to the problem itself.
My Initial Thoughts
So for this problem I have managed to break it down into:
Finding the products of all pairs of three digit numbers
Figuring out whether each product is a palindrome or not
Finding the largest palindrome
In order to solve the first sub-problem I know that I will need to incorporate a pair of nested for loops to iterate through the range of three digit numbers. This is used to be able to multiply every three digit number by every other three digit number in order to get all the products. But we don't want a list of products so then we need to move onto the second sub-problem and figure out whether the product is a palindrome or not.
And for the second sub-problem we must take each product and compare each individual number from the start and end moving inwards to see if they are each the same until we reach the centre where we will stop. After this process we will be able to create a list of palindromes, or we could assign the palindrome to a variable called maxPalindrome which will hold the current maximum palindrome. During this stage we will need to make use of the fact that the number will be six digits long. We know this because we're multiplying a 3 digit number by another 3 digit number so the answer is either 5 or 6 digits long. And because we're looking for the largest number from the product of two 3 digit numbers we can assume this is likely to be 6 digits long.
Then when all of the products have been iterated through, maxPalindrome will hold the overall maximum palindrome and will be the solution to this problem. So we will then print this value out at the end and it should be our answer. The reason why we didn't choose to use a list and then find the maximum value in the list is because it would take up much more memory to store a whole list of palindromes, especially if we aren't going to be making use of the list any time soon. And generally we want to keep the number of characters and lines used to a minimum which can be done by not using a list.
So now let's begin to program our solution!
1. Now first let's use nested for loops to iterate through all of the three digit numbers and multiply them
2. Now we must convert this number into a string so we can use indexing to see if it's a palindrome or not
3. If it is a palindrome it must be the largest palindrome we have found so far and must therefore be stored under a variable named 'maxPalindrome'
4. Lastly we should print this variable as it will be the max palindrome
Summary of Program
First we have declared a variable maxPalindrome which has been equated to zero, this is because we must declare this variable for use later on otherwise an error will be returned
Next we enter the nested for loops. The first for loop begins from 100 and goes up to 999 inclusive and the same for the second for loop. However, this set of nested for loops essentially means that each number within the range will be multiplied by every number in that same range which is indicated in the next for loop. The task performed is multiplication because this is stated when we assign 'product' to 'i * j'
Next we must convert the product to a string which is essentially a sequence of characters. This enables us to use something called 'indexing' which is a common term within programming and simply allows us to pick on specific characters of the product.
I then go on to say, 'if (productStr[0] == productStr[-1]) and ...', this line of code simply compares the first and last characters and then moves onto compare the second and second from last characters and so on. This is the point where we are checking to see if our number is a palindrome or not.
Finally, if the number is a palindrome and the current value of the maximum palindrome is less than the product that we just calculated, we will store this product as the maxPalindrome. Once the for loops have finished iterating, we can then print out our maxPalindrome which will be the answer to our challenging problem!
Thank you :)akes sense, if there are any questions feel free to ask me and I will try and answer them as soon as possible! And feel free to recommend any interesting topics you want me or any of my colleagues take a look into and we will investigate them right away!
Thank you for reading :)
Comments