13
\$\begingroup\$

I'm looking for a clever way to do the following operation:

Take a list of numbers:

1, 2, 3, 4, 5, 12, 13, 14, 19

and compact it into a string like so:

1-5, 12-14, 19

With the following rule: only compress into a range (i.e. use a dash) when the count of numbers in the range is 3 or more.

I.e.: 1, 2, 4, 5 would result in: 1, 2, 4, 5 and NOT: 1-2, 4-5

This is my implementation, but I feel like it could be improved upon greatly:

 public string CompactNumberRanges(IEnumerable<int> numbers, 
                                   int requiredRangeCount)
 {
     if (requiredRangeCount <= 1)
         throw new ArgumentOutOfRangeException("requiredRangeCount");

     int[] sorted = numbers.OrderBy(e => e).ToArray();

     StringBuilder b = new StringBuilder();

     for (int i = 0; i < sorted.Length; i++)
     {
         int cv = sorted[i];
         int count = 0;

         for (int j = cv; ; j++)
         {
             if (Array.IndexOf(sorted, j) == -1)
                 break;
             else
                 count++;
         }

         if (count == 0)
             throw new InvalidOperationException();
         else if (count < requiredRangeCount)
             b.Append(", ").Append(cv);
         else if (count >= requiredRangeCount)
         {
             b.Append(", ").AppendFormat("{0}-{1}", cv, sorted[i + count - 1]);

             i += count - 1;
         }
     }

     return b.ToString().Trim(',', ' '); ;
 }

As an example:

List<int> numbers = new List<int>
    (
        new int[] { 1, 2, 3, 4, 5, 12, 13, 14, 19 }
    );

Console.WriteLine(CompactNumberRanges(numbers, 3));
//  output: 1-5, 12-14, 19

I have this working fine, I'm really just looking to find better ways to do the same operation because I think it's a fun one.

\$\endgroup\$
17
\$\begingroup\$

You could calculate a value to group on, i.e. number - index. All consecutive numbers have the same value:

index  number  number - index
-----  ------  --------------
  0       1          1
  1       2          1
  2       3          1
  3       4          1
  4       5          1
  5      12          7
  6      13          7
  7      14          7
  8      19         11

Then you just check how many items there is in each group to determine if it should be a range.

Example:

List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 12, 13, 14, 19 };

List<string> items = numbers
  .Select((n,i) => new { number = n, group = n - i })
  .GroupBy(n => n.group)
  .Select(g =>
    g.Count() >= 3 ?
      g.First().number + "-" + g.Last().number
    :
      String.Join(", ", g.Select(x => x.number))
  )
  .ToList();

Console.WriteLine(String.Join(", ", items));

Output:

1-5, 12-14, 19
\$\endgroup\$
4
  • \$\begingroup\$ +1 - Really elegant solution but not a fan of the two space indents and line breaking in the ternary operator! \$\endgroup\$
    – RobH
    May 8 '15 at 13:12
  • \$\begingroup\$ @RobH: Thanks. Really no a fan of spaces for indentation in the first place, Courier, and an editor that is only about 90 characters wide before you need to scroll horizontally. :) \$\endgroup\$
    – Guffa
    May 8 '15 at 13:22
  • \$\begingroup\$ Brilliant solution! I would only Distinct() it before grouping. \$\endgroup\$
    – orad
    Mar 8 '17 at 1:07
  • \$\begingroup\$ Superb! Love the simplicity of it, I'm newish to C# so took me a little while to work out what was happening. Good job, thanks \$\endgroup\$
    – 93196.93
    Jul 4 '18 at 17:56
6
\$\begingroup\$

Review

Good things:

  1. IEnumerable in place of List - IEnumerable is more than enough to get the desired data.
  2. Argument checking - never trust the input.
  3. Use of StringBuilder - often forgotten(not known) initially but very performance-wise approach.
  4. Code seems not to have problems at the start or the end of a sequence (forgetting to return some ranges for items at the beginning or the end in some edge cases)

