Ants mainly communicate with each other using odorants called pheromones. Like other insects, ants perceive smells with their long, thin, and mobile antennae. The paired antennae provide information about the direction and intensity of scents. Since most ants live on the ground, they use the soil surface to leave pheromone trails that may be followed by other ants. A forager that finds food, marks a trail on the way back to the colony. If this trail is followed by other ants, these ants then reinforce the trail when they head back with food to the colony. When the food source is exhausted, no new trails are marked by returning ants and the scent slowly dissipates.

Foraging ants travel distances of up to 200 meters from their nest and scent trails allow them to find their way back even in the dark. Distances traveled are measured using an internal pedometer that keeps count of the steps taken and also by evaluating the movement of objects in their visual field. Directions are measured using the position of the sun. They integrate this information to find the shortest route back to their nest. Ants that become separated from pheromone trails (for example because they have been moved to another location by a human being) may run around continuously until they die of exhaustion.

Assignment

We simulate the behavior of an ant tracking its way back to the nest by following a disturbed pheromone trail. The environment in which the ant forages is represented by a square $$n \times n$$ grid having $$n$$ row and $$n$$ columns. The ant is initially located at the bottom left corner of the grid and its nest is located at the top right corner of the grid. Each cell in the grid contains a pheromone trail that points up, down, left or right. During each simulation step, the ant moves to the neighboring cell that is pointed to by the pheromone trail, and then the direction of the trail on the cell that it has left turns 90° clockwise. If the ant is not able to move in the indicated direction because the edge of the grid blocks its path, it remains on its current cell and the direction of the trail on the cell turns 90° clockwise.

The original configuration of a square $$n \times n$$ grid with pheromone trails is given as a string containing $$n^2$$ characters, representing the direction symbols in the grid. The $$n \times n$$ grid must be filled from left to right, and from top to bottom, using the sequence of characters in the string. The following four characters are used as direction symbols:

• >: the pheromone trail points to the right

• <: the pheromone trail points to the left

• ^: the pheromone trail points up

• v: the pheromone trail points down

A position in the grid is represented as a tuple whose first element indicates the row index and whose second element indicates the column index. The rows of the grid are indexed from top to bottom, and the columns from left to right, where indexing starts at zero. Your task:

• Write a function grid that takes an integer $$n \in \mathbb{N}_0$$ and a string as its arguments. The function must return a list of lists that represents a square $$n \times n$$ grid with pheromone trails, where the grid must be filled from left to right, and from top to bottom, using the sequence of characters in the given string. In case the given string does not contain $$n^2$$ characters, the function must raise an AssertionError with the message invalid arguments.

• Write a function text that takes a square $$n \times n$$ grid with pheromone trails, represented as a list of lists. The function must return a string containing the representation of the $$n \times n$$ grid, where all symbols on a given row are separated by spaces, and all rows are on a separate line.

• Write a function step that takes two arguments: i) a square $$n \times n$$ grid with pheromone trails represented as a list of lists, and ii) a position in the grid. The function must perform a single simulation step, with the ant leaving at the given position in the grid. In doing so, the function must modify the pheromone trails at the ant's starting position and return the position of the ant after the simulation step has finished.

• Write a function steps that can be used to perform an entire simulation of the steps taken by the ant from its starting position at the bottom left corner of the grid until it reaches its nest at the top right corner of the grid. The function takes the original configuration of the $$n \times n$$ grid with pheromone trails, represented as a list of lists. The function must return a list of positions that begins with the original position of the ant at the start of the simulation, followed by the positions of the ant after each simulation step. After the function returns, the grid must contain the configuration of pheromone trails at the time the ant has reached its nest.

Example

>>> square = grid(4, '>>>>^<^v^v^^>>v>')
>>> square
[['>', '>', '>', '>'], ['^', '<', '^', 'v'], ['^', 'v', '^', '^'], ['>', '>', 'v', '>']]
>>> print(text(square))
> > > >
^ < ^ v
^ v ^ ^
> > v >
>>> step(square, (3, 0))
(3, 1)
>>> print(text(square))
> > > >
^ < ^ v
^ v ^ ^
v > v >
>>> step(square, (3, 1))
(3, 2)
>>> print(text(square))
> > > >
^ < ^ v
^ v ^ ^
v v v >

>>> square = grid(4, '>>>>^<^v^v^^>>v>')
>>> print(text(square))
> > > >
^ < ^ v
^ v ^ ^
> > v >
>>> steps(square)    
[(3, 0), (3, 1), (3, 2), (3, 2), (3, 1), (3, 1), (3, 0), (3, 0), (3, 0), (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3)]
>>> print(text(square))
v v v >
> < ^ v
> v ^ ^
> ^ ^ >

>>> grid(4, '>>>>^<^v^v^>>v>')
Traceback (most recent call last):
AssertionError: invalid arguments