ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

Published at Jul 06 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, get_max_pal/2, get_pal_min_max/2,
get_min_pal/2, get_minpal_min_max/2]).
largest(Min, Max) when Max < Min ->
erlang:error("Max must large then Min");
largest(Min, Max) ->
get_max_pal(Min, Max).
smallest(Min, Max) when Max < Min ->
erlang:error("Max must large then Min");
smallest(Min, Max) ->
get_min_pal(Min, Max).
%%
%% use digit method to check number is palindrome
%% it will better then convert it to string list and check
check_pal(N) ->
L = check_pal(N, []),
L =:= lists:reverse(L).
check_pal(N, R) when (N div 10 =:= 0) andalso (N rem 10 =:= 0) ->
R;
check_pal(N, R) ->
NewR = [N rem 10 | R],
check_pal(N div 10, NewR).
%%
get_min_pal(Min, Max) ->
MaxValue = Max * Max + 1,
case get_min_pal(Min, Min, Max, {MaxValue, []}) of
{MaxValue, []} ->
undefined;
Best -> Best
end.
get_min_pal(_Min, Cur, Max, Best) when Cur =:= Max + 1 ->
Best;
get_min_pal(_Min, Cur, _Max, {Value, _L} = Best ) when Cur * Cur > Value ->
Best;
get_min_pal(Min, Cur, Max, {Value, Products} = Best) ->
case get_minpal_min_max(Cur, Max) of
{0, {0,0}} ->
get_min_pal(Min, Cur + 1, Max, Best);
{Product, {_, _}} when Product > Value->
get_min_pal(Min, Cur + 1, Max, Best);
{Product, {A, B}} when Product =:= Value ->
get_min_pal(Min, Cur + 1, Max, {Value, [{A, B} | Products]});
{Product, {A, B}} when Product < Value ->
get_min_pal(Min, Cur + 1, Max, {Product, [{A,B}]})
end.
get_minpal_min_max(Min, Max) ->
get_minpal_min_max(Min, Min, Max).
get_minpal_min_max(_Min, Cur, Max) when Cur =:= Max + 1 ->
{0, {0,0}};
get_minpal_min_max(Min, Cur, Max) ->
case check_pal(Min * Cur) of
true ->
{Min * Cur, {Min, Cur}};
_ ->
get_minpal_min_max(Min, Cur + 1, Max)
end.
%% get the first large product pair
%% and from the is pair, to find the largest pair
get_max_pal(Min, Max) ->
case get_max_pal(Min, Max, {0, []}) of
{0, []} ->
undefined;
Best -> Best
end.
get_max_pal(Min, Cur, Best) when Min =:= Cur + 1 ->
Best;
get_max_pal(_Min, Cur, {Value, _L} = Best ) when Cur * Cur < Value ->
Best;
get_max_pal(Min, Cur, {Value, Products} = Best) ->
case get_pal_min_max(Min, Cur) of
%% can not find palindrome product
{0, {0,0}} ->
get_max_pal(Min, Cur - 1, Best);
{Product, {_A, _B}} when Product < Value ->
get_max_pal(Min, Cur - 1, Best);
{Product, {A, B}} when Product =:= Value ->
get_max_pal(Min, Cur - 1, {Value, [{A, B} | Products]});
{Product, {A, B}} when Product > Value ->
get_max_pal(Min, Cur - 1, {Product, [{A, B}]})
end.
get_pal_min_max(Min, Max) ->
get_pal_min_max(Min, Max, Max).
get_pal_min_max(Min, Cur, _Max) when Min =:= Cur + 1 ->
{0, {0,0}};
get_pal_min_max(Min, Cur, Max) ->
case check_pal(Cur * Max) of
true ->
{Cur * Max, {Cur, Max}};
_ ->
get_pal_min_max(Min, Cur - 1, Max)
end.
```

Try a lot of method, still can not solve the timeout problem when the products number is too large. it spend a lot of time to find out all the palindrome numbers.

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