Determine Event Recurrence Pattern for a set of dates

Question

I am looking for a pattern, algorithm, or library that will take a set of dates and return a description of the recurrence if one exits, i.e. the set [11-01-2010, 11-08-2010, 11-15-2010, 11-22-2010, 11-29-2010] would yield something like "Every Monday in November".

Has anyone seen anything like this before or have any suggestions on the best way to implement it?

Answer 1

Grammatical Evolution (GE) is suitable for this kind of problem, because you are searching for an answer that adheres to a certain language. Grammatical Evolution is also used for program generation, composing music, designing, etcetera.

I'd approach the task like this:

Structure the problem space with a grammar.

Construct a Context-free Grammar that can represent all desired recurrence patterns. Consider production rules like these:

datepattern -> datepattern 'and' datepattern
datepattern -> frequency bounds
frequency -> 'every' ordinal weekday 'of the month'
frequency -> 'every' weekday
ordinal -> ordinal 'and' ordinal
ordinal -> 'first' | 'second' | 'third'
bounds -> 'in the year' year

An example of a pattern generated by these rules is: 'every second and third wednesday of the month in the year 2010 and every tuesday in the year 2011'

One way to implement such a grammar would be through a class hierarchy that you will later operate on through reflection, as I've done in the example below.

Map this language to a set of dates

You should create a function that takes a clause from your language and recursively returns the set of all dates covered by it. This allows you to compare your answers to the input.

Guided by the grammar, search for potential solutions

You could use a Genetic algorithm or Simulated Annealing to match the dates to the grammar, try your luck with Dynamic Programming or start simple with a brute force enumeration of all possible clauses.

Should you go with a Genetic Algorithm, your mutation concept should consist of substituting an expression for another one based on the application of one of your production rules.

Have a look at the following GE-related sites for code and information: http://www.bangor.ac.uk/~eep201/jge/
http://nohejl.name/age/
http://www.geneticprogramming.us/Home_Page.html

Evaluate each solution

The fitness function could take into account the textual length of the solution, the number of dates generated more than once, the number of dates missed, as well as the number of wrong dates generated.

Example code

