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.

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