Welcome to another edition of Jared rediscovers grade school math! Today we are tackling problem 4 of Project Euler. We are going to talk about Palindromes and for loops. Let's get into it!

Problem Discussion

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Video Version

If you like to watch rather than read, check out the video that accompanies this article. If not, keep reading!

Statement

Find the largest palindrome made from the product of two 3-digit numbers.

Palindrome

A word that reads the same forwards as backwards. Example is 9009 or racecar.

Solution

The approach I'm taking is both brute force and algorithmic.

Steps

1. Determine the highest products to work from, e.g. 99 x 99
2. Multiply the highest products together
3. Reduce right number by one
   1. Check if palindrome
   2. Repeat until reaching 1
4. Reduce left number by one.
   1. Check if palindrome
   2. Repeat step 3
5. If at any time, number is palindrome, return that number.

Solution

For this solution, I am going to reach for my old friend: functional programming. First let's create a function that checks if a string is a palindrome.

Palindrome?

Our friend Javascript has a ton of helper functions in dealing with strings. Unfortunately, this means that we have to convert our number to a string, then reconvert it back after we've checked it. It takes some extra time, but it's not to computationaly expensive.

    function isPalindrome(num) {
      // get reverse
      let reversed = String(num)
        .split('')
        .reverse()
        .join('');
      // return equality check
      return Number(reversed) === num;
    }

Tale of Two Loops

In order to check all numbers, we have to check all products from 99 x 99 → 1 x 1. To accomplish this, we're going to loop the right number inside of the left number, i.e. 99 x 99 → 99 x 98...and so forth.

    function largestPalindromeProduct(n) {
      let highest = 0;
      // Find largest number
      let largestNum = '9';
      largestNum += Number(largestNum.repeat(n - 1));
      largestNum = Number(largestNum);

        // loop left number
      for (let i = largestNum; i > 0; i--) {
            // loop right number
        for (let j = largestNum; j > 0; j--) {
          let product = i * j;
                // check if palindrome
          if (isPalindrome(product)) {
            if (product > highest) highest = product;
            // we have the highest palindrome for this set, skip to next loop
            break;
          }
        }
      }
        // return the highest palindrome we found
      return highest;
    }

Full Solution

    function isPalindrome(num) {
      // get reverse
      let reversed = String(num)
        .split('')
        .reverse()
        .join('');
      // return equality check
      return Number(reversed) === num;
    }

    function largestPalindromeProduct(n) {
      let highest = 0;
      // Find largest number
      let largestNum = '9';
      largestNum += Number(largestNum.repeat(n - 1));
      largestNum = Number(largestNum);

        // loop left number
      for (let i = largestNum; i > 0; i--) {
            // loop right number
        for (let j = largestNum; j > 0; j--) {
          let product = i * j;
                // check if palindrome
          if (isPalindrome(product)) {
            if (product > highest) highest = product;
            // we have the highest palindrome for this set, skip to next loop
            break;
          }
        }
      }
        // return the highest palindrome we found
      return highest;
    }

Final Thoughts

This approach includes both a minor algorithm, in that it skips over any numbers below a certain threshold and brute force. It will check all the highest palindromes from 99 x 99 to 1 x 1.

There is definitely room for improvement here. In fact I found a couple out there that are better than mine, but this works for now.

If you have any suggestions or adjustments you think would make it better, feel free to leave a comment!

As always, happy coding.

Resources

https://www.xarg.org/puzzle/project-euler/problem-4/

https://github.com/Matt-1123/project-euler/blob/master/solutions.js