LINQ Challenge #3 Answers in C#

Last week I posted my third LINQ Challenge. Thanks to everyone who attempted the puzzles. As usual I learned a lot from the different ways people attempted the puzzles. In this post I'll share how I solved the puzzles, and I've tried to take on board a few of the tips I picked up from looking at other people's approaches.

Problem 1 - Longest Sequence

The following string contains number of sales made per day in a month:

"1,2,1,1,0,3,1,0,0,2,4,1,0,0,0,0,2,1,0,3,1,0,0,0,6,1,3,0,0,0"

How long is the longest sequence of days without a sale? (in this example it's 4).

This puzzle was a tricky one, as we need to group on sequences within a sequence. The approach I took was to convert it into a string of Y's and N's based on whether there was a sale that day. Then I split the string on the letter 'Y', to leave me with a sequence of strings containing only the letter 'N'. The longest string is then the longest sequence of days without a sale.

"1,2,1,1,0,3,1,0,0,2,4,1,0,0,0,0,0,2,1,0,3,1,0,0,0"
    .Split(',')
    .Select(n => n == "0" ? "N":"Y")
    .Aggregate ("", (acc, next) => acc+next)
    .Split(new [] {'Y'}, StringSplitOptions.RemoveEmptyEntries)
    .Max(n=>n.Length)

Another way to solve it is to make use of the GroupAdjacent method from MoreLINQ. This lets you select a "key" for every element in the sequence, and then group the sequence up based on that key. So here I group the days sales totals into groups of "Y" and "N", and then I find the largest group whose key is "N":

sales
.Split(',')
.GroupAdjacent(n => n == "0" ? "N" : "Y")
.Where(g => g.Key == "N")
.Max(g => g.Count())

Problem 2 - Full House

In poker a hand is a "full house" if it contains three cards of one value and two of another value. The following string defines five poker hands, separated by a semicolon:

"4♣ 5♦ 6♦ 7♠ 10♥;10♣ Q♥ 10♠ Q♠ 10♦;6♣ 6♥ 6♠ A♠ 6♦;2♣ 3♥ 3♠ 2♠ 2♦;2♣ 3♣ 4♣ 5♠ 6♠".

Write a LINQ expression that returns an sequence containing only the "full house" hands.

We can detect if a string representing a single hand is a full house by grouping on the card value (we can cheat by just looking at the first character which is always unique - which was a nice optimization from Mark Jones). Then it's a full house if our hand only contains groups of size 2 or 3.

"4♣ 5♦ 6♦ 7♠ 10♥;10♣ Q♥ 10♠ Q♠ 10♦;6♣ 6♥ 6♠ A♠ 6♦;2♣ 3♥ 3♠ 2♠ 2♦;2♣ 3♣ 4♣ 5♠ 6♠"
    .Split(';')
    .Where(hand => hand.Split(' ')
                       .GroupBy(value => value[0])
                       .All(g => g.Count() == 2 || g.Count() == 3))

Problem 3 - Christmas Days

What day of the week is Christmas day (25th December) on for the next 10 years (starting with 2018)? The answer should be a string (or sequence of strings) starting: Tuesday,Wednesday,Friday,...

This one was a nice easy one, meant to highlight the usefulness of the Enumerable.Range method which lets you specify a starting number and the number of elements in the sequence. We can then construct a new DateTime, and access the DayOfWeek property:

String.Join(",", Enumerable.Range(2018,10)
    .Select(y => new DateTime(y,12,25))
    .Select(d => d.DayOfWeek))

Problem 4 - Anagrams

From the following dictionary of words,

"parts,traps,arts,rats,starts,tarts,rat,art,tar,tars,stars,stray"

return all words that are an anagram of star (no leftover letters allowed).

The key to solving this challenge is realizing that if you sort the letters in the words into alphabetical order, those that are anagrams will all have the same value (in this case arst). This allows us to do a simple filter on the sorted values of each string

"parts,traps,arts,rats,starts,tarts,rat,art,tar,tars,stars,stray"
    .Split(',')
    .Where(x => new string(x.OrderBy(c => c).ToArray()) == "arst")

By the way, this is a good example of where a C# 7 "local function" can help readability. If we define our own local Sort method that sorts a string, the LINQ expression becomes more readable:

string Sort(string s) => new string(s.OrderBy(c => c).ToArray());
"parts,traps,arts,rats,starts,tarts,rat,art,tar,tars,stars,stray"
    .Split(',')
    .Where(x => Sort(x) == Sort("star"))

Problem 5 - Initial Letters

From the following list of names

"Santi Cazorla, Per Mertesacker, Alan Smith, Thierry Henry, Alex Song, Paul Merson, Alexis Sánchez, Robert Pires, Dennis Bergkamp, Sol Campbell"

find any groups of people who share the same initials as each other.

This was a fairly simple grouping problem. I learned from Mark Jones' answer that there is an overload of String.Split that allows us to split on a string ", " which saves us trimming the space as a second step after splitting on comma.

We then just group by the initials, using String.Join to construct them out of the first letter of each part of the name, and then filter out any groups with only one element:

names
    .Split(new[] { ", "},StringSplitOptions.None)
    .GroupBy(n => String.Join("", n.Split(' ').Select(p => p[0])))
    .Where(g => g.Count() > 1)

Problem 6 - Video Editing

A video is two hours long exactly, and we want to make some edits, cutting out the following time ranges (expressed in H:MM:SS):

"0:00:00-0:00:05;0:55:12-1:05:02;1:37:47-1:37:51".

(You can assume that the input ranges are in order and contain no overlapping portions)

We would like to turn this into a sequence of time-ranges to keep. So in this example, the output should be:

"0:00:05-0:55:12;1:05:02-1:37:47;1:37:51-2:00:00"

This one was a tricky one, and I was intending to show the value of MoreLINQ's Batch, Prepend and Append methods. The approach I am taking is treating every time as simply an edit point, and then by appending an extra element to the start and end of the list, we can then group them up into pairs (with Batch) and then filter out any empty ranges before joining it all together.

Here's the approach with MoreLINQ:

"0:00:00-0:00:05;0:55:12-1:05:02;1:37:47-1:37:51"
    .Split(';', '-')
    .Prepend("0:00:00")
    .Append("2:00:00")
    .Batch(2, b => b.ToArray())
    .Where(a => a[0] != a[1])
    .Select(a => $"{a[0]}-{a[1]}")
    .Aggregate((x, y) => x + ";" + y)

However, there is a problem with some MoreLINQ extension method names clashing with LINQ methods. For example, the Prepend and Append methods are new in .NET 4.7.1. This is something the MoreLINQ maintainers are aware of and the workaround is to explictly enable only the MoreLINQ extension methods you plan to use with the following syntax (there's an "extension" per MoreLINQ method):

using static MoreLinq.Extensions.BatchExtension;

Now the code will compile in .NET 4.7.1 (and use LINQ's built-in Prepend and Append) but it does mean that if you wanted to use any other MoreLINQ methods (such as ToDelimitedString instead of Aggregate) you'd need to add another using static statement

using static MoreLinq.Extensions.ToDelimitedStringExtension;

...

.ToDelimitedString(";")

Of course you can create a pure LINQ solution to this problem, but it needs a bit of a hack to batch into groups of two:

"0:00:00-0:00:05;0:55:12-1:05:02;1:37:47-1:37:51"
    .Split(';','-')
    .Prepend("0:00:00")
    .Append("2:00:00")

    // ugly way to batch
    .Select((item, index) => new { item, index })
    .GroupBy(x => x.index / 2)
    .Select(g => g.Select(x => x.item).ToArray())

    // eliminate empty ranges
    .Where(a => a[0] != a[1])

    .Select(a => $"{a[0]}-{a[1]}")
    .Aggregate ((x, y) => x + ";" + y)

Hear me speak on LINQ at Techorama

Finally, on 3rd October 2018 I'll be speaking on LINQ at Techorama. Do come and say hello if you can make it.