[AdamSpeight2008]

Challenge: Longest Consecutive Sequence.

Definition:
Write a generic function that return the longest consecutive sequence contained within a source sequence.

Examples

 { 1, 2, 3, 0, 1 } => { 1, 2, 3 }
 ABABCERSTU => RSTU
 00001 => 0

To ensure compatibility and consistency between different entries, all entries must implement the following interface.
This is available via NuGet: DIC Challenge Longest Consecutive Sequence
Minimum .Net Framework:= .net 3.5 (Client Profile)

Interface

  ''' <summary>
  ''' the Interface required for the Challege: Longest Consecutive Sequence.
  ''' </summary>
  ''' <typeparam name="T">The Generic Type Parameter</typeparam>
  ''' <param name="Source">The Source IEnumerable</param>
  ''' <param name="SeqPred">Used to determing the consectiviness of the sequence.</param>
  ''' <returns>An IEnumerable containing the longest consecutive sequence contained in the source.</returns>
  ''' <remarks></remarks>
  Function LCSeq(Of T)(Source As IEnumerable(Of T), SeqPred As Func(Of T, T, Boolean)) As IEnumerable(Of T)

This post has been edited by AdamSpeight2008: 10 December 2011 - 10:25 AM

[Tethik]

LCSeq:

Spoiler

    ''' <summary>
    ''' the Interface required for the Challege: Longest Consecutive Sequence.
    ''' </summary>
    ''' <typeparam name="T">The Generic Type Parameter</typeparam>
    ''' <param name="Source">The Source IEnumerable</param>
    ''' <param name="SeqPred">Used to determing the consectiviness of the sequence.</param>
    ''' <returns>An IEnumerable containing the longest consecutive sequence contained in the source.</returns>
    ''' <remarks></remarks>
    Function LCSeq(Of T)(ByVal Source As IEnumerable(Of T), ByVal SeqPred As Func(Of T, T, Boolean)) As IEnumerable(Of T)
        If Source Is Nothing OrElse Source.Count() <= 0 Then
            Return Nothing
        Else
            Dim history As New List(Of T)
            Dim iterator As IEnumerator(Of T) = Source.GetEnumerator()
            iterator.MoveNext()
            history.Add(iterator.Current)

            While iterator.MoveNext()

                If Not SeqPred(history.Last(), iterator.Current) Then
                    Exit While
                Else
                    history.Add(iterator.Current)
                End If
            End While

            If Not iterator.MoveNext() Then '' We've gone thru the whole list
                Return history.ToArray()
            End If

            Dim recursive As IEnumerable(Of T) = LCSeq(Source.Skip(history.Count), SeqPred)


            Return IIf(recursive.Count() > history.Count(), recursive, history.ToArray())
        End If
    End Function

My own testing code:

Spoiler

    Function SeqPred(Of T)(ByVal arg1 As IComparable(Of T), ByVal arg2 As IComparable(Of T)) As Boolean
        Return (arg1.CompareTo(arg2) = -1)
    End Function

    Function SeqPred01(ByVal arg1 As Char, ByVal arg2 As Char) As Boolean
        Return IIf(IsNumeric(arg1) And IsNumeric(arg2), False, SeqPred(arg1, arg2))
    End Function

    Sub Write(Of T)(ByRef enumerable As IEnumerable(Of T))
        If enumerable Is Nothing Then
            Console.Write("{ }")
            Return
        End If

        Console.Write("{ ")
        Dim numerator As IEnumerator = enumerable.GetEnumerator()
        While numerator.MoveNext()
            Console.Write(numerator.Current.ToString() & " ")
        End While


        Console.Write(" }")
    End Sub

    Sub TestLCSeq(Of T As IComparable)(ByRef list As IEnumerable(Of T))
        TestLCSeq(list, AddressOf SeqPred(Of T))
    End Sub

    Sub TestLCSeq(Of T As IComparable)(ByRef list As IEnumerable(Of T), ByVal func As Func(Of T, T, Boolean))
        Write(list)

        Dim result As IEnumerable(Of T) = LCSeq(list, func)
        Console.Write(" => ")

        Write(result)
        Console.WriteLine()
    End Sub


    Sub Main()
        '' Unit tests I guess
        '' SeqPred:
        '' 
        Console.WriteLine("SeqPred1: " & SeqPred(1, 2))
        Console.WriteLine("SeqPred2: " & Not SeqPred(1, 1))
        Console.WriteLine("SeqPred3: " & Not SeqPred(2, 2))
        Console.WriteLine("SeqPred4: " & SeqPred("a", "b"))
        Console.WriteLine("SeqPred4: " & Not SeqPred("a", "c"))

        Dim numbers As Integer() = {1, 2, 3, 0, 1}


        TestLCSeq("") ' Default case
        TestLCSeq("a") ' 
        TestLCSeq("abcdef") ' whole word
        TestLCSeq("abcABCD") ' ending subset
        TestLCSeq("abcABC") ' two same
        TestLCSeq(numbers)
        TestLCSeq("ABABCERSTU")
        TestLCSeq("00001", AddressOf SeqPred01)
        Console.WriteLine()

        While (True)
            Console.ReadKey()
        End While
    End Sub

