CODEWITHSUNDEEP
c#algorithmlinq
Sandro Manzo
Sandro Manzo

Reputation: 13

Linq : Checking how many times the same value consecutively

it's my first question so if it's not quite clear , you can ask for extra information. Keep in mind that english is not my native language :).

I was wondering if it's possible to have an elegant way for next specification. I think linq could be a possibility but i haven't got enough experience with the technology to get it to work:).

Remark this is not a homework assignment it's just a way to get an new angle to solve these kind of problems.

I've tried with the aggegrate function, maybe an action could help.

I want to keep track of:

for example:

we have an array of 6 elements with elements either 0 or 1

0 , 0 , 0 , 1 , 1 ,0 result : 3 times 0 , 2 times 1
0 , 0 , 1 , 1 , 1 ,0 result : 2 times 0 , 3 times 1
0 , 1 , 0 , 1 , 1 ,0 result : 1 time  0 , 2 times 1
0 , 0 , 1 , 1 , 0 ,0 result : 2 times 0 , 2 times 1

Thanks in advance

Upvotes: 0

Views: 367

Answers (6)

Sandro Manzo
Sandro Manzo

Reputation: 13

First of all thanks to everyone who put the time and effort in answering the question.

I've choosen Dmitry Bychenko as a valid answer , he was the first to provide an answer , and it was an elegant answer.

Matthew diserves also credit because he has shown me how the aggregate function works with conditionals.

