Euler Golang #4 – Largest Palindrome Product

The Problem

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

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

This problem is easily solvable with brute force; I could just find all of the palindromes that are a product of 3-digit numbers, then find the largest of those. That seems like the easy way out.

Instead, I want to be able to generate the products from largest to smallest. I'll continue to generate the products until I find a palindrome, at which point I'll have the answer and I can stop.

Generating Products

At first glance, it seems like generating the products in order should be easy. As it turns out, this process was the most interesting aspect of this problem. After a lot of thought and admittedly a bit of Googling, I found a solution that would work.

To began, I created a structure that can produce all of the products of a single integer in order. It also stores the next highest possible product.

//productProvider
type productProvider struct {
	multiplier  int
	staticValue int
	nextProduct int
}

//calculate populates the nextProduct field
func (p *productProvider) calculate() {
	p.nextProduct = p.multiplier * p.staticValue
}

//pop gets the next product then recalculates the next largest
func (p *productProvider) pop() int {
	product := p.nextProduct
	p.multiplier--
	p.calculate()

	return product
}

I then created the what is essentially a priority que of these structures, one structure for each 3 digit integer. With this, the process of finding the next product is essitially just poping off the top of the que.

//productQueue stores a sorted slice of productProviders
type productQueue struct {
	productProviders []productProvider
	min, max         int
}

//init sets up the productQueue with a min and max value
func (q *productQueue) init(min, max int) {
	q.productProviders = make([]productProvider, max-min+1)
	q.min = min
	q.max = max

	//this will be sorted
	for index := range q.productProviders {
		q.productProviders[index].multiplier = max
		q.productProviders[index].staticValue = min + index
		q.productProviders[index].calculate()
	}
}

//pop gets the next largest integer
func (q *productQueue) pop() int {
	value := q.productProviders[q.max-q.min].pop()

	//keep the list sorted
	offset := 0
	for q.productProviders[q.max-q.min-offset].nextProduct < q.productProviders[q.max-q.min-offset-1].nextProduct {
		//swap down the list
		temp := q.productProviders[q.max-q.min-offset]
		q.productProviders[q.max-q.min-offset] = q.productProviders[q.max-q.min-offset-1]
		q.productProviders[q.max-q.min-offset-1] = temp
		offset++
	}

	return value
}

Palindrome Test

The last of the problem involves checking if integers are palindromes. I went the kind of easy way out and did the test based on a string. This could be done with the integer itself.

func isPalindrome(str string) bool {
	length := len(str)

	for i := 0; length-(2*i) >= 1; i++ {
		if str[i] != str[length-i-1] {
			return false
		}
	}

	return true
}

Putting it All Together

With those components in place, I just needed a loop that checks the next product until it finds a palindrome.

func main() {
	pq := new(productQueue)
	pq.init(100, 999)
	for {
		value := strconv.Itoa(pq.pop())
		if isPalindrome(value) {
			fmt.Println(value)
			break
		}
	}
}

Whole Source

package main

import (
	"fmt"
	"strconv"
	"time"
)

func main() {
	start := time.Now()

	pq := new(productQueue)
	pq.init(100, 999)
	for {
		value := strconv.Itoa(pq.pop())
		if isPalindrome(value) {
			fmt.Println(value)
			break
		}
	}

	elapsed := time.Since(start)
	fmt.Printf("elapsed: %s \n", elapsed)
}

//productProvider
type productProvider struct {
	multiplier  int
	staticValue int
	nextProduct int
}

//calculate populates the nextProduct field
func (p *productProvider) calculate() {
	p.nextProduct = p.multiplier * p.staticValue
}

//pop gets the next product then recalculates nextProduct
func (p *productProvider) pop() int {
	product := p.nextProduct
	p.multiplier--
	p.calculate()

	return product
}

//productQueue stores a sorted slice of productProviders
type productQueue struct {
	productProviders []productProvider
	min, max         int
}

//init sets up the productQueue with a min and max value
func (q *productQueue) init(min, max int) {
	q.productProviders = make([]productProvider, max-min+1)
	q.min = min
	q.max = max

	//this will be sorted
	for index := range q.productProviders {
		q.productProviders[index].multiplier = max
		q.productProviders[index].staticValue = min + index
		q.productProviders[index].calculate()
	}
}

//pop gets the next largest integer
func (q *productQueue) pop() int {
	value := q.productProviders[q.max-q.min].pop()

	//keep the list sorted
	offset := 0
	for q.productProviders[q.max-q.min-offset].nextProduct < q.productProviders[q.max-q.min-offset-1].nextProduct {
		//swap down the list
		temp := q.productProviders[q.max-q.min-offset]
		q.productProviders[q.max-q.min-offset] = q.productProviders[q.max-q.min-offset-1]
		q.productProviders[q.max-q.min-offset-1] = temp
		offset++
	}

	return value
}

func isPalindrome(str string) bool {
	length := len(str)

	for i := 0; length-(2*i) >= 1; i++ {
		if str[i] != str[length-i-1] {
			return false
		}
	}

	return true
}