# Challenge: Longest Consecutive Sequence

Page 1 of 1

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

### #1 AdamSpeight2008

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

# Challenge: Longest Consecutive Sequence

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

• D.I.C Head

Reputation: 17
• Posts: 63
• 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

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• 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

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Challenge: Longest Consecutive Sequence

Posted 11 December 2011 - 04:49 AM

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

• D.I.C Head

Reputation: 17
• Posts: 63
• Joined: 14-March 10

## Re: Challenge: Longest Consecutive Sequence

Posted 11 December 2011 - 06:38 AM

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

Was This Post Helpful? 0

### #6 AdamSpeight2008

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• 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

• Cabbage

Reputation: 2388
• Posts: 5,013
• 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

• D.I.C Head

Reputation: 17
• Posts: 63
• 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

• Cabbage

Reputation: 2388
• Posts: 5,013
• 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

• D.I.C Head

Reputation: 17
• Posts: 63
• Joined: 14-March 10

## Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 03:32 AM

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

### #11 cfoley

• Cabbage

Reputation: 2388
• Posts: 5,013
• 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

• The Algorithmi

Reputation: 729
• 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

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 01:50 PM

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.
Was This Post Helpful? 1

### #14 cfoley

• Cabbage

Reputation: 2388
• Posts: 5,013
• Joined: 11-December 07

## Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 02:24 PM

No wonder my unit tests wouldn't pass!
Was This Post Helpful? 0

### #15 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: Challenge: Longest Consecutive Sequence

Posted 12 December 2011 - 06:13 PM

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

Was This Post Helpful? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }