Manipulating arrays with recursive function

Question

def rps_tournament_winner(tournament)
  for i in 0..1 do
    if tournament[i][1].is_a? Array then
      rps_tournament_winner(tournament[i])
    else 
      tournament=rps_game_winner(tournament)
      return
    end
  end
  return tournament
end

This is a part of rock-papers-scissors implementation in Ruby

rps_game_winner

takes an array of two arrays in format of

[ ["Allen", "S"], ["Omer", "P"] ]

where first element is player's name, second element is their decision and returns the winner.

rps_tournament_winner

takes an input of nested arrays with arbitrary depth like

[
  [
    [ ["Armando", "P"], ["Dave", "S"] ],
    [ ["Richard", "R"], ["Michael", "S"] ],
  ],
  [
    [ ["Allen", "S"], ["Omer", "P"] ],
    [ ["David E.", "R"], ["Richard X.", "P"] ]
  ]
]

What I am trying to do is modifying the original input as the function makes progress but the input comes out as it came in. Incorporating global variables are a solution but this is a work to be graded with an auto grader and I suspect it is just going to push some input directly to the function and compare the output so its not an option.

@NiklasB. Of course, since this is Ruby, it's impossible not to use objects ;). (I assume you mean classes, I'm just being pedantic.) — Andrew Marshall
– Andrew Marshall, Commented Mar 2, 2012 at 22:23
@Andrew: Oh, of course I meant objects with types sensible for the purpose ;) — Niklas B.
– Niklas B., Commented Mar 2, 2012 at 22:24

Niklas B. · Accepted Answer · 2012-03-02 22:32:13Z

3

Several problems with your original code:

You mix iteration with recursion
You throw away the result of the recursion (rps_tournament_winner(tournament[i]))
You don't return anything useful (return simply returns nil, but it doesn't matter, because you don't use the result anyways)

A fixed version using the original logic would be:

def rps_tournament_winner(tournament)
  result = []
  for i in 0..1 do
    if tournament[i][0][0].is_a? Array then
      result << rps_tournament_winner(tournament[i])
    else
      result << rps_game_winner(tournament[i])
    end
  end
  return result    
end

But actually that's equivalent to a simple

def rps_tournament_winner(tournament)
  if tournament[0][0].is_a? String
    rps_game_winner(tournament)
  else
    tournament.map { |t| rps_tournament_winner(t) }
  end
end

And it would be so much nicer using objects:

class Game < Struct.new(:player1, :choice1, :player2, :choice2)
  def winner
    'PRSP'.include?(choice1 + choice2) ? player1 : player2
  end
end

def rps_tournament_winner(tourn)
  return tourn.winner if tourn.is_a? Game
  tourn.map { |t| rps_tournament_winner(t) }
end

edited Mar 2, 2012 at 22:32

answered Mar 2, 2012 at 21:57

Niklas B.

95.8k18 gold badges201 silver badges228 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Phrogz Over a year ago

IMHO re-using the same variable name in the block as outside is not the best way to teach a new user :)

Niklas B. Over a year ago

@Phrogz: Yeah, I guess the actual problem is that I used a one-letter argument name :P fixed.

Andrew Marshall Over a year ago

I think an actual if/else statement would be better than the one line conditional early return (especially since the method is so short). Yes, it'd be two more lines, but I think it reads better.

Andrew Marshall Over a year ago

@NiklasB. Coming from C/C++ it makes me think the second line will never execute because by brain jumps over the if. Probably because I rarely use the return keyword at all in Ruby and it puts me in a different parsing mode.

Niklas B. Over a year ago

@Andrew: I don't like if/else constructs spanning a whole method, especially in cases like this where it's just an edge condition to check for. I also do this in C: Check and return early on special conditions like edge conditions of recursions or invalid arguments. It's a matter of taste, IMO. As a Perl programmer, this would surely feel a lot easier on the eyes :)

|

Community · Accepted Answer · 2017-05-23 11:48:09Z

3

Your recursive solution should keep choosing winners unless the final winner is decided. Niklas's second solution stops at when the first level winners are decided. It should be refined as follows:

def rps_tournament_winner(tournament)
    if(tournament[0][0].is_a? String)
        rps_game_winner(tournament)
    else
        rps_tournament_winner(
            [rps_tournament_winner(tournament[0]),
            rps_tournament_winner(tournament[1])]
        )
    end
end

edited May 23, 2017 at 11:48

CommunityBot

11 silver badge

answered Oct 16, 2012 at 13:36

mert

2,0122 gold badges25 silver badges43 bronze badges

1 Comment

PerseP Over a year ago

This is a much better solution

Jorge Saldivar · Accepted Answer · 2012-07-23 12:47:18Z

1

The following function can also be a solution to manipulate arrays with a recursive function:

def rps_tournament_winner(tournament)
    while not tournament[0].is_a? String do
        i = i == 0 ? 1 : 0
        if tournament[i][0].is_a? String
            return rps_game_winner(tournament)
        else
            tournament[i] = rps_tournament_winner(tournament[i])
        end
    end
    return tournament
end

answered Jul 23, 2012 at 12:47

Jorge Saldivar

111 bronze badge

Collectives™ on Stack Overflow

Manipulating arrays with recursive function

3 Answers 3

8 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related