How can I use LINQ to calculate the longest streak?

Question

Currently, this is just something I am curious about, I don't have any code I am working on but I am wondering how this could be achieved...

Lets say for example that I have an application that tracks the results of all the football teams in the world. What I want to be able to do is to identify the longest "win" streak for any given team.

I imagine I would most likely have some sort of data table like so:

• MatchDate datetime
• TeamA string
• TeamB string
• TeamAGoals int
• TeamBGoals int

So what I would want to do for example is find the longest win streak where TeamA = "My Team" and obviously this would mean TeamAGoals must be greater than TeamBGoals.

As I have said, this is all just for example. It may be better for a different DB design for something like this. But the root question is how to calculate the longest streak/run of matching results.

Answer 1

This is an old question now, but I just had to solve the same problem myself, and thought people might be interested in a fully LINQ implementation of Rawling's LongestStreak extension method. This uses Aggregate with a seed and result selector to run through the list.

    public static int LongestStreak<TSource>(
        this IEnumerable<TSource> source,
        Func<TSource, bool> predicate)
    {
        return source.Aggregate(
            new {Longest = 0, Current = 0},
            (agg, element) => predicate(element) ? 
                new {Longest = Math.Max(agg.Longest, agg.Current + 1), Current = agg.Current + 1} : 
                new {agg.Longest, Current = 0},
            agg => agg.Longest);
    }

Answer 2

There's no out-of-the-box LINQ method to count streaks, so you'll need a custom LINQy method such as

public static int LongestStreak<TSource>(
    this IEnumerable<TSource> source,
    Func<TSource, bool> predicate)
{
    int longestStreak = 0;
    int currentStreak = 0;
    foreach (TSource s in source)
    {
        if (predicate(s))
            currentStreak++;
        else
        {
            if (currentStreak > longestStreak) longestStreak = currentStreak;
            currentStreak = 0;
        }
    }
    if (currentStreak > longestStreak) longestStreak = currentStreak;
    return longestStreak;
}

Then, to use this, first turn each "match result" into a pair of "team results".

var teamResults = matches.SelectMany(m => new[] {
        new {
            MatchDate = m.MatchDate,
            Team = m.TeamA,
            Won = m.TeamAGoals > m.TeamBGoals },
        new {
            MatchDate = m.MatchDate,
            Team = m.TeamB,
            Won = m.TeamBGoals > m.TeamAGoals }
    });

Group these by team.

var groupedResults = teamResults.GroupBy(r => r.Team);

Then calculate the streaks.

var streaks = groupedResults.Select(g => new
    {
        Team = g.Key,
        StreakLength = g
            // unnecessary if the matches were ordered originally
            .OrderBy(r => r.MatchDate)
            .LongestStreak(r => r.Won)
    });

If you want the longest streak only, use MoreLinq's MaxBy; if you want them all ordered, you can use OrderByDescending(s => s.StreakLength).

Alternatively, if you want to do this in one pass, and assuming matches is already ordered, using the following class

class StreakAggregator<TKey>
{
    public Dictionary<TKey, int> Best = new Dictionary<TKey, int>();
    public Dictionary<TKey, int> Current = new Dictionary<TKey, int>();

    public StreakAggregator<TKey> UpdateWith(TKey key, bool success)
    {
        int c = 0;
        Current.TryGetValue(key, out c);
        if (success)
        {
            Current[key] = c + 1;
        }
        else
        {
            int b = 0;
            Best.TryGetValue(key, out b);
            if (c > b)
            {
                Best[key] = c;
            }
            Current[key] = 0;
        }
        return this;
    }

    public StreakAggregator<TKey> Finalise()
    {
        foreach (TKey k in Current.Keys.ToArray())
        {
            UpdateWith(k, false);
        }
        return this;
    }
}

you can then do

var streaks = teamResults.Aggregate(
    new StreakAggregator<string>(),
    (a, r) => a.UpdateWith(r.Team, r.Won),
    (a)    => a.Finalise().Best.Select(kvp => 
        new { Team = kvp.Key, StreakLength = kvp.Value }));

and OrderBy or whatever as before.

Answer 3

You can get all results of team with single query:

var results = from m in Matches
            let homeMatch = m.TeamA == teamName
            let awayMatch = m.TeamB == teamName
            let hasWon = (homeMatch && m.TeamAGoals > m.TeamBGoals) || 
                         (awayMatch && m.TeamBGoals > m.TeamAGoals)
            where homeMatch || awayMatch
            orderby m.MatchDate
            select hasWon;

Then just do simple calculation of longest streak:

int longestStreak = 0;
int currentStreak = 0;

foreach (var hasWon in results)
{
    if (hasWon)
    {
        currentStreak++;
        if (currentStreak > longestStreak)
            longestStreak = currentStreak;

        continue;
    }

    currentStreak = 0;
}

You can use it as is, extract to method, or create IEnumerable extension for calculating longest sequence in results.

Answer 4

You could make use of string.Split. Something like this:

int longestStreak = 
    string.Concat(results.Select(r => (r.ours > r.theirs) ? "1" : "0"))
          .Split(new[] { '0' })
          .Max(s => s.Length);

Or, better, create a Split extension method for IEnumerable<T> to avoid the need to go via a string, like this:

public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> items, Predicate<T> p)
{
    while (true)
    {
        items = items.SkipWhile(i => !p(i));
        var trueItems = items.TakeWhile (i => p(i)).ToList();
        if (trueItems.Count > 0)
        {
            yield return trueItems;
            items = items.Skip(trueItems.Count);
        }
        else
        {
            break;
        }
    }   
}

You can then simply do this:

int longestStreak = results.Split(r => r.ours > r.theirs).Max(g => g.Count());