Compact a comma delimited number list into ranges

Question

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

Answer 1

I have tried to make it as simple as possible, you need to first initialise a start value, a start position variable and an end position variable. Keep on incrementing the start variable if it is consecutive, or else make start and end position as the current position variable and append the result. In case the difference in position of start and end is zero, just append one value of that position. In case the value is one, add both the values individually. In case it is greater than one, add the start and end position variables to the result separated by a dash.

nums = [1, 2, 3, 4, 5, 12, 13, 14, 19]
nums.sort()
print(nums)
res = []


# Initialise the values for start and end position variables along with the start
start = nums[0]
sPos = 0
ePos = 0

for i in range(1,len(nums)):
    if nums[i] == start+1:
        # Keep incrementing ePos and start if the numbers are consecutive
        ePos = i
        start=start+1
    else:
        # In case there is a break in the sequence, calculate the difference between start and end
        if sPos == ePos:
            # If both pointing at same place add the element
            res.append(nums[sPos])
        elif ePos - sPos == 1:
            # In case there are just 2 numbers then add both of them
            res.append(nums[sPos])
            res.append(nums[ePos])
        else:
            # In case there are more than 2 numbers, then add the start and end with dash in between
            res.append(str(nums[sPos])+"-"+str(nums[ePos]))
        start = nums[i]
        sPos = i
        ePos = i
# Finally just check in the same manner for the last elements
if sPos == ePos:
    res.append(nums[sPos])
elif ePos - sPos == 1:
    res.append(nums[sPos])
    res.append(nums[ePos])
else:
    res.append(str(nums[sPos])+"-"+str(nums[ePos]))
start = nums[i]
sPos = i
ePos = i
print(res)

Answer 2

This is array range compacting. Here is a Python solution:

" """"considering input as "1,2,3,4,5,6,11,13,11,23" """" "


arr=list(map(int,input().strip().split(',')))
arr=list(set(arr))
arr.sort()
l2=[arr[0]]
for i in range(len(arr)):
    if i+1<len(arr) and i-1>-1:
        if arr[i]-arr[i-1]==1 and  arr[i+1]-arr[i]==1 :
            if  l2[-1]!='-':
                l2+=['-']
            else:
                l2=l2
        else:
                l2+=[arr[i]]
if len(arr)>1:
    l2+=[arr[len(arr)-1]]       
st=str(l2[0])
for i in range(1,len(l2)):
    if str(type(l2[i]))!=str(type(l2[i-1])):
        st+=str(l2[i])
    else:
        st+=','+str(l2[i])
print(st,sep='\n')

I know this is very bad code and not so optimum one yet. If someone needs help he can refer to this one. Edits are welcome, to make the code in Python using good data structure.

Answer 3

I would like to suggest solution that is even more compact:

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

import static org.hamcrest.CoreMatchers.equalTo;
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

public class CompactComaDelimitedNumbersTest {

    @Test
    public void testCompactingNumbersWithJavaStream() {
        //given:
        final List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 12, 13, 14, 19);

        //when:
        final List<Object> finalResult = list.stream()
                // Firstly let's pair every number with a number it starts from in
                // given sequence
                .reduce(new ArrayList<Pair<Integer, Integer>>(), (result, number) -> {
                    if (result.isEmpty()) {
                        result.add(new Pair<>(number, number));
                        return result;
                    }

                    final Pair<Integer, Integer> previous = result.get(result.size() - 1);
                    if (previous.getFirst() + 1 == number) {
                        result.add(new Pair<>(number, previous.getSecond()));
                    } else {
                        result.add(new Pair<>(number, number));
                    }
                    return result;
                }, (a, b) -> a)
                // Now let's group list of pair into a Map where key is a number 'from' and value is a list of values
                // in given sequence starting from 'from' number
                .stream()
                .collect(Collectors.groupingBy(Pair::getSecond, Collectors.mapping(Pair::getFirst, Collectors.toList())))
                // Finally let's sort entry set and convert into expected format
                .entrySet()
                .stream()
                .sorted(Comparator.comparing(Map.Entry::getKey))
                .map(e -> e.getValue().size() < 3 ?
                        e.getValue() :
                        Collections.singletonList(String.format("%d-%d", e.getValue().get(0), e.getValue().get(e.getValue().size() - 1))))
                .flatMap(Collection::stream)
                .collect(Collectors.toList());

