You are provided with a stub in which you need to insert your code where indicated without doing any

changes to the existing code to complete the task. Although it is not needed for this quiz, you may import

any extra module that is already installed in Ed if you wish.

The program randomly generates a grid with $0$s and $1$s$,$ whose dimension is controlled by user input, as

well as the density of $1$s in the grid, and finds out for a given step$\_$number $>=1$ and a given step$\_$size $>=2,$

the number of stairs of step$\_$number many steps, with all steps of size step$\_$size.

A stair of $1$ step of size $2$ is of the form:

$11$

$11$

A stair of $2$ steps of size $2$ is of the form

$11$

$11$

$11$

A stair of $1$ step of size $3$ is of the form

$111$

$1$

$111$

A stair of $2$ steps of size $3$ is of the form

$111$

$1$

$111$

$1$

$111$

$2$

The output lists the number of stairs from smallest step sizes to largest step sizes, and for a given step size,

from stairs with the smallest number of steps to stairs with the largest number of stairs.

Your task is to implement the function called stairs$\_$in$\_$grid$().$

You may possibly define other functions.

The provided stub and the outputs of the sample test cases explain the task to be performed.

here is the stub :

from random import seed, randint

import sys

from collections import defaultdict

def display$\_$grid$()$:

for i in range$($len$($grid$))$:

print$(\text{'}\text{'},\text{'}\text{'}.$join$($str$($int$($grid$[$i$][$j$]!=0))$

for j in range$($len$($grid$))$

$)$

$)$

try:

arg$\_$for$\_$seed, density, dim $=($int$($x$)$ for x in

input$(\text{'}$Enter three positive integers: $\text{'}).$split$()$

$)$

if arg$\_$for$\_$seed $<mtext\; id="EditorElement\_410225"></mtext><mn\; id="EditorElement\_410226">0</mn>$ or density $<mtext\; id="EditorElement\_410240"></mtext><mn\; id="EditorElement\_410241">0</mn>$ or dim $<mtext\; id="EditorElement\_410251"></mtext><mn\; id="EditorElement\_410252">0</mn>$:

raise ValueError

except ValueError:

print$(\text{'}$Incorrect input, giving up$.\text{'})$

sys$.$exit$()$

seed$($arg$\_$for$\_$seed$)$

grid $=[[$randint$(0,$ density$)$ for $\_$ in range$($dim$)]$ for $\_$ in range$($dim$)]$

print$(\text{'}$Here is the grid that has been generated:$\text{'})$

display$\_$grid$()$

def stairs$\_$in$\_$grid$()$:

return $\{\}$

# REPLACE THE RETURN STATEMENT ABOVE WITH YOUR CODE

# POSSIBLY DEFINE OTHER FUNCTIONS

# A dictionary whose keys are step sizes, and whose values are lists of pairs

# of the form $($number$\_$of$\_$steps,

# number$\_$of$\_$stairs$\_$with$\_$that$\_$number$\_$of$\_$steps$\_$of$\_$that$\_$step$\_$size

# $),$

# ordered from smallest to largest number$\_$of$\_$steps.

stairs $=$ stairs$\_$in$\_$grid$()$

for step$\_$size in sorted$($stairs$)$:

print$($f$\text{'}$

For steps of size $\{$step$\_$size$\},$ we have:$\text{'})$

for nb$\_$of$\_$steps, nb$\_$of$\_$stairs in stairs$[$step$\_$size$]$:

stair$\_$or$\_$stairs $=$ 'stair' if nb$\_$of$\_$stairs $==1$ else 'stairs'

step$\_$or$\_$steps $=$ 'step' if nb$\_$of$\_$steps $==1$ else 'steps'

print$(\text{'}\text{'},$ nb$\_$of$\_$stairs, stair$\_$or$\_$stairs, 'with',

nb$\_$of$\_$steps, step$\_$or$\_$steps

$)$

Grid can only contain $0$ and $1\text{'}$s$,$ The patterns and testcases are in the images please make sure the caclulation passes the correct calculation of stairs