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\$
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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ ys.size if y == item equals y == item ? ys.size : nil right? \$\endgroup\$ – Caridorc Aug 23 '15 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 '15 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 '15 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 '15 at 8:09
  • \$\begingroup\$ To me separate lines help for chronological order, top before, then bottom. It is subjective though. \$\endgroup\$ – Caridorc Aug 23 '15 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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This last length probably fails when arr has no item in it. \$\endgroup\$ – tokland Aug 23 '15 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 '15 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 '15 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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