        //then:
        assertThat(finalResult, is(equalTo(Arrays.asList("1-5", "12-14", 19))));

    }

    static final class Pair<T,K> {
        private final T first;
        private final K second;
        Pair(T first, K second) {
            this.first = first;
            this.second = second;
        }
        public T getFirst() {
            return first;
        }

        public K getSecond() {
            return second;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "first=" + first +
                    ", second=" + second +
                    '}';
        }
    }
}

It pairs every number with a starting number for a current sequence, then groups all pairs by this from number and lastly it converts map into list of ranges like 1-5 or plain numbers. I hope you like this solution.

Answer 4

Edit

I'm sorry, I misunderstand your requirement since my English is so bad. Thank everybody of forgiveness. I'll give a configurable compress method later to thank everybody.

After working, I found I can't apply your rule above by use stream easily: "the count of numbers in the range is 3 or more." . so I down to the traditional approach. I wish it can helped you.

//        v--- "1-5, 12-14, 19"
String ranges = compress(asList(1,2,3,4,5, 12,13,14, 19)).collect(joining(", "));

//              v--- ["1", "2"]
Stream<String> lessThan3 = compress(asList(1, 2));

//              v--- ["1-4"]
Stream<String> step2 = compress(asList(1, 3, 4), 2, 3);

---

Build the range of Stream<String> immediately by using Stream.Builder.

static Stream<String> compress(List<Integer> numbers) {
    return compress(numbers, 1, 3);
}

static Stream<String> compress(List<Integer> numbers, int step, int minSize) {
    Builder<String> ranges = Stream.builder();
    IntBuffer queue = IntBuffer.allocate(minSize + 1);
    for (int it : numbers) {
        int prev = queue.position() - 1;
        if (prev >= 0 && queue.get(prev) + step < it) {
            copy(queue, ranges, minSize);
            queue.put(it);
        } else {
            if (queue.hasRemaining()) {
                queue.put(it);
            } else {
                queue.put(prev, it);
            }
        }
    }
    return copy(queue, ranges, minSize).build();
}

static Builder<String> copy(IntBuffer queue, Builder<String> target, int minSize) {
    queue.flip();
    if (queue.limit() >= minSize) {
        target.add(format("%d-%d", queue.get(0), queue.get(queue.limit() - 1)));
    } else {
        while (queue.hasRemaining()) target.add(Integer.toString(queue.get()));
    }
    queue.clear();
    return target;
}

Edit2

Build the range of Stream<String> lazily by using Spliterator.

static Stream<String> compress(List<Integer> numbers, int step, int minSize) {
    return compress(numbers, minSize, (prev, current) -> current - prev <= step);
}


static Stream<String> compress(List<Integer> numbers,
                               int minSize,
                               IntBiPredicate rule) {
    return StreamSupport.stream(spliterator(numbers, minSize, rule), false);
}


static AbstractSpliterator<String> spliterator(List<Integer> numbers,
                                               int minSize,
                                               IntBiPredicate rule) {
    return new AbstractSpliterator<String>(numbers.size(), ORDERED) {
        private Iterator<Integer> data;
        private Queue<String> queue;
        private IntBuffer buff;


        @Override
        public boolean tryAdvance(Consumer<? super String> action) {
            init();
            return tryConsuming(action) || evaluate();
        }

        private void init() {
            if (data != null) return;
            data = numbers.iterator();
            queue = new LinkedList<>();
            buff = IntBuffer.allocate(minSize + 1);
        }

        private boolean tryConsuming(Consumer<? super String> action) {
            if (queue.isEmpty()) return false;
            action.accept(queue.poll());
            return true;
        }

        private boolean evaluate() {
            if (!data.hasNext()) {
                return buff.position() > 0 && fill();
            } else {
                evaluateNext(data.next());
                return true;
            }
        }

        private void evaluateNext(int it) {
            int prev = buff.position() - 1;
            if (prev >= 0 && !rule.test(buff.get(prev), it)) {
                fill();
                buff.put(it);
            } else {
                if (!buff.hasRemaining()) {
                    buff.put(buff.position() - 1, it);
                } else {
                    buff.put(it);
                }
            }
        }

        private boolean fill() {
            buff.flip();
            if (buff.limit() >= minSize) {
                int min = buff.get(0);
                int max = buff.get(buff.limit() - 1);
                queue.add(format("%d-%d", min, max));
            } else {
                while (buff.hasRemaining()) {
                    queue.add(Integer.toString(buff.get()));
                }
            }
            buff.clear();
            return true;
        }
    };
}

interface IntBiPredicate {
    boolean test(int first, int second);
}

Oldest

How about this? String ranges are grouped by n/m:

