current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.6 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 1 down vote favorite

I have a coding challenge to reverse a an array with 5 elements in it. How would I do this without using the reverse method?

Code:

def reverse(array)
 array
end

p reverse(["a", 1, "apple", 8, 90])
share|improve this question
    
array.values_at( 4, 3, 2, 1, 0 ) – Boris Stitnicky Aug 3 '14 at 0:06
2  
Could you clarify your question, please? In the question text you ask about reversing without using Array#reverse, but in the question title you are asking about reversing without using a loop (and yet you accepted an answer which uses a loop). – Jörg W Mittag Aug 3 '14 at 3:45
    
If we have a collection, we need to loop or iterate. No escape. – Arup Rakshit Aug 3 '14 at 4:06
    
So what do StackOverflow get for answering your coding challenge for you?! :-/ – Pavling Aug 3 '14 at 11:04
up vote 5 down vote accepted

You can treat array as a stack and pop the elements from the end:

def reverse(array)
  rev = []
  rev << array.pop until array.empty?
  rev
end

or if you don't like modifying objects, use more functional-like reduce:

def reverse(array)
  array.reduce([]) {|acc, x| [x] + acc}
end

Cary mentioned in the comment about the performance. The functional approach might not be the fastest way, so if you really want to do it fast, create a buffor array and just add the items from the end to begin:

def reverse(array)
  reversed = Array.new(array.count)
  array.each_with_index do |item, index|
    reversed[-(index + 1)] = item
  end
  reversed
end
share|improve this answer
3  
The latter has the efficiency disadvantage of creating a new array for each x. If you look at acc.object_id you'll see it changes each iteration. – Cary Swoveland Aug 3 '14 at 3:00
    
Yes, of course - this is a pure functional approach, without modifying any data, so the new object must be created every iteration. – Grych Aug 3 '14 at 11:16
up vote 3 down vote

Recursion indeed is the solution if you're not going to use a loop. while or until is still a loop, and using built-in methods not doing recursion may also still be using a loop internally.

#!/usr/bin/env ruby

a = [1, 2, 3]

def reverse(array)
  t = array.pop
  reverse(array) if array.length > 0
  array.unshift t
end

puts reverse(Array.new(a)).inspect # [3, 2, 1]

Update

Naturally recursion has limits since it depends on the stack but that's the best you can have if you don't want to use a loop. Following Cary Swoveland's post, this is the benchmark on 8500 elements:

                         user     system      total        real
@Grych               0.060000   0.010000   0.070000 (  0.073179)
@ArupRakshit         0.000000   0.000000   0.000000 (  0.000836)
@konsolebox          0.000000   0.000000   0.000000 (  0.001771)
@JörgWMittag recursion  0.050000   0.000000   0.050000 (  0.053475)
@Jörg        tail    0.210000   0.040000   0.250000 (  0.246849)
@Jörg        fold    0.040000   0.010000   0.050000 (  0.045788)
@Jörg        loop    0.000000   0.000000   0.000000 (  0.000924)
Cary         rotate  0.060000   0.000000   0.060000 (  0.059954)
Cary         boring  0.000000   0.000000   0.000000 (  0.001004)
share|improve this answer
    
You can have a different implementation. But you shouldn't override core methods. – Arup Rakshit Aug 3 '14 at 5:06
    
@ArupRakshit Originally yes, but I thought I wouldn't want to define a method that doesn't explicitly say that it alters its argument's data. – konsolebox Aug 3 '14 at 5:07
    
An obvious way is to create a new array instance within but that would complicate the recursion method with ifs. Another obvious method as well is to use a submethod like __reverse. – konsolebox Aug 3 '14 at 5:10
up vote 3 down vote

Gentlemen, start your engines!

[Edit: added two method from @Grych and results for n = 8_000.]

@Grych, @ArupRakshit, @konsolebox and @JörgWMittag: please check that I've written your method(s) correctly.

Methods

def grych_reduce(array)
  array.reduce([]) {|acc, x| [x] + acc}
end

def grych_prebuild(array)
  reversed = Array.new(array.count)
  array.each_with_index do |item, index|
    reversed[-(index + 1)] = item
  end
  reversed
end

def arup(ary)
  ary.values_at(*(ary.size-1).downto(0))
end

def konsolebox(array)
  t = array.pop
  konsolebox(array) if array.length > 0
  array.unshift t
end    

