I was asked this problem for a challenge, and I decided to share my solution here to review the code:
Here is the problem statement:
For this challenge, 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 as nodes in a graph, we can calculate the optimal number of people to mark each of the players.
Let's assume that a player 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 and D. Each edge of the graph should be covered.
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 (i.e. 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 vertices where you would place your player.
We want every player of the opponent'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]]
To solve this problem, I was thinking about all algorithms related to graphs like: depth-first search, breadth-first search and Dijkstra shortest path. However, none of them was appropriate for this challenge.
So I decide to go with a simple approach using loops.
1. To 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.
Here is my solution :
def valid_markings(solution, graph): marked =  # the list will contain an edge if it's marked for idx, i in enumerate(solution): # in this loop we are going to check for marked item if i == 1: # add element as marked by him for edx_j, j in enumerate(graph[i]): if graph[idx][edx_j] == 1: marked.append(edx_j) return list(set(marked)) == list(range(0, len(graph)))
In the end, we will compare the marked list, with a list of all elements to check if all elements were marked, so for example:
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]],
valid_markings([1, 0, 1, 0], graph1) will return
valid_markings([1, 0, 1, 0, 1], graph1) will return
2. The second task was: Write a function that returns the most optimal marking solution for an input graph.
The following function will return the most optimal marking for an input graph. To do it, we will try all possibles markings, and check if they are valid markings by using the previous function. Once all valid markings are found, we need to sort them according to the number of the element it required to achieve a full marking. The most optimal markings are the markings with the lowest number of players.
def optimal_markings(input_graph): results_counts =  for combination in itertools.product([1, 0], repeat=len(input_graph)): results = combination if valid_markings(results, input_graph): results_counts.append((results.count(1), results)) optimal_required = sorted(results_counts, key = lambda x : x ) optimal_marking = list(filter( lambda x : x == optimal_required, results_counts)) return optimal_marking
So one of the optimal markings is
(2, (0, 1, 1, 0, 0)).
- I think my solution is too simple for this problem. If someone has another solution using graph theory kindly add it and explain it.
- So if my solution is a good one please help me to improve it for performance, readability, etc.