Avatar of vlzware

vlzware's solution

to Palindrome Products in the C Track

Published at Jul 13 2018 · 1 comment
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code 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).

Getting Started

Make sure you have read the C page 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"

void setUp(void)
{
}

void tearDown(void)
{
}

void check_factors(factor_t * actual, int depth, factor_t expected[])
{
   if (depth == 0) {
      TEST_ASSERT_EQUAL_PTR(NULL, actual);
      return;
   }
   int i;
   int count_ok = 0;
   for (i = 0; i < depth; i++) {
      if (actual == NULL)
         break;
      if ((actual->factor_a == expected[i].factor_a) &&
          (actual->factor_b == expected[i].factor_b))
         count_ok++;
      actual = actual->next;
   }
   TEST_ASSERT_EQUAL_PTR(NULL, actual);
   TEST_ASSERT_EQUAL_INT(depth, count_ok);
}

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);
}

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);
}

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);
}

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);
}

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);
}

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);
}

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);
}

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);
}

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);
}

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);
}

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);
}

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

   UnityEnd();
   return 0;
}

src/palindrome_products.c

#include "palindrome_products.h"
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

static int palindrome(int n);
static int addfactors(factor_t ** p, int i, int k);
static void free_ll(struct factors *p);

product_t *get_palindrome_product(int from, int to)
{
	product_t *res = malloc(sizeof(product_t));
	if (res == NULL) {
		fprintf(stderr, "Memory error!\n");
		return NULL;
	}

	res->error[MAXERR - 1] = '\0';
	res->smallest = INT_MAX;
	res->largest = INT_MIN;
	res->factors_lg = NULL;
	res->factors_sm = NULL;

	if (from > to) {
		snprintf(res->error, MAXERR - 1,
			 "invalid input: min is %i and max is %i", from, to);
		return res;
	}

	int i, k, n;
	int err = 0;
	for (i = from; i <= to; i++)
		for (k = i; k <= to; k++)
			if (palindrome(n = i * k)) {
				if (n <= res->smallest) {
					res->smallest = n;
					err =
					    addfactors(&res->factors_sm, i, k);
				} else if (n >= res->largest) {
					res->largest = n;
					err =
					    addfactors(&res->factors_lg, i, k);
				}
				if (err) {
					free(res);
					return NULL;
				}
			}

	if ((res->smallest == INT_MAX) || (res->largest == INT_MIN)) {
		snprintf(res->error, MAXERR - 1,
			 "no palindrome with factors in the range %i to %i",
			 from, to);
		return res;
	}
	return res;
}

void free_product(product_t * p)
{
	if (p == NULL)
		return;
	free_ll(p->factors_lg);
	free_ll(p->factors_sm);
	free(p);
}

static void free_ll(struct factors *p)
{
	if (p == NULL)
		return;
	if (p->next != NULL)
		free_ll(p->next);
	free(p);
}

static int addfactors(factor_t ** p, int i, int k)
{
	int n = i * k;
	if ((*p == NULL) || (((*p)->factor_a) * (*p)->factor_b != n)) {
		free_ll(*p);
		*p = NULL;
	}

	factor_t *tmp = malloc(sizeof(factor_t));
	if (tmp == NULL) {
		fprintf(stderr, "Memory error!\n");
		return 1;
	}

	tmp->next = *p;
	tmp->factor_a = i;
	tmp->factor_b = k;
	*p = tmp;
	return 0;
}

static int palindrome(int n)
{
	if (n < 0)
		n *= -1;
	int r = 0;
	int nn = n;

	/* inverse n in r */
	while (n >= 1) {
		r = (r * 10) + (n % 10);
		n /= 10;
	}

	return (nn == r);
}

src/palindrome_products.h

#ifndef PALINDROME_PRODUCTS_H
#define PALINDROME_PRODUCTS_H

#define MAXERR 100

struct factors {
	int factor_a;
	int factor_b;
	struct factors *next;
};

typedef struct factors factor_t;

struct product {
	int smallest;
	int largest;
	factor_t *factors_sm;
	factor_t *factors_lg;
	char error[MAXERR];
};

typedef struct product product_t;

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

#endif

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of vlzware

The exercise tests got updated and are now matching the problem better. Here is a solution matching the new tests.

This works but some advanced mathematical solution would be better in regards of speed.

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?