Task 2 - CSP - Taxi driving

In a small town, there is an unnamed taxi service that wants to maximize its profit. The service has multiple vehicles at their disposal, and multiple customers to satisfy. One day, an exceptionally large number of customers appeared and the taxi service is overwhelmed. They are quite stubborn and want to satisfy all the customers at once, even if they have to stuff more of them in a single taxi. Suddenly, a clever programmer came up (you) and declared that he can solve the problem.

However, the problem is rather tricky.

The available taxi cars only serve certain destinations, have a limited capacity and what's more, they are of different class. Customers, on the other hand, want to go from their origin to a destination and also belong to a certain class. The customers are rather picky, so they won't get in a taxi of a worse class than theirs (the class 1 is best, hence a customer with a class 2 won't go into a taxi with a class 3 or more). Also, the taxi can serve only a certain number of customers, up to their capacity. What's more, all the customers in a single taxi have to start in the same origin and go to the same destination.

Your program will receive a single JSON input defining the available taxis and the customers. See the following example:

{
	"taxis": [
		{
			"id": "taxi_01",
			"serves": ["A", "B", "C"],
			"class": 1,
			"capacity": 2
		},
		{
			"id": "taxi_02",
			"serves": ["A", "B", "C"],
			"class": 2,
			"capacity": 2
		}
	],
	"customers": [
		{
			"id": "customer_01",
			"origin": "A",
			"destination": "B",
			"class": 1
		},
		{
			"id": "customer_02",
			"origin": "C",
			"destination": "A",
			"class": 3
		}
	]
}

In the example, there are 2 taxis, taxi_01 and taxi_02 (the ids are always unique) with their respective attributes. There are also 2 customers, customer_01 and customer_02. As this is not the first day of the taxi service, they provide you with a method to load this input into a python dictionary.

The program should output a single json with a mapping of customers to taxis. In the example above, there is only one solution:

{"customer_01": "taxi_01", "customer_02": "taxi_02"}

If there are multiple solutions, any single of them is sufficient. If there is no solution, your program should print out an empty json object:

{}

• The CSP library is provided for you, you only need to implement a definition of variable, their domains and constraints. You are not allowed to modify `csp.py` file.
• The basic routines are already implemented for you (input loading, constraint class definition and calling of CSP backtracking)
• The input file is determined by a first argument. A special file name `-` means standard input.
• The program has only 10 seconds to run. If the time limit is exceeded, the program is terminated and it is considered as a failed solution.

Download a package csp_student.zip. It consists of the following files

• `csp.py`: The CSP solver implemented for you. Inspect the code, learn from it, but don't modify it.
• `example_money.py` and `example_queens.py`: Two implemented examples to get you familiar with the library. Two well-known problems (SEND MORE MONEY and 8-queens).
• `samples/`: This directory consists of multiple sample inputs you can test your algorithm on. For all of them, a solution is also provided (however, your program can possibly find a different solution). The samples differ in size and complexity. Some of them are solvable (in the 10s limit) only with at least MCV heuristic.
• `student.py`: You will implement your code here.
• we use Python 3.7, we recommend to install numpy package

You submit on BRUTE - odevzdávací systém. You submit only the `student.py` file.

Your submission will be evaluated on a number of problems and will receive a certain number of points, based on a number of the correctly solved ones (in the time limit). The maximum what your program can receive is 10 points. Some problems are harder than others and require implementation of at least MCV heuristic.

Final score is computed by formula:

score = (correct - 3)/2

• Start by thinking and writing a CSP formalization on a piece of paper. It will save your time later.
• You can test whether your program fits in the time limit by pre-fixing the command with time or timeout 10s (on linux), i.e.:

timeout 10s python student.py samples/hg_01.json

• It might happen that you need to search for a particular object. A dictionary is the right structure as they have O(1) time complexity for search. Lists are not suitable, as they do search in O(n).
• If you need to get indices of a sorted array, use np.argsort, i.e.:

arr_1 = [5,2,3,1,4]
indices = np.argsort(arr_1)
# [3, 1, 2, 4, 0]

• If you need to use the indices for sorting another array, use construction:

arr_2 = ['a', 'b', 'c', 'd', 'e']
arr_2_sorted = [arr_2[i] for i in indices]
# ['d', 'b', 'c', 'e', 'a']

• You can test if x is present in an iterable y with x in y. It will always be faster for sets than lists, however.