Possible issues:

  1. CompactNumberRanges is an instance method, but doesn't use any instance data. It, perhaps, was your design decision to avoid static helpers, or if it wasn't, then you may want to consider refactoring it into some helper method.

Correctness issues

  1. The most visible is that while you check the requiredRangeCount, you do not check numbers variable for being null. It is not critical, but will make your method a bit more bullet-proof and a lot more consistent.
  2. This code will probably have some problems with duplicates, because inner loop doesn't account for them - it searches for next incremented value each new iteration.

Performance issues:

  1. Array.IndexOf use - it is implemented with linear search, so it doesn't take advantage of the fact that the array is already ordered.
  2. And Array.IndexOf is called multiple times, executing linear search for an item existence of which that can be checked from the array[current index + 1] element.

Style issues

  1. It has been already mentioned in another answer, but for the sake of completeness, use of nondescriptive variable names shall be pointed : i is not a problem, because it is just an index, but use of j that actually means next item to find and cv can probably be made more clear with few more letters.

Other(design) issues

  1. This method actually does two things at once - processes the original sequence to discern ranges of sequential elements and aggregates these ranges into one string. While doing it at the same time may seem simpler, it really combines two concrete and reusable operations into one. It is a mix of a domain-related logic (getting ranges) and presentation logic(creating their string representations)

Alternative generic solution

As an alternative, I can propose to you the following solution that separates range-finding and string formatting logic with LINQ-like extension method that operates using yield sequence generation.

Range class

Create some class to represent a Range (as first and last element or as only the first element). For simplicity we will make ToString method to output exactly the desired format:

public class Range<T>
{
    public Range(T start, T end)
    {
        this.Start = start;
        this.End = end;
    }

    public Range(T startOnly)
    {
        this.Start = startOnly;
    }

    public T Start
    {
        get;
        private set;
    }

    private T m_end;

    public T End
    {
        get
        {
            if (!this.HasEnd)
                throw new InvalidOperationException("Range is a single element");

            return this.m_end;
        }                
        private set
        {
            this.HasEnd = true;
            this.m_end = value;
        }
    }

    public Boolean HasEnd
    {
        get;
        private set;
    }

    public override string ToString()
    {
        if (this.HasEnd)
            return String.Format("{0}-{1}", this.Start, this.End);

        return this.Start.ToString();
    }
}

Generic method

Create generic method that requires additional Func delegate to determine whether item are in a sequential range. WARNING: This method assumes that collection is either a nondecreasing or a nonincreasing sequence, so unordered sequences must be ordered before calling it:

public static IEnumerable<Range<T>> CompactOrderedRanges<T>(this IEnumerable<T> collection, Int32 minForRange, Func<T, T, Boolean> areNeighbours)
{
    if (collection == null)
        throw new ArgumentNullException("collection");
    if (minForRange < 1)
        throw new ArgumentException("minForRange");
    if (areNeighbours == null)
        throw new ArgumentNullException("areNeighbours");

    List<T> range = new List<T>()
        {
            collection.First()
        };

    foreach (var item in collection.Skip(1))
    {
        if (areNeighbours(range.Last(), item))
        {
            range.Add(item);
            continue;
        }

        if (range.Count >= minForRange)
        {
            // Yield range
            yield return new Range<T>(range.First(), range.Last());
        }
        else
        {
            // Yield items in range one by one
            foreach (var rangeItem in range)
            {
                yield return new Range<T>(rangeItem);
            }
        }

        range.Clear();
        range.Add(item);
    }

    // Deal with leftovers. Code duplication, but I am not sure that it can  
    // be avoided due to yields other than with another helper function 
    // that returns IEnumerable<Range<T>>, so for now leave it as it is.
    if (range.Count >= minForRange)
    {
        // Yield range
        yield return new Range<T>(range.First(), range.Last());
    }
    else
    {
        // Yield items in range one by one
        foreach (var rangeItem in range)
        {
            yield return new Range<T>(rangeItem);
        }
    }
}

Int32 specialization

For simplicity, also create specialized method that deals with IEnumerable<Int32> collections:

