Questions Specifications P2.txt

Project Description
Two types of gnomes live in a fairy land: those wearing black hats and those wearing white. The gnomes are not aware of the color of their own hats and do not have any mirrors, but they can observe each other and communicate the colors of other hats. Unfortunately, the gnomes have very limited memory and can only remember exactly two gnomes they met and the number of white hats they have seen on them. Sometimes they might recall the hat colors incorrectly, and this might lead to contradictions. At some point their observations (evidences) are collected and analysed. And only observations that are not contradicting are considered for further analysis. If at least a single evidence contains a contradiction, all evidences should be ignored.

Now, let’s try to operationalise it. Hat colors can be encoded as 1 (white) and 0 (black). Gnome IDs are integer values. Their evidences are represented as a list of tuples containing

a tuple of two gnome IDs;
the number of white hats the corresponding gnome saw on them (0, 1, 2): 0 – both gnomes were in black hats, 1 – one of them was wearing a white hat; 2 – both gnomes were in white hats.
The evidences are then recorded as a list of such tuples, e.g. [((3,4), 2), ((2,6), 0)] would be interpreted as gnomes 3 and 4 were in white hats, gnomes 2 and 6 were in black hats.

---

Question 1 (5 marks)
Identify gnomes in black hats and gnomes in white hats
Write a function get_colors_straightforward(evidences) that takes a list ‘evidences’ and returns a tuple with

(1) a sorted list of gnomes (IDs) in white hats, and (2) a sorted list of gnomes (IDs) in black hats IF no contradiction was found in each single evidence,
None IF a contradiction was found.
Assume that all gnome pairs in the input 'evidences' list wear same color hats, i.e. ((11, 2), 1) is not valid because gnomes 11 and 2 have different hat colors.

def get_colors_straightforward(evidences)

Input: a list of tuples
Returns: a tuple of two sorted lists OR None if a contradiction was found
>>> evidences = [((11, 2), 0), ((3, 6), 2), ((7, 9), 2)]
>>> print(get_colors_straightforward(evidences))
([3, 6, 7, 9], [2, 11])
If we now change ((3, 6), 2) to ((3, 2), 2), it will contradict ((11, 2), 0), and the function returns None:

>>> evidences = [((11, 2), 0), ((3, 2), 2), ((7, 9), 2)]
>>> print(get_colors_straightforward(evidences))
None

---

Question 2 (4 marks)
Identify gnomes in different hat colors
In this question, we start conceptualising gnome evidences as a graph, focusing on the cases where gnomes in the same tuple (i.e. a gnome pair) in the evidence can wear hats that differ in colors. The graph is represented as a dictionary. Nodes in the graph are gnome IDs, and edges connect genome-pairs who have distinct hat colors.

Note: In this question, we only focus on gnome pairs with different coloured hats in evidence.

Write a function make_color_mutex_graph(evidences) that takes a list of evidences as input and returns a graph (dictionary) of gnomes with different hat colors (negation_edges). The keys of the dictionary are gnome IDs, and the values contain other gnome IDs, which satisfy:

(1) the key gnome and each value gnome are in the same evidence tuple (i.e. they are gnome pairs)
(2) the key and value gnomes differ in hat colors.
(Just for this question) For consistency of the output, if a dictionary value contains two or more entries, please make sure that they are sorted in the increasing order (and, therefore, each value should be a list).

Sample runs:

>>> evidences = [((11, 2), 0), ((3, 6), 2), ((4, 9), 2), ((4, 6), 1)]
>>> print(make_color_mutex_graph(evidences))
{4: [6], 6: [4]}

>>> evidences = [((11, 2), 0), ((3, 2), 2), ((4, 9), 2)]
>>> print(make_color_mutex_graph(evidences))
{}
There are no gnome pairs with different coloured hats.

>>> evidences = [((11, 2), 1), ((3, 2), 1), ((4, 9), 2)]
>>> print(make_color_mutex_graph(evidences))
{11: [2], 2: [3, 11], 3: [2]}

---

Let's use the example of

evidences = [((11, 2), 0), ((3, 6), 2), ((4, 9), 1), ((4, 6), 1)].

From Q1, you know that gnomes 3, 6 wear white hats and 11, 2 wear black hats. From Q2, the graph you build shows that gnomes 4 and 6 as well as 4 and 9 differ in their hat colors.

Combining the two pieces of information, you will realise that "gnome 4 wears a black hat" and “gnome 9 wears a white hat” ! Now your job in Q3 and Q4 is to translate this reasoning into codes.

We will continue working with a graph representation in these question. In order to explore (traverse) the graph, you will need to consider implementing Depth First Search (DFS).

---

Question 3 (4 marks)
Learning to reason
In this question we will write an auxiliary function search(negation_edges, visited, start, color) which will then be used in Q4 to infer as many hat colors as possible. The function takes

the negation_edges (Q2). Values can be provided as a list OR (better) as a set since we are no longer interested in the order of nodes, and sets are optimised for fast membership testing (and remove duplicates)
a dictionary of already visited nodes (gnome ID: color (as a boolean value, False – black, True – white)). Note that the color stored in visited is the opposite color of the gnome - if the gnome wears False (black), we store True (white) in visited instead.
a node to start search (gnome ID) and its color (False/True)
and returns the whites and blacks in the graph (a tuple of two lists, just like Q1).

