Coding puzzle

virang_21

I had a requirement which looked like a coding puzzle. Something so intuitive to us humans is hard to express in programming term. Well not so hard but something that makes you think. So here is the deal. Given a list of integers split list into series of sub lists.Each sub list contains consecutive digits until digit in input list is not equal to previous digit plus one. At that point start new sub list. List lstInput = new List(){1,2,3,5,6,7,22}; Sub lists should be {1,2,3} {5,6,7} {22} Here is my not so elegant solution My Not So Elegant Solution [^] Smart minds of CP it is your opportunity to show your genius. I know you can make it more elegant.

Zen and the art of software maintenance : rm -rf * Maths is like love : a simple idea but it can get complicated.

PIEBALDconsult

Ah, so the Friday Programming Challenge is being revived, but on Wednesday? I'd start with a List<List<int>>

Initialize list
Set index to 0
Iterate input values
If test fails
Add a new List
Increment index
List [ index ].Add ( value )

Maybe I'll write it later, maybe I won't. Now I'll have a look at yours... Here's mine:

private static System.Collections.Generic.List<System.Collections.Generic.List<int>>
Split
(
System.Collections.Generic.IList<int> values
)
{
System.Collections.Generic.List<System.Collections.Generic.List<int>> result =
new System.Collections.Generic.List<System.Collections.Generic.List<int>>() ;

if ( ( values != null ) && ( values.Count > 0 ) )
{
result.Add ( new System.Collections.Generic.List<int>() ) ;

int l = 0 ;

result \[ l \].Add ( values \[ 0 \] ) ;

for ( int i = 1 ; i < values.Count ; i++ )
{
  if ( values \[ i \] - values \[ i - 1 \] != 1 )
  {
    result.Add ( new System.Collections.Generic.List<int>() ) ;

    l++ ;
  }

  result \[ l \].Add ( values \[ i \] ) ;
}

}

return ( result ) ;
}

ImHere2Learn

I'm learning ES6:

function* consec(array) {
let arr = array.splice(0);

while (arr.length > 0) {
	let nextSeqIndex = arr.findIndex((v, i, a) => v != a\[0\] + i);
	
	if (nextSeqIndex === -1) return yield arr;
	
	yield arr.splice(0, nextSeqIndex);
}

}

let array = [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 22];

for (let sub of consec(array)) {
console.log(sub);
}

code@repl.it[^]

Staffan Bruun

Use Linq:

using System.Linq;

// ...

List> output = lstInput
.Select((n,ix)=>new {n, ix})
.GroupBy(p=>p.ix / 3, p=>p.n)
.Select(g=>g.ToList())
.ToList();
Never mind, I didn't read the post completely, sorry. :doh:

Staffan Bruun

OK here is my improved solution, using Linq:

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
public static void Main()
{
List<int> lstInput = new List<int>(){1,2,3,4,5,6,7,9,10,11,22};

    var aggResult = lstInput
    .Aggregate(new 
        { 
            last = lstInput.First()-1, 
            result = new List<List<int>>(), 
            current = new List<int>()
        }, 
        (agg, n)=>
        {
            List<int> current = agg.current;

	if(n != agg.last + 1)
	{
	    agg.result.Add(current);
	    current = new List<int>();
	}

	current.Add(n);
			
            return new {last = n, result = agg.result, current};
    });

    if(aggResult.current.Count > 0)
    {
        aggResult.result.Add(aggResult.current);
    }

    Console.Out.WriteLine(
        "{{{0}}}",
        string.Join(
            "},{", 
            aggResult.result.Select(o=>string.Join(",", o.Select(e=>e.ToString())))
        )
    );
}

}

Not sure it's any more elegant, though... :sigh:

Kenneth Haugland

Perhaps come old fashioned coding like this:

private List<List<int>> GetList(List<int> Input)
{
List<List<int>> Result = new List<List<int>>();
List<int> CurrentList = new List<int>();

CurrentList.Add(Input\[0\]);
for (int i = 1; i < Input.Count; i++)
{
    if (Input\[i\] == (Input\[i - 1\] + 1))
        CurrentList.Add(Input\[i\]);
    else
    {
        Result.Add(CurrentList);
        CurrentList = new List<int>();
        CurrentList.Add(Input\[i\]);
    }
}

if (CurrentList.Count != 0)
    Result.Add(CurrentList);

return Result;

}

Mycroft Holmes

Staffan Bruun wrote:

Not sure it's any more elegant, though

Comparing this dogs breakfast to kenneths I know which one I would want to support. I use Linq quite a bit but only for the simplest things. Once you get into aggregates I start looking for other options.

Never underestimate the power of human stupidity RAH

Staffan Bruun

Yeah, it kind of blew up in my face as I wrote it. The problem with coding is that it is hard to pick the simple, correct and maintainable solution when it just seems so... ordinary sometimes, compared to a conceptually elegant solution where the true devil hides in the details.

Anthony Mushrow

You could also use the GetRange function on the list to do the actual work of making the sub lists, and then you don't need to keep track of so many things.

List> GetSubLists(List lstInput)
{
List> lstSubLists = new List>();

if (lstInput.Count == 0)
    return lstSubLists;

int subListStartIndex = 0;
for (int i = 1; i < lstInput.Count; ++i)
{
    if (lstInput\[i\] - lstInput\[i-1\] != 1)
    {
        lstSubLists.Add(lstInput.GetRange(subListStartIndex, i - subListStartIndex));
        subListStartIndex = i;
    }
}

lstSubLists.Add(lstInput.GetRange(subListStartIndex, lstInput.Count - subListStartIndex));

return lstSubLists;

}

BillWoodruff

technical ? => QA forum

«There is a spectrum, from "clearly desirable behaviour," to "possibly dodgy behavior that still makes some sense," to "clearly undesirable behavior." We try to make the latter into warnings or, better, errors. But stuff that is in the middle category you don’t want to restrict unless there is a clear way to work around it.» Eric Lippert, May 14, 2008

Eytukan

No footprints. Nothing modified from the previous post, just removed the optional extra solutions. :)

typedef std::map<int*, int>::iterator it_type;
int arrNum[] = { 1, 2, 6, 4, 5, 7, 8, 9, 2, 2, NULL };
int* pBegin = (int*)&arrNum[0];
int* pStart = pBegin; int* pNext = pBegin +1;
std::map<int*, int> _mapSeg;int nCounter = 0;
_mapSeg[pBegin] = nCounter;

while (NULL != \*pBegin)
{	\_mapSeg\[pStart\] = nCounter++;
	if (\*pBegin + 1 != \*pNext && (\*pBegin != \*pNext))
	{   nCounter = 0;pStart = pNext;}
	++pBegin;++pNext;
}

Starting to think people post kid pics in their profiles because that was the last time they were cute - Jeremy.

Staffan Bruun

Then there is the Manager solution:

Ted,

I need a function that splits a list of integers into sublists, so that each sublist only contains runs of consecutive digits.

I know you're busy with all the extra items this week, but if you could get that for me today, that would be great.

TIA,
Mike

virang_21

That is why I provided my solution so it does not look like I am asking for "give me code"

Zen and the art of software maintenance : rm -rf * Maths is like love : a simple idea but it can get complicated.

virang_21

Now that is simple and beautiful

Zen and the art of software maintenance : rm -rf * Maths is like love : a simple idea but it can get complicated.

PIEBALDconsult

The "lean and green" solution asks "Why perform all those allocations, copies, and inserts? Just return an array of the substrings' lengths":

int
MapSubarrays
(
int Len
,
int* Arr
,
int* Map
)
{
int result = 0 ;

int i ;

Map [ 0 ] = 1 ;

for ( i = 1 ; i < Len ; i++ )
{
Map [ i ] = 0 ;

if ( Arr \[ i \] - Arr \[ i - 1 \] != 1 )
{
  result++ ;
}

Map \[ result \]++ ;

}

return ( result ) ;
}

Then let the caller do what it wants with the result.

3 : { 1 , 2 , 3 }
3 : { 5 , 6 , 7 }
1 : { 22 }