CODEWITHSUNDEEP
rubyrecursion
Felipe
Felipe

Reputation: 11887

How to recurse through arrays in Ruby

I'm trying to use the two following methods to recursively traverse arrays of arrays until the bottom and then come back up with the match results.

You know how in a tennis tournament they start with 32 matches and pair by pair the winner moves ahead, and at the end there's only one winner? That's what I want to replicate in Ruby.

I created a match_winner that always returns the first array for the sake of simplicity. Then, I send the whole tournament array into winner that calls itself recursively until it finds a simple array corresponding to a single match.

def match_winner(array_of_arrays)
  return array_of_arrays[0]
end

def winner(tournament)
  if tournament[0][0].is_a?(String)
    return match_winner(tournament)
  else
    tournament.each{|e|
      winner(e)
    }
  end
end

tournament = [
  [["one", "two"],["three", "four"]],
  [["five", "six"],["seven", "eight"]]
  ]

puts winner(tournament).inspect

Which outputs:

[[["one", "two"], ["three", "four"]], [["five", "six"], ["seven", "eight"]]]

I tried different permutations and variations on this algorithm but I couldn't make it work correctly and return only the final winner.

Does anyone see anything obviously wrong here?

Now I'm calling winner.

Upvotes: 0

Views: 1022

Answers (3)

emre nevayeshirazi
emre nevayeshirazi

Reputation: 19241

Assuming you have 2^n number of games always and match_winner works ok:

def winner(game)
  if game[0][0][0] == game[0][0][0][0]
    match_winner( [ game[0], game[1] ] )
  else
    match_winner( [winner(game[0]), winner(game[1])] ) 
  end
end

Upvotes: 0

Clergyman
Clergyman

Reputation: 283

I know that the question looks like it's answered, but I just did the same problem and I have to say that simply changing each to map didn't work for me, because, as the code posted, the result is an array of the first-round winners. What worked for me is:

def winner(tournament)
  if tournament[0][0].is_a?(String)
    return match_winner(tournament)
  else
    tournament.map!{|e| #use map!, because we need to apply winner() to new values
      e=winner(e)       #assign new value somewhere, so recursion can climb back
    }
  end
end

Maybe more experienced developers can explain why that is. Without these two tips it won't work.

And yes, I know "bang" is a bad coding style, danger danger high voltage, but it's my second day with Ruby and I wanted to get this to work.

And, to understand recursion, you have to understand recursion.

Upvotes: 1

Thomas Andrews
Thomas Andrews

Reputation: 1597

Looks like you want map, not each, and, as a commenter above notes, you didn't call winner in the above code.

When you call:

tournament.each {...}

that method actually returns the tournament, which is thus what winner returns.

What you want is to replace it with 

tournament.map {...}

which returns a new array consisting of calling "winner" on each element of tournament.

Upvotes: 0

Related Questions