Exercism v3 launches on Sept 1st 2021. Learn more! ๐Ÿš€๐Ÿš€๐Ÿš€
Avatar of danielchirich

danielchirich's solution

to Palindrome Products in the Erlang Track

Published at Aug 02 2020 · 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).

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.

Running tests

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

Questions?

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.

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.

palindrome_products_tests.erl

%% 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, 
	       reverse/1,
	       palindrome/1]).



largest(Min,Max) when Min >= Max -> {error, "Minimo mayor o igual que Maximo"};
largest(Min,Max) ->   Lista = lists:seq(Min,Max),
                      L1 = [element(1,{X*Y,X,Y}) || X <- Lista, Y <- Lista, X >= Y],
                      Pred = fun(X) -> integer_to_list(X) end,
                      L11 = lists:map(Pred,L1),
                      L2 = [{X,Y} || X <- Lista, Y <- Lista, X >= Y],
                      R = lists:zipwith(fun(X, Y) -> {X,Y} end, L11, L2),
                      Pal = [X || X <- R, palindrome(element(1,X))],
                      Pred2 = fun(X) -> list_to_integer(X) end,
                      Map = lists:keymap(Pred2,1,Pal),
                      Map1 = [element(1,X) || X <- Map],
                      lists:keysearch(lists:max(Map1),1,Map).

smallest(Min,Max) when Min >= Max -> {error, "Minimo mayor o igual que Maximo"};
smallest(Min,Max) ->  Lista = lists:seq(Min,Max),
                      L1 = [element(1,{X*Y,X,Y}) || X <- Lista, Y <- Lista, X >= Y],
                      Pred = fun(X) -> integer_to_list(X) end,
                      L11 = lists:map(Pred,L1),
                      L2 = [{X,Y} || X <- Lista, Y <- Lista, X >= Y],
                      R = lists:zipwith(fun(X, Y) -> {X,Y} end, L11, L2),
                      Pal = [X || X <- R, palindrome(element(1,X))],
                      Pred2 = fun(X) -> list_to_integer(X) end,
                      Map = lists:keymap(Pred2,1,Pal),
                      Map1 = [element(1,X) || X <- Map],
                      lists:keysearch(lists:min(Map1),1,Map).


                     
                      
reverse(Xs) -> reverse(Xs, []).
reverse([], Acc) -> Acc;
reverse([X|Xs], Acc) ->
    reverse(Xs, [X|Acc]).

palindrome(Xs) ->
    Ys = Xs,
    Ys == reverse(Ys).

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?