<jupyter_start><jupyter_text>![DSA log](dsalogo.png)  Instructions 1. Make sure you are using a version of notebook greater than v.3. If you installed Anaconda with python 3 - this is likely to be fine. The next piece of code will check if you have the right version.2. The notebook has both some open test cases that you can use to test the functionality of your code - however it will be run on another set of test cases that you can't from which marks will be awarded. So passing all the tests in this notebook is not a guarantee that you have done things correctly - though its highly probable.3. Also make sure you submit a notebook that doesn't return any errors. One way to ensure this is to run all the cells before you submit the notebook.4. When you are done create a zip file of your notebook and upload that5. For each cell where you see "YOUR CODE HERE" delete the return notImplemented statement when you write your code there - don't leave it in the notebook.6. Once you are done, you are done.  Python ++<NAME> (03/2018) For this notebook we are going to cover some graph problems. We shall imagine a game of basketball or football. If we think of each of the players are a node in a graph, we can calculate the optimal number of people to mark each of the players. Lets assume that a play at one vertex can only mark another player if there is an edge between them. So from the example graph, a player at A can mark an opponent at A, B and C. A player at D can mark an opponent at C, i.e. each edge of the graph should be covered.![Graph](graph.png)Your goal is to provide a minimum number of players to mark all opponents represented by a graph. So for example one solution to this graph could be `[1,1,1,1]` which indicates you have players stationed at A,B,C,D marking all positions, a total of 4 players. However this would not be the most optimal. A solution like `[0,1,0,1]` may be a better solution because the two players at B and D represented by the 1's can mark all other positions comfortably. However again it may not be the most optimal (ie. the minimum deployment needed to mark all players.  To solve this problem we shall require a function that takes a graph that represents the positions of all players on the football pitch and returns the most optimal marking strategy in the form `[1,0,X,X,...]` where the 1's represent vertice where you would place your player. We want every player of the oponent's side marked. We shall represent the graph as an adjacency matrix. For example the above graph of 4 nodes can be represented as a 4 X 4 matrix where the 1's represent an edge between two nodes.`[[0,1,1,0],  [1,0,1,0],  [1,1,0,1],  [0,0,1,0]]`<jupyter_code>import itertools
import numpy as np
# Graphs
graph0 = [[0,1,1,0], [1,0,1,0], [1,1,0,1], [0,0,1,0]]
graph1 = [[0,1,0,0,1],[1,0,1,0,0],[0,1,0,1,1],[0,0,1,0,0],[1,0,1,0,0]]
graph2 = [[0,1,0,0,0,1],[1,0,1,0,0,0],[0,1,0,1,1,0],[0,0,1,0,1,0],[0,0,1,1,0,1],[1,0,0,0,1,0]]
graph3 = [[0,1,0,0,0,1],[1,0,1,0,1,0],[0,1,0,1,0,0],[0,0,1,0,1,0],[0,1,0,1,0,1],[1,0,0,0,1,0]]<jupyter_output><empty_output><jupyter_text>Question 1To solve this problem we will have a function that returns True if a set of markings is a valid solution to a graph of players. E.g for the graph above: `valid_markings([1,1,1,1], graph) -> True`<jupyter_code>def valid_markings(solution, graph):
    # Return True if the solution is valid for the graph
    # YOUR CODE HERE
    raise NotImplementedError()
assert valid_markings([1,0,1,0], graph1) == False
assert valid_markings([1,1,1,1,1,1], graph3) == True
assert valid_markings([1,0,1,0,1], graph1) == True
assert valid_markings([0,0,0,0,0], graph1) == False<jupyter_output><empty_output><jupyter_text>Question 2Write a function that returns the most optimal marking solution for an input graphE.g for the graph above: `optimal_marking(graph) -> True`<jupyter_code>def optimal_markings(input_graph):
    # YOUR CODE HERE
    raise NotImplementedError()
assert optimal_markings(graph0) == (2, (0, 1, 1, 0))
assert optimal_markings(graph1) == (2, (1, 0, 1, 0, 0))
assert optimal_markings(graph1)[1][2] == 1<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10422195416164053, 'fraction_numerical': 0.05090470446320868, 'mean_word_length': 4.922857142857143, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '394012', 'license': 'MIT', 'n_tokens_mistral': 1365, 'n_tokens_neox': 1304, 'n_words': 604, 'path': 'Python Basics/DSA-Python-2.ipynb', 'repo_name': 'Jarvin-M/DataScience-Africa-2018', 'size': '4147'}