Problem 4

Problem

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

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

Julia

function is_palindrome(s::AbstractString)
    l = length(s)

    for i ∈ 1:fld(l, 2)
        s[i] != s[l + 1 - i] && return false        
    end

    return true
end;

is_palindrome(n::Integer) = is_palindrome(string(n));

function p4()
  a, b, largest_palindrome = 0, 0, 0
  
  for x ∈ reverse(100:999)
      for y ∈ reverse(100:999)
          x < y && continue
          p = x * y
          p < largest_palindrome && break # we can break the inner loop, because the next product is going to be even lesser
          if is_palindrome(p)
            a, b, largest_palindrome = x, y, p 
          end
      end
  end

  # if no palindrome was found:
  return (a, b, a*b)
end;

p4()

(993, 913, 906609)

using BenchmarkTools;
@benchmark p4()

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  349.601 μs …   5.049 ms  ┊ GC (min … max): 0.00% … 84.77%
 Time  (median):     386.531 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   458.974 μs ± 279.958 μs  ┊ GC (mean ± σ):  5.65% ±  8.92%
  █▇▅▅▅▂▁▁        ▂▂▂▁                                          ▂
  ████████████▇▇▇█████▇▄▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▅▅▄▅ █
  350 μs        Histogram: log(frequency) by time       2.34 ms <
 Memory estimate: 526.28 KiB, allocs estimate: 12248.