[Résolu] Algorithme de match making - Composer des équipes sans joueurs en commun

[Sephi-Chan]

Impeccable ! Je trouve cet algorithme bien plus propre que celui que j'avais produit (récursif). Je prends !

Pour info, voici le code de mon dispatcheur et de sa suite de tests unitaires. L'algorithme décrit est implémenté dans dispatchable_groups_for_format.

# Dispatch ready game searches into games whenever it is possible.

class Dispatcher

  attr_reader :communication_client





  def initialize(game_searches, communication_client)

    @game_searches        = game_searches

    @communication_client = communication_client

  end





  def dispatch!

    Game.transaction do

      dispatchable_game_searches_by_format.inject([]) do |games, (format, group_of_game_searches)|

        group_of_game_searches.each do |game_searches|

          game = Game.create!(format: format, status: Game::CREATED)

          game_searches.each do |game_search|

            team = game.teams.create!(game_search: game_search, status: Team::ALIVE, players: game_search.players)

            game_search.update!(status: GameSearch:ISPATCHED, game: game)

            team.players.each do |player|

              communication_client.push(player, {

                event:          Queues::MatchMaker::GAME_SEARCH_SUCCEEDED,

                players:        team.players.map { |player| { id: player.id, name: player.name } },

                game_search_id: team.game_search_id,

                status:         GameSearch::SUCCEEDED,

                game_id:        game.id

              })

            end

          end



          games << game

        end



        games

      end

    end

  end





  private



  def game_searches_by_format

    @game_searches.group_by(&:format)

  end





  def dispatchable_game_searches_by_format

    game_searches_by_format.inject({}) do |hash, (format, game_searches)|

      groups         = dispatchable_groups_for_format(format, game_searches)

      hash[format] ||= groups if groups.any?

      hash

    end

  end





  # For a given format, returns a list of game searches for each dispatchable game.

  # Example: [ [ GameSearch A, GameSearch B ], [ GameSearch C, GameSearch D ] ]

  def dispatchable_groups_for_format(format, game_searches)

    dispatched_player_ids  = []

    selected_game_searches = []

    groups                 = []



    game_searches.each do |game_search|

      if (game_search.player_ids & dispatched_player_ids).empty?

        dispatched_player_ids.push(*game_search.player_ids)

        selected_game_searches << game_search

        if format.teams_count == selected_game_searches.size

          groups << selected_game_searches

          selected_game_searches = []

        end

      end

    end



    groups

  end

end

Et la suite de tests, avec la participation bénévole des personnages du Cycle des Princes d'Ambre.

require 'spec_helper'



