3
\$\begingroup\$

Task description

You are given a list and an item, find the length of the longest consecutive subsequence of the list containing only the item.

Testcases

[1, 1, 2, 3] 1 -> 2
[1, 0, 0, 2, 3, 0, 4, 0, 0, 0, 6] 0 -> 3

This code is pretty readable in my opinion but I fear that the \$O(N^2)\$ time complexity is sub-optimal.

def subsequences(arr)
  ((0...arr.length).to_a)
    .repeated_permutation(2)
    .select {|start, finish| finish >= start}
    .collect {|start, finish| arr[start..finish] }
end 

def longest_item_only_subsequence_len(arr, item)
   subsequences(arr)
     .select {|seq| seq.all? {|i| i == item} }
     .max_by(&:length)
     .length
end

p subsequences([1, 2, 3])
p longest_item_only_subsequence_len([1, 0, 0, 2, 3, 0, 4, 0, 0, 0, 6], 0)
\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

Yes, chunk is the way to go. I'd write it differently, though, using a list-comphehension approach (in Ruby: map+if+compact. Or with a custom method.) and taking in account the edge case (no elements item in the array):

def longest_item_only_subsequence_len(xs, item)
  xs.chunk(&:itself).map { |y, ys| ys.size if y == item }.compact.max || 0
end
\$\endgroup\$
7
  • \$\begingroup\$ ys.size if y == item equals y == item ? ys.size : nil right? \$\endgroup\$
    – Caridorc
    Aug 23, 2015 at 7:59
  • \$\begingroup\$ Right. In fact, I like it with ? better because it looks more like an expression, but the other looks more like a list-comprehension. Take your pick. \$\endgroup\$
    – tokland
    Aug 23, 2015 at 8:01
  • \$\begingroup\$ As a minor comment, which spacing style is reccomended in Ruby? All on one line or each method call on its own line? \$\endgroup\$
    – Caridorc
    Aug 23, 2015 at 8:08
  • 1
    \$\begingroup\$ IMO: if it fits in one line, one line. If I think it's too long, I give it a name and use it in another line. \$\endgroup\$
    – tokland
    Aug 23, 2015 at 8:09
  • \$\begingroup\$ To me separate lines help for chronological order, top before, then bottom. It is subjective though. \$\endgroup\$
    – Caridorc
    Aug 23, 2015 at 8:11
1
\$\begingroup\$

After some more thinking, I realized that Array.chunk is O(N) and what I was looking for:

 def longest_item_only_subsequence_len(arr, item)
   return 0 if ! arr.include?(item)
   arr
    .chunk(&:itself)
    .select{|kind, _| kind == item}
    .collect {|_, subseq| subseq}
    .max_by(&:length)
    .length
end
\$\endgroup\$
3
  • \$\begingroup\$ This last length probably fails when arr has no item in it. \$\endgroup\$
    – tokland
    Aug 23, 2015 at 8:00
  • \$\begingroup\$ @tokland I may just add a check at the start of the function, but maybe it should fail. Not finding a subsequence is exceptional. (An empty subsequence counts in your opinion?) \$\endgroup\$
    – Caridorc
    Aug 23, 2015 at 8:06
  • \$\begingroup\$ Yes, I think the code should just work (return 0) if there is no item item in the sequence. \$\endgroup\$
    – tokland
    Aug 23, 2015 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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