The Sheep and Wolves problem is identical to the Guards & Prisoners problem from the lecture, except that it makes more semantic sense why the wolves can be alone (they have no sheep to eat). Ignore for a moment the absurdity of wolves needing to outnumber sheep in order to overpower them. Maybe it's baby wolves vs. adult rams.

As a reminder, the problem goes like this: you are a shepherd tasked with getting sheep and wolves across a river for some reason. If the wolves ever outnumber the sheep on either side of the river, the wolves will overpower and eat the sheep. You have a boat, which can only take one or two animals in it at a time, and must have at least one animal in it because you'll get lonely (and because the problem is trivial otherwise). How do you move all the animals from one side of the river to the other?

In the original Sheep & Wolves (or Guards & Prisoners) problem, we specified there were 3 sheep and 3 wolves; here, though, your agent should be able to solve the problem for an arbitrary number of initial sheep and wolves. You may assume that the initial state of the problem will follow those rules (e.g. we won't give you more wolves than sheep to start). However, not every initial state will be solvable; there may be combinations of sheep and wolves that cannot be solved.

You will return a list of moves that will solve the problem, or an empty list if the problem is unsolvable based on the initial set of Sheep and Wolves. You will also submit a brief report describing your approach.

Your Agent

To write an agent, download the starter code below. Complete thesolve()method, then upload it to Gradescope to test it against the autograder. Before the deadline, make sure to select your best performance in Gradescope as your submission to be graded.

Starter Code

Here is your starter code:SemanticNetsAgent.zip.

The starter code contains two files: SemanticNetsAgent.py and main.py. You will write an agent in SemanticNetsAgent.py. You may test your agent by running main.py. You will only submit SemanticNetsAgent.py; you may modify main.py to test your agent with different inputs.

In SemanticNetsAgent.py, yoursolve()method will have two parameters: the number of sheep and the number of wolves. For example, for the original Sheep & Wolves problem from the lectures, we would call your agent withyour_agent.solve(3, 3). You may assume that the initial state is valid (there will not be more Wolves than Sheep in the initial state).

Returning Your Solution

Yoursolve()method should return a list of moves that will result in the successful solving of the problem. These areonlythe moves your agent ultimately selected to be performed, not the entire web of possible moves. Each item in the list should be a 2-tuple where each value is an integer representing the number of sheep (the first integer) or wolves (the second integer) to be moved; we assume the moves are alternating. So, if your first move is (1, 1), that means you're moving one sheep and one wolf to the right. If your second move is (0, 1), that means you're moving one wolf to the left.

For example, one possible solution to the test case of 3 sheep and 3 wolves would be:

[(1, 1), (1, 0), (0, 2), (0, 1), (2, 0), (1, 1), (2, 0), (0, 1), (0, 2), (0, 1), (0, 2)]

The result of running the moves in order should be (a) that all animals are successfully moved from left to right, and (b) that all intermediate states along the way are valid (wolves never outnumber sheep in any state).