Avatar of einheitsvektor

einheitsvektor's solution

to Sublist in the C Track

Published at Sep 11 2019 · 0 comments
Instructions
Test suite
Solution

Given two lists determine if the first list is contained within the second list, if the second list is contained within the first list, if both lists are contained within each other or if none of these are true.

Specifically, a list A is a sublist of list B if by dropping 0 or more elements from the front of B and 0 or more elements from the back of B you get a list that's completely equal to A.

Examples:

  • A = [1, 2, 3], B = [1, 2, 3, 4, 5], A is a sublist of B
  • A = [3, 4, 5], B = [1, 2, 3, 4, 5], A is a sublist of B
  • A = [3, 4], B = [1, 2, 3, 4, 5], A is a sublist of B
  • A = [1, 2, 3], B = [1, 2, 3], A is equal to B
  • A = [1, 2, 3, 4, 5], B = [2, 3, 4], A is a superlist of B
  • A = [1, 2, 4], B = [1, 2, 3, 4, 5], A is not a superlist of, sublist of or equal to B

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.

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

test_sublist.c

#include "vendor/unity.h"
#include "../src/sublist.h"

#define ELEMENT_COUNT(array) (sizeof(array) / sizeof(array[0]))

void setUp(void)
{
}

void tearDown(void)
{
}

static void test_empty_lists(void)
{
   TEST_ASSERT_EQUAL(EQUAL, check_lists(NULL, NULL, 0, 0));
}

static void test_empty_list_within_non_empty_list(void)
{
   TEST_IGNORE();               // delete this line to run test
   int base_list[] = { 1, 2, 3 };

   TEST_ASSERT_EQUAL(SUBLIST,
                     check_lists(NULL, base_list, 0, ELEMENT_COUNT(base_list)));
}

static void test_non_empty_list_contains_empty_list(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 2, 3 };

   TEST_ASSERT_EQUAL(SUPERLIST,
                     check_lists(list_to_compare, NULL,
                                 ELEMENT_COUNT(list_to_compare), 0));
}