def jorg_recurse(array)
  return array if array.size < 2
  reverse(array.drop(1)) + array.first(1)
end

def jorg_tail(array, accum=[])
  return accum if array.empty?
  reverse(array.drop(1), array.first(1) + accum)
end

def jorg_fold(array)
  array.reduce([]) {|accum, el| [el] + accum }
end

def jorg_loop(array)
  array.each_with_object([]) {|el, accum| accum.unshift(el) }
end

def cary_rotate(arr)
  arr.size.times.with_object([]) { |_,a| a << arr.rotate!(-1).first }
end

def cary_boring(arr)
  (arr.size-1).downto(0).with_object([]) { |i,a| a << arr[i] }
end

Benchmark

require 'benchmark'

arr = [*(1..n)]
puts "n = #{n}"    

Benchmark.bm(16) do |bm|
  bm.report('grych_reduce')    { grych_reduce(arr) }
  bm.report('grych_prebuild')  { grych_prebuild(arr) }
  bm.report('arup')            { arup(arr)  }
  bm.report('konsolebox')      { konsolebox(arr) }
  bm.report('jorg_recurse')    { jorg_recurse(arr) }
  bm.report('jorg_tail')       { jorg_tail(arr)  }
  bm.report('jorg_fold')       { jorg_fold(arr)  }
  bm.report('jorg_loop')       { jorg_loop(arr)  }
  bm.report('cary_rotate')     { cary_rotate(arr)  }
  bm.report('cary_boring')     { cary_boring(arr) }
  bm.report('grych_destructo') { grych_destructo(arr) }
end

Wednesday: warm-up (n = 8_000)

                       user     system      total        real
grych_reduce       0.060000   0.060000   0.120000 (  0.115510)
grych_prebuild     0.000000   0.000000   0.000000 (  0.001150)
arup               0.000000   0.000000   0.000000 (  0.000563)
konsolebox         0.000000   0.000000   0.000000 (  0.001581)
jorg_recurse       0.060000   0.040000   0.100000 (  0.096417)
jorg_tail          0.210000   0.070000   0.280000 (  0.282729)
jorg_fold          0.060000   0.080000   0.140000 (  0.138216)
jorg_loop          0.000000   0.000000   0.000000 (  0.001174)
cary_rotate        0.060000   0.000000   0.060000 (  0.056863)
cary_boring        0.000000   0.000000   0.000000 (  0.000961)
grych_destructo    0.000000   0.000000   0.000000 (  0.000524)

Thursday: trials #1 (n = 10_000)

                       user     system      total        real
grych_reduce       0.090000   0.080000   0.170000 (  0.163276)
grych_prebuild     0.000000   0.000000   0.000000 (  0.001500)
arup               0.000000   0.000000   0.000000 (  0.000706)
jorg_fold          0.080000   0.060000   0.140000 (  0.139656)
jorg_loop          0.000000   0.000000   0.000000 (  0.001388)
cary_rotate        0.090000   0.000000   0.090000 (  0.087327)
cary_boring        0.000000   0.000000   0.000000 (  0.001185)
grych_destructo    0.000000   0.000000   0.000000 (  0.000694)

konsolebox, jorg_recurse and jorg_tail eliminated (stack level too deep).

Friday: trials #2 (n = 50_000)

                       user     system      total        real
grych_reduce       2.430000   3.490000   5.920000 (  5.920393)
grych_prebuild     0.010000   0.000000   0.010000 (  0.007000)
arup               0.000000   0.000000   0.000000 (  0.003826)
jorg_fold          2.430000   3.590000   6.020000 (  6.026433)
jorg_loop          0.010000   0.010000   0.020000 (  0.008491)
cary_rotate        2.680000   0.000000   2.680000 (  2.686009)
cary_boring        0.010000   0.000000   0.010000 (  0.006122)
grych_destructo    0.000000   0.000000   0.000000 (  0.003288)

Saturday: qualifications (n = 200_000)

                       user     system      total        real
grych_reduce      43.720000  66.140000 109.860000 (109.901040)
grych_prebuild     0.030000   0.000000   0.030000 (  0.028287)
jorg_fold         43.700000  66.490000 110.190000 (110.252620)
jorg_loop          0.030000   0.010000   0.040000 (  0.030409)
cary_rotate       43.060000   0.050000  43.110000 ( 43.118151)
cary_boring        0.020000   0.000000   0.020000 (  0.024570)
grych_destructo    0.010000   0.000000   0.010000 (  0.013338)

