How do I return a group of sequential numbers that might exist in an array?

Question

If I have a sorted array, how do I find the sequential numbers? Btw, this is for determining if a poker hand is a straight or not. Duplicates in the array have been removed. I can do this, but it would be a multi-line method and I thought there might be a quick one liner using an Enumerable method.

For example:

FindSequence([9,8,7,5,4]) = [9,8,7]
FindSequence([4,2,0]) = nil

Any other requirements with regards to sequence length perhaps? How should it behave if there are two sequences? — Captain Giraffe, Jun 06 '11 at 23:04
Generally speaking you're going to want to try something before you ask a question like this. What have you tried? What are you using this for? — Kyle Sletten, Jun 06 '11 at 23:06
Is the input array already sorted in reverse order, as your examples show? — Mark Thomas, Jun 06 '11 at 23:18
possible duplicate of [Array of indexes to array of ranges](http://stackoverflow.com/questions/3728660/array-of-indexes-to-array-of-ranges) — Andrew Grimm, Jun 07 '11 at 00:15

J-_-L · Answer 1 · 2015-04-24T08:44:56.350

In 1.9.2, a mysterious slice_before method was added to Enumerable. You can utilize it:

def find_sequences_desc(a)
  prev = a[0]
  a.slice_before { |cur|
    prev, prev2 = cur, prev  # one step further
    prev2 - 1 != prev        # two ago != one ago ? --> new slice
  }.to_a
end
# find_sequences_desc [9,8,7,4,4] #=> [[9, 8, 7], [4], [4]]
# find_sequences_desc [9,8,7,5,4] #=> [[9, 8, 7], [5, 4]]

def find_sequences_asc(a)
  prev = a[0]
  a.slice_before { |cur|
    prev, prev2 = cur, prev  # one step further
    prev2 + 1 != prev        # two ago != one ago ? --> new slice
  }.to_a
end
# find_sequences_asc [1,2,4,5,7] #=> [[1, 2], [4,5], [7]]
# find_sequences_asc [1,2,3,5,6] #=> [[1, 2, 3], [5, 6]]

You can get the semantics you need with

def find_longest_sequence(a)
  s = find_sequences_desc(a).max
  s unless s.size <= 1
end

Update

Ruby 2.2 adds a slice_when method, which simplifies the code a lot:

def find_sequences_desc(a)
  a.slice_when { |prev, cur|
    cur != prev - 1
  }.to_a
end
# find_sequences_desc [9,8,7,4,4] #=> [[9, 8, 7], [4], [4]]
# find_sequences_desc [9,8,7,5,4] #=> [[9, 8, 7], [5, 4]]

p find_sequences [1,3,4,5,6] #=>[[1], [3], [4], [5], [6]] fails? — eastafri, Jan 22 '13 at 17:47

score 3 · Accepted Answer · answered Jun 06 '11 at 23:26

3

Assuming it is presorted, you can easily test for a straight like so:

array.each_cons(2).all? { |x,y| y == x - 1 }

To be safe you may want to add the sort:

array.sort.each_cons(2).all? { |x,y| y == x + 1 }

But if you really need to extract the largest sequence, it will take another solution.

answered Jun 06 '11 at 23:26

Mark Thomas

37,131
11
74
101

I came up with this based on your help. ary.uniq.sort.reverse.each_cons(5) { |a| p a if a[0] == a[4] + 4} Thanks! – Jeremy Smith Jun 07 '11 at 02:14
right now i have the same problem, and this solutions looks good BUT...! in poker straight is not only 2,3,4,5,6 but K,A,2,3,4 also. any idea what to do with it? – Leo Feb 19 '13 at 23:18
@KubaPolaczek create a Card class, mix in Enumerable, and you can define 2, 3, 4, ... J, Q, K, A as the sequence for sorting and other Enumerable-style manipulation. But K,A,2,3,4 is not a straight in any poker games that I know. – Mark Thomas Feb 19 '13 at 23:48

score 1 · Answer 3 · answered Jun 06 '11 at 23:42

If as you say you've sorted and removed duplicates, then the array is in sequence if the difference between the first and last elements of the array equals the difference in their indices. (I'm being vague here because I believe my answer can be generalised.)

How do I return a group of sequential numbers that might exist in an array?

3 Answers3

Linked