By request, and because it's such an interesting challenge, I've written a rudimentary implementation of the algorithm to get you started. Although it works it is by no means finished, the design should definitively get some more thought, and once you have gleaned the fundamental take-aways from this example I recommend you consider using one the libraries I've mentioned above.

  /// <summary>
  ///  This is a very basic example implementation of a grammatical evolution algorithm for formulating a recurrence pattern in a set of dates.
  ///  It needs significant extensions and optimizations to be useful in a production setting.
  /// </summary>
  static class Program
  {

    #region "Class hierarchy that codifies the grammar"

    class DatePattern
    {

      public Frequency frequency;
      public Bounds bounds;

      public override string ToString() { return "" + frequency + " " + bounds; }

      public IEnumerable<DateTime> Dates()
      {
        return frequency == null ? new DateTime[] { } : frequency.FilterDates(bounds.GetDates());
      }

    }

    abstract class Bounds
    {
      public abstract IEnumerable<DateTime> GetDates();
    }

    class YearBounds : Bounds
    {

      /* in the year .. */
      public int year;

      public override string ToString() { return "in the year " + year; }

      public override IEnumerable<DateTime> GetDates()
      {
        var firstDayOfYear = new DateTime(year, 1, 1);
        return Enumerable.Range(0, new DateTime(year, 12, 31).DayOfYear)
          .Select(dayOfYear => firstDayOfYear.AddDays(dayOfYear));
      }
    }

    abstract class Frequency
    {
      public abstract IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates);
    }

    class WeeklyFrequency : Frequency
    {

      /* every .. */
      public DayOfWeek dayOfWeek;

      public override string ToString() { return "every " + dayOfWeek; }

      public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
      {
        return Dates.Where(date => (date.DayOfWeek == dayOfWeek));
      }

    }

    class MonthlyFrequency : Frequency
    {

      /* every .. */
      public Ordinal ordinal;
      public DayOfWeek dayOfWeek;
      /* .. of the month */

      public override string ToString() { return "every " + ordinal + " " + dayOfWeek + " of the month"; }

      public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
      {
        return Dates.Where(date => (date.DayOfWeek == dayOfWeek) && (int)ordinal == (date.Day - 1) / 7);
      }

    }

    enum Ordinal { First, Second, Third, Fourth, Fifth }

    #endregion

    static Random random = new Random();
    const double MUTATION_RATE = 0.3;
    static Dictionary<Type, Type[]> subtypes = new Dictionary<Type, Type[]>();

    static void Main()
    {

      // The input signifies the recurrence 'every first thursday of the month in 2010':
      var input = new DateTime[] {new DateTime(2010,12,2), new DateTime(2010,11,4),new DateTime(2010,10,7),new DateTime(2010,9,2),
                    new DateTime(2010,8,5),new DateTime(2010,7,1),new DateTime(2010,6,3),new DateTime(2010,5,6),
                    new DateTime(2010,4,1),new DateTime(2010,3,4),new DateTime(2010,2,4),new DateTime(2010,1,7) };


      for (int cTests = 0; cTests < 20; cTests++)
      {
        // Initialize with a random population
        int treesize = 0;
        var population = new DatePattern[] { (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize) };
        Run(input, new List<DatePattern>(population));
      }
    }

    private static void Run(DateTime[] input, List<DatePattern> population)
    {
      var strongest = population[0];
      int strongestFitness = int.MinValue;
      int bestTry = int.MaxValue;
      for (int cGenerations = 0; cGenerations < 300 && strongestFitness < -100; cGenerations++)
      {
        // Select the best individuals to survive:
        var survivers = population
            .Select(individual => new { Fitness = Fitness(input, individual), individual })
            .OrderByDescending(pair => pair.Fitness)
            .Take(5)
            .Select(pair => pair.individual)
            .ToArray();
        population.Clear();

        // The survivers are the foundation for the next generation:
        foreach (var parent in survivers)
        {
          for (int cChildren = 0; cChildren < 3; cChildren++)
          {
            int treeSize = 1;
            DatePattern child = (DatePattern)Mutate(parent, ref treeSize); // NB: procreation may also be done through crossover.
            population.Add((DatePattern)child);

            var childFitness = Fitness(input, child);
            if (childFitness > strongestFitness)
            {
              bestTry = cGenerations;
              strongestFitness = childFitness;
              strongest = child;
            }

          }
        }
      }
      Trace.WriteLine("Found best match with fitness " + Fitness(input, strongest) + " after " + bestTry + " generations: " + strongest);

    }

    private static object Mutate(object original, ref int treeSize)
    {
      treeSize = 0;


      object replacement = Construct(original.GetType());
      foreach (var field in original.GetType().GetFields())
      {
        object newFieldValue = field.GetValue(original);
        int subtreeSize;
        if (field.FieldType.IsEnum)
        {
          subtreeSize = 1;
          if (random.NextDouble() <= MUTATION_RATE)
            newFieldValue = ConstructRandomEnumValue(field.FieldType);
        }
        else if (field.FieldType == typeof(int))
        {
          subtreeSize = 1;
          if (random.NextDouble() <= MUTATION_RATE)
            newFieldValue = (random.Next(2) == 0
            ? Math.Min(int.MaxValue - 1, (int)newFieldValue) + 1
            : Math.Max(int.MinValue + 1, (int)newFieldValue) - 1);
        }
        else
        {
          subtreeSize = 0;
          newFieldValue = Mutate(field.GetValue(original), ref subtreeSize); // mutate pre-maturely to find out subtreeSize

          if (random.NextDouble() <= MUTATION_RATE / subtreeSize) // makes high-level nodes mutate less.
          {
            subtreeSize = 0; // init so we can track the size of the subtree soon to be made.
            newFieldValue = Generate(field.FieldType, ref subtreeSize);
          }
        }
        field.SetValue(replacement, newFieldValue);
        treeSize += subtreeSize;
      }
      return replacement;

    }

    private static object ConstructRandomEnumValue(Type type)
    {
      var vals = type.GetEnumValues();
      return vals.GetValue(random.Next(vals.Length));
    }

    private static object Construct(Type type)
    {
      return type.GetConstructor(new Type[] { }).Invoke(new object[] { });
    }

    private static object Generate(Type type, ref int treesize)
    {
      if (type.IsEnum)
      {
        return ConstructRandomEnumValue(type);
      }
      else if (typeof(int) == type)
      {
        return random.Next(10) + 2005;
      }
      else
      {
        if (type.IsAbstract)
        {
          // pick one of the concrete subtypes:
          var subtypes = GetConcreteSubtypes(type);
          type = subtypes[random.Next(subtypes.Length)];
        }
        object newobj = Construct(type);

        foreach (var field in type.GetFields())
        {
          treesize++;
          field.SetValue(newobj, Generate(field.FieldType, ref treesize));
        }
        return newobj;
      }
    }


    private static int Fitness(DateTime[] input, DatePattern individual)
    {
      var output = individual.Dates().ToArray();
      var avgDateDiff = Math.Abs((output.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000)) - input.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000))));
      return
        -individual.ToString().Length // succinct patterns are preferred.
        - input.Except(output).Count() * 300 // Forgetting some of the dates is bad.
        - output.Except(input).Count() * 3000 // Spurious dates cause even more confusion to the user.
      - (int)(avgDateDiff) * 30000; // The difference in average date is the most important guide.
    }

    private static Type[] GetConcreteSubtypes(Type supertype)
    {
      if (subtypes.ContainsKey(supertype))
      {
        return subtypes[supertype];
      }
      else
      {

        var types = AppDomain.CurrentDomain.GetAssemblies().ToList()
            .SelectMany(s => s.GetTypes())
            .Where(p => supertype.IsAssignableFrom(p) && !p.IsAbstract).ToArray();
        subtypes.Add(supertype, types);
        return types;
      }
    }
  }

Hope this gets you on track. Be sure to share your actual solution somewhere; I think it will be quite useful in lots of scenarios.

Answer 2

If your purpose is to generate human-readable descriptions of the pattern, as in your "Every Monday in November", then you probably want to start by enumerating the possible descriptions. Descriptions can be broken down into frequency and bounds, for example,

Frequency:

• Every day ...
• Every other/third/fourth day ...
• Weekdays/weekends ...
• Every Monday ...
• Alternate Mondays ...
• The first/second/last Monday ...
• ...

Bounds:

• ... in January
• ... between 25 March and 25 October
• ...

There won't be all that many of each, and you can check for them one by one.