주중 연속 일을 찾는 알고리즘

Question

사용자는 목록에서 원하는 요일을 선택할 수 있습니다. 알고리즘은 선택된 날짜 중 가장 긴 연속 그룹을 찾아야한다. 그룹이 2 주간 지속되는 경우 시작일은 종료일 이후 일 수 있습니다. 그것이 더 간단하게 만듬 적어도 3 일의 그룹 만 검출 될 필요가있다. 주 경계를 넘으면 최대 1 개의 그룹이됩니다. 예를 들어 사용자가 목록에서 월요일, 화요일, 수요일 및 토요일을 선택한 경우 "월요일부터 금요일까지"와 같이 표시되어야합니다. 수요일과 토요일 ".

또 다른 예 : Wed, Fri, Sat, Sun, Mon -> "Wed, Fri-Mon"

C# 또는 이와 유사한 언어로 효율적인 알고리즘이 있습니까? 내 C# hackwork는 이제 페이지가 길어졌고 (몇 개의 주석 포함) 아직 끝나지 않았습니다.

Answer 1

나는 내 버전을 완성했다. 그것은 다른 하나보다 약간 길지만, 다시 텍스트 표현을 처리하고 정확히이 작업을 수행합니다. 어떻게에 대한?

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

Answer 2

사용 this answer은 약간 변경 :

가 매개 변수로 minCount 받아 dtb '의 GroupAdjacentBy의 수정 된 버전 사용

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

을 또한 주 전환에 그룹에 GroupAdjacentBy에 대한 기준을 변경 :

// 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