The weekly challenge 343 - Task 2: Champion Team

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-343/#TASK2
  3 #
  4 # Task 2: Champion Team
  5 # =====================
  6 #
  7 # You have n teams in a tournament. A matrix grid tells you which team is stronger between any two teams:
  8 #
  9 # If grid[i][j] == 1, then team i is stronger than team j
 10 # If grid[i][j] == 0, then team j is stronger than team i
 11 #
 12 # Find the champion team - the one with most wins, or if there is no single such team, the strongest of the teams with most wins. (You may assume that there is a definite answer.)
 13 #
 14 ## Example 1
 15 ##
 16 ## Input: @grid = (
 17 ##                  [0, 1, 1],
 18 ##                  [0, 0, 1],
 19 ##                  [0, 0, 0],
 20 ##                )
 21 ## Output: Team 0
 22 ##
 23 ## [0, 1, 1] => Team 0 beats Team 1 and Team 2
 24 ## [0, 0, 1] => Team 1 beats Team 2
 25 ## [0, 0, 0] => Team 2 loses to all
 26 #
 27 #
 28 ## Example 2
 29 ##
 30 ## Input: @grid = (
 31 ##                  [0, 1, 0, 0],
 32 ##                  [0, 0, 0, 0],
 33 ##                  [1, 1, 0, 0],
 34 ##                  [1, 1, 1, 0],
 35 ##                )
 36 ## Output: Team 3
 37 ##
 38 ## [0, 1, 0, 0] => Team 0 beats only Team 1
 39 ## [0, 0, 0, 0] => Team 1 loses to all
 40 ## [1, 1, 0, 0] => Team 2 beats Team 0 and Team 1
 41 ## [1, 1, 1, 0] => Team 3 beats everyone
 42 #
 43 #
 44 ## Example 3
 45 ##
 46 ## Input: @grid = (
 47 ##                  [0, 1, 0, 1],
 48 ##                  [0, 0, 1, 1],
 49 ##                  [1, 0, 0, 0],
 50 ##                  [0, 0, 1, 0],
 51 ##                )
 52 ## Output: Team 0
 53 ##
 54 ## [0, 1, 0, 1] => Team 0 beats teams 1 and 3
 55 ## [0, 0, 1, 1] => Team 1 beats teams 2 and 3
 56 ## [1, 0, 0, 0] => Team 2 beats team 0
 57 ## [0, 0, 1, 0] => Team 3 beats team 2
 58 ##
 59 ## Of the teams with 2 wins, Team 0 beats team 1.
 60 #
 61 #
 62 ## Example 4
 63 ##
 64 ## Input: @grid = (
 65 ##                  [0, 1, 1],
 66 ##                  [0, 0, 0],
 67 ##                  [0, 1, 0],
 68 ##                )
 69 ## Output: Team 0
 70 ##
 71 ## [0, 1, 1] => Team 0 beats Team 1 and Team 2
 72 ## [0, 0, 0] => Team 1 loses to Team 2
 73 ## [0, 1, 0] => Team 2 beats Team 1 but loses to Team 0
 74 #
 75 #
 76 ## Example 5
 77 ##
 78 ## Input: @grid = (
 79 ##                  [0, 0, 0, 0, 0],
 80 ##                  [1, 0, 0, 0, 0],
 81 ##                  [1, 1, 0, 1, 1],
 82 ##                  [1, 1, 0, 0, 0],
 83 ##                  [1, 1, 0, 1, 0],
 84 ##                )
 85 ## Output: Team 2
 86 ##
 87 ## [0, 0, 0, 0, 0] => Team 0 loses to all
 88 ## [1, 0, 0, 0, 0] => Team 1 beats only Team 0
 89 ## [1, 1, 0, 1, 1] => Team 2 beats everyone except self
 90 ## [1, 1, 0, 0, 0] => Team 3 loses to Team 2
 91 ## [1, 1, 0, 1, 0] => Team 4 loses to Team 2
 92 #
 93 ############################################################
 94 ##
 95 ## discussion
 96 ##
 97 ############################################################
 98 #
 99 # First, we count the wins per team and find the maximum.
100 # Then, we find all teams that match the maximum. If that
101 # is only one team, we can return it. Otherwise, we pick all
102 # the teams that match the maximum and only compare them by
103 # calling the function recursively. We also keep a mapping
104 # of the temporary array indices to the big @grid indices so
105 # we can map back to the correct entry.
106 #
107 
108 use v5.36;
109 
110 champion_team([0, 1, 1], [0, 0, 1], [0, 0, 0]);
111 champion_team([0, 1, 0, 0], [0, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 0]);
112 champion_team([0, 1, 0, 1], [0, 0, 1, 1], [1, 0, 0, 0], [0, 0, 1, 0]);
113 champion_team([0, 1, 1], [0, 0, 0], [0, 1, 0]);
114 champion_team([0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1],
115     [1, 1, 0, 0, 0], [1, 1, 0, 1, 0]);
116 
117 
118 sub champion_team(@grid) {
119     say "Input: (";
120     foreach my $tmp (@grid) {
121         say "        [" . join(", ", @$tmp) . "],";
122     }
123     say ")";
124     my $result = _champion_team(@grid);
125     say "Output: $result";
126 }
127 
128 sub _champion_team(@grid) {
129     my @wins_by_team = ();
130     my $max = 0;
131     foreach my $team_results (@grid) {
132         my $wins = 0;
133         foreach my $game (@$team_results) {
134             $wins++ if $game;
135         }
136         push @wins_by_team, $wins;
137         $max = $wins if $wins > $max;
138     }
139     my @max_winning_teams = ();
140     foreach my $i (0..$#wins_by_team) {
141         push @max_winning_teams, $i if $wins_by_team[$i] == $max;
142     }
143     if(scalar(@max_winning_teams) == 1) {
144         return $max_winning_teams[0];
145     }
146     my $map = {};
147     my @minigrid = ();
148     foreach my $i (0..$#max_winning_teams) {
149         my @tmp = ();
150         $map->{$i} = $max_winning_teams[$i];
151         foreach my $j (0..$#max_winning_teams) {
152             push @tmp, $grid[$max_winning_teams[$i]][$max_winning_teams[$j]];
153         }
154         push @minigrid, [ @tmp ];
155     }
156     if(scalar(@grid) == scalar(@minigrid)) {
157         die "Can't reduce number of teams for finding best of the best";
158     }
159     return _champion_team(@minigrid);
160 }