Performance of Codility MaxCounter challenge solution

Question

I'm doing some of the Codility challenges using Ruby. The current challenge is "The MaxCounter," which is described as:

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

See the link above for more details. I managed to get a solution. The performance, however, scored 0, being that some operations timed out. How can I improve my algorithm to perform better?

def solution(n, a)
 counter = (0..n-1).to_a.map{|z| z = 0}
 for value in a
 counter.map!{|x| x = counter.max} unless value <= n
 counter[value-1] += 1 unless value == n+1
 end
 counter
end

Update - my second and third attempts, still fails on performance

2nd

def solution(n, a)
 counter = (0..n-1).to_a.map{|z| z = 0}
 a.each{|x| counter.map!{|c| c = counter.max} unless x <= n; counter[x-1] +=1 unless x==n+1;}
 counter
end

3rd

def solution(n, a)
 counter = (0..n-1).to_a.map{|z| z = 0}
 a.each{|x| counter[x-1] +=1 and next unless x==n+1; counter.map!{|x| x = counter.max};}
 return counter
end

Answer 1

I can't speak to performance, since I don't know what codility considers acceptable, but I'll give it a go.

In terms of reviewing your code, your solutions seem to be getting more and more compact, but that doesn't necessarily help performance. Shorter code does not equal faster code. Sure, if you can skip code, that's one thing, but just shaving off bytes of source code is unnecessary.

You certainly should not make confusing constructions like unless ... unless or and next unless. Just read that out loud, and it'll sound strange.

And I don't think there's any advantage to using the self-modifying map!. In fact, there's no reason to use map at all.

And please don't add pointless semi-colons. A nice aspect of Ruby is not having to use those darn things everywhere.

You also seem to misinterpreting how map (with or without the !) works. These are all equivalent:

 counter.map! {|x| x = counter.max}
 counter.map! {|x| counter.max}
 counter.map! {counter.max}

In other words, you setting the block parameter x does absolutely nothing useful - you don't even need the block parameter. The map method(s) only use the block's return value.

Moreover, your block gets invoked n times by map!, since n is the counter-array's length. That means that counter.max gets called n times, even though the result is the same each time! If n is large, you're looking at a lot of unnecessary work being done there. Worst case is at that all of the values in a equal n + 1, in which case you'll be calling counter.max a total of a.count * n times. And given that you're using map!, I doubt Ruby even has a chance to cache/memoize or otherwise optimize the result of counter.max, since you keep changing the array in-place.

Besides, Array provides a lot of help here, if you check the docs.

• fill does what it says in the name: Fills the array with a given value (or by using a block), which is what you're trying to do with map!
• and Array.new accepts a length and a seed value, so you can fill a brand new array right away. Don't muck around with mapping a range; just make an array of the right length that's filled with zeros.

Here's my take

def solution(n, a)
 counters = Array.new(n, 0) # an array of zeros (and make the var name plural, since it's an array)
 limit = n + 1 # let's just calculate this once, since it's constant
 a.each do |v|
 if v == limit
 counters.fill(counters.max) # max gets called once, and the array gets filled
 elsif v > 0 && v < limit
 counters[v-1] += 1 # just increment
 end
 end
 counters
end

It works for the sample input in Codility's example, but as mentioned I haven't gone beyond that.

---

Update: With a bit of manual work, you can get rid of the call to max entirely by tracking the maximum yourself:

def solution(n, a)
 counters = Array.new(n, 0)
 limit = n + 1
 maximum = 0 # the maximum counter value
 a.each do |v|
 if v == limit
 counters.fill(maximum) # use our known maximum
 elsif v > 0 && v < limit
 counter = (counters[v-1] += 1) # increment a counter and store the result
 maximum = counter if counter > maximum # use the new value as maximum, if it's higher
 end
 end
 counters
end

This will likely be faster than the first approach, especially for larger values of n. It's maybe not quite as Ruby-esque to do things "manually" like this, but it's not terribly complex either.

• Antarr Byrd: Thanks this is much more efficient algorithm according to Codility. It got 40/100 vs my 0, with a complexity of O(N*M). You're explanation for the path was very valuable as well. I appreciate it.
• Flambino: @AntarrByrd You're welcome. You can probably improve performance further by manually keeping track of the current maximum instead of using counters.max. I'll update my answer a little (I can't help myself) :)
• Antarr Byrd: Nice. That got it up to 80/100
• Flambino: @AntarrByrd Nice - although now I really want to get it to 100/100. But I don't really have any great ideas, so I'll just let it be, I think :)

Answer 2

Codility 100/100%

https://github.com/mrhead/codility

Credits to MrHead

def solution(n, a)
 counters = Array.new(n, 0)
 max = 0
 min = 0
 a.each do |v|
 if v <= n
 if counters[v - 1] < min + 1
 counters[v - 1] = min + 1
 else
 counters[v - 1] += 1
 end
 max = [max, counters[v - 1]].max
 else
 min = max
 end
 end
 counters.each_index do |i|
 counters[i] = min if counters[i] < min
 end
 counters
end