Besides the correctness, your program will also be evaluated based on readability $($e$.$g$.,$ comments, variable names, structures, etc$)$ and design of functions $($for $(3)$ only$).$ Each question carries $20$ points.

Important reminders and restrictions Points will be deducted if violating these restrictions.

$1.$ This is an individual project.

$2.$ You are expected to write all the code yourself.

$3.$ No import statements allowed.

$4.$ You have to use all the functions given.

$5.$ You cannot change the doctrings of all functions and their names.

$6.$ You cannot change the code in explore$\_$paths $()$ and find$\_$all$\_$shortest$\_$paths $().$

$7.$ You cannot use any built$-$in functions except print $()$ and type conversion functions.

$8.$ You cannot use list comprehensions.

This assignment is for you to write genStates $().$ Use the template below and name the file midterm$\_$states.py$.$

$```$

$"""$CS $108-$ Midterm project $-$ part $1$

Describe the module here. Fix the lab number above and the name$/$date below.

@author: YOUR$-$NAME $($yourid$123)$

@date: semester, year

$"""$

def genStates$()$:

$"""$Generate a tuple of all states for the MCGW problem

Parameters

None

Returns

Tuple of strings

All possible states

$"\%"$

# testing the function

print$("$Test $1$: All possible states"$)$

print$($genStates$())$

$```$

The expected results are:

Test $1$: All possible states

$(\text{'}$EEEE$\text{'},$ 'EEEW', 'EEWE', 'EEWW', 'EWEE', 'EWEW', 'EWWE', 'EWWW', 'WEEE', 'WEEW', 'WEWE', 'WEWW', 'WWEE', 'WWEW', 'WWWE', $\text{'}$WWWW$\text{'})$