Today's challenge comes from the website fivethirtyeight.com, where Oliver Roeder runs a weekly Riddler column. Today's challenge was the riddler on 2018-04-06.
From Matt Gold, a chance, perhaps, to redeem your busted bracket:
On Monday, Villanova won the NCAA men’s basketball national title. But I recently overheard some boisterous Butler fans calling themselves the “transitive national champions,” because Butler beat Villanova earlier in the season. Of course, other teams also beat Butler during the season and their fans could therefore make exactly the same claim.
How many transitive national champions were there this season? Or, maybe more descriptively, how many teams weren’t transitive national champions?
(All of this season’s college basketball results are here. To get you started, Villanova lost to Butler, St. John’s, Providence and Creighton this season, all of whom can claim a transitive title. But remember, teams beat those teams, too.)
The input is a list of all the NCAA men's basketball games from this past season via https://www.masseyratings.com/scores.php?s=298892&sub=12801&all=1
Your program should output the number of teams that can claim a "transitive" national championship. This is any team that beat the national champion, any team that beat one of those teams, any team that beat one of those teams, etc...
In [12]:
from pathlib import Path
from collections import namedtuple, defaultdict
import itertools
In [13]:
games = Path('../../FiveThirtyEightRiddler/2018-04-06/scores.txt').read_text().split('\n')
In [14]:
def parse_game_text(line):
team_1 = line[12:36].strip()
team_2 = line[41:65].strip()
score_1 = int(line[36:39])
score_2 = int(line[65:68])
return (team_1, team_2)
In [15]:
loser_dict = defaultdict(set)
all_teams_set = set()
for winner, loser in [parse_game_text(game) for game in games]:
loser_dict[loser].add(winner)
all_teams_set.add(winner)
all_teams_set.add(loser)
In [17]:
new_transitive_winners = {'Villanova'}
transitive_winners = new_transitive_winners
while new_transitive_winners:
all_transitive_winners = set.union(*[loser_dict[winner] for winner in new_transitive_winners])
new_transitive_winners = all_transitive_winners - transitive_winners
transitive_winners |= new_transitive_winners
In [18]:
len(transitive_winners)
Out[18]: