Avatar of artemkorsakov

artemkorsakov's solution

to Sublist in the C# Track

Published at May 03 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

Hints

To be able to compare data, the IComparable interface is used. For more information, see this page.

Running the tests

To run the tests, run the command dotnet test from within the exercise directory.

Initially, only the first test will be enabled. This is to encourage you to solve the exercise one step at a time. Once you get the first test passing, remove the Skip property from the next test and work on getting that test passing. Once none of the tests are skipped and they are all passing, you can submit your solution using exercism submit Sublist.cs

Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

SublistTest.cs

// This file was auto-generated based on version 1.1.0 of the canonical data.

using System.Collections.Generic;
using Xunit;

public class SublistTest
{
    [Fact]
    public void Empty_lists()
    {
        Assert.Equal(SublistType.Equal, Sublist.Classify(new List<int>(), new List<int>()));
    }

    [Fact(Skip = "Remove to run test")]
    public void Empty_list_within_non_empty_list()
    {
        Assert.Equal(SublistType.Sublist, Sublist.Classify(new List<int>(), new List<int> { 1, 2, 3 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Non_empty_list_contains_empty_list()
    {
        Assert.Equal(SublistType.Superlist, Sublist.Classify(new List<int> { 1, 2, 3 }, new List<int>()));
    }

    [Fact(Skip = "Remove to run test")]
    public void List_equals_itself()
    {
        Assert.Equal(SublistType.Equal, Sublist.Classify(new List<int> { 1, 2, 3 }, new List<int> { 1, 2, 3 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Different_lists()
    {
        Assert.Equal(SublistType.Unequal, Sublist.Classify(new List<int> { 1, 2, 3 }, new List<int> { 2, 3, 4 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void False_start()
    {
        Assert.Equal(SublistType.Sublist, Sublist.Classify(new List<int> { 1, 2, 5 }, new List<int> { 0, 1, 2, 3, 1, 2, 5, 6 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Consecutive()
    {
        Assert.Equal(SublistType.Sublist, Sublist.Classify(new List<int> { 1, 1, 2 }, new List<int> { 0, 1, 1, 1, 2, 1, 2 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Sublist_at_start()
    {
        Assert.Equal(SublistType.Sublist, Sublist.Classify(new List<int> { 0, 1, 2 }, new List<int> { 0, 1, 2, 3, 4, 5 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Sublist_in_middle()
    {
        Assert.Equal(SublistType.Sublist, Sublist.Classify(new List<int> { 2, 3, 4 }, new List<int> { 0, 1, 2, 3, 4, 5 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Sublist_at_end()
    {
        Assert.Equal(SublistType.Sublist, Sublist.Classify(new List<int> { 3, 4, 5 }, new List<int> { 0, 1, 2, 3, 4, 5 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void At_start_of_superlist()
    {
        Assert.Equal(SublistType.Superlist, Sublist.Classify(new List<int> { 0, 1, 2, 3, 4, 5 }, new List<int> { 0, 1, 2 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void In_middle_of_superlist()
    {
        Assert.Equal(SublistType.Superlist, Sublist.Classify(new List<int> { 0, 1, 2, 3, 4, 5 }, new List<int> { 2, 3 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void At_end_of_superlist()
    {
        Assert.Equal(SublistType.Superlist, Sublist.Classify(new List<int> { 0, 1, 2, 3, 4, 5 }, new List<int> { 3, 4, 5 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void First_list_missing_element_from_second_list()
    {
        Assert.Equal(SublistType.Unequal, Sublist.Classify(new List<int> { 1, 3 }, new List<int> { 1, 2, 3 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Second_list_missing_element_from_first_list()
    {
        Assert.Equal(SublistType.Unequal, Sublist.Classify(new List<int> { 1, 2, 3 }, new List<int> { 1, 3 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Order_matters_to_a_list()
    {
        Assert.Equal(SublistType.Unequal, Sublist.Classify(new List<int> { 1, 2, 3 }, new List<int> { 3, 2, 1 }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Same_digits_but_different_numbers()
    {
        Assert.Equal(SublistType.Unequal, Sublist.Classify(new List<int> { 1, 0, 1 }, new List<int> { 10, 1 }));
    }
}
using System;
using System.Collections.Generic;
using System.Linq;

public enum SublistType
{
    Equal,
    Unequal,
    Superlist,
    Sublist
}

public static class Sublist
{
    public static SublistType Classify<T>(List<T> list1, List<T> list2)
        where T : IComparable
    {
        var isFirstSublist = IsSubList(list1, list2);
        var isSecondSublist = IsSubList(list2, list1);
        return isFirstSublist && isSecondSublist
            ? SublistType.Equal
            : isFirstSublist
                ? SublistType.Sublist
                : isSecondSublist
                    ? SublistType.Superlist
                    : SublistType.Unequal;
    }

    private static bool IsSubList<T>(List<T> list1, List<T> list2)
        where T : IComparable
    {
        if (list1.Count == 0)
        {
            return true;
        }

        if (list1.Count > list2.Count)
        {
            return false;
        }

        int idx = list2.IndexOf(list1[0]);
        if (idx == -1)
        {
            return false;
        }

        for (int i = 1; i < list1.Count; i++)
        {
            if (idx + i >= list2.Count)
            {
                return false;
            }

            if (!list1[i].Equals(list2[idx + i]))
            {
                return IsSubList(list1, list2.Skip(idx + 1).ToList());
            }
        }

        return true;
    }
}

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?