$8\mathrm{.}3$ Midterm project $-$ part $3$

In this third 'assignment," you will write the function genGraph $().$ Unlike the first two assignments, you will design and implement at least one more new function to help you implement genGraph $().$ In testing the genGraph $()$ and the new function$($s$),$ you also need to copy your code from the last two assignments to here. Make sure you include a docstring for each new function and choose a meaningful function name.

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$).$ This 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.

Use the template below and name the file midterm$\_$graph.py$.$

$```$

def genGraph$($S$)$:

$"""$Generate a graph for the MCGW problem

Parameters

$-----------$

S : a tuple of strings

A tuple of all possible states

Returns

$--------$

Dictionary $($key : string, value : a list of strings$)$

A graph for the MCGW problem

$"""$

# Print the graph

print$("$Test $3$: The graph"$)$

graph $=$ genGraph$($genStates$())$

for node in graph:

print$($node$,$ graph$[$node$])$

$```$

The expected results are:

$```$

Test $3$: The graph

EEEE $[\text{'}$WEWE$\text{'}]$

EEEW $[\text{'}$WEWW$\text{'},$ 'WWEW'$]$

EEWE $[\text{'}$WEWE$\text{'},$ 'WEWW', 'WWWE'$]$

EWEE $[\text{'}$WWEW$\text{'},$ 'WWWE'$]$

EWEW $[\text{'}$WWEW$\text{'},\text{'}$WWWW$\text{'}]$

WEWE $[\text{'}$EEEE$\text{'},$ 'EEWE'$]$

WEWW $[\text{'}$EEEW$\text{'},$ 'EEWE'$]$

WWEW $[\text{'}$EEEW$\text{'},$ 'EWEE', 'EWEW'$]$

WWWE $[\text{'}$EEWE$\text{'},$ 'EWEE'$]$

WWWW $[\text{'}$EWEW$\text{'}]$

$``````$

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

$8\mathrm{.}1$ Midterm project $-$ part $1$

@author: Blake Johnson $(1120593)$

@date: Fall, $2024$

$"""$

def genstates$()$:

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

Parameters

None

Returns

Tuple of strings

All possible states

$"""$

# Generate all $16$ states by iterating over every combination

states $=[]$

sides $=[\text{'}$E$\text{'},\text{'}$W$\text{'}]$

for m in sides:

for c in sides:

for g in sides:

for w in sides:

state $=$ m $+$ c $+$ g $+$ w

states.append$($state$)$

return tuple$($states$)$

# testing the function

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

print$($genstates$())$

$```$ @author: Blake Johnson

@date: Fall, $2024$

$```$

$"""$

def isAStateLegal$($state$)$:

$"""$Determine whether a state is legal

$```$

Parameters

state : string

A state string composed of $\text{'}$W$\text{'}$ and $\text{'}$E$\text{'}$

Returns

Boolean

True if the state is legal; False otherwise

# Check if the state is composed entirely of $\text{'}$E$\text{'}$s

if state $=="$E$"*$ len$($state$)$:

return True

# Check for alternating pattern of $\text{'}$W$\text{'}$ and $\text{'}$E$\text{'}$

for i in range$(1,$ len$($state$))$:

if state$[$i$]==$ state$[$i $-1]$: # Adjacent characters should not be the same

return False

return True

# testing the function

print$("$Test $2$: Testing the legality of states"$)$

print$("$EEEE is legal:", isAStateLegal$(\text{'}$EEEE$\text{'}))$ # Expected: True

print$("$WEEE is legal:", isAStateLegal$(\text{'}$WEEE$\text{'}))$ # Expected: False

print$("$WEWE is legal:", isAStateLegal$(\text{'}$WEWE$\text{'}))$ # Expected: True

print$("$WEEW is legal:", isAStateLegal$(\text{'}$WEEE$\text{'}))$ # Expected: False