static void test_list_equals_itself(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 2, 3 };
   int base_list[] = { 1, 2, 3 };

   TEST_ASSERT_EQUAL(EQUAL,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_different_lists(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 2, 3 };
   int base_list[] = { 2, 3, 4 };

   TEST_ASSERT_EQUAL(UNEQUAL,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_false_start(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 2, 5 };
   int base_list[] = { 0, 1, 2, 3, 1, 2, 5, 6 };

   TEST_ASSERT_EQUAL(SUBLIST,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_consecutive(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 1, 2 };
   int base_list[] = { 0, 1, 1, 1, 2, 1, 2 };

   TEST_ASSERT_EQUAL(SUBLIST,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_sublist_at_start(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 0, 1, 2 };
   int base_list[] = { 0, 1, 2, 3, 4, 5 };

   TEST_ASSERT_EQUAL(SUBLIST,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_sublist_at_middle(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 2, 3, 4 };
   int base_list[] = { 0, 1, 2, 3, 4, 5 };

   TEST_ASSERT_EQUAL(SUBLIST,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_sublist_at_end(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 3, 4, 5 };
   int base_list[] = { 0, 1, 2, 3, 4, 5 };

   TEST_ASSERT_EQUAL(SUBLIST,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_at_start_of_superlist(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 0, 1, 2, 3, 4, 5 };
   int base_list[] = { 0, 1, 2 };

   TEST_ASSERT_EQUAL(SUPERLIST,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_in_middle_of_superlist(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 0, 1, 2, 3, 4, 5 };
   int base_list[] = { 2, 3 };

   TEST_ASSERT_EQUAL(SUPERLIST,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_at_end_of_superlist(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 0, 1, 2, 3, 4, 5 };
   int base_list[] = { 3, 4, 5 };

   TEST_ASSERT_EQUAL(SUPERLIST,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_first_list_missing_element_from_second_list(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 3 };
   int base_list[] = { 1, 2, 3 };

   TEST_ASSERT_EQUAL(UNEQUAL,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_second_list_missing_element_from_first_list(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 2, 3 };
   int base_list[] = { 1, 3 };

   TEST_ASSERT_EQUAL(UNEQUAL,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_order_matters_to_a_list(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 2, 3 };
   int base_list[] = { 3, 2, 1 };

   TEST_ASSERT_EQUAL(UNEQUAL,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_same_digits_but_different_numbers(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 0, 1 };
   int base_list[] = { 10, 1 };

   TEST_ASSERT_EQUAL(UNEQUAL,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

static void test_different_signs(void)
{
   TEST_IGNORE();
   int list_to_compare[] = { 1, 2, 3 };
   int base_list[] = { 1, -2, 3 };

   TEST_ASSERT_EQUAL(UNEQUAL,
                     check_lists(list_to_compare, base_list,
                                 ELEMENT_COUNT(list_to_compare),
                                 ELEMENT_COUNT(base_list)));
}

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

   RUN_TEST(test_empty_lists);
   RUN_TEST(test_empty_list_within_non_empty_list);
   RUN_TEST(test_non_empty_list_contains_empty_list);
   RUN_TEST(test_list_equals_itself);
   RUN_TEST(test_different_lists);
   RUN_TEST(test_false_start);
   RUN_TEST(test_consecutive);
   RUN_TEST(test_sublist_at_start);
   RUN_TEST(test_sublist_at_middle);
   RUN_TEST(test_sublist_at_end);
   RUN_TEST(test_at_start_of_superlist);
   RUN_TEST(test_in_middle_of_superlist);
   RUN_TEST(test_at_end_of_superlist);
   RUN_TEST(test_first_list_missing_element_from_second_list);
   RUN_TEST(test_second_list_missing_element_from_first_list);
   RUN_TEST(test_order_matters_to_a_list);
   RUN_TEST(test_same_digits_but_different_numbers);
   RUN_TEST(test_different_signs);

   return UnityEnd();
}

src/sublist.c

#include "sublist.h"

comparison_result_t check_lists(int *list_to_compare, int *base_list,
                                size_t list_to_compare_element_count,
                                size_t base_list_element_count) {
    
    if (!list_to_compare && !base_list) return EQUAL;
    if (!list_to_compare && base_list)  return SUBLIST;
    if (list_to_compare && !base_list)  return SUPERLIST;

    /* Approach via converting both int-arays into a string and then 
       search for substring */
    char s_compare[list_to_compare_element_count * sizeof(char) + 1];
    char s_base[base_list_element_count * sizeof(char) + 1];
    for (size_t i = 0, n = 0; i < list_to_compare_element_count; i++)
        n += sprintf(&s_compare[n], "%d", list_to_compare[i]);
    for (size_t i = 0, n = 0; i < base_list_element_count; i++)
        n += sprintf(&s_base[n], "%d", base_list[i]);

    if (strlen(s_compare) < strlen(s_base)) {
        if (strstr(s_base, s_compare)) return SUBLIST;
        else return UNEQUAL;
    }

    if (list_to_compare_element_count > base_list_element_count) {
        for (size_t i = 0; i < base_list_element_count; i++)
            if (list_to_compare[i] == base_list[0])
                for (size_t j = i, k = 0; k < base_list_element_count; j++, k++)
                    if (base_list[k] != list_to_compare[j]) return UNEQUAL;

        // Does first element even occur in list_to_compare?
        size_t count = 0;
        for (size_t i = 0; i < list_to_compare_element_count; i++)
            if (base_list[0] == list_to_compare[i]) count++; 
        if (count == 0) return UNEQUAL;
        return SUPERLIST;
    }

    if (list_to_compare_element_count == base_list_element_count) {
        for (size_t i = 0; i < list_to_compare_element_count; i++) 
            if (list_to_compare[i] != base_list[i]) return UNEQUAL;
        return EQUAL;
    }

    return SUPERLIST;;
}

src/sublist.h

#ifndef SUBLIST_H
#define SUBLIST_H

#include <stddef.h>
#include <stdio.h>
#include <string.h>

typedef enum {
   EQUAL,
   UNEQUAL,
   SUBLIST,
   SUPERLIST
} comparison_result_t;

comparison_result_t check_lists(int *list_to_compare, int *base_list,
                                size_t list_to_compare_element_count,
                                size_t base_list_element_count);

#endif

Community comments

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

einheitsvektor's Reflection

Tailored if-conditions to pass the tests. Kind of a dissatisfying solution.