From: Gavin Sinclair <gsinclair@...>
Date: 2004-07-11T17:23:13+09:00
Subject: Re: A little algorithmic help requested...

On Sunday, July 11, 2004, 5:10:34 PM, Hal wrote:

> Here's a problem my tired brain is having trouble with.

> Given a sorted array of integers, convert them into as many
> ranges as possible (ranges of three or more).

> Example:
> [1,2,3,4,6,7,8,11,12,15,16,17] ==> [1..4,6..8,11,12,15..17]

> How would *you* do this?

  def ranges(list, min_range_size=3)
    curr = []             # The current group as we traverse the input list.
    groups = [curr]       # e.g. [[1,2,3,4], [6,7,8], [11], ...]
    list.each do |n|
        # Either N fits into the current group (curr), or it begins a
        # new one.
      if curr.empty?
        curr << n
      elsif curr.last == n - 1
        curr << n
      else
        curr = [n]
        groups << curr
      end
    end
      # Now we turn the groups into ranges.
    result = []
    groups.each do |g|
      if g.size < min_range_size
        result.concat g
      else
        result << (g.first .. g.last)
      end
    end
    result.compact
  end

  require 'test/unit'
  class RangeTest < Test::Unit::TestCase
    def test_range
      assert_equal([1], ranges([1]))
      assert_equal([1,2], ranges([1,2]))
      assert_equal([1..3], ranges([1,2,3]))
      assert_equal([1..4,6], ranges([1,2,3,4,6]))
      assert_equal([1,2,3,4,6], ranges([1,2,3,4,6], 10))
      assert_equal([1..4,6..8,11,12,15..17], ranges([1,2,3,4,6,7,8,11,12,15,16,17]))
      assert_equal([1..4,6..8,11..12,15..17], ranges([1,2,3,4,6,7,8,11,12,15,16,17], 2))
      assert_equal([1..1,3..3,5..5,7..7], ranges([1,3,5,7], 1))
      assert_equal([1..4,6..6,8..9], ranges([1,2,3,4,6,8,9], 0))
    end
  end

Cheers,
Gavin