Avatar of blu-sta

blu-sta's solution

to Palindrome Products in the C# Track

Published at Sep 21 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution was written.

Detect palindrome products in a given range.

A palindromic number is a number that remains the same when its digits are reversed. For example, 121 is a palindromic number but 112 is not.

Given a range of numbers, find the largest and smallest palindromes which are products of numbers within that range.

Your solution should return the largest and smallest palindromes, along with the factors of each within the range. If the largest or smallest palindrome has more than one pair of factors within the range, then return all the pairs.

Example 1

Given the range [1, 9] (both inclusive)...

And given the list of all possible products within this range: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 15, 21, 24, 27, 20, 28, 32, 36, 25, 30, 35, 40, 45, 42, 48, 54, 49, 56, 63, 64, 72, 81]

The palindrome products are all single digit numbers (in this case): [1, 2, 3, 4, 5, 6, 7, 8, 9]

The smallest palindrome product is 1. Its factors are (1, 1). The largest palindrome product is 9. Its factors are (1, 9) and (3, 3).

Example 2

Given the range [10, 99] (both inclusive)...

The smallest palindrome product is 121. Its factors are (11, 11). The largest palindrome product is 9009. Its factors are (91, 99).

Hints

For this exercise, you will need to create a set of factors using tuples. For more information on tuples, see this link.

Source

Problem 4 at Project Euler http://projecteuler.net/problem=4

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

PalindromeProductsTest.cs

// This file was auto-generated based on version 1.1.0 of the canonical data.

using System;
using Xunit;

public class PalindromeProductsTest
{
    [Fact]
    public void Finds_the_smallest_palindrome_from_single_digit_factors()
    {
        var actual = PalindromeProducts.Smallest(1, 9);
        var expected = (1, new[] { (1, 1) });
        Assert.Equal(expected.Item1, actual.Item1);
        Assert.Equal(expected.Item2, actual.Item2);
    }

    [Fact(Skip = "Remove to run test")]
    public void Finds_the_largest_palindrome_from_single_digit_factors()
    {
        var actual = PalindromeProducts.Largest(1, 9);
        var expected = (9, new[] { (1, 9), (3, 3) });
        Assert.Equal(expected.Item1, actual.Item1);
        Assert.Equal(expected.Item2, actual.Item2);
    }

    [Fact(Skip = "Remove to run test")]
    public void Find_the_smallest_palindrome_from_double_digit_factors()
    {
        var actual = PalindromeProducts.Smallest(10, 99);
        var expected = (121, new[] { (11, 11) });
        Assert.Equal(expected.Item1, actual.Item1);
        Assert.Equal(expected.Item2, actual.Item2);
    }

    [Fact(Skip = "Remove to run test")]
    public void Find_the_largest_palindrome_from_double_digit_factors()
    {
        var actual = PalindromeProducts.Largest(10, 99);
        var expected = (9009, new[] { (91, 99) });
        Assert.Equal(expected.Item1, actual.Item1);
        Assert.Equal(expected.Item2, actual.Item2);
    }

    [Fact(Skip = "Remove to run test")]
    public void Find_smallest_palindrome_from_triple_digit_factors()
    {
        var actual = PalindromeProducts.Smallest(100, 999);
        var expected = (10201, new[] { (101, 101) });
        Assert.Equal(expected.Item1, actual.Item1);
        Assert.Equal(expected.Item2, actual.Item2);
    }

    [Fact(Skip = "Remove to run test")]
    public void Find_the_largest_palindrome_from_triple_digit_factors()
    {
        var actual = PalindromeProducts.Largest(100, 999);
        var expected = (906609, new[] { (913, 993) });
        Assert.Equal(expected.Item1, actual.Item1);
        Assert.Equal(expected.Item2, actual.Item2);
    }

    [Fact(Skip = "Remove to run test")]
    public void Find_smallest_palindrome_from_four_digit_factors()
    {
        var actual = PalindromeProducts.Smallest(1000, 9999);
        var expected = (1002001, new[] { (1001, 1001) });
        Assert.Equal(expected.Item1, actual.Item1);
        Assert.Equal(expected.Item2, actual.Item2);
    }

