Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Adjacent number algorithm grouper

By which I mean this:

Given the input set of numbers:

1,2,3,4,5 becomes "1-5".

1,2,3,5,7,9,10,11,12,14 becomes "1-3, 5, 7, 9-12, 14"

This is the best I managed to come up with: [C#]

Which feels a little sloppy to me, so the question is, is there somehow more readable and/or elegant solution to this?

public static string[] FormatInts(int[] ints)
{
    if (ints == null)
        throw new ArgumentNullException("ints"); // hey what are you doing?

    if (ints.Length == 0)
        return new string[] { "" }; // nothing to process

    if (ints.Length == 1)
        return new string[] { ints[0].ToString() }; // nothing to process

    Array.Sort<int>(ints); // need to sort these lil' babies
    List<string> values = new List<string>();

    int lastNumber  = ints[0]; // start with the first number
    int firstNumber = ints[0]; // same as above

    for (int i = 1; i < ints.Length; i++)
    {
        int current     = ints[i];
        int difference  = (lastNumber - current ); // compute difference between last number and current number

        if (difference == -1) // the numbers are adjacent
        {
            if (firstNumber == 0) // this is the first of the adjacent numbers
            {
                firstNumber = lastNumber;
            }
            else // we're somehow in the middle or at the end of the adjacent number set
            {
                lastNumber = current;
                continue;
            }
        }
        else
        {
            if (firstNumber > 0 && firstNumber != lastNumber) // get ready to print a set of numbers
            {
                values.Add(string.Format("{0}-{1}", firstNumber, lastNumber));
                firstNumber = 0; // reset
            }
            else // print a single value
            {
                values.Add(string.Format("{0}", lastNumber));
            }
        }

        lastNumber = current;
    }

    if (firstNumber > 0) // if theres anything left, print it out
    {
        values.Add(string.Format("{0}-{1}", firstNumber, lastNumber));                
    }

    return values.ToArray();
}
like image 933
arul Avatar asked Oct 29 '08 03:10

arul


4 Answers

VBA

Public Function convertListToRange(lst As String) As String
    Dim splLst() As String
    splLst = Split(lst, ",")
    Dim x As Long
    For x = 0 To UBound(splLst)
        Dim groupStart As Integer
        groupStart = splLst(x)
        Dim groupEnd As Integer
        groupEnd = groupStart
        Do While (x <= UBound(splLst) - 1)
            If splLst(x) - splLst(x + 1) <> -1 Then Exit Do
            groupEnd = splLst(x + 1)
            x = x + 1
        Loop
        convertListToRange = convertListToRange & IIf(groupStart = groupEnd, groupStart & ",", groupStart & "-" & groupEnd & ",")
    Next x
    convertListToRange = Left(convertListToRange, Len(convertListToRange) - 1)
End Function

convertListToRange("1,2,3,7,8,9,11,12,99,100,101")
Return: "1-3,7-9,11-12,99-101"

like image 162
Christopher Thomas Nicodemus Avatar answered Sep 26 '22 11:09

Christopher Thomas Nicodemus


I've rewritten your code like this:

    public static string[] FormatInts(int[] ints)
    {
        Array.Sort<int>(ints);
        List<string> values = new List<string>();

        for (int i = 0; i < ints.Length; i++)
        {
            int groupStart = ints[i];
            int groupEnd = groupStart;
            while (i < ints.Length - 1 && ints[i] - ints[i + 1] == -1)
            {
                groupEnd = ints[i + 1];
                i++;
            }
            values.Add(string.Format(groupEnd == groupStart ? "{0}":"{0} - {1}", groupStart, groupEnd));
        }
        return values.ToArray();
    }

And then:

/////////////////
int[] myInts = { 1,2,3,5,7,9,10,11,12,14 };
string[] result = FormatInts(myInts); // now result haves "1-3", "5", "7", "9-12", "14"
like image 44
Christian C. Salvadó Avatar answered Sep 25 '22 11:09

Christian C. Salvadó


See How would you display an array of integers as a set of ranges? (algorithm)

My answer to the above question:

void ranges(int n; int a[n], int n)
{
  qsort(a, n, sizeof(*a), intcmp);
  for (int i = 0; i < n; ++i) {
    const int start = i;
    while(i < n-1 and a[i] >= a[i+1]-1)
      ++i;
    printf("%d", a[start]);
    if (a[start] != a[i])
      printf("-%d", a[i]);
    if (i < n-1)
      printf(",");
  }
  printf("\n");
}
like image 21
jfs Avatar answered Sep 25 '22 11:09

jfs


Pure functional Python:

#!/bin/env python

def group(nums):
    def collect((acc, i_s, i_e), n):
        if n == i_e + 1: return acc, i_s, n
        return acc + ["%d"%i_s + ("-%d"%i_e)*(i_s!=i_e)], n, n
    s = sorted(nums)+[None]
    acc, _, __ = reduce(collect, s[1:], ([], s[0], s[0]))
    return ", ".join(acc)

assert group([1,2,3,5,7,9,10,11,12,14]) == "1-3, 5, 7, 9-12, 14"
like image 42
Deestan Avatar answered Sep 23 '22 11:09

Deestan