Convert a double list to a grouped string

Question

The program has an input a list of doubles and the output needs to be a string containing the list values grouped by their value. The list values will be grouped if they are equal. Something like: input 9,77,5,5,31 => output 9 77 2*5 31

I created an algorithm in C# (in Java I think that is almost the same) for this but I am not sure if it can be improved regarding its speed or code quaility, or if it has some bugs that I could not see. The algorithm having also some more input, output examples is below.

    List<double> input = new List<double> { 11, 32, 32, 43}; // output 11 2*32 43
    //List<double> input = new List<double> { 11, 11, 43, 43 }; // output 2*11 2*43
    //List<double> input = new List<double> { 10, 11, 12, 13, 14, 15, 16 }; // output 10 11 12 13 14 15 16
    //List<double> input = new List<double> { 11, 11, 11, 11, 11 }; // output 5 * 11
    //List<double> input = new List<double> { 11, 11, 32, 22, 22, 22, 4, 10, 10 }; // output 2*11 32 3*22 4 2*10

    string listAsString = string.Empty;
    double nextElem = double.MinValue;
    for (int i = 0; i < input.Count; i++)
    {
        double currentElem = input[i];

        if (i + 1 < input.Count)
        {
            nextElem = input[i + 1];
        }

        int equalCount = 0;
        while (currentElem.Equals(nextElem) && i < input.Count)
        {
            equalCount++;
            i++;
            currentElem = nextElem;

            if (i < input.Count)
            {
                nextElem = input[i];
            }
        }

        if (equalCount < 2)
        {
            listAsString += currentElem + " ";
        }
        else
        {
            listAsString += equalCount + "*" + currentElem + " ";
            i--;
        }
    }

    Console.WriteLine(listAsString);

Please let me know if you noticed some bugs or see some improvements that can be done.

Also if you know another implementation of this requirement please add it so that a comparation regarding results, speed, code quality between the algorithms can be done... and find the best way to handle this.

Answer 1

Disclaimer: Edit

OP later specified that the numbers must be grouped only if they are adjacent. My code does not do that. It groups all equal elements. Please refer to @Xiaoy312's answer for that. I have my own solution, but as that is not a significant improvement over @Xiaoy312's I'm not posting it. To me, @Xiaoy312's answer is overkill for the specific use case the OP mentions, it promotes good programming practices and code reusability.

Old answer

What you're trying to achieve here is similar to Run-Length Encoding, a basic data compression technique.

Off the bat, I'll make a few observations:

1. You are repeatedly concatenating immutable strings. Usually not a great idea, as it involves large overheads in creating and discarding a whole lot of string objects. Use StringBuilder in the System.Text namespace instead, and append to it instead of doing repeated string concatenation.

2. Too much code in one function. Split it up! An obvious candidate is the part which counts the number of occurrences of a value in the list. Try to follow separation of concerns and the Single Responsibility Principle.

3. You do redundant counting for values. For a particular value, you should cache its count and not repeat the count for the same value again (memoization).

4. Try LINQ. It might even make this code into a one-liner. And be more idiomatic at the same time, if a bit slower.

5. You could do this better by doing the logic in 2 passes - in the first, you construct a map between the unique values in the list and their count, and in the second, you use this map to generate the string representation.

6. Ideally for comparing 2 doubles for equality, keeping in mind their error margins and inexact representation of certain values, you would check that the modulus of the difference of the 2 values was less than some small epsilon. However, for code like this, that's probably overkill.

7. Try to program as generic as possible. Use an IEnumerable<T> instead of a very specific List<double>, you will be able to use the resulting code for many different types of collections. This also involves typing to interfaces instead of concrete classes.

Using most of the above suggestions, herein follows the code (test fiddle here):

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

public class RLEofList
{
    
    private static Dictionary<double, int> CountMap(List<double> input)
    {
        var countMap = new Dictionary<double, int>(input.Count);
        foreach(double item in input)
        {
            if(!countMap.ContainsKey(item))
            {
                countMap.Add(item, input.Count(x => x == item));
            }
        }
        return countMap;
    }

    public static string ListToRLEString(List<double> input)
    {
        var countMap = CountMap(input);
        var accumulator = new StringBuilder(input.Count);//rough guess for capacity of StringBuilder
        foreach(KeyValuePair<double, int> itemWithCount in countMap)
        {
            if(itemWithCount.Value > 1)
            {
                accumulator
                .Append(itemWithCount.Value)
                .Append("*");
            }
            accumulator
            .Append(itemWithCount.Key)
            .Append(" ");
        }
        return accumulator.ToString();
    }
    
    public static void Main()
    {
        var list = Console
            .ReadLine()
            .Split(',')
            .ToList()
            .ConvertAll<double>(x => Double.Parse(x));
        Console.WriteLine(ListToRLEString(list));
    }
}

The piece of code above will accept input as a single line of comma-separated numbers as per the example in the question. You might need to use Regex.Split for more complicated input patterns.

I'm not collapsing this code into a LINQ one-liner as I feel this is more educational.

Answer 2

As @TamoghnaChowdhury has already pointed out, you have too much code in, what I assume, your main method. You should divide it into multiple methods, so that the indention of your code can be reflect by glancing at it, and not studying line by line.

If we examine the code, we can see that it performs 2 different tasks that can be split, counting continuous occurrence and RLE formatting. With this in mind, we can rewrite the main method like this:

void Main()
{
    // input
    var input = new List<double>{ /*...*/ };

    // processing
    var occurrences = CountContinuousOccurrences(input);
    var result = RleFormat(occurrences);

    // output
    Console.WriteLine(result);
}

Counting Continuous Occurrence

Now, this part you don't need nested loop to get the job done. Although, it is natural to think this way: taking an element and all the same that follows. You can just compare previous and the current element and check if they are the same.

public static class CountingExtension
{
    public static IEnumerable<IOccurrence<T>> CountOccurrences<T>(this IEnumerable<T> source)
    {
        using(var enumerator = source.GetEnumerator())
        {
            if (!enumerator.MoveNext()) yield break;

            var comparer = Comparer<T>.Default;
            var previousOccurrence = new Occurrence<T>(enumerator.Current);
            while(enumerator.MoveNext())
            {
                var current = enumerator.Current;
                if (comparer.Compare(current, previousOccurrence.Element) != 0)
                {
                    yield return previousOccurrence;
                    previousOccurrence = new Occurrence<T>(current);
                    continue;
                }

                previousOccurrence.Count++;
            }

            yield return previousOccurrence;
        }
    }

    private class Occurrence<T> : IOccurrence<T>
    {
        public T Element { get; set; }
        public int Count { get; set; }

        public Occurrence(T element)
        {
            Element = element;
            Count = 1;
        }
    }
}
public interface IOccurrence<T>
{
    T Element { get; }
    int Count { get; }
}

RLE Formatting

If we were to explain it in english, the sequence is joined by a space() where repeated elements a denoted in the format of {count}*{element}.

If we were to code it in C#, it is not much different:

private string RleFormat<T>(IEnumerable<IOccurrence<T>> occurrences)
{
    return string.Join(" ", occurrences
        .Select(x => x.Count == 1 ? x.Element.ToString() : string.Concat(x.Count, "*", x.Element))
        // if you have c# 6, it can be even shorter
        //.Select(x => x.Count == 1 ? x.Element.ToString() : $"{x.Count}*{x.Element}")
        );
}

Putting all together

void Main()
{
    var input = new List<double> { 11, 11, 32, 22, 1, 22, 22, 4, 10, 10 };

    var occurrences = input.CountOccurrences();
    var result = RleFormat(occurrences);

    Console.WriteLine(result);
}