Exercism v3 launches on Sept 1st 2021. Learn more! ๐๐๐

Published at Mar 31 2020
·
0 comments

Instructions

Test suite

Solution

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.

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)`

.

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)`

.

A goal of this exercise is teaching you about efficiency. There are many ways to create a solution that produces correct results, but some solutions are more efficient and thereby finish faster than others.

On the `Erlang`

track, some of your tests may even time out if your solution is
not efficient enough.

Here are some general points to consider when it comes to optimize your algorithms:

- Some operations are cheap, others are expensive. Try to figure out which are which, then try to find a way to perform expensive operations rarely, by executing them only if needed, eg when a cheap operation alone is not enough.
- Skip out early. Often it is clear that, beyond a certain point, no better solution can be found, so it makes no sense to search further.
- More generally, reduce the overall steps or iterations your algorithm has to perform.
- When generating results, it may be better to allow duplicates and weed them out before returning the final result, instead of ensuring that duplicates never get created in the first place along the way.

Those are only some general rules of thumb, things you might want to keep an eye out for. They are not universally applicable to any problem, and often they come with trade-offs.

In order to run the tests, issue the following command from the exercise directory:

For running the tests provided, `rebar3`

is used as it is the official build and
dependency management tool for erlang now. Please refer to the tracks installation
instructions on how to do that.

In order to run the tests, you can issue the following command from the exercise directory.

```
$ rebar3 eunit
```

For detailed information about the Erlang track, please refer to the help page on the Exercism site. This covers the basic information on setting up the development environment expected by the exercises.

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

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

```
%% Based on canonical data version 1.1.0
%% https://github.com/exercism/problem-specifications/raw/master/exercises/palindrome-products/canonical-data.json
%% This file is automatically generated from the exercises canonical data.
-module(palindrome_products_tests).
-include_lib("erl_exercism/include/exercism.hrl").
-include_lib("eunit/include/eunit.hrl").
normalize({V, F}) ->
{
V,
lists:sort(
lists:map(
fun
({A, B}) when A>B -> {B, A};
(AB) -> AB
end,
F
)
)
}.
'1_finds_the_smallest_palindrome_from_single_digit_factors_test'() ->
?assertEqual(normalize({1, [{1, 1}]}),
normalize(palindrome_products:smallest(1, 9))).
'2_finds_the_largest_palindrome_from_single_digit_factors_test'() ->
?assertEqual(normalize({9, [{1, 9}, {3, 3}]}),
normalize(palindrome_products:largest(1, 9))).
'3_find_the_smallest_palindrome_from_double_digit_factors_test'() ->
?assertEqual(normalize({121, [{11, 11}]}),
normalize(palindrome_products:smallest(10, 99))).
'4_find_the_largest_palindrome_from_double_digit_factors_test'() ->
?assertEqual(normalize({9009, [{91, 99}]}),
normalize(palindrome_products:largest(10, 99))).
'5_find_smallest_palindrome_from_triple_digit_factors_test'() ->
?assertEqual(normalize({10201, [{101, 101}]}),
normalize(palindrome_products:smallest(100, 999))).
'6_find_the_largest_palindrome_from_triple_digit_factors_test'() ->
?assertEqual(normalize({906609, [{913, 993}]}),
normalize(palindrome_products:largest(100, 999))).
'7_find_smallest_palindrome_from_four_digit_factors_test'() ->
?assertEqual(normalize({1002001, [{1001, 1001}]}),
normalize(palindrome_products:smallest(1000, 9999))).
'8_find_the_largest_palindrome_from_four_digit_factors_test'() ->
?assertEqual(normalize({99000099, [{9901, 9999}]}),
normalize(palindrome_products:largest(1000, 9999))).
'9_empty_result_for_smallest_if_no_palindrome_in_the_range_test'() ->
?assertEqual(undefined,
palindrome_products:smallest(1002, 1003)).
'10_empty_result_for_largest_if_no_palindrome_in_the_range_test'() ->
?assertEqual(undefined,
palindrome_products:largest(15, 15)).
'11_error_result_for_smallest_if_min_is_more_than_max_test'() ->
?assertError(_, palindrome_products:smallest(10000, 1)).
'12_error_result_for_largest_if_min_is_more_than_max_test'() ->
?assertError(_, palindrome_products:largest(2, 1)).
```

```
-module(palindrome_products).
-export([largest/2, smallest/2]).
largest(Min, Max) when Min > Max -> error(badarg);
largest(Min, Max) -> products(Min, Max, true).
smallest(Min, Max) when Min > Max -> error(badarg);
smallest(Min, Max) -> products(Min, Max, false).
products(Start, End, Largest) ->
%products(Start, Start, Start, Start + ((End - Start) div 2), End + 1, Largest, []).
products(Start, Start, Start, End + 1, End + 1, Largest, []).
products(LeftEnd, _, _, LeftEnd, _, _, Product) -> remove_duplicates(Product);
products(Left, RightEnd, Start, LeftEnd, RightEnd, Largest, Product) ->
products(Left + 1, Start, Start, LeftEnd, RightEnd, Largest, Product);
products(Left, Right, Start, LeftEnd, RightEnd, Largest, []) ->
Product = Left * Right,
NewProduct = case is_palindrome(Product) of
true -> {Product, [{min(Left, Right), max(Left, Right)}]};
_ -> []
end,
products(Left, Right + 1, Start, LeftEnd, RightEnd, Largest, NewProduct);
products(Left, Right, Start, LeftEnd, RightEnd, Largest, {Product, Factors}) ->
NewProduct = case Left * Right of
Product -> {Product, [{min(Left, Right), max(Left, Right)} | Factors]};
Number when (Largest and (Product < Number)) or ((not Largest) and (Product > Number)) ->
case is_palindrome(Number) of
true -> {Number, [{min(Left, Right), max(Left, Right)}]};
_ -> {Product, Factors}
end;
_ -> {Product, Factors}
end,
products(Left, Right + 1, Start, LeftEnd, RightEnd, Largest, NewProduct).
is_palindrome(Number) ->
String = integer_to_list(Number),
String =:= lists:reverse(String).
remove_duplicates([]) -> undefined;
remove_duplicates({Product, Factors}) ->
[H | SortedFactors] = lists:sort(Factors),
remove_duplicates({Product, [H]}, SortedFactors).
remove_duplicates(Product, []) -> Product;
remove_duplicates({Product, [H | Filtered]}, [H | Factors]) -> remove_duplicates({Product, [H | Filtered]}, Factors);
remove_duplicates({Product, Filtered}, [H | Factors]) -> remove_duplicates({Product, [H | Filtered]}, Factors).
```

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?

Level up your programming skills with 3,450 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments