Algorithm to find continuous days in a week

Question

The user can select any number of week days from a list. An algorithm shall find the longest continuous group of selected days. The start day can be after the end day, if the group spans two weeks. If it makes it simpler, only a group of at least 3 days needs to be detected. With crossing the week border, this makes for a maximum of one group. (There can be no two groups of 3 days within a week that are not connected.)

For example, if the user selects Monday, Tuesday, Wednesday and Saturday from a list, the display should be something like "Monday-Wednesday and Saturday".

Another example is: Wed, Fri, Sat, Sun, Mon -> "Wed, Fri-Mon".

Is there an efficient algorithm for that, preferrably in C# or a similar language? My C# hackwork is now over a page long (incl. few comments) and still not finished.

Answer 1

Use this answer, slightly changed:

Use a modified version of dtb's GroupAdjacentBy which accepts a minCount as a parameter:

public static IEnumerable<IEnumerable<T>> GroupAdjacentBy<T>(
    this IEnumerable<T> source, Func<T, T, bool> predicate, int minCount)
{
    using (var e = source.GetEnumerator())
    {
        if (e.MoveNext())
        {
            var list = new List<T> { e.Current };
            var pred = e.Current;
            while (e.MoveNext())
            {
                // if adjacent, add to list
                if (predicate(pred, e.Current))
                {
                    list.Add(e.Current);
                }
                else
                {
                    // otherwise return previous elements:
                    // if less than minCount elements,
                    // return each element separately
                    if (list.Count < minCount)
                    {
                        foreach (var i in list)
                            yield return new List<T> { i };
                    }
                    else
                    {
                        // otherwise return entire group
                        yield return list;
                    }

                    // create next group
                    list = new List<T> { e.Current };
                }
                pred = e.Current;
            }
            yield return list;
        }
    }
}

and change the criteria for GroupAdjacentBy to group on week transitions also:

// week starts with Monday, so this should
// represent: Wed, Fri, Sat, Sun, Mon
int[] array = new int[] { 1, 2, 4, 5, 6, 0 };

Func<int, int, bool> adjacentCriteria = (x, y) => (x+1==y) || (x==6 && y==0);

string result = string.Join(", ", array
    .GroupAdjacentBy(adjacentCriteria, 3)
    .Select(g => new int[] { g.First(), g.Last() }.Distinct())
    .Select(g => string.Join("-", g)));

Console.WriteLine(result); // output: 1, 2, 4-0

Answer 2

I've finished my version of it. It's a bit longer than the other one, but then again it also handles the text representation and does exactly this task. How about that?

using System;
using System.Text;

namespace WeekMathTest
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] weekDayNames = new string[] {
                "Mon",
                "Tue",
                "Wed",
                "Thu",
                "Fri",
                "Sat",
                "Sun"
            };

            WeekDays weekDays = WeekDays.Monday | WeekDays.Tuesday | WeekDays.Thursday | WeekDays.Saturday | WeekDays.Sunday;

            Console.WriteLine(WeekDayGroup(weekDays, weekDayNames));
        }

        static string WeekDayGroup(WeekDays weekDays, string[] weekDayNames)
        {
            int groupStart = 0, groupEnd = 0, groupLength = 0;
            int maxGroupStart = 0, maxGroupEnd = 0, maxGroupLength = 0;

            // Iterate all days in a repeated range
            // (Sat/Sun doesn't need to be repeated or it would be in the first group)
            for (int day = 1; day <= 7 + 5; day++)
            {
                // Is this day set?
                int bitValue = 1 << ((day - 1) % 7);
                bool daySet = ((int) weekDays & bitValue) != 0;
                if (daySet)
                {
                    if (groupStart == 0)
                    {
                        // First day set, remember it as group start
                        groupStart = day;
                        groupEnd = day;
                        groupLength = 1;
                    }
                    else
                    {
                        // Group has already been started, set new end
                        groupEnd = day;
                        groupLength = groupEnd - groupStart + 1;
                        if (groupLength == 7)
                        {
                            // Seen every day of the week, stop here
                            break;
                        }
                    }
                }
                else
                {
                    if (groupLength >= 3 && groupLength > maxGroupLength)
                    {
                        // Group was long enough and longer than the last one, save it
                        maxGroupStart = groupStart;
                        maxGroupEnd = groupEnd;
                        maxGroupLength = groupLength;
                    }
                    // Reset operation variables
                    groupStart = 0;
                    groupEnd = 0;
                    groupLength = 0;
                }
            }
            // Final check
            if (groupLength >= 3 && groupLength > maxGroupLength)
            {
                // Group was long enough and longer than the last one, save it
                maxGroupStart = groupStart;
                maxGroupEnd = groupEnd;
                maxGroupLength = groupLength;
            }

            // Clear all group days from the original value
            for (int day = maxGroupStart; day <= maxGroupEnd; day++)
            {
                int bitValue = 1 << ((day - 1) % 7);
                weekDays = (WeekDays) ((int) weekDays & ~bitValue);
            }

            // Generate output string
            StringBuilder sb = new StringBuilder();
            for (int day = 1; day <= 7; day++)
            {
                int bitValue = 1 << ((day - 1) % 7);
                bool daySet = ((int) weekDays & bitValue) != 0;
                if (daySet)
                {
                    if (sb.Length > 0) sb.Append(", ");
                    sb.Append(weekDayNames[day - 1]);
                }
                else if (day == maxGroupStart)
                {
                    if (sb.Length > 0) sb.Append(", ");
                    sb.Append(weekDayNames[day - 1]);
                    sb.Append("-");
                    sb.Append(weekDayNames[(maxGroupEnd - 1) % 7]);
                }
            }
            return sb.ToString();
        }

        [Flags]
        enum WeekDays
        {
            Monday = 1,
            Tuesday = 2,
            Wednesday = 4,
            Thursday = 8,
            Friday = 16,
            Saturday = 32,
            Sunday = 64
        }
    }
}