14 Replies - 16566 Views - Last Post: 12 December 2011 - 06:13 PM

#1 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Challenge: Longest Consecutive Sequence

Post icon  Posted 10 December 2011 - 09:57 AM

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


Is This A Good Question/Topic? 3
  • +

Replies To: Challenge: Longest Consecutive Sequence

#2 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Challenge: Longest Consecutive Sequence

Posted 10 December 2011 - 04:13 PM

LCSeq:
Spoiler


My own testing code:
Spoiler

Attached File(s)


Was This Post Helpful? 1
  • +
  • -

#3 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Re: Challenge: Longest Consecutive Sequence

Posted 11 December 2011 - 04:27 AM

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


I'll add the testing code later.

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

Was This Post Helpful? 0
  • +
  • -

#4 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Re: Challenge: Longest Consecutive Sequence

Posted 11 December 2011 - 04:49 AM

Tethik: Fails on the following. :no:
{1, 3, 5, 7, 9, 0, 1, 2}




The testing my implementations.
Spoiler

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

Was This Post Helpful? 1
  • +
  • -

#5 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Challenge: Longest Consecutive Sequence

Posted 11 December 2011 - 06:38 AM

View PostAdamSpeight2008, 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.

View PostAdamSpeight2008, on 11 December 2011 - 04:49 AM, said:

Tethik: Fails on the following. :no:
{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

Was This Post Helpful? 0
  • +
  • -

#6 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Re: Challenge: Longest Consecutive Sequence

Posted 11 December 2011 - 07:41 AM

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)
Was This Post Helpful? 0
  • +
  • -

#7 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: Challenge: Longest Consecutive Sequence

Posted 11 December 2011 - 08:09 PM

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


And a quick test module:

Spoiler


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

Spoiler

Was This Post Helpful? 1
  • +
  • -

#8 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Challenge: Longest Consecutive Sequence

Posted 11 December 2011 - 09:16 PM

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

Attached File(s)


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

Was This Post Helpful? 0
  • +
  • -

#9 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 01:52 AM

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.
Was This Post Helpful? 0
  • +
  • -

#10 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 03:32 AM

View Postcfoley, 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.
Was This Post Helpful? 0
  • +
  • -

#11 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 04:22 AM

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.
Was This Post Helpful? 0
  • +
  • -

#12 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 09:53 AM

I dont get it. in the last example shouldn't 0001 => 01 instead of 0?
Was This Post Helpful? 1
  • +
  • -

#13 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 01:50 PM

View Postmostyfriedman, 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.
Was This Post Helpful? 1
  • +
  • -

#14 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 02:24 PM

No wonder my unit tests wouldn't pass! :P
Was This Post Helpful? 0
  • +
  • -

#15 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 06:13 PM

View PostAdamSpeight2008, on 12 December 2011 - 11:50 PM, said:

View Postmostyfriedman, 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 :P. Anyway this is a simpler version of the longest increasing subsequence problem, but since I don't know VB.NET, I'll shut up :P.

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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1