"Reverse Groups" challenge

Question

I'm trying to do the Reverse Groups Challenge on CodeEval:

Given a list of numbers and a positive integer k, reverse the elements of the list, k items at a time. If the number of elements is not a multiple of k, then the remaining items in the end should be left as is.

My logic is functional, but when I try to submit my solution is says that it timed out at 10 seconds. How can I improve the speed here?

File.open(ARGV.first).readlines.each do |line|  
  values, k = line.split(';')
  k = k.to_i
  values = values.split(',')
  current = values.shift(k)
  str = ""   
  while current.count % k == 0 do
    current.reverse_each{ |val| str += "#{val},"}
    current = values.shift(k)
  end    
  str << "#{current.join(',')}"
  puts str
end

Other attempt:

open(ARGV[0]).readlines.each do |line|  
  values, k = line.chomp.split(';')
  k = k.to_i
  values = values.split(',')
  current = values.shift(k)
  str = ""   
  while current.count % k == 0 do
    current.reverse_each{ |val| str << "#{val},"}
    current = values.shift(k)
  end    
  str << "#{current.join(',')}"
  puts str
end

Answer 1

I can't say what CodeEval's time limits are, or why this code should particularly slow. There are a lot of things you could do differently, though:

1. Instead of readlines, you can use each_line to iterate the lines, instead of reading all of them into an array, and then iterating.

2. You can get the values and k in a single line:

   *values, k = line.chomp.split(/[,;]/)
   

3. Look up each_slice; it'll iterate an array in "chunks" of the given length

4. Don't do "manual" string concatenation. You already use join in one place, but you can use it anywhere you need a string representation of an array.

5. You're shifting k items off of the array, and you then check if the number of shifted items is divisible by k. But shift will either shift exactly k items or fewer, so the modulus operator is a really roundabout way of saying current.count == k.

6. You code fails if there are blank lines. CodeEval doesn't say whether the file can contain blank lines, but, if it does, well...

All in all, you're approaching this very procedurally. A nicer approach would be something like

1. Chunk the items in k-sized arrays (the last chunk may be smaller)
2. Reverse the chunks that are k items long
3. Put the arrays back together into one
4. Join with commas and print

Or, in code:

File.open(ARGV.first).each_line do |line|
  *items, k = line.chomp.split(/[,;]/)
  next unless k # skip empty lines
  puts items.each_slice(k.to_i).map { |group| group.count < k.to_i ? group : group.reverse }.flatten.join(",")
end

Edit: As Naklion points out in the comments, using flat_map is of course better than using map and flatten separately, i.e.:

items.each_slice(k.to_i).flat_map { |group| group.count < k.to_i ? group : group.reverse }.join(",")

I've update the rest of the code blocks to use flat_map

That 3rd line is a bit long, though, so to spell it out:

File.open(ARGV.first).each_line do |line|
  *items, k = line.chomp.split(/[,;]/)
  next unless k
  chunks = items.each_slice(k.to_i)
  reversed = chunks.flat_map { |chunk| chunk.count < k.to_i ? chunk : chunk.reverse }
  puts reversed.join(",")
end

You can also do pop off the last chunk if you know it to be smaller than k, which lets you say simply map(&:reverse) on the remaining elements

File.open(ARGV.first).each_line do |line|
  *items, k = line.chomp.split(/[,;]/)
  next unless k
  k = k.to_i
  chunks = items.each_slice(k).to_a
  tail = items.count % k == 0 ? [] : chunks.pop
  puts chunks.flat_map(&:reverse).concat(tail).join(",")
end

Last alternative: Pop off enough items that the remaining ones are cleanly divisible by k before slicing

File.open(ARGV.first).each_line do |line|
  *items, k = line.chomp.split(/[,;]/)
  next unless k
  k = k.to_i
  tail = items.pop(items.count % k)
  puts items.each_slice(k).flat_map(&:reverse).concat(tail).join(",")
end

But frankly, I like the first code block the best.

All of these are a little faster than your code, by the way. It's not a huge difference, but it's faster.

Answer 2

You're probably exceeding the time limit because you have an infinite loop. If the length of the list is a multiple of k, then at some point values and current will both be empty arrays.