Attached File(s)

•  Module1.zip (1.23K)
  Number of downloads: 101

[AdamSpeight2008]

Tethik: You could have made it easier for me to test by using the NuGet version, has it keeps the interface in the same Namespace. Thus I could use MEF to import them various implementation DLLs, and test each sequentially. Never mind I figure out a way and check it later.

Any how, I've done an implementation.

Spoiler

About 23 LoC in total.

Public Class _AdamSpeight2008
  Implements DreamInCode_Challenges_LCSec.LCSeq

  Public Function LCSeq(Of T)(Source As IEnumerable(Of T), SeqPred As Func(Of T, T, Boolean)) As IEnumerable(Of T) Implements DreamInCode_Challenges_LCSec.LCSeq.LCSeq
    Return Source.GetLongestConsecutiveSeq(SeqPred)
  End Function
End Class

the minimum set of extension methods (for it to work.)

Spoiler

Public Module LCSeq_Stuff
  <Extension()> Function GetLongestConsecutiveSeq(Of T)(Source As IEnumerable(Of T), SeqPred As Func(Of T, T, Boolean)) As IEnumerable(Of T)
    If Source Is Nothing Then Throw New ArgumentNullException("Source can not be null")
    If SeqPred Is Nothing Then Throw New ArgumentNullException("SeqPred can not be null")
    Return (From seq In Source.Select(Function(c, i) Source.Skip(i).LongestConsecutive(SeqPred)) Order By seq.Count Descending).FirstOrDefault
  End Function

  <Extension()> Function LongestConsecutive(Of t)(Source As IEnumerable(Of t), SeqPred As Func(Of t, t, Boolean)) As IEnumerable(Of t)
    If Source Is Nothing Then Throw New ArgumentNullException("Source can not be null")
    If SeqPred Is Nothing Then Throw New ArgumentNullException("SeqPred can not be null")
    Return Source.TakeWhile(Function(p, i) If(i = 0, True, SeqPred(Source(i - 1), p)))
  End Function

  <Extension()> Public Function SlidingFrame(Of T)(Source As IEnumerable(Of T), FrameSize As Integer) As IEnumerable(Of IEnumerable(Of T))
    If Source Is Nothing Then Throw New ArgumentNullException("Source can not be null.")
    If FrameSize < 1 Then Throw New ArgumentOutOfRangeException("FrameSize can not be less than one (1)")
    If FrameSize > Source.Count Then Throw New ArgumentOutOfRangeException("FrameSize can not be more that the length of the Source")
    Return From i In Enumerable.Range(0, (Source.Count - FrameSize) + 1) Select Source.Skip(i).Take(FrameSize)
  End Function

End Module

The Sanity Checks on the method arguments is more LOC than code need to perform the task?!

I'll add the testing code later.

This post has been edited by AdamSpeight2008: 11 December 2011 - 04:50 AM

[AdamSpeight2008]

Tethik: Fails on the following.

{1, 3, 5, 7, 9, 0, 1, 2}

The testing my implementations.

Spoiler

Uses: TTF (Tiny Testing Framework)

    Dim nums = {1, 3, 5, 7, 9, 0, 1, 2}
    Dim TestingThisMethod = New Func(Of IEnumerable(Of Integer), Func(Of Integer, Integer, Boolean), IEnumerable(Of Integer)) _
                                 (AddressOf (New _AdamSpeight2008).LCSeq(Of Integer))
    Dim res = TTF.Testing._TimeNVerify(Of IEnumerable(Of Integer))(MethodUnderTest:=TestingThisMethod,
               args:={nums, New Func(Of Integer, Integer, Boolean)(Function(p, c) (c - p) = 1)},
               ReturnResult:=True,
               TestAlso:=True,
               WhatIsExpected:={0, 1, 2})

Verbosity Explicitness Coding.
Well what do expect for a Single Generic Test Function.

The test results are contained in the variable res

