# a4_2017sp_soln.py
# SOLUTION by Lillian Lee (LJL2)
# April 2017
class Outcome(object):
"""An instance is an outcome in a tournament tree.
Attributes:
winner [nonempty str]: name of the winner in this Outcome
Must be the same as the name of *exactly one* of attributes input1 or
input2, defined next.
input1 [Outcome or nonempty string]:
If a nonempty string, the name of a competitor in the tournament, and
we say that the name of input1 is that string.
If an Outcome, then the name of input1 is its winner attribute.
input2 [Outcome or nonempty string]:
If a nonempty string, the name of a competitor in the tournament, and
we say that the name of input2 is that string
If an Outcome, then the name of input2 is its winner attribute.
Note that the constraints (invariants) on winner imply that the names of
input1 and input2 must be different.
"""
def __init__(self, in1, in2, one_won=True):
"""Makes an Outcome have input1 set to in1, input2 set to in2, and winner
set as follows:
If one_won is True or not given, winner is in1's winner (if in1 is
an Outcome) or in1 itself (if in1 is a string)
Otherwise, winner is set to in2's winner (if in2 is an Outcome) or
in2 itself (if in2 is a string)
We choose the default value of one_won as True because tournaments
are often set up so that input1 is the competitor favored to win.
Preconditions:
in1 is either a nonempty string or an Outcome
in2 is either a nonempty string or an Outcome.
name1 is different from name2, where:
if in1 is an Outcome, name1 is in1's winner, otherwise name1 is in1
if in2 is an Outcome, name2 is in2's winner, otherwise name2 is in2
one_won is a boolean."""
self.input1 = in1
self.input2 = in2
if one_won:
self.winner = _extract_name(in1)
else:
self.winner = _extract_name(in2)
def __str__(self):
"""String representation of this Outcome"""
output = self.winner + "\n"
output += "\t" # start indenting for the sub-Outcomes
s1 = str(self.input1) # A recursive call
# Inspiration for using splitlines with True, which preserves newlines
# at line ends:
# http://stackoverflow.com/questions/18389454/add-some-characters-at-the-beginning-of-each-line
s1_lines = s1.splitlines(True)
#
# The join in the next line of code indents the 2nd through the last
# line of s1, since it puts tabs "between" all the lines in the
# split-line version.
output += "\t".join(s1_lines)
#
if isinstance(self.input1, str):
output += "\n"
# More compact version of above recursion except on self.input2
output += "\t" + "\t".join(str(self.input2).splitlines(True))
if isinstance(self.input2, str):
output += "\n"
return output
def teams(self):
"""Returns: alphabetized list of names of teams participating in this Outcome
or any of its sub-Outcomes or any of their sub-Outcomes, and so on.
No team should be included more than once."""
output = []
if isinstance(self.input1, str):
output = [self.input1]
else:
output.extend(self.input1.teams())
if isinstance(self.input2, str):
output.append(self.input2)
else:
output.extend(self.input2.teams())
output = list(set(output)) # remove duplicates
return sorted(output)
def pathToVictory(self):
"""Returns: list of teams that the winner of this Outcome defeated in
this Outcome and all of its sub-Outcomes, sorted in order of earliest
opponents first."""
# Determine which sub-Outcome this Outcome's winner comes from, and
# the name of the loser for the top-level game. This loser must be the
# last item in our eventual output list.
name1 = _extract_name(self.input1)
if self.winner == name1:
sub = self.input1
loser = _extract_name(self.input2)
else:
sub = self.input2
loser = name1
if isinstance(sub, str):
return [loser]
else:
outputlist = sub.pathToVictory()
outputlist.append(loser)
return outputlist
def hasHeadToHead(self, c1, c2):
"""Returns True if anywhere in the tournament tree represented by this
Outcome there is an Outcome oc where the name of one of oc's inputs
is c1 and the name of the other of oc's inputs is c2.
Returns False otherwise, including if c1 and c2 are not in self.teams()
Precondition: c1 and c2 are different non-empty strings."""
# base case
if not (c1 in self.teams() and c2 in self.teams()):
return False
# base case
self_names = [_extract_name(self.input1), _extract_name(self.input2)]
if c1 in self_names and c2 in self_names:
# This Outcome is a head-to-head matchup of c1 against c2
return True
if isinstance(self.input1, Outcome) and isinstance(self.input2, Outcome):
return self.input1.hasHeadToHead(c1, c2) or \
self.input2.hasHeadToHead(c1, c2)
elif isinstance(self.input1, Outcome):
return self.input1.hasHeadToHead(c1, c2)
else:
return self.input2.hasHeadToHead(c1, c2)
## NON-METHOD FUNCTIONS GO BELOW THIS LINE
def _extract_name(x):
"""Returns: string that is the "name" of x, defined as follows:
If x is an Outcome, then the name is x's winner.
If x is a string, then the name of x is x itself.
Precondition: x is either a non-empty string or an Outcome."""
if isinstance(x, Outcome):
return x.winner
else:
# x must be a string, by precondition
assert isinstance(x, str), "_extract_name: bad input x: " + str(x)
return x