The dictionary of visited nodes should be updated each time we resolve/label the color of a new node (gnome’s hat). If any contradiction is found between any node being processed and the ones in visited, the function returns None. There's no need to revisit any previously visited nodes. Since we are working with negated nodes, visited will also contain the opposite node color (for convenience).

def search(negation_edges, visited, start, color)

Input: a graph (dictionary) of negation edges, labelled nodes (visited), a node to start reasoning from with its color
Returns: a tuple of two sorted lists
The function resembles the iterative version of the DFS algorithm.

Sample runs:

Example 1:

>>> print(search({6: {2}, 11: {2}, 3: {2}, 2:{11, 3, 6, 4}, 4: {2, 5}, 5:{4, 8}, 8: {5}, 9: {1}, 1: {9}}, {}, 11, False))
>>> ([2, 5], [3, 4, 6, 8, 11])
Explanation:

Suppose we have the following graph based on negated edges {6: {2}, 11: {2}, 3: {2}, 2: {11, 3, 6, 4}, 4: {2, 5}, 5: {4, 8}, 8: {5}, 9: {1}, 1: {9}} 

Assume that we start with node (gnome ID) 11, assigning it to black, and the visited dictionary is empty. The resulting graph should be then: 

i.e. the function should return ([2, 5], [3, 4, 6, 8, 11]).

Example 2:

This example has the same negation edges as Example 1 but the visited dictionary has a gnome ID 4 that is black (not True). Subsequent nodes after the branch of the visited node are not to be 'searched' further.


>>> print(search({6: {2}, 11: {2}, 3: {2}, 2:{11, 3, 6, 4}, 4: {2, 5}, 5:{4, 8}, 8: {5}, 9: {1}, 1: {9}}, {4: True}, 11, False))
>>> ([2], [3, 4, 6, 11])
Example 3:

Using the same negation edges from Example 1, this is a example of a contradiction found between a node being processed and one in visited. Here gnome ID 4 is listed as white (not False). The output should return None.

>>> print(search({6: {2}, 11: {2}, 3: {2}, 2: {11, 3, 6, 4}, 4: {2, 5}, 5:{4, 8}, 8: {5}, 9: {1}, 1: {9}}, {4: False}, 11, False))
>>> None
Example 4:

In this example we start with Gnome ID 6 (white hat), we also have a gnome ID 3 (not False = white) in visited. The resulting list of gnomes in white hats would be [3,6,7] (3 comes from visited, 6 is the starting one, and 7 is linked to 6 through 4 (the black one)).


>>> print(search({4: {6, 7}, 6: {4}, 7: {4}, 21: {33}, 33: {21}}, {3: False}, 6, True))
([3, 6, 7], [4])
Example 5 (Added on 10 Oct):

In this example we start with Gnome ID 0 (white hat). 0 it is already in the visited list, so we don't search its neighbours. As a result, the stack is empty with no more gnomes to check, and we return ([0], []).

>>> print(search({0: {1}, 1: {0}}, {0: False}, 0, True))
([0], [])

---

Question 4 (2 marks)
Connecting the dots
Now let's go directly from evidences to all possible conclusions! Use the graph builder from Q2 on top of the function from Q1 and the search function from Q3 to resolve as many hat colors as possible. Note that we start with the state when visited is empty, and is being gradually updated inside of the search function (as we traverse the graph).

Write a function resolve_colors(evidences) that takes a list of evidences and, using the function search from Q3, returns a tuple containing a sorted list of gnomes (IDs) in white hats and a sorted list of gnomes (IDs) in black hats (similar to Q1). If a contradiction exists, it should return None.

Assume that the graph does not contain cycles (a closed path or a path that starts from a node and ends at the same node).

Note: Unlike Q1, you need to consider gnome-pairs in evidence who wear hats in different colors.

Sample runs:

>>> evidences = [((11, 2), 0), ((3, 6), 2), ((4, 6), 1), ((4, 7), 1),  ((4, 6), 1), ((21, 33), 1), ((31, 115), 2)]
>>> print(resolve_colors(evidences))
([3, 6, 7, 31, 115], [2, 4, 11])
Note that we don't have enough information to derive hat colours for gnomes 21 and 33, so they are not in the returned lists.

>>> evidences = [((8, 2), 2), ((3, 6), 2), ((7, 9), 2), ((3, 7), 2), ((7, 12), 2)]
>>> print(resolve_colors(evidences))
([2, 3, 6, 7, 8, 9, 12], [])
​
>>> evidences = [((11, 2), 0), ((3, 6), 2), ((4, 9), 2), ((4, 6),1)]
>>> print(resolve_colors(evidences))
None
​
>>> evidences = [((11, 2), 0), ((3, 6), 2),  ((4, 7), 1),  ((4, 6), 0), ((21, 33), 1), ((31, 115), 2)]
>>> print(resolve_colors(evidences))
None