arup_verse eliminated (stack level too deep); grych_reduce, jorg_fold and cary_rotate eliminated (uncompetitive).

Sunday: final (n = 10_000_000)

                       user     system      total        real
grych_prebuild     1.450000   0.020000   1.470000 (  1.478903)
jorg_loop          1.530000   0.040000   1.570000 (  1.649403)
cary_boring        1.250000   0.040000   1.290000 (  1.288357)
grych_destructo    0.640000   0.030000   0.670000 (  0.689819)
share|improve this answer
    
You hurt me at last! :-) – Arup Rakshit Aug 3 '14 at 6:12
2  
One thing.. I learned today.. There is a limit to the number arguments of a method. – Arup Rakshit Aug 3 '14 at 6:14
    
This is a great benchmark, thanks! Could you please add the method I just added to my answer (the one with each_with_index)? It should be quite fast I assume – Grych Aug 3 '14 at 11:46
    
Yeah I expected it nevertheless recursion is the only method you can have if you don't want to use a loop :) – konsolebox Aug 3 '14 at 12:36
    
I confirm my method. It's a nicely done report. +1 – konsolebox Aug 4 '14 at 7:25
up vote 2 down vote

One thought :-

ary = ["a", 1, "apple", 8, 90]
ary.values_at(*(ary.size-1).downto(0))
# => [90, 8, "apple", 1, "a"]

ary.size.downto(0) gives #<Enumerator: ...>. And *#<Enumerator: ...> is just a Enumerable#to_a method call which splats the Enumerator to [4, 3, 2, 1, 0]. Finally, Array#values_at is working as documented.

share|improve this answer
    
Arup, is there a way to count downwards with the infamous for loop? – Boris Stitnicky Aug 3 '14 at 3:49
    
@BorisStitnicky Fixnum#downto.. – Arup Rakshit Aug 3 '14 at 3:50
    
@BorisStitnicky When you use for loop, it also call internally #each method. So you can't do with for loop. – Arup Rakshit Aug 3 '14 at 3:54
    
I'd be thinking more about something like for x in [*4..0] do ... end, but that doesn't work. So I just wondered whether the infamous for loop can actually count downwards. – Boris Stitnicky Aug 3 '14 at 3:54
    
That means the only way to perform something similar would be by using while / until loop and decrement by hand... – Boris Stitnicky Aug 3 '14 at 3:55
up vote 2 down vote

The obvious solution is to use recursion:

def reverse(array)
  return array if array.size < 2
  reverse(array.drop(1)) + array.first(1)
end

We can make this tail-recursive using the standard accumulator trick:

def reverse(array, accum=[])
  return accum if array.empty?
  reverse(array.drop(1), array.first(1) + accum)
end

But of course, tail recursion is isomorphic to looping.

We could use a fold:

def reverse(array)
  array.reduce([]) {|accum, el| [el] + accum }
end

But fold is equivalent to a loop.

def reverse(array)
  array.each_with_object([]) {|el, accum| accum.unshift(el) }
end

Really, each_with_object is an iterator and it is the side-effectful cousin of fold, so there's actually two reasons why this is equivalent to a loop.

share|improve this answer
up vote 1 down vote

Here's another non-destructive approach:

arr = ["a", 1, "apple", 8, 90]

arr.size.times.with_object([]) { |_,a| a << arr.rotate!(-1).first }
  #=> [90, 8, "apple", 1, "a"]
arr
  #=> ["a", 1, "apple", 8, 90]

Another would the most uninteresting method imaginable:

(arr.size-1).downto(0).with_object([]) { |i,a| a << arr[i] }
  #=> [90, 8, "apple", 1, "a"]
arr
  #=> ["a", 1, "apple", 8, 90]
share|improve this answer
up vote 1 down vote

Konsolebox is right. If they are asking for the method without loops, that simply means that you cannot use any kind of loop whether it is map, each, while, until or any even built in methods that use loops, like length, size and count etc.

Everything needs to be recursive:

def recursive_reversal(array)

  return array if array == [] # or array.empty?
  last_element = array.pop
  return [last_element, recursive_reversal(array)].flatten

end

Ruby uses recursion to flatten, so flatten will not entail any kind of loop.

share|improve this answer
up vote 1 down vote 
def reverse(array)
    array.values_at(*((array.size-1).downto 0))
end
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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