res	{TTF.Timings.ValidResultTiming(Of System.Collections.Generic.IEnumerable(Of Integer))}	TTF.Timings.Timing
-		TTF.Timings.ValidResultTiming(Of System.Collections.Generic.IEnumerable(Of Integer))	{TTF.Timings.ValidResultTiming(Of System.Collections.Generic.IEnumerable(Of Integer))}	TTF.Timings.ValidResultTiming(Of System.Collections.Generic.IEnumerable(Of Integer))
-		Result	In-Memory Query	<enumerable type>
-		Results	Expanding will process the collection	<enumerable type>
		(0)	0	Integer
		(1)	1	Integer
		(2)	2	Integer
-		TimeTaken	{00:00:00.0134562}	System.TimeSpan
		Valid	True	Boolean

This post has been edited by AdamSpeight2008: 11 December 2011 - 05:54 AM

[Tethik]

AdamSpeight2008, on 11 December 2011 - 04:27 AM, said:

Tethik: You could have made it easier for me to test by using the NuGet version, has it keeps the interface in the same Namespace. Thus I could use MEF to import them various implementation DLLs, and test each sequentially. Never mind I figure out a way and check it later.

I'm using Visual Studio 2008 (for work reasons) and I don't think NuGet is available for it. If theres some way I can make it easier for you without using NuGet then I'll do that.

AdamSpeight2008, on 11 December 2011 - 04:49 AM, said:

Tethik: Fails on the following.

{1, 3, 5, 7, 9, 0, 1, 2}

I'll check it out.

Edit: Found the problem. For some reason I thought IComparable.CompareTo returned the difference.

This post has been edited by Tethik: 11 December 2011 - 06:51 AM

[AdamSpeight2008]

Sometime is difference, (Char I think)

See Tutorial: Custom Sorting

Basic Rules to follow when implementing IComparable
z = x.ComparedTo(y)