describe Dispatcher do

  let(:communication_client) { stub }

  let(:format_2_3)           { FactoryGirl.build(:format, teams_count: 2, teams_size: 3) }



  let(:corwin)               { FactoryGirl.create(:player, name: 'Corwin') }

  let(:mandor)               { FactoryGirl.create(:player, name: 'Mandor') }

  let(:caine)                { FactoryGirl.create(:player, name: 'Caine') }

  let(:corwin_invitation)    { FactoryGirl.build(:invitation, :accepted, player: corwin) }

  let(:mandor_invitation)    { FactoryGirl.build(:invitation, :accepted, player: mandor) }

  let(:caine_invitation)     { FactoryGirl.build(:invitation, :accepted, player: caine) }

  let(:first_game_search)    { FactoryGirl.create(:game_search, :ready, invitations: [ corwin_invitation, mandor_invitation, caine_invitation ], format: format_2_3) }



  let(:brand)                { FactoryGirl.create(:player, name: 'Brand') }

  let(:bleys)                { FactoryGirl.create(:player, name: 'Bleys') }

  let(:julian)               { FactoryGirl.create(:player, name: 'Julian') }

  let(:brand_invitation)     { FactoryGirl.build(:invitation, :accepted, player: brand) }

  let(:bleys_invitation)     { FactoryGirl.build(:invitation, :accepted, player: bleys) }

  let(:julian_invitation)    { FactoryGirl.build(:invitation, :accepted, player: julian) }

  let(econd_game_search)   { FactoryGirl.create(:game_search, :ready, invitations: [ brand_invitation, bleys_invitation, julian_invitation ], format: format_2_3) }



  let(:fiona)                { FactoryGirl.create(:player, name: 'Fiona') }

  let(:deirdre)              { FactoryGirl.create(:player, name: 'Deirdre') }

  let(:flora)                { FactoryGirl.create(:player, name: 'Flora') }

  let(:fiona_invitation)     { FactoryGirl.build(:invitation, :accepted, player: fiona) }

  let(:deirdre_invitation)   { FactoryGirl.build(:invitation, :accepted, player: deirdre) }

  let(:flora_invitation)     { FactoryGirl.build(:invitation, :accepted, player: flora) }

  let(:third_game_search)    { FactoryGirl.create(:game_search, :ready, invitations: [ fiona_invitation, deirdre_invitation, flora_invitation ], format: format_2_3) }



  let(:random)               { FactoryGirl.create(:player, name: 'Random') }

  let(:gerard)               { FactoryGirl.create(:player, name: 'Gerard') }

  let(:dworkin)              { FactoryGirl.create(:player, name: 'Dworkin') }

  let(:random_invitation)    { FactoryGirl.build(:invitation, :accepted, player: random) }

  let(:gerard_invitation)    { FactoryGirl.build(:invitation, :accepted, player: gerard) }

  let(:dworkin_invitation)   { FactoryGirl.build(:invitation, :accepted, player: dworkin) }

  let(:fourth_game_search)   { FactoryGirl.create(:game_search, :ready, invitations: [ random_invitation, gerard_invitation, dworkin_invitation ], format: format_2_3) }





  it 'composes no game when there is only 1 ready team' do

    games = Dispatcher.new([ first_game_search ], communication_client).dispatch!

    games.should be_empty

  end





  it 'composes 1 game when 2 teams are ready for the same 2-teams format' do

    common_keys     = { event: Queues::MatchMaker::GAME_SEARCH_SUCCEEDED, status: GameSearch::SUCCEEDED, game_id: anything }

    expected_hash_1 = hash_including(common_keys.merge(game_search_id: first_game_search.id, players: [ { id: corwin.id, name: corwin.name }, { id: mandor.id, name: mandor.name }, { id: caine.id, name: caine.name } ]))

    communication_client.should_receive(:push).with(corwin, expected_hash_1)

    communication_client.should_receive(:push).with(mandor, expected_hash_1)

    communication_client.should_receive(:push).with(caine,  expected_hash_1)



    expected_hash_2 = hash_including(common_keys.merge(game_search_id: second_game_search.id, players: [ { id: brand.id, name: brand.name }, { id: bleys.id, name: bleys.name }, { id: julian.id, name: julian.name } ]))

    communication_client.should_receive(:push).with(brand,  expected_hash_2)

    communication_client.should_receive(:push).with(bleys,  expected_hash_2)

    communication_client.should_receive(:push).with(julian, expected_hash_2)



    game_searches  = [ first_game_search, second_game_search ]

    games          = Dispatcher.new(game_searches, communication_client).dispatch!



    games[0].teams[0].players.should == [ corwin, mandor, caine ]

    games[0].teams[1].players.should == [ brand, bleys, julian ]

  end





  it 'compose 2 games when 4 teams are ready for the same 2-teams format' do

    common_keys     = { event: Queues::MatchMaker::GAME_SEARCH_SUCCEEDED, status: GameSearch::SUCCEEDED, game_id: anything }

    expected_hash_1 = hash_including(common_keys.merge(game_search_id: first_game_search.id, players: [ { id: corwin.id, name: corwin.name }, { id: mandor.id, name: mandor.name }, { id: caine.id, name: caine.name } ]))

    communication_client.should_receive(:push).with(corwin, expected_hash_1)

    communication_client.should_receive(:push).with(mandor, expected_hash_1)

    communication_client.should_receive(:push).with(caine,  expected_hash_1)



    expected_hash_2 = hash_including(common_keys.merge(game_search_id: second_game_search.id, players: [ { id: brand.id, name: brand.name }, { id: bleys.id, name: bleys.name }, { id: julian.id, name: julian.name } ]))

    communication_client.should_receive(:push).with(brand,  expected_hash_2)

    communication_client.should_receive(:push).with(bleys,  expected_hash_2)

    communication_client.should_receive(:push).with(julian, expected_hash_2)



    expected_hash_3 = hash_including(common_keys.merge(game_search_id: third_game_search.id, players: [ { id: fiona.id, name: fiona.name }, { id: deirdre.id, name: deirdre.name }, { id: flora.id, name: flora.name } ]))

    communication_client.should_receive(:push).with(fiona,   expected_hash_3)

    communication_client.should_receive(:push).with(deirdre, expected_hash_3)

    communication_client.should_receive(:push).with(flora,   expected_hash_3)



    expected_hash_4 = hash_including(common_keys.merge(game_search_id: fourth_game_search.id, players: [ { id: random.id, name: random.name }, { id: gerard.id, name: gerard.name }, { id: dworkin.id, name: dworkin.name } ]))

    communication_client.should_receive(:push).with(random,  expected_hash_4)

    communication_client.should_receive(:push).with(gerard,  expected_hash_4)

    communication_client.should_receive(:push).with(dworkin, expected_hash_4)



    game_searches  = [ first_game_search, second_game_search, third_game_search, fourth_game_search ]

    games          = Dispatcher.new(game_searches, communication_client).dispatch!



    games[0].teams[0].players.should == [ corwin, mandor, caine ]

    games[0].teams[1].players.should == [ brand, bleys, julian ]



    games[1].teams[0].players.should == [ fiona, deirdre, flora ]

    games[1].teams[1].players.should == [ random, gerard, dworkin ]

  end





  it 'compose 1 games when 3 teams are ready for the same 2-teams format' do

    common_keys     = { event: Queues::MatchMaker::GAME_SEARCH_SUCCEEDED, status: GameSearch::SUCCEEDED, game_id: anything }

    expected_hash_1 = hash_including(common_keys.merge(game_search_id: first_game_search.id, players: [ { id: corwin.id, name: corwin.name }, { id: mandor.id, name: mandor.name }, { id: caine.id, name: caine.name } ]))

    communication_client.should_receive(:push).with(corwin, expected_hash_1)

    communication_client.should_receive(:push).with(mandor, expected_hash_1)

    communication_client.should_receive(:push).with(caine,  expected_hash_1)



    expected_hash_2 = hash_including(common_keys.merge(game_search_id: second_game_search.id, players: [ { id: brand.id, name: brand.name }, { id: bleys.id, name: bleys.name }, { id: julian.id, name: julian.name } ]))

    communication_client.should_receive(:push).with(brand,  expected_hash_2)

    communication_client.should_receive(:push).with(bleys,  expected_hash_2)

    communication_client.should_receive(:push).with(julian, expected_hash_2)



    game_searches = [ first_game_search, second_game_search, third_game_search ]

    games         = Dispatcher.new(game_searches, communication_client).dispatch!



    games[0].teams[0].players.should == [ corwin, mandor, caine ]

    games[0].teams[1].players.should == [ brand, bleys, julian ]

    games[0].game_searches.should == [ first_game_search, second_game_search]

  end





  it 'composes no game since the 2 teams has players in common' do

    corwin_invitation       = FactoryGirl.build(:invitation, :accepted, player: corwin)

    mandor_invitation       = FactoryGirl.build(:invitation, :accepted, player: mandor)

    caine_invitation        = FactoryGirl.build(:invitation, :accepted, player: caine)

    first_game_search       = FactoryGirl.create(:game_search, :ready, invitations: [ corwin_invitation, mandor_invitation, caine_invitation ], format: format_2_3)



    corwin_other_invitation = FactoryGirl.build(:invitation, :accepted, player: corwin)

    bleys_invitation        = FactoryGirl.build(:invitation, :accepted, player: bleys)

    julian_invitation       = FactoryGirl.build(:invitation, :accepted, player: julian)

    second_game_search      = FactoryGirl.create(:game_search, :ready, invitations: [ corwin_other_invitation, bleys_invitation, julian_invitation ], format: format_2_3)



    game_searches = [ first_game_search, second_game_search ]

    games         = Dispatcher.new(game_searches, communication_client).dispatch!



    games.should be_empty

  end





  it 'composes one game with searches 1 and 3 since team 2 has players in common with 1' do

    communication_client.should_receive(:push).exactly(6).times



    corwin_invitation       = FactoryGirl.build(:invitation, :accepted, player: corwin)

    mandor_invitation       = FactoryGirl.build(:invitation, :accepted, player: mandor)

    caine_invitation        = FactoryGirl.build(:invitation, :accepted, player: caine)

    first_game_search       = FactoryGirl.create(:game_search, :ready, invitations: [ corwin_invitation, mandor_invitation, caine_invitation ], format: format_2_3)



    corwin_other_invitation = FactoryGirl.build(:invitation, :accepted, player: corwin)

    bleys_invitation        = FactoryGirl.build(:invitation, :accepted, player: bleys)

    julian_invitation       = FactoryGirl.build(:invitation, :accepted, player: julian)

    second_game_search      = FactoryGirl.create(:game_search, :ready, invitations: [ corwin_other_invitation, bleys_invitation, julian_invitation ], format: format_2_3)



    fiona_invitation        = FactoryGirl.build(:invitation, :accepted, player: fiona)

    deirdre_invitation      = FactoryGirl.build(:invitation, :accepted, player: deirdre)

    flora_invitation        = FactoryGirl.build(:invitation, :accepted, player: flora)

    third_game_search       = FactoryGirl.create(:game_search, :ready, invitations: [ fiona_invitation, deirdre_invitation, flora_invitation ], format: format_2_3)



    game_searches = [ first_game_search, second_game_search, third_game_search ]

    games         = Dispatcher.new(game_searches, communication_client).dispatch!



    games[0].teams[0].players.should == [ corwin, mandor, caine ]

    games[0].teams[1].players.should == [ fiona, deirdre, flora ]

  end

end

Merci Ter Rowan !