 # fjarboleda's solution

## to Palindrome Products in the C Track

Published at Jun 29 2019 · 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.

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

## Getting Started

Make sure you have read the "Guides" section of the C track on the Exercism site. This covers the basic information on setting up the development environment expected by the exercises.

## Passing the Tests

Get the first test compiling, linking and passing by following the three rules of test-driven development.

The included makefile can be used to create and run the tests using the `test` task.

``````make test
``````

Create just the functions you need to satisfy any compiler errors and get the test to fail. Then write just enough code to get the test to pass. Once you've done that, move onto the next test.

As you progress through the tests, take the time to refactor your implementation for readability and expressiveness and then go on to the next test.

Try to use standard C99 facilities in preference to writing your own low-level algorithms or facilities by hand.

## 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.

### test_palindrome_products.c

``````#include "vendor/unity.h"
#include "../src/palindrome_products.h"

#include <stdbool.h>
#include <stddef.h>

void setUp(void)
{
}

void tearDown(void)
{
}

/* factor_t_are_equal compares the values of the factors
* that are stored in the passed f1, f2 factor_t structs
* regardless of their order in the said structs. Returns
* true if the values are equal, false otherwise.
*
*
* Examples:
*
* factor_t_are_equal(&{1, 9}, &{1, 9}) returns true
* factor_t_are_equal(&{1, 9}, &{9, 1}) returns true
* factor_t_are_equal(&{1, 9}, &{1, 8}) returns false
* */
static bool factor_t_are_equal(const factor_t * const f1,
const factor_t * const f2)
{
return ((f1->factor_a == f2->factor_a) && (f1->factor_b == f2->factor_b)) ||
((f1->factor_a == f2->factor_b) && (f1->factor_a == f2->factor_b));
}

/* contains_factor checks if the `factor` variable is stored
* in the `factors` linked-list. The function traverses the
* `factors` list, until it finds the desired element, in which case
* it returns true. If the function gets to the end of the list or
* exceeds the number of checked elements (passed as the `depth` variable),
* it returns false.
* */
static bool
contains_factor(factor_t * factors, const factor_t * const factor,
const size_t depth)
{
size_t current_depth = 0;
factor_t *current_factor = factors;
while ((current_factor != NULL) && (current_depth != depth)) {
if (factor_t_are_equal(current_factor, factor)) {
return true;
}
current_factor = current_factor->next;
current_depth += 1;
}
return false;
}

/* check_factors checks if all the factor_t elements that are
* passed in the `expected` variable are present in the `actual`
* variable that contains a linked list of factor_t elements from
* the student's solution. For every element of `expected` found in
* `actual` the `found_count` variable is incremented. In the end
* `found_count` is compared with the expected number of the found
* elements passed in the `depth` variable.
* */
static void check_factors(factor_t * actual, size_t depth, factor_t expected[])
{
if (depth == 0) {
TEST_ASSERT_EQUAL_PTR(NULL, actual);
return;
}
int found_count = 0;
for (size_t i = 0; i < depth; ++i) {
if (!contains_factor(actual, &expected[i], depth)) {
break;
}
found_count += 1;
}
TEST_ASSERT_EQUAL_INT_MESSAGE(depth, found_count,
"Not every expected factor found in the actual result.");
}

static void test_smallest_palindrome_from_single_digit_factors(void)
{
product_t *product = get_palindrome_product(1, 9);
TEST_ASSERT_NOT_NULL(product);
TEST_ASSERT_EQUAL_INT(1, product->smallest);

factor_t expected_sm[] = { {1, 1, NULL} };
check_factors(product->factors_sm, 1, expected_sm);

free_product(product);
}

static void test_largest_palindrome_from_single_digit_factors(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(1, 9);
TEST_ASSERT_NOT_NULL(product);
TEST_ASSERT_EQUAL_INT(9, product->largest);

factor_t expected_lg[] = { {3, 3, NULL}, {1, 9, NULL} };
check_factors(product->factors_lg, 2, expected_lg);

free_product(product);
}

static void test_smallest_palindrome_from_double_digit_factors(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(10, 99);
TEST_ASSERT_NOT_NULL(product);
TEST_ASSERT_EQUAL_INT(121, product->smallest);

factor_t expected_sm[] = { {11, 11, NULL} };
check_factors(product->factors_sm, 1, expected_sm);

free_product(product);
}