public static IEnumerable<Range<Int32>> CompactOrderedRanges(this IEnumerable<Int32> collection, Int32 minForRange)
{
    return collection.CompactOrderedRanges(minForRange,
        (a, b) =>
        {
            checked { return Math.Abs(a - b) <= 1; }
        });
}

Use

List<List<Int32>> numberSequences = new List<List<Int32>>
{
    new List<Int32> { 1 },
    new List<Int32> { 1, 2 },
    new List<Int32> { 1, 3 },
    new List<Int32> { 1, 2, 3 },
    new List<Int32> { 1, 5, 3 },
    new List<Int32> { 1, 2, 4, 5 },
    new List<Int32> { 1, 2, 3, 4, 10 }, 
    new List<Int32> { -5, 1, 2, 3, 4}, 
    new List<Int32> { 1, 2, 3, 4, 7, 11, 12, 13}, 
    new List<Int32> { 1, 2, 1 }, // fails because it is unoredered
    new List<Int32> { 1, 1, 2 } // works
};

foreach (var sequence in numberSequences)
{
    Console.WriteLine("{0} : {1}",
        String.Join(",", sequence),
        String.Join(",",
            sequence
                .CompactOrderedRanges(3)));
}

PROS

  1. It is quite generic.
  2. It has LINQ friendly interface, so it can be easily weaved into other scenarios.
  3. It doesn't use any additional Find(IndexOf) methods and, basically, touches all elements sequentially and at worst two times.

CONS

  1. It requires the sequence to be ordered (this can be avoided by adding additional comparer delegate parameter and checking the "direction" of items' proximity to each other).
\$\endgroup\$
2
  • \$\begingroup\$ Great answer! I'm looking for something that will do the opposite, take a compacted range string and convert it to a list or ienumerable. \$\endgroup\$ Jul 3 '19 at 18:23
  • \$\begingroup\$ Never mind, found this: stackoverflow.com/a/37213725/992419 \$\endgroup\$ Jul 3 '19 at 18:34
2
\$\begingroup\$

A few remarks on your code;

Naming:

Names like b or cv don't mean much, not to you, nor to others. Use meaningful names for your variables.

The var keyword:

From the C# Programming Guide:

The var keyword can also be useful when the specific type of the variable is tedious to type on the keyboard, or is obvious, or does not add to the readability of the code.

So lines like:

int count = 0;

would become:

var count = 0;

Implementation:

Your implementation is not bad, and so aren't the ones from other solutions. Although I don't like too much LinQ methods, creating separate classes or multiple loops for something rather simple as this "problem".

I implemented a non-LinQ solution that requires only one loop over the collection, using the IENumerable.GetEnumerator() method.

The logic is as follows:

  1. Get the enumerator
  2. Loop over the collection
  3. Calculate the difference between the previous and the current item
    • if it is 1, it is consecutive
    • if not, append the correct format to the string
  4. At the end, if count is greater than 1, append the last number to the ouput

The explanation is a bit simple but the code is clear enough normally :) Anyway, here goes:

public static string CompactNumberRange(IEnumerable<int> range)
{
    var sorted = range.OrderBy(x => x);
    var output = new StringBuilder();

    using (var enumerator = sorted.GetEnumerator())
    {
        if (!enumerator.MoveNext())
            return "";

        var current = enumerator.Current;
        var count = 1;

        output.Append(current);

        while (enumerator.MoveNext())
        {
            var previous = current;
            current = enumerator.Current;

            if (current - previous == 1)
            {
                count++;
            }
            else
            {
                var format = count >= 3 ? "-{0}, {1}" : ", {0}, {1}, ";
                output.AppendFormat(format, previous, current);
                count = 1;
            }
        }

        if (count > 1)
            output.Append(current);
    }

    return output.ToString();
}
\$\endgroup\$
1
  • \$\begingroup\$ While this solution is nice, it fails when there is a group at the end of the collection. Example int[] { 1,2,3,5,6,7 } outputs "1-3, 57" \$\endgroup\$
    – Itanex
    Aug 15 '19 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.