🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of tam

tam's solution

to Palindrome Products in the Erlang Track

Published at Jan 04 2019 · 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).

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

Test versioning

Each problem defines a macro TEST_VERSION in the test file and verifies that the solution defines and exports a function test_version returning that same value.

To make tests pass, add the following to your solution:

-export([test_version/0]).

test_version() ->
  1.

The benefit of this is that reviewers can see against which test version an iteration was written if, for example, a previously posted solution does not solve the current problem or passes current tests.

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.

palindrome_products_tests.erl

%% based on canonical data version 1.1.0
%% https://raw.githubusercontent.com/exercism/problem-specifications/master/exercises/palindrome-products/canonical-data.json

-module(palindrome_products_tests).

-define(TEST_VERSION, 1).
-include_lib("erl_exercism/include/exercism.hrl").
-include_lib("eunit/include/eunit.hrl").

smallest_from_single_digit_factors_test() ->
	?assertMatch({1, [{1, 1}]}, normalize_output(palindrome_products:smallest(1, 9))).

largest_from_single_digit_factors_test() ->
	?assertMatch({9, [{1, 9}, {3, 3}]}, normalize_output(palindrome_products:largest(1, 9))).

smallest_from_double_digit_factors_test() ->
	?assertMatch({121, [{11, 11}]}, normalize_output(palindrome_products:smallest(10, 99))).

largest_from_double_digit_factors_test() ->
	?assertMatch({9009, [{91, 99}]}, normalize_output(palindrome_products:largest(10, 99))).

smallest_from_triple_digit_factors_test() ->
	?assertMatch({10201, [{101, 101}]}, normalize_output(palindrome_products:smallest(100, 999))).

largest_from_triple_digit_factors_test() ->
	?assertMatch({906609, [{913, 993}]}, normalize_output(palindrome_products:largest(100, 999))).

smallest_from_four_digit_factors_test() ->
	?assertMatch({1002001, [{1001, 1001}]}, normalize_output(palindrome_products:smallest(1000, 9999))).

largest_from_four_digit_factors_test() ->
	?assertMatch({99000099, [{9901, 9999}]}, normalize_output(palindrome_products:largest(1000, 9999))).

smallest_none_in_range_test() ->
	?assertMatch(undefined, palindrome_products:smallest(1002, 1003)).

largest_none_in_range_test() ->
	?assertMatch(undefined, palindrome_products:largest(15, 15)).

smallest_min_greater_than_max_test() ->
	?assertMatch({error, invalid_range}, palindrome_products:smallest(10000, 1)).

largest_min_greater_than_max_test() ->
	?assertMatch({error, invalid_range}, palindrome_products:largest(2, 1)).

normalize_output({Pal, Factors}) ->
	{
		Pal,
		lists:sort(
			lists:map(
				fun
					({A, B}) when A>B -> {B, A};
					(AB) -> AB
				end,
				Factors
			)
		)
	};

normalize_output(Other) -> Other.

version_test() ->
	?assertMatch(?TEST_VERSION, palindrome_products:test_version()).
-module(palindrome_products).

-export([smallest/2, largest/2, test_version/0]).

smallest(Min, Max) when Min > Max -> {error, invalid_range};
smallest(Min, Max) -> smallest(Min, Max, int_to_pal(Min*Min), Max*Max).
smallest(Min, Max, PN, NMax) ->
	case pal_to_int(PN) of
		N when N > NMax -> undefined;
		N -> 
			case divs(N, Min, Max) of
				[] -> smallest(Min, Max, nxtp(PN), NMax);
				Divs -> {N, Divs}
			end
	end.

largest(Min, Max) when Min > Max -> {error, invalid_range};
largest(Min, Max) -> largest(Min, Max, int_to_pal(Max*Max), Min*Min).
largest(Min, Max, PN, NMin) ->
	case pal_to_int(PN) of
		N when N < NMin -> undefined;
		N -> 
			case divs(N, Min, Max) of
				[] -> largest(Min, Max, prvp(PN), NMin);
				Divs -> {N, Divs}
			end
	end.

% products of a number C
divs(C, Min, Max) -> divs(C, Min, Max, Min, []).
divs(C, Min, Max, D, Ds) -> 
	case C div D of
		Q when Q < D -> lists:reverse(Ds);
		Q when Q > Max -> divs(C, Min, Max, D+1, Ds);
		Q when C rem D == 0 -> divs(C, Min, Max, D+1, [{D,Q}|Ds]);
		_ -> divs(C, Min, Max, D+1, Ds)
	end.

% takes a palindrome and gives the next palindrom
nxtp({N, even, Min, Max}) when N+1 == Max -> {N+1, odd, Min*10, Max*10};
nxtp({N, odd, Min, Max}) when N+1 == Max -> {Max div 10, even, Min, Max};
nxtp({N, Phase, Min, Max}) -> {N+1, Phase, Min, Max}.

% takes a palindrome and gives the previous palindrom
prvp({N, even, Min, Max}) when N == Min -> {Min * 10 - 1, odd, Min, Max};
prvp({N, odd, Min, Max}) when N == Min -> {N-1, even, Min div 10, Max div 10};
prvp({N, Phase, Min, Max}) -> {N-1, Phase, Min, Max}.

% palindrome representation to integer
pal_to_int({N, Phase, _Min, _Max}) ->
	Head = integer_to_list(N),
	Tail = case Phase of
		even -> lists:reverse(Head);
		odd -> tl(lists:reverse(Head))
	end,
	list_to_integer(Head ++ Tail).

% int to palindrome representation
int_to_pal(A) -> 
	AStr = integer_to_list(A),
	Length = length(AStr),
	Rem = Length rem 2,
	Phase = case Rem of 0 -> even; 1 -> odd end,
	HeadL = Length div 2 + Rem,
	Head = list_to_integer(lists:sublist(AStr, HeadL)),
	Min = trunc( math:pow(10, HeadL-1) ),
	{ Head,	Phase, Min, 10*Min }.

test_version() -> 1.

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?