static void test_largest_palindrome_from_double_digit_factors(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(10, 99);
TEST_ASSERT_NOT_NULL(product);
TEST_ASSERT_EQUAL_INT(9009, product->largest);

factor_t expected_lg[] = { {91, 99, NULL} };
check_factors(product->factors_lg, 1, expected_lg);

free_product(product);
}

static void test_smallest_palindrome_from_triple_digit_factors(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(100, 999);
TEST_ASSERT_NOT_NULL(product);
TEST_ASSERT_EQUAL_INT(10201, product->smallest);

factor_t expected_sm[] = { {101, 101, NULL} };
check_factors(product->factors_sm, 1, expected_sm);

free_product(product);
}

static void test_largest_palindrome_from_triple_digit_factors(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(100, 999);
TEST_ASSERT_NOT_NULL(product);
TEST_ASSERT_EQUAL_INT(906609, product->largest);

factor_t expected_lg[] = { {913, 993, NULL} };
check_factors(product->factors_lg, 1, expected_lg);

free_product(product);
}

static void test_smallest_palindrome_from_four_digit_factors(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(1000, 9999);
TEST_ASSERT_NOT_NULL(product);
TEST_ASSERT_EQUAL_INT(1002001, product->smallest);

factor_t expected_sm[] = { {1001, 1001, NULL} };
check_factors(product->factors_sm, 1, expected_sm);

free_product(product);
}

static void test_largest_palindrome_from_four_digit_factors(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(1000, 9999);
TEST_ASSERT_NOT_NULL(product);
TEST_ASSERT_EQUAL_INT(99000099, product->largest);

factor_t expected_lg[] = { {9901, 9999, NULL} };
check_factors(product->factors_lg, 1, expected_lg);

free_product(product);
}

static void test_empty_result_for_smallest_if_no_palindrome_in_the_range(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(1002, 1003);
TEST_ASSERT_NOT_NULL(product);
const char *expected =
"no palindrome with factors in the range 1002 to 1003";
TEST_ASSERT_EQUAL_STRING(expected, product->error);

free_product(product);
}

static void test_empty_result_for_largest_if_no_palindrome_in_the_range(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(15, 15);
TEST_ASSERT_NOT_NULL(product);
const char *expected = "no palindrome with factors in the range 15 to 15";
TEST_ASSERT_EQUAL_STRING(expected, product->error);

free_product(product);
}

static void test_error_result_for_smallest_if_min_is_more_than_max(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(10000, 1);
TEST_ASSERT_NOT_NULL(product);
const char *expected = "invalid input: min is 10000 and max is 1";
TEST_ASSERT_EQUAL_STRING(expected, product->error);

free_product(product);
}

static void test_error_result_for_largest_if_min_is_more_than_max(void)
{
TEST_IGNORE();               // delete this line to run test
product_t *product = get_palindrome_product(2, 1);
TEST_ASSERT_NOT_NULL(product);
const char *expected = "invalid input: min is 2 and max is 1";
TEST_ASSERT_EQUAL_STRING(expected, product->error);

free_product(product);
}

int main(void)
{
UnityBegin("test/test_palindrome_products.c");

RUN_TEST(test_smallest_palindrome_from_single_digit_factors);
RUN_TEST(test_largest_palindrome_from_single_digit_factors);

RUN_TEST(test_smallest_palindrome_from_double_digit_factors);
RUN_TEST(test_largest_palindrome_from_double_digit_factors);

RUN_TEST(test_smallest_palindrome_from_triple_digit_factors);
RUN_TEST(test_largest_palindrome_from_triple_digit_factors);

RUN_TEST(test_smallest_palindrome_from_four_digit_factors);
RUN_TEST(test_largest_palindrome_from_four_digit_factors);

RUN_TEST(test_empty_result_for_smallest_if_no_palindrome_in_the_range);
RUN_TEST(test_empty_result_for_largest_if_no_palindrome_in_the_range);

RUN_TEST(test_error_result_for_smallest_if_min_is_more_than_max);
RUN_TEST(test_error_result_for_largest_if_min_is_more_than_max);

return UnityEnd();
}``````

### src/palindrome_products.h