x = y => z = 0
x < y => z < 0 (Note: Doesn't have to be -1)
x > y => z > 0 (Note: Doesn't have to be 1)

[cfoley]

I couldn't find the package manager in VB express. Hope it's OK to copy and paste the method header.

Here is my attempt. I went for simple concise code, and possibly sacrificed a bit of efficiency to not repeat code:

Spoiler

Class Cfoley

    Function LCSeq(Of T)(ByVal Source As IEnumerable(Of T), ByVal SeqPred As Func(Of T, T, Boolean)) As IEnumerable(Of T)
        Dim result As New List(Of T)
        Dim seq As New List(Of T)

        For Each X In Source
            Dim isNewSegment = seq.Any AndAlso Not SeqPred(seq.Last, X)
            If isNewSegment Then seq = New List(Of T)
            seq.Add(X)
            If seq.Count > result.Count Then result = seq
        Next

        Return result
    End Function

End Class

And a quick test module:

Spoiler

Module Test

    Sub Main()
        Dim testSets()() = New Integer()() {
            New Integer() {}, New Integer() {1}, New Integer() {1, 3, 5},
            New Integer() {1, 2}, New Integer() {1, 2, 4}, New Integer() {1, 2, 4, 5},
            New Integer() {1, 3, 4}, New Integer() {1, 2, 4, 5, 6, 8, 9}, New Integer() {0, 0, 0, 1},
            New Integer() {1, 3, 5, 7, 9, 0, 1, 2}
        }

        For Each seq In testSets
            Trace(seq)
        Next
        Console.ReadLine()
    End Sub

    Private Sub Trace(ByVal seq As IEnumerable(Of Integer))
        Dim answer = New Cfoley().LCSeq(seq, AddressOf areConsecutiveInts)
        Console.WriteLine(asStr(seq) & " " & asStr(answer))
    End Sub

    Private Function areConsecutiveInts(ByVal a As Integer, ByVal b As Integer) As Boolean
        Return a + 1 = b
    End Function

    Private Function asStr(Of T)(ByVal seq As IEnumerable(Of T)) As String
        Return "{" & String.Join(" ", seq) & "}"
    End Function

End Module

And another module with me playing with the definitions of a contiguous sequence:

Spoiler

Module Playing
    Private Function areEqual(Of E)(ByVal a As E, ByVal b As E) As Boolean
        Return a.Equals(B)/>
    End Function

    Private Function alwaysGreater(ByVal a As IComparable, ByVal b As IComparable) As Boolean
        Return a.CompareTo(B)/> < 0
    End Function

    Private Function neverSmaller(ByVal a As IComparable, ByVal b As IComparable) As Boolean
        Return a.CompareTo(B)/> <= 0
    End Function

    Sub Main()
        Dim sequence = "aabbbcdefgbcdefffffffff".ToCharArray
        Trace("Are equal     ", sequence, AddressOf areEqual)
        Trace("Always greater", sequence, AddressOf alwaysGreater)
        Trace("Never smaller ", sequence, AddressOf neverSmaller)
        Console.ReadLine()
    End Sub

    Private Sub Trace(Of T)(ByVal message As String, ByVal seq As IEnumerable(Of T), ByVal SeqPred As Func(Of T, T, Boolean))
        Dim answer = New Cfoley().LCSeq(seq, SeqPred)
        Console.WriteLine(message & " " & asStr(seq) & " " & asStr(answer))
    End Sub

    Private Function asStr(Of T)(ByVal seq As IEnumerable(Of T)) As String
        Return "{" & String.Join("", seq) & "}"
    End Function

End Module

[Tethik]

Changing SeqPred to the following or writing separate SeqPred functions for each type fixes my problem:
From

Function SeqPred(Of T)(ByVal arg1 As IComparable(Of T), ByVal arg2 As IComparable(Of T)) As Boolean
     Return (arg1.CompareTo(arg2) = -1)
End Function

To

Function SeqPred(Of T)(ByVal arg1 As IComparable(Of T), ByVal arg2 As IComparable(Of T)) As Boolean
    Return (Convert.ToInt32(arg1) - Convert.ToInt32(arg2) = -1)
End Function

I did some restructuring as well:

Spoiler

New class. Hopefully implementing the right interface:

Spoiler

Public Class Tethik
    Implements DreamInCode_Challenges_LCSec.LCSeq

    ''' <summary>
    ''' the Interface required for the Challege: Longest Consecutive Sequence.
    ''' </summary>
    ''' <typeparam name="T">The Generic Type Parameter</typeparam>
    ''' <param name="Source">The Source IEnumerable</param>
    ''' <param name="SeqPred">Used to determing the consectiviness of the sequence.</param>
    ''' <returns>An IEnumerable containing the longest consecutive sequence contained in the source.</returns>
    ''' <remarks></remarks>
    Public Function LCSeq(Of T)(ByVal Source As IEnumerable(Of T), ByVal SeqPred As Func(Of T, T, Boolean)) As IEnumerable(Of T) Implements DreamInCode_Challenges_LCSec.LCSeq.LCSeq


        ' Could throw exceptions here instead, just have to make sure recursion still works.
        If Source Is Nothing OrElse Source.Count() <= 0 Then Return Nothing

        ' I don't like that I m creating a new list every time... maybe I ll fix that later..
        Dim history As New List(Of T)
        Dim iterator As IEnumerator(Of T) = Source.GetEnumerator()

        While iterator.MoveNext()
            If Not history.Count = 0 AndAlso Not SeqPred(history.Last(), iterator.Current) Then Exit While

            history.Add(iterator.Current)
        End While

        If Not iterator.MoveNext() Then Return history.ToArray() '' We've gone thru the whole list

        Dim recursive As IEnumerable(Of T) = LCSeq(Source.Skip(history.Count), SeqPred) '' Check the rest of the list recursively.

        Return IIf(recursive.Count() > history.Count(), recursive, history.ToArray()) '' Return the longest

    End Function

End Class

Testing code moved to new module:

Spoiler

Module Testing

    ''' <summary>
    ''' Converts arg1 and arg2 to Integers and checks for consecutiveness. 
    ''' </summary>
    Function SeqPred(Of T)(ByVal arg1 As IComparable(Of T), ByVal arg2 As IComparable(Of T)) As Boolean
        Return (Convert.ToInt32(arg1) - Convert.ToInt32(arg2) = -1)
    End Function

    ''' <summary>    
    ''' Checks for consecutivness but never between numbers.
    ''' </summary>
    Function SeqPred01(ByVal arg1 As Char, ByVal arg2 As Char) As Boolean
        Return IIf(IsNumeric(arg1) And IsNumeric(arg2), False, SeqPred(arg1, arg2))
    End Function

    ''' <summary>
    ''' Tests LCSeq with default SeqPred function
    ''' </summary>
    Sub TestLCSeq(Of T As IComparable)(ByRef list As IEnumerable(Of T))
        TestLCSeq(list, AddressOf SeqPred(Of T))
    End Sub

    ''' <summary>
    ''' Tests LCSeq, writing input and result to console.
    ''' </summary>
    Sub TestLCSeq(Of T As IComparable)(ByRef list As IEnumerable(Of T), ByVal func As Func(Of T, T, Boolean))
        Write(list)

        Dim result As IEnumerable(Of T) = (New Tethik).LCSeq(list, func)
        Console.Write(" => ")

        Write(result)
        Console.WriteLine()
    End Sub

    ''' <summary>
    ''' Writes IEnumerable to Console.
    ''' </summary>
    Sub Write(Of T)(ByRef enumerable As IEnumerable(Of T))
        If enumerable Is Nothing Then
            Console.Write("{ }")
            Return
        End If

        Console.Write("{ ")

        Dim numerator As IEnumerator = enumerable.GetEnumerator()
        While numerator.MoveNext()
            Console.Write(numerator.Current.ToString() & " ")
        End While

        Console.Write(" }")
    End Sub

    Sub Main()
        '' Unit tests I guess
        '' SeqPred:
        '' 
        Console.WriteLine("SeqPred1: " & SeqPred(1, 2))
        Console.WriteLine("SeqPred2: " & Not SeqPred(1, 1))
        Console.WriteLine("SeqPred3: " & Not SeqPred(2, 2))
        Console.WriteLine("SeqPred4: " & SeqPred("a"c, "b"c))
        Console.WriteLine("SeqPred4: " & Not SeqPred("a"c, "c"c))

        Dim numbers As Integer() = {1, 2, 3, 0, 1}
        Dim numbers2 As Integer() = {1, 3, 5, 7, 9, 0, 1, 2}


        TestLCSeq("") ' Default case
        TestLCSeq("a") ' 
        TestLCSeq("aa")
        TestLCSeq("abcdef") ' whole word
        TestLCSeq("abcABCDFFF") ' ending subset
        TestLCSeq("abcABC") ' two same
        TestLCSeq(numbers)
        TestLCSeq(numbers2)
        TestLCSeq("ABABCERSTU")
        TestLCSeq("00001", AddressOf SeqPred01)
        Dim evil As String = Nothing
        TestLCSeq(evil)
        Console.WriteLine()

        While (True)
            Console.ReadKey()
        End While
    End Sub
End Module

Attached File(s)

•  Tethik.zip (1.82K)
  Number of downloads: 51

This post has been edited by Tethik: 11 December 2011 - 09:22 PM

[cfoley]

Tethik, The fixes your problem with regards to ints, but what if you want to find consecutive sequences of Strings or dates or verses of 99 bottles of beer on the wall? A generic method will let you do that but the SeqPred method will have to be specific to the data type, and possibly the definition of consecutive that matches your problem.

[Tethik]

cfoley, on 12 December 2011 - 01:52 AM, said:

Tethik, The fixes your problem with regards to ints, but what if you want to find consecutive sequences of Strings or dates or verses of 99 bottles of beer on the wall? A generic method will let you do that but the SeqPred method will have to be specific to the data type, and possibly the definition of consecutive that matches your problem.

Well yeah, if it can't be casted to an int or the int cast has nothing to do with its consecutiveness then it won't work. Theres only that much a generic function will do in this case. For non-primitive types you'll have to make a new SeqPred.

[cfoley]

I'm no expert in VB, but my take on it is if the comparison logic could be coded in a generic way then you wouldn't need a delegate to handle it. i.e. it could be hard coded in the LCSeq method.

The logic is specific to the type. That means you have separate delegates for integers, dates, Strings and whatever else you need. It seems like hard work but really it isn't. You code the LCSeq method and maybe 1 or 2 delegates for common cases. This allows another developer to reuse your LCSeq method with any class and all he has to do is provide a delegate defining what a sequence means to him.

It's more powerful than this, though. What if you want to define a descending sequence? Write a delegate. What if you want to define a contiguous sequence as repeated instances of the same item? It may not be the original intent of the method but you can coax it into doing it by writing another delegate. The list goes on.

Feel free to take a look at my entry to see what I mean.

[mostyfriedman]

I dont get it. in the last example shouldn't 0001 => 01 instead of 0?

[AdamSpeight2008]

mostyfriedman, on 12 December 2011 - 05:53 PM, said:

I dont get it. in the last example shouldn't 0001 => 01 instead of 0?

Yep.
I shall claim it was deliberate to see if reader were paying attention.

[cfoley]

No wonder my unit tests wouldn't pass!

[mostyfriedman]

AdamSpeight2008, on 12 December 2011 - 11:50 PM, said:

mostyfriedman, on 12 December 2011 - 05:53 PM, said:

I dont get it. in the last example shouldn't 0001 => 01 instead of 0?

Yep.
I shall claim it was deliberate to see if reader were paying attention.

yea, right . Anyway this is a simpler version of the longest increasing subsequence problem, but since I don't know VB.NET, I'll shut up .

This post has been edited by mostyfriedman: 12 December 2011 - 07:44 PM