Here are the test cases I used for testing my solutions to starred problems.
would be helpful if you don't want to spend time design your own test cases.
Just copy and paste the "Input" part at the end of your code. Hope you enjoy it!
1 - Reachability
Input:
graph = {'a': ['b', 'c'], 'b': ['a', 'c'], 'c': ['b', 'd'], 'd': ['a'], 'e': ['a']}
print reachable(graph, 'a')
print reachable(graph, 'd')
print reachable(graph, 'e')
graph2 = {'1': ['2', '3'], '2': [], '3': ['5', '7'], '4': ['3'], '5': ['4'], '6': ['3', '5', '7'], '7': ['1', '6']}
for i in range(len(graph2)):
print reachable(graph2, str(i + 1))
graph3 = {'1': ['2', '4', '5'], '2': [], '3': ['6'], '4': ['3', '7', '8'], '5': ['7'], '6': ['9', '10'], '7': ['6', '11'], '8': ['10', '11'], '9': [], '10': ['9', '11'], '11' :[], '12': []}
for i in range(len(graph3)):
print reachable(graph3, str(i + 1))
Output:
['a', 'c', 'd', 'b']
['d', 'a', 'c', 'b']
['e', 'a', 'c', 'd', 'b']
['1', '3', '7', '6', '5', '4', '2']
['2']
['3', '7', '6', '1', '2', '5', '4']
['4', '3', '7', '6', '1', '2', '5']
['5', '4', '3', '7', '6', '1', '2']
['6', '7', '1', '2', '5', '4', '3']
['7', '6', '5', '4', '3', '1', '2']
['1', '5', '7', '11', '6', '10', '9', '4', '8', '3', '2']
['2']
['3', '6', '10', '11', '9']
['4', '8', '11', '10', '9', '7', '6', '3']
['5', '7', '11', '6', '10', '9']
['6', '10', '11', '9']
['7', '11', '6', '10', '9']
['8', '11', '10', '9']
['9']
['10', '11', '9']
['11']
['12']
2 - Spelling Correction
Input:
print edit_distance('', '')
print edit_distance('a', 'a')
print edit_distance('God', 'good')
print edit_distance('city', 'cities')
print edit_distance('chance', 'charge')
print edit_distance('programming', 'programmer')
print edit_distance('destruct', 'constructor')
print edit_distance('trace-back', 'traceback')
print edit_distance('Pepsi', 'Coca-Cola')
print edit_distance('Coke', 'Coca-Cola')
print edit_distance('Kitamura', 'Kitahara')
print edit_distance('James Joyce', 'Rolls-Royce')
print edit_distance('Pneumothorax', 'Pneumonoultramicroscopicsilicovolcanoconiosis')
print edit_distance('ATCCTAGCCATGCAATGACATTG', 'ACTCTAGCCATGCATTGACATGT')
print edit_distance('LCLYTHIGRNIYYGSYLYSETWNTGIMLLLITMATAFMGYVLPWGQMSFWGATVITNLFSAIPYIGTNLVEWIWGGFSVDKATLNRFFAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLGLLILILLLLLLALLSPDMLGDPDNHMPADPLNTPLHIKPEWYFLFAYAILRSVPNKLGGVLALFLSIVILGLMPFLHTSKHRSMMLRPLSQALFWTLTMDLLTLTWIGSQPVEYPYTIIGQMASILYFSIILAFLPIAGXIENY', 'LCTYTHIGRNIYYGSYLYSETWNTGIMLLLITMATAFMGYVLPWGQMSFWGATVITNLFSAIPYIGTNLVEWIWGGFSVDKATLRFLAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLGLLILILLLLLLALLSPDMLGDPDNHMPADPLNTPLHIKLEWYFLFAYAILRSVPNKLGGVLALFFSIVILGLMPFLHTSKHRSMGLRPLSQALFWTLTMDLLTLTWIGSQPVEYPYTIIGQMASILYFSIILAFLPIAGXXIENY')
Output:
0
0
2
3
2
3
5
1
9
7
2
6
36
5
7
3 - Multiword Queries
Input:
cache = {
'http://localhost/index.html': """<html>
<body>
<a href="http://localhost/01.html"> OpenGL 2.0 </a><br/>
<a href="http://localhost/02.html"> ARB </a><br/>
<a href="http://localhost/03.html"> Cg shading language </a><br/>
<a href="http://localhost/04.html"> HLSL shading language </a><br/>
</body>
""",
'http://localhost/01.html': """<html>
<body>
OpenGL 2.0 was originally conceived by 3Dlabs to address concerns that OpenGL was stagnating and lacked a strong direction. 3Dlabs proposed a number of major additions to the standard. Most of these were, at the time, rejected by the ARB or otherwise never came to fruition in the form that 3Dlabs proposed. However, their proposal for a C-style shading language was eventually completed, resulting in the current formulation of GLSL (the OpenGL Shading Language, also slang). Like the assembly-like shading languages that it was replacing, it allowed the programmer to replace the fixed-function vertex and fragment pipe with shaders, though this time written in a C-like high-level language.
The design of GLSL was notable for making relatively few concessions to the limitations of the hardware then available; this hearkened back to the earlier tradition of OpenGL setting an ambitious, forward-looking target for 3D accelerators rather than merely tracking the state of currently available hardware. The final OpenGL 2.0 specification includes support for GLSL.
OpenGL 2.0 added support for a true, GPU-based assembly language called ARB (designed by the Architecture Review Board), which would become the standard for vertex and fragment shaders. Cards released with OpenGL 2.0 were the first to offer user-programmable shaders.
</body>
</html>
""",
'http://localhost/02.html': """<html>
<body>
Subsequent high-level shading languages sometimes compile to this ARB standard. While 3D developers are now more likely to use a C-like, high-level shading language for GPU programming, ARB assembly has the advantage of being supported on a wide range of hardware.
Note however that some features, such as loops and conditionals, are not available in ARB assembly, and using them requires to adopt either the NV_gpu_program4 extension, or the GLSL shading language.
Most non-nVidia OpenGL implementations do not provide the nVidia ARB assembly extension and do not offer any other way to access all the shader features directly in assembly, forcing the use of GLSL even for machine generated shaders where assembly would be more appropriate.
</body>
</html>
""",
'http://localhost/03.html': """<html>
<body>
Cg (short for C for Graphics) is a high-level shading language developed by Nvidia in close collaboration with Microsoft for programming vertex and pixel shaders. It is very similar to Microsoft's HLSL.
Cg is based on the C programming language and although they share the same syntax, some features of C were modified and new data types were added to make Cg more suitable for programming graphics processing units.
This language is only suitable for GPU programming and is not a general programming language.
The Cg compiler outputs DirectX or OpenGL shader programs.
</body>
</html>
""",
'http://localhost/04.html': """<html>
<body>
The High Level Shader Language or High Level Shading Language (HLSL) is a proprietary shading language developed by Microsoft for use with the Microsoft Direct3D API. It is analogous to the GLSL shading language used with the OpenGL standard. It is the same as the Nvidia Cg shading language, and it was developed alongside it.
HLSL programs come in three forms, vertex shaders, geometry shaders, and pixel (or fragment) shaders. A vertex shader is executed for each vertex that is submitted by the application, and is primarily responsible for transforming the vertex from object space to view space, generating texture coordinates, and calculating lighting coefficients such as the vertex's tangent, binormal and normal vectors. When a group of vertices (normally 3, to form a triangle) come through the vertex shader, their output position is interpolated to form pixels within its area; this process is known as rasterisation. Each of these pixels comes through the pixel shader, whereby the resultant screen colour is calculated.
</body>
</html>
"""
}
index2, graph2 = crawl_web('http://localhost/index.html')
print multi_lookup(index2, ['OpenGL'])
print multi_lookup(index2, ['GLSL'])
print multi_lookup(index2, ['high-level'])
print multi_lookup(index2, ['vertex'])
print multi_lookup(index2, ['vertex', 'shader'])
print multi_lookup(index2, ['GPU', 'programming'])
print multi_lookup(index2, ['assembly', 'language'])
print multi_lookup(index2, ['shading', 'languages'])
print multi_lookup(index2, ['C', 'programming', 'language'])
print multi_lookup(index2, ['shading', 'language'])
print multi_lookup(index2, ['shading', 'languages'])
print multi_lookup(index2, ['GLSL', 'shading', 'language'])
print multi_lookup(index2, ['Cg', 'shading', 'language'])
print multi_lookup(index2, ['HLSL', 'shading', 'language'])
print multi_lookup(index2, ['proprietary', 'shading', 'language'])
Output:
['http://localhost/index.html', 'http://localhost/04.html', 'http://localhost/03.html', 'http://localhost/02.html', 'http://localhost/01.html']
['http://localhost/04.html', 'http://localhost/02.html', 'http://localhost/01.html']
['http://localhost/03.html', 'http://localhost/02.html', 'http://localhost/01.html']
['http://localhost/04.html', 'http://localhost/03.html', 'http://localhost/01.html']
['http://localhost/04.html']
['http://localhost/03.html']
['http://localhost/01.html']
['http://localhost/02.html', 'http://localhost/01.html']
['http://localhost/03.html']
['http://localhost/index.html', 'http://localhost/04.html', 'http://localhost/03.html', 'http://localhost/02.html', 'http://localhost/01.html']
['http://localhost/02.html', 'http://localhost/01.html']
['http://localhost/04.html']
['http://localhost/index.html']
['http://localhost/index.html']
['http://localhost/04.html']
how did you get
print edit_distance('Pneumothorax', 'Pneumonoultramicroscopicsilicovolcanoconiosis') == 36 ?
I get 37, which is both the output of my program and my own consideration:
len(microscopicsilicovolcanoconiosis) + edit_distance('tho','noult') = 32 + 5 = 37
@proftobes For this case, you can't simply count the length of "microscopicsilicovolcanoconiosis" as a whole word.
See this result I got: (36 steps)
Pneumothorax -> Pneumonoulthorax: 4 insertions
Pneumonoulthorax -> Pneumonoultrarax: 2 substitutionsPneumonoultrarax -> Pneumonoultramicrax: 3 insertions
Pneumonoultramicrax -> Pneumonoultramicroscopicsilicovolcax: 17 insertions
Pneumonoultramicroscopicsilicovolcax -> Pneumonoultramicroscopicsilicovolcan: 1 substitutions
Pneumonoultramicroscopicsilicovolcan -> Pneumonoultramicroscopicsilicovolcanoconiosis: 9 insertions
you're right. Thanks!