A student council has nine members. For privacy reasons, we will refer to these students with the letters A, B, …, I. Not all of the nine students are on speaking terms. This table shows which students are speaking to each other — 1 means the two students are on speaking terms and 0 means the two students are not on speaking terms.
A B C D E F G H I A - 0 0 1 0 0 1 0 0 B 0 - 1 1 1 1 1 1 1 C 0 1 - 0 0 0 1 1 0 D 1 1 0 - 1 0 1 0 1 E 0 1 0 1 - 0 1 0 0 F 0 1 0 0 0 - 0 0 1 G 1 1 1 1 1 0 - 0 0 H 0 1 1 0 0 0 0 - 0 I 0 1 0 1 0 1 0 0 -
Note that who speaks to whom is a symmetric relationship: if student $$x$$ speaks to student $$y$$, then student $$y$$ also speaks to student $$x$$. As a result, the table is also symmetrical: the two sections on either side of the main diagonal mirror each other. The complete relationship is therefore known if we know the values above the main diagonal (indicated in blue).
Recently student A started a rumor, and it was heard by each other student once and only once. Each student heard it from, and passed it to, another student with whom she was on speaking terms. If we count student A as zero, then student E was the eighth and last student to hear the rumor. Who was the fourth?
We know that A is at the start of the chain, and E is at the end. Of the others, F and H are each speaking to only two other students. So F must pass the rumor between B and I (in one direction or the other, BFI or IFB), and H must pass it between B and C (BHC or CHB). Putting these fragments together, we must have either CHBFI or IFBHC. Also, this larger fragment can't connect directly to either of the endpoints A or E, because neither C nor I is speaking to either of them. That means that the remaining students, D and G, must go on either end of our fragment before we can attach the endpoints. So the extended fragment is either GCHBFID or DIFBHCG, and with the endpoints A and E added we get the full chain AGCHBFIDE or ADIFBHCGE. In either case, if A is counted as zero then the fourth person is B.
For a student council with $$n$$ students ($$2 \leq n \leq 26$$), we label the students with the first $$n$$ uppercase letters (str) of the alphabet. Your task:
Write a function fill_table that takes two arguments: i) the number of students $$n$$ (int) in a student council and ii) a string (str) with the $$\frac{n(n-1)}{2}$$ zeros (0) and ones (1) above the main diagonal in the table that indicates which students are on speaking terms (1) or not (0), read from left to right and from top to bottom. The function must return the full table represented as a list containing the $$n$$ rows (listed from top to bottom). Each row is itself represented as a list containing the $$n$$ values on the row, listed from left to right: True (bool) if the two students are on speaking terms, False (bool) if the two students are not on speaking terms and None at the diagonal. We call this the student council speech table.
Write a function print_table that takes the speech table $$\mathcal{S}$$ of a student council. The function must print a representation of speech table $$\mathcal{S}$$, according to the format used in the introduction of this assignment. So with rows and columns labeled with the students' uppercase letters (in alphabetical order), columns separated by spaces, and the digit 1 for two students that are on speaking terms, the digit 0 for two students that are not on speaking terms and a dash (-) at the diagonal.
Write a function speaks_to that takes two arguments: i) the uppercase letter $$s$$ of a student and ii) the speech table $$\mathcal{S}$$ of a student council. The function must return a set with the uppercase letters of all other students to whom student $$s$$ speaks according to speech table $$\mathcal{S}$$.
Write a function on_speaking_terms that takes three arguments: i) the uppercase letter $$s$$ of a student, ii) the uppercase letter $$t$$ of another student and iii) the speech table $$\mathcal{S}$$ of a student council. The function must return a Boolean value (bool) that indicates if students $$s$$ and $$t$$ are on speaking terms according to speech table $$\mathcal{S}$$.
Write a function is_chain that takes two arguments: i) a string $$k$$ (str) containing uppercase letters and ii) the speech table $$\mathcal{S}$$ of a student council. The function must return a Boolean value (bool) that indicates if $$k$$ is a chain. That is the case if
$$k$$ is a permutation of the uppercase letters for the students in the council (in other words, $$k$$ contains $$n$$ letters and the uppercase letter of each student occurs exactly once)
each pair of successive letters in $$k$$ corresponds to two students that are on speaking terms according to speech table $$\mathcal{S}$$
A chain thus indicates how a rumor may have spread among all students, that each passed it to one other student to whom they spoke. For example, the chain AGCHBFIDE indicates that student A started the rumor by telling it to student G, who in turn passed it on to student C, and so on, until it was finally passed on by student D to student E.
Write a function chains that takes three arguments: i) the uppercase letter $$s$$ of a student, ii) the uppercase letter $$t$$ of another student and iii) the speech table $$\mathcal{S}$$ of a student council. The function must return a set with all chains for speech table $$\mathcal{S}$$ that start with $$s$$ and end with $$t$$.
To find all chains, you can iterate over all possible permutations
of the uppercase letters that start with letter $$s$$ and end with
letter $$t$$, and check which of these permutations is a chain. The
Python
Standard Library1 has a module itertools2 that defines a function
permutations3 that could be useful
to implement this.
You may assume that these functions only take arguments that comply with the description in the assignment, without the need to check this explicitly.
This interactive session uses the student council speech table from the introduction of this assignment.
>>> table = fill_table(9, '001001001111111000110101010100001000')
>>> table
[[None, False, False, True, False, False, True, False, False], [False, None, True, True, True, True, True, True, True], [False, True, None, False, False, False, True, True, False], [True, True, False, None, True, False, True, False, True], [False, True, False, True, None, False, True, False, False], [False, True, False, False, False, None, False, False, True], [True, True, True, True, True, False, None, False, False], [False, True, True, False, False, False, False, None, False], [False, True, False, True, False, True, False, False, None]]
>>> print_table(table)
A B C D E F G H I
A - 0 0 1 0 0 1 0 0
B 0 - 1 1 1 1 1 1 1
C 0 1 - 0 0 0 1 1 0
D 1 1 0 - 1 0 1 0 1
E 0 1 0 1 - 0 1 0 0
F 0 1 0 0 0 - 0 0 1
G 1 1 1 1 1 0 - 0 0
H 0 1 1 0 0 0 0 - 0
I 0 1 0 1 0 1 0 0 -
>>> speaks_to('A', table)
{'D', 'G'}
>>> speaks_to('B', table)
{'C', 'D', 'E', 'F', 'G', 'H', 'I'}
>>> on_speaking_terms('A', 'B', table)
False
>>> on_speaking_terms('G', 'A', table)
True
>>> is_chain('AGCHBFIDE', table)
True
>>> is_chain('ADIFBHCGE', table)
True
>>> chains('A', 'E', table)
{'ADIFBHCGE', 'AGCHBFIDE'}
>>> chains('H', 'F', table)
{'HCBEGADIF', 'HCGADEBIF'}
>>> chains('I', 'A', table)
{'IFBHCGEDA'}
>>> chains('B', 'D', table)
set()