Write a function collision(p1, start1, p2,start2) that takes p1 and start1 of one vehicle, and p2and start2 of another vehicle, and checks whether the two vehicleswill collide (i.e., at some stage they will be in the same cell atthe same time). The function should return a tuplecontaining the (x,y) coordinates of the cell where theycollide or None if they do not ever collide. If the twovehicles collide in multiple cells, return the coordinates of thefirst cell where they collide.

The parameters to this function are as follows:

• program1 is a list of actions, representing a program.
• start1 is a tuple representing a location and direction of thevehicle.
• program2 is a list of actions, representing a program.
• start2 is a tuple representing a location and direction of thevehicle.

Assumptions:

• Both vehicles start executing their programs at the sametime.
• Both vehicles perform actions at the same rate.
• All actions take the same amount of time.
• Once a vehicle completes its program, it remains in the samelocation.
• A collision occurs when two vehicles that are in the same cellat the same time, irrespective of their directions.

Preferably do not use the zip function/ importitertools :)

Example calls to function:

>>> collision(['Drive', 'TurnR', 'Drive'], (0, 0, 'E'), ['Drive', 'Drive'], (1, 1, 'S'))

(1, 0)

>>> collision(['Drive', 'Drive', 'Drive'], (2, 2, 'N'), ['Drive', 'Drive', 'Drive'], (2, 1, 'N'))

None

>>> collision(['Drive', 'Drive', 'Drive'], (2, 2, 'N'), ['Drive', 'Drive', 'Drive'], (2, 2, 'N'))

(2, 2)

>>> collision(['Drive', 'TurnR', 'Drive'], (2, 2, 'N'), ['Drive', 'Drive', 'Drive'], (2, 1, 'N'))

(2, 3)