Puzzled Over Palindromic Product Problem

Puzzled over palindromic product problem

You are testing 999* (999...100), then 998 * (999...100)

Hence you will be testing 999 * 500 before you test 997 * 996.

So, how you we find that right number?

First note the multiplication is reflective, a * b == b * a, so b need not go from 999...0 every time, just a ...0.

When you find a palindrone, add the two factors together and save the sum (save the two factors also)

Inside the loop, if (a+b) is ever less than the saved sum, abandon the inner loop and move to the next a. When a falls below sum/2, no future value you could find would be higher than the one you've already found, so you're done.

Project Euler #4 with C#

Because once you do find a palindrome you are looping forever inside your while loop. Change the while to and if and it should work.

EDIT:

Yes, you will need to keep track of the largest product found so far, not simply assume the last product found is the largest.

Palindrome product

Try and think about what you are telling your code to do in plain english:

"Until x is a palindrome, do this doubly nested loop to completion"

The until loop is never breaking because it is FULLY running both loops BEFORE checking if x is a palindrome. The solution would be to instead break when you find a palindrome Try this:

999.downto(100) do |i|
  i.downto(100) do |j|
    x = i * j
    break if x == x.to_s.reverse.to_i
    puts "#{i} * #{j} = #{x}"
  end
  break if x == x.to_s.reverse.to_i
end

puts x

Ah but now we have arrived at another problem - looping in this way does not guarantee that the product will be the highest product. We can modify slightly to achieve this:

palindromes = []

999.downto(100) do |i|
  i.downto(100) do |j|
    x = i * j
    palindromes << x if x == x.to_s.reverse.to_i
  end
end

puts palindromes.max

This probably isn't the best solution, but it works.

All possible products

Looking at your code a quick optimization you can make is to use a set rather than an array to store the already computed products.

Since a is an array, a.include?(num) will have to iterate through the entire list of elements before returning true / false.

If a were to be a set, a.include?(num) will return in sub linear time.

Example:

require 'set'
a = Set.new
for x in 100..999
    for y in 100..999
        num = (x * y)
        unless a.include? num
          a.add(num)
        end
    end
end
puts a.to_a.join(", ")

Moreover one of the nice properties of a set is that it only stores unique elements so the following would be equivalent:

require 'set'
a = Set.new
for x in 100..999
    for y in 100..999
        num = (x * y)
        a.add(num)
    end
end
puts a.to_a.join(", ")

Haskell-Project Euler 4

The first big error is that you're calling

reverse (x * y)

Since x * y is a number, and reverse only works on lists, this won't compile. You can convert the number to a String (which is a list) with show:

reverse $ show $ x * y

However, reversing the string is not what you really want to do, you want to filter find all the palindromes, so you need to filter your list of (x * y)s by a predicate. Instead you could write

palindromeList = [z | x <- [1..999], y <- [1..999], let z = x * y, if show z == reverse (show z)]

But since this marches off the side of the screen, I would recommend breaking it up into smaller functions

-- Generates all products
products :: [Integer] -> [Integer] -> [Integer]
products ns ms = [x * y | x <- ns, y <- ms]

-- Checks if a number is a palindrome
isPalindrome :: Integer -> Bool
isPalindrome n = let s = show n in s == reverse s

-- Generates problem-specific palindromes
palindromes :: [Integer]
palindromes = ??? -- Implementation here.  Hint: filter

The next big problem is because you're using the max function, which has the type

max :: Ord a => a -> a -> a

But we really want to find the max of a list, so we turn to maximum, which has the type

maximum :: Ord a => [a] -> a

So you can finalize your program as

projectEuler4 :: Integer
projectEuler4 = maximum palindromes

One final thought: the problem says that you need to find the largest palindrome that is a multiple of 2 three-digit numbers, but your range that you're looking over is [1..999], which includes 1 and 2 digit numbers. What could you do to not check those? Conveniently, it'll make the program faster.

Solving palindromic 'Triangle Quest' puzzle in Python

I ended up doing the following (thanks @raina77ow for the idea):

for i in range(1, N+1):
    print((111111111//(10**(9-i)))**2)

---

Related Topics