1

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])
Improve this question
4
  • array.values_at( 4, 3, 2, 1, 0 ) Commented Aug 3, 2014 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). Commented Aug 3, 2014 at 3:45
  • If we have a collection, we need to loop or iterate. No escape. Commented Aug 3, 2014 at 4:06
  • So what do StackOverflow get for answering your coding challenge for you?! :-/ Commented Aug 3, 2014 at 11:04

8 Answers 8

Reset to default
6

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
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

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.
Yes, of course - this is a pure functional approach, without modifying any data, so the new object must be created every iteration.
4

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)
Improve this answer

4 Comments

You hurt me at last! :-)
One thing.. I learned today.. There is a limit to the number arguments of a method.
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
Yeah I expected it nevertheless recursion is the only method you can have if you don't want to use a loop :)
3

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)
Improve this answer

3 Comments

You can have a different implementation. But you shouldn't override core methods.
@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.
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.
2

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.

Improve this answer

6 Comments

Arup, is there a way to count downwards with the infamous for loop?
@BorisStitnicky When you use for loop, it also call internally #each method. So you can't do with for loop.
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.
That means the only way to perform something similar would be by using while / until loop and decrement by hand...
yes.. But why don't you like Fixnum#downto method ? :-)
|
2

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.

Improve this answer

Comments

1

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]
Improve this answer

Comments

0

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.

Improve this answer

Comments

0 
def reverse(array)
    array.values_at(*((array.size-1).downto 0))
end
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.