int m = 5 + 1; 
//        v--- "1-5, 12-14, 19"
String ranges =
     Stream.of(1, 2, 3, 4, 5, 12, 13, 14, 19)
           //       v--- calculate ranges until grouping is done
           .collect(collectingAndThen(
                groupingBy(
                    //     v--- group n by n/m
                    n -> n / m,
                    TreeMap::new,
                    // v--- summarizing the current group
                    summarizingInt(Integer::intValue) 
                ),
                summary -> summary.values()
                                  .stream()
                                  .map(
                       //create range string from IntSummaryStats ---v        
                                      it ->String.format(
                                          it.getMin()==it.getMax()?"%d":"%d-%d",
                                          it.getMin(),
                                          it.getMax()
                                      )
                                  )
                                  .collect(joining(", "))
            ));

Answer 5

I can only think about a custom collector... You can obviously create a method that would return this collector and the code would be really compact in this case, provided that the collector is hidden via a static factory method.

Notice how the combiner is doing basically nothing, not good for parallel coding. I'm still trying to think of a good way to provide an implementation for it.

 List<String> result = IntStream.of(1, 2, 3, 4, 5, 12, 13, 14, 19)
            .boxed()
            .collect(Collector.of(
                    () -> {
                        List<List<Integer>> list = new ArrayList<>();
                        list.add(new ArrayList<>());
                        return list;
                    },
                    (list, x) -> {
                        List<Integer> inner = list.get(list.size() - 1);
                        if (inner.size() == 0) {
                            inner.add(x);
                        } else {
                            int lastElement = inner.get(inner.size() - 1);
                            if (lastElement == x - 1) {
                                inner.add(x);
                            } else {
                                List<Integer> oneMore = new ArrayList<>();
                                oneMore.add(x);
                                list.add(oneMore);
                            }
                        }
                    },
                    (left, right) -> {
                        throw new IllegalArgumentException("No parallel!");
                    },

                    list -> {

                        return list.stream()
                                .map(inner -> {
                                    if (inner.size() > 1) {
                                        return inner.get(0) + "-" + inner.get(inner.size() - 1);
                                    }
                                    return "" + inner.get(0);
                                }).collect(Collectors.toList());

                    }));

    System.out.println(result);

Answer 6

Now that we have seen several Stream variants, here the non-Stream variant for comparison:

private static StringBuilder appendRange(StringBuilder sb, int start, int previous) {
    sb.append(start);
    if(start!=previous) sb.append(previous-start>1? " - ": ", ").append(previous);
    return sb;
}

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 12, 13, 14, 19);
StringBuilder sb = new StringBuilder();
int previous = list.get(0), start = previous;
for(int next: list.subList(1, list.size())) {
    if(previous+1 != next) {
        appendRange(sb, start, previous).append(", ");
        start = next;
    }
    previous = next;
}
String result = appendRange(sb, start, previous).toString();

Answer 7

I've written a specific implementation of Collector which should do what you want.

NOTICE: this implementation fails horribly when trying to use in parallel

public class RangeCollector implements Collector<Integer, List<String>, List<String>>{

    private int last = 0;
    private LinkedList<Integer> intermediate = new LinkedList<>();

    @Override
    public Supplier<List<String>> supplier(){
        return ArrayList::new;
    }

    @Override
    public BiConsumer<List<String>, Integer> accumulator(){
        return ( finalList, current ) -> {
            if( current - last == 1 ){ // check if adjacent to last value
                intermediate.add(current);
            } else{
                if( intermediate.size() > 2 ){
                    finalList.add(intermediate.getFirst() + "-" + intermediate.getLast()); // add new range
                } else{
                    addLeftOverValues(finalList);
                }
                intermediate.clear();
                intermediate.add(current);
            }
            last = current;
        };
    }

    @Override
    public BinaryOperator<List<String>> combiner(){
        return (list, list2) -> {
            list.addAll(list2);
            return list;
        };
    }

    @Override
    public Function<List<String>, List<String>> finisher(){
        return ( finalList ) -> {
            if( !intermediate.isEmpty() ){
                addLeftOverValues(finalList);
            }
            return finalList;
        };
    }

    @Override
    public Set<Characteristics> characteristics(){
        return EnumSet.noneOf(Characteristics.class);
    }

    private void addLeftOverValues( List<String> list ){
        list.addAll(
            intermediate.stream()
                .map(String::valueOf)
                .collect(Collectors.toList())
       );
    }
}

which then can be used like this:

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 12, 13, 14, 19);
System.out.println(list.stream().collect(new RangeCollector()));

which finally prints [1-6, 12-14, 19]