    [Fact(Skip = "Remove to run test")]
    public void Find_the_largest_palindrome_from_four_digit_factors()
    {
        var actual = PalindromeProducts.Largest(1000, 9999);
        var expected = (99000099, new[] { (9901, 9999) });
        Assert.Equal(expected.Item1, actual.Item1);
        Assert.Equal(expected.Item2, actual.Item2);
    }

    [Fact(Skip = "Remove to run test")]
    public void Empty_result_for_smallest_if_no_palindrome_in_the_range()
    {
        Assert.Throws<ArgumentException>(() => PalindromeProducts.Smallest(1002, 1003));
    }

    [Fact(Skip = "Remove to run test")]
    public void Empty_result_for_largest_if_no_palindrome_in_the_range()
    {
        Assert.Throws<ArgumentException>(() => PalindromeProducts.Largest(15, 15));
    }

    [Fact(Skip = "Remove to run test")]
    public void Error_result_for_smallest_if_min_is_more_than_max()
    {
        Assert.Throws<ArgumentException>(() => PalindromeProducts.Smallest(10000, 1));
    }

    [Fact(Skip = "Remove to run test")]
    public void Error_result_for_largest_if_min_is_more_than_max()
    {
        Assert.Throws<ArgumentException>(() => PalindromeProducts.Largest(2, 1));
    }
}
using System;
using System.Collections.Generic;
using System.Linq;

public static class PalindromeProducts
{
    private enum Mode
    {
        Smallest,
        Largest
    }

    public static (int, IEnumerable<(int,int)>) Largest(int minFactor, int maxFactor) => 
        FindPalindromeInRange(minFactor, maxFactor, Mode.Largest);

    public static (int, IEnumerable<(int, int)>) Smallest(int minFactor, int maxFactor) =>
        FindPalindromeInRange(minFactor, maxFactor, Mode.Smallest);

    private static (int, IEnumerable<(int, int)>) FindPalindromeInRange(int minFactor, int maxFactor, Mode mode) => 
        FindPalindromeInRange(GetNumberRange(minFactor, maxFactor), mode);

    private static int[] GetNumberRange(int minFactor, int maxFactor) =>
        maxFactor > minFactor
            ? Enumerable.Range(minFactor, maxFactor - minFactor + 1).ToArray()
            : throw new ArgumentException();

    private static (int, IEnumerable<(int, int)>) FindPalindromeInRange(IReadOnlyList<int> numbers, Mode mode)
    {
        var palindrome = FindPalindromeFromProducts(numbers, mode);

        var factors = FindFactorsInRange(palindrome, numbers);

        return (palindrome, factors);
    }

    private static int FindPalindromeFromProducts(IEnumerable<int> numbers, Mode mode)
    {
        int palindromeLimit;
        int[] orderedNumbers;
        if (mode == Mode.Largest)
        {
            palindromeLimit = 0;
            orderedNumbers = numbers.Reverse().ToArray();
        }
        else
        {
            palindromeLimit = int.MaxValue;
            orderedNumbers = numbers.ToArray();
        }

        foreach (var i in orderedNumbers)
        {
            foreach (var j in orderedNumbers)
            {
                var product = i * j;

                if (mode == Mode.Largest && product < palindromeLimit ||
                    mode == Mode.Smallest && product > palindromeLimit)
                    break;

                var numberAsString = product.ToString();
                var reversedNumberString = new string(numberAsString.Reverse().ToArray());

                if (numberAsString != reversedNumberString)
                    continue;

                palindromeLimit = product;
                break;
            }
        }

        if (palindromeLimit == 0 ||
            palindromeLimit == int.MaxValue)
            throw new ArgumentException();

        return palindromeLimit;
    }

    private static IEnumerable<(int, int)> FindFactorsInRange(int palindrome, IReadOnlyList<int> numbers)
    {
        var palindromeRoot = Math.Sqrt(palindrome);
        for (var i = 0; numbers[i] <= palindromeRoot && i < numbers.Count; i++)
        {
            var factor1 = numbers[i];
            if (palindrome % factor1 != 0)
                continue;

            var factor2 = palindrome / factor1;
            if (numbers.Contains(factor2))
            {
                yield return (factor1, factor2);
            }
        }
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?