``````#ifndef PALINDROME_PRODUCTS_H
#define PALINDROME_PRODUCTS_H

typedef struct factor
{
int factor_a;
int factor_b;
struct factor *next;
} factor_t;

#define MAX_LENGTH 256

typedef struct product
{
int start;
int end;
int smallest;
int largest;
factor_t *factors_sm;
factor_t *factors_lg;
char error[MAX_LENGTH];
} product_t;

product_t *get_palindrome_product(const int from, const int to);
void free_product(product_t * p);

#endif``````

### src/palindrome_products.c

``````#include <stdbool.h>
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

#include "palindrome_products.h"

static product_t* alloc_product( const int factor_a, const int factor_b )
{
product_t* result = (product_t*) malloc (sizeof(struct product));
if(!result) exit(1);

result->smallest = INT_MAX;
result->largest = INT_MIN;

result->start = factor_a;
result->end = factor_b;

result->factors_sm = NULL;
result->factors_lg = NULL;

return result;
}

static void free_factor_list( factor_t * first )
{
while(first)
{
factor_t *old = first;
first = first->next;
free(old);
}
}

void free_product(product_t * p)
{
free_factor_list( p->factors_sm );
free_factor_list( p->factors_lg );
free(p);
}

static bool equals_factor( const factor_t * self, const int a, const int b )
{
return ( self->factor_a == a && self->factor_b == b) ||
( self->factor_a == b && self->factor_b == a) ;

}

static bool find_factor( factor_t * first, const int a, const int b )
{
while(first)
{
if( equals_factor(first, a, b) )
return true;

first = first->next;

}
return false;
}

static void append_factor( factor_t ** first, const int a, const int b )
{
factor_t* f = (factor_t*) malloc (sizeof(struct factor));
if (!f) exit(-1);

f->factor_a = a;
f->factor_b = b;
f->next = (*first);
*first = f;
}

static bool test_input_palindrome( product_t* pal )
{
if (pal->start > pal->end)
{
sprintf( pal->error, "invalid input: min is %i and max is %i",
pal->start, pal->end );
return false;
}
return true;
}

static bool test_output_palindrome( product_t* pal )
{
if (!(pal->factors_sm))
{
sprintf( pal->error, "no palindrome with factors in the range %i to %i",
pal->start, pal->end  );
return false;
}
return true;
}

// calc as strlen() of printf() of MAX_INT + '-' + '\0'
#define MAX_LEN_PALINDROME 12

static bool is_number_palindrome( const int value )
{
char buffer[MAX_LEN_PALINDROME];

int n = snprintf( buffer, MAX_LEN_PALINDROME, "%i", value );

char *begin = (char*) buffer;
char *end = begin + n -1;

while ( begin < end )
{
if (*begin++ != *end--)
return false;
}

return true;
}

#undef MAX_LEN_PALINDROME

static bool update_max_min( int* value, factor_t** f, const int factor_a, const int factor_b )
{
int product = factor_a * factor_b;
if ( *value != product)
{
free_factor_list(*f);
*f = NULL;
*value = product;
}
else
{
if (find_factor( *f, factor_a, factor_b ))
return false;
}

append_factor( f, factor_a, factor_b);

return true;
}

static bool update_largest( product_t* pal, const int fact1, const int fact2 )
{
return update_max_min( &(pal->largest), &(pal->factors_lg), fact1, fact2 );
}

static bool update_smallest( product_t* pal, const int fact1, const int fact2 )
{
return update_max_min( &(pal->smallest), &(pal->factors_sm), fact1, fact2 );
}

static product_t* execute_palindrome_product( product_t* pal )
{
for (int i=pal->start; i<=pal->end; ++i)
{
int product = i * pal->start;

for (int j=pal->start; j<=pal->end; ++j)
{
if ( is_number_palindrome(product) )
{
if (product >= pal->largest)
{
update_largest(pal, i, j);
}

if (product <= pal->smallest)
{
update_smallest(pal, i, j);
}
}

product += i;
}
}

return pal;
}

product_t* get_palindrome_product(const int a, const int b)
{
product_t* result = alloc_product(a, b);

if (test_input_palindrome( result ) )
{
execute_palindrome_product( result );
test_output_palindrome( result );
}

return (result);
}``````