last but not least the answer of victor was the simplest one. I did enhance it to work with generics .

 void Main()
    {
            var groups = new[] { 0, 0, 1, 1, 0,30,1,1,1,1,1 , 22, 22, 15,15,0,0,0,0,0,0 }.GroupConsecutive();

    groups.Dump();
            var maxGroupped = groups.GroupBy(i => i.First()).Select(i => new
            {
                   i.Key,
                   Count = i.Max(j => j.Count())
            });

    foreach (var g in maxGroupped)
           Console.WriteLine(g.Count + " times " + g.Key);
    }

     public static class Extension
        {

            public static IEnumerable<IEnumerable<T>> GroupConsecutive<T>(this IEnumerable<T> list) 
            {
                var group = new List<T>();
                foreach (var value in list)
                {
                    if (group.Count == 0 || value.Equals(group[group.Count-1])) 
                        group.Add(value);
                    else
                    {
                        yield return group;
                        group = new List<T> {value};
                    }
                }
                yield return group;
            }

Upvotes: 0

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186833

I don't think Linq being a good way out; but a simple method will do:

// Disclamer: Dictionary can't have null key; so source must not coтtain nulls
private static Dictionary<T, int> ConsequentCount<T>(IEnumerable<T> source) {
  if (null == source)
    throw new ArgumentNullException("source");

  Dictionary<T, int> result = new Dictionary<T, int>();

  int count = -1;
  T last = default(T);

  foreach (T item in source) {
    count = count < 0 || !object.Equals(last, item) ? 1 : count + 1;
    last = item;

    int v;

    if (!result.TryGetValue(last, out v))
      result.Add(last, count);
    else if (v < count)
      result[item] = count;
  }

  return result;
}

Tests:

  int[][] source = new int[][] { 
    new[] { 0, 0, 0, 1, 1, 0 },
    new[] { 0, 0, 1, 1, 1, 0 },
    new[] { 0, 1, 0, 1, 1, 0 },
    new[] { 0, 0, 1, 1, 0, 0 }, };

  string report = string.Join(Environment.NewLine, source
    .Select(array => $"{string.Join(" , ", array)} result : " + 
                         string.Join(", ", 
        ConsequentCount(array)
          .OrderBy(pair => pair.Key)
          .Select(pair => $"{pair.Value} times {pair.Key}"))));

  Console.Write(report);

Outcome:

0 , 0 , 0 , 1 , 1 , 0 result : 3 times 0, 2 times 1
0 , 0 , 1 , 1 , 1 , 0 result : 2 times 0, 3 times 1
0 , 1 , 0 , 1 , 1 , 0 result : 1 times 0, 2 times 1
0 , 0 , 1 , 1 , 0 , 0 result : 2 times 0, 2 times 1

Upvotes: 1

Dbuggy
Dbuggy

Reputation: 911

Like others said, performance wise Linq might not be the right tool for the job.

My linq only version would be:

from array in arrayOfArrays
let result = new { 
    Zeroes = array.TakeWhile(x => x == 0).Count(), 
    Ones = array.SkipWhile(x => x == 0).TakeWhile(x => x == 1).Count()
}
select $"{String.Join(", ", array)} result : {result.Zeroes} times 0, {result.Ones} times 1"

I'm not sure if Linq2Objects will be smart here to optimize the query internally. We ARE within the query iterating mutliple times over the array. So like i said in advance there may be a performance hit if you execute this over a lot of arrays. If anyone would care to check performance of this in regards to other non linq solutions.

Upvotes: 0

Mat J
Mat J

Reputation: 5632

Linq will be a bit ugly, but it is possible though, your choice of Aggregate is the way to go, but it won't be a one liner in any case,

Something like this will work,

static void Main(string[] args)
{
    var list = new List<int>() { 0, 0, 1, 1, 1, 0, 0 };
    var result = list.Aggregate(new
                                {
                                    Last = (int?)null,
                                    Counts = new Dictionary<int, int>(),
                                    Max = new Dictionary<int, int>()
                                }, (context, current) =>

                                {
                                    int count;
                                    if (!context.Counts.TryGetValue(current, out count))
                                        count = 1;

                                    if (context.Last == current)
                                        count += 1;

                                    int lastMax;
                                    context.Max.TryGetValue(current, out lastMax);
                                    context.Max[current] = Math.Max(lastMax, count);

                                    if (context.Last != current)
                                        count = 1;


                                    context.Counts[current] = count;

                                    return new { Last = (int?)current,  context.Counts, context.Max };
                                });

    Console.WriteLine(string.Join(",", list) + "  Result: ");
    var output = string.Join(",  ", result.Max.Select(x => string.Format("{0} times {1}", x.Value, x.Key)));
    Console.WriteLine(output);
    Console.ReadKey();
}

Upvotes: 0

Slai
Slai

Reputation: 22896

Here is a lazy inefficient way (seems like linear complexity to me):

int[] arr = { 0, 0, 0, 1, 1, 0 };

string str = string.Concat(arr);              // "000110"
int max0 = str.Split('1').Max(s => s.Length); // 3
int max1 = str.Split('0').Max(s => s.Length); // 2

and here is the efficient O(n) version:

int[] arr = { 0, 1, 1, 0, 0, 0 };

int i1 = 0, i = 1;
int[] max = { 0, 0 };

for (; i < arr.Length; i++)
{
    if (arr[i] != arr[i1])
    {
        if (i - i1 > max[arr[i1]]) max[arr[i1]] = i - i1; 
        i1 = i;
    }
}
if (i - i1 > max[arr[i1]]) max[arr[i1]] = i - i1;

Debug.Print(max[0] + "," + max[1]); // "3,2"

Upvotes: 0

Victor Leontyev
Victor Leontyev

Reputation: 8736

You can write your own method for groupping by consecutive

    public static class Extension
    {
        public static IEnumerable<IEnumerable<int>> GroupConsecutive(this IEnumerable<int> list)
        {
            var group = new List<int>();
            foreach (var i in list)
            {
                if (group.Count == 0 || i - group[group.Count - 1] == 0)
                    group.Add(i);
                else
                {
                    yield return group;
                    group = new List<int> {i};
                }
            }
            yield return group;
        }
    }

And then use it like that:

var groups = new[] { 0, 0, 1, 1, 0, 0 }.GroupConsecutive();
var maxGroupped = groups.GroupBy(i => i.First()).Select(i => new
{
       i.Key,
       Count = i.Max(j => j.Count())
});
foreach (var g in maxGroupped)
       Console.WriteLine(g.Count + " times " + g.Key);

Upvotes: 0

Related Questions