Ch24 Sample Programming Exam.docx

Chapter 24. Sample Programming Exam – Topic #1 In This Chapter In this chapter we will look at and offer solutions to three problems from a sample programming exam. While solving them we will put into practice the methodology described in the chapter "Methodology of Problem Solving". Problem 1: Extract Text from HTML Document We are given HTML file named Problem1.html. Write a program, which removes all HTML tags and retains only the text inside them. Output should be written into the file Problem1.txt. Sample input file for Problem1.html:


Home Contacts About

Sample output file for Problem1.txt: Welcome to our site! Home Contacts About Inventing an Idea The first thing that occurs to us as an idea for solving this problem is to read sequentially (e.g. line by line) the input file and to remove any tags. It is easily seen that all tags starting with the character "<" and end with the character ">". This also applies to opening and closing tags. This means that for each line in the file we should remove all substrings starting with "<" and ending with ">". Checking the Idea We have an idea for solving the problem. Whether the idea is correct? First we should check it. We can ensure it is correct for the sample input file, and then consider whether there are specific cases where the idea could be incorrect. We take a pen and paper and check by manually whether the idea is correct. We do this by striking out all text substrings that start with the character "<" and end with the character ">". As we do so, we see that there is only pure text and any tags disappear:


Home Contacts About

Now we have to think of some more special cases. We do not want to write 200 lines of code and only then think about special case, finding out we have to redesign the entire program. It is important to check the problematic situations now, before we begin writing the code of the solution. We can think of the following special example: Clickon this linkfor more info.
This isboldtext. There are two things to consider: There are tags containing text that open and close at separate lines. Such tags in our example are ,  and . There are tags that contain text and other tags in themselves (nested tags). For example  and . What should be the result of this example? If we directly remove all tags we will get something like this: Clickon this linkfor more info. This isboldtext. Or maybe we should follow the rules of the HTML language and get the following result: Click on this link for more info. This is bold text. There are other options, such as putting each piece of text, which is not a tag, on a new line: Click on this link for more info. This is bold text. If we remove all the text in tags and snap the other text, we will get words that are stuck together. From the task’s description it is not clear if this is the requested result or it must be as in the HTML language. In the HTML language each series of separators (spaces, new lines, tabs, etc.) appear as a space. However, this was not mentioned in the task’s description it is not clear from the sample input and output. It is not clear yet whether to print the words that are in a tag which holds other tags or to skip them. If we print only the contents of the tags, which consist of text only, we will get something like this: on this link bold It is yet not clear from the description, how to display the text that is located on a few lines inside a tag. Clarification of the Statement of the Problem The first thing to do when we find ambiguity in the description of the task is to read it carefully. In this case the problem statement is not really clear and does not give us the answers. Probably we should not follow the HTML rules, because they are not described in the problem statement, but it is not clear whether to connect the words in neighboring tags or separate them by a space or new line. This leaves us only one thing – to ask. If we have an exam, we will ask the one who gives us the task. In real life, someone is an owner of the software we develop, and he could answer the questions. If nobody can give an answer, choose one option that seems most correct under the information we have and act on it. Assume that we need to print text, which remains after removing all opening and closing tags, using a blank line separator at the positions of the tags. If there are blank lines in the text, we keep them. For our example, we should obtain the following correct output: Click on this link for more info. This is bold text. A New Idea for Solving the Problem So, after adapting these new requirements, the following idea comes: read file line by line and substitute each tag with a new line. To avoid duplication of new lines in the resulting file, replace every two consecutive lines of new results with a new line. We check the new idea with the example from the original statement of the problem with our example to ensure it is correct. It remains to implement it. Break a Task into Subtasks The task can easily break into 3 subtasks: Read the input file. Processing of a line of input file: replace tags with a new line. Print results in the output file. What Data Structures to Use? In this task we must perform simple word processing and file management. The question of what data structures to use is not a problem – for word processing we use string and if necessary – StringBuilder. Consider the Efficiency If we read the lines one by one, it will not be a slow operation. Processing of one line can be done by replacing some characters with others – a quick operation. We should not have performance problems. A possible problem could be the clearing of the empty lines. If we collect all lines in a buffer (StringBuilder) and then remove double blank lines, this buffer will occupy too much memory for large input files (for example 500 MB input file). To save memory, we will try to clean the excess blank lines just after the replacement tags with the white space character. Now we examined the idea of solving the task, we ensured that it is good and covers the special cases that may arise, and believe we will have no performance issues. Now we can safely proceed to implementation of the algorithm. We will write the code step by step to find errors as early as possible. Step 1 – Read the Input File The first step solving the given task is reading the input file. In our case it is a HTML file. This should not bother us, because HTML is a text format. Therefore, to read it, we will use the StreamReader class. We will traverse the input file line by line and each line we will derive (for now it is not important how we will do it) all the information we need (if any) and save it into an object of type StringBuilder. Extraction we will implement in the next step (step 2). Let’s write the necessary code for the implementation of our first step: string line = string.Empty; StreamReader reader = new StreamReader("Problem1.html"); while ((line = reader.ReadLine()) != null) { // Find what we need and save it in the result } reader.Close(); With this code we will read the input file line by line. Let’s think whether we have completed a good first step. Do you know what we have missed? From the code written we will read the input file, but only if it exists. What if the input file does not exist or could not be opened for some reason? Our present decision does not deal with these problems. There is another problem in our code too: if an error occurs while reading or processing the data file, it will not be closed. With File.Exists(…) we will check if the input file exists. If not – we will display an appropriate message and stop program execution. To avoid the second problem we will use the try-catch-finally statement (we may use the using statement in C# as well). Thus, if an exception arises, we will process it and will always close the file, which we worked with. We must not forget that the object of the StreamReader class must be declared outside the try block, otherwise it will be unavailable in the finally block. This is not a fatal error, but often made by novice programmers. It is better to define the input file name as a constant, because we probably will use it in several places. Another thing: when reading from a text file it is appropriate to specify explicitly the character encoding. Let’s see what we get: using System; using System.IO; using System.Text; class HtmlTagRemover { private const string InputFileName = "Problem1.html"; private const string Charset = "windows-1251"; static void Main() { if (!File.Exists(InputFileName)) { Console.WriteLine( "File " + InputFileName + " not found."); return; } StreamReader reader = null; try { Encoding encoding = Encoding.GetEncoding(Charset); reader = new StreamReader(InputFileName, encoding); string line; while ((line = reader.ReadLine()) != null) { // Find what we need and save it in the result } } catch (IOException) { Console.WriteLine( "Can not read file " + InputFileName + "."); } finally { if (reader != null) { reader.Close(); } } } } Test the Input File Reading Code We handled the described problems and it seems we have implemented the reading of the input file. We wrote a lot of code. To be convinced that it is correct, we can test our unfinished code. For example let’s print the content of the input file to the console, and then try processing nonexistent files. The writing will be done in a while loop using Console.WriteLine(…): … while ((line = reader.ReadLine()) != null) { Console.WriteLine(line); } … If we test the piece of code we have with the Problem1.html sample file from the problem description, the result is correct – the input file itself:


Home - Contacts - About

Let’s try a nonexistent file. We change the file name Problem1.html with Problem2.html. The result is the following: File Problem2.html not found We are convinced that the code till now is correct. Let’s move to the next step of the implementation of our idea (algorithm). Step 2 – Remove the Tags Now we want to find a suitable way to remove all tags. How should we do this? One possible way is to check the line character by character. For each character in the current row we will look for the character "<". On the right side of it we will know that we have a tag (opening or closing). The end tag character is ">". So we can find tags and remove them. To not get the words connected between adjacent tags, each tag will be replaced with the character for a blank line "\n". The algorithm is simple to implement, but isn’t there a more clever way? Can we use regular expressions? They can easily look for tags and replace them with "\n", right? In the same time the code will be simple and in case of errors, they will be removed more easily. We will consider this option. What should we do? First we need to write a regular expression. Here is how it may look: <[^>]*> The idea is simple: any string, that starts with "<", continues with arbitrary sequence of characters, other than ">" and ends with ">" is an HTML tag. Here’s how we can replace the tags with a new line: private static string RemoveAllTags(string str) { string textWithoutTags = Regex.Replace(str, "<[^>]*>", "\n"); return textWithoutTags; } After coding this step, we should test it. For this purpose again we print to the console the strings we found via Console.WriteLine(…). And test the code: HtmlTagRemover.cs using System; using System.IO; using System.Text; using System.Text.RegularExpressions; class HtmlTagRemover { private const string InputFileName = "Problem1.html"; private const string Charset = "windows-1251"; static void Main() { if (!File.Exists(InputFileName)) { Console.WriteLine( "File " + InputFileName + " not found."); return; } StreamReader reader = null; try { Encoding encoding = Encoding.GetEncoding(Charset); reader = new StreamReader(InputFileName, encoding); string line; while ((line = reader.ReadLine()) != null) { line = RemoveAllTags(line); Console.WriteLine(line); } } catch (IOException) { Console.WriteLine( "Can not read file " + InputFileName + "."); } finally { if (reader != null) { reader.Close(); } } } private static string RemoveAllTags(string str) { string strWithoutTags = Regex.Replace(str, "<[^>]*>", "\n"); return strWithoutTags; } } Testing the Tag Removal Code Let’s test the program with the following input file: Clickon this linkfor more info.
This isboldtext. The result is as follows: (empty rows) Click on this link for more info. (empty row) This is bold text. (empty rows) Everything works perfectly, only that we have extra blank lines. Can we remove them? This will be our next step. Step 3 – Remove the Empty Lines We can remove unnecessary blank lines, replacing a double blank line "\n\n" with a single blank line "\n". We should not have groups of more than one character for a new line "\n". Here is an example how we can perform the substitution: private static string RemoveDoubleNewLines(string str) { return str.Replace("\n\n", "\n"); } Testing the Empty Lines Removal Code As always, before we move forward, we test whether the method works correctly. We try a text, which has no blank rows, and then add 2, 3, 4 and 5 blank lines, including at the beginning and at the end of text. We find that the above method does not work correctly, when there are 4 blank lines one after another. For example, if we submit as input "ab\n\n\n\ncd", we will get "ab\n\n\cd" instead of "ab\ncd". This defect occurs because the Replace(…) finds and replaces a single match, scanning the text from left to right. If in result of a substitution the searched string reappears, it is skipped. See how useful it is when each method is tested on time. We do not end up wondering why the program does not work when we have 200 lines of code, full of errors. Early detection of defects is very useful and we should do it whenever possible. Here is the corrected code: private static string RemoveDoubleNewLines(string str) { string pattern = "[\n]+"; return Regex.Replace(str, pattern, "\n"); } The above code uses a regular expression to find any sequence of \n characters and replaces it with a single \n. After a series of tests, we are convinced that the method works correctly. We are ready to test the program that removes all unnecessary newlines. For this purpose we make the following changes: while ((line = reader.ReadLine()) != null) { line = RemoveAllTags(line); line = RemoveDoubleNewLines(line); Console.WriteLine(line); } We test the code again. Still it seems there are blank lines. Where do they come from? Perhaps, if we have a line that contains only tags, it will cause a problem. Therefore we may prevent this case. We add the following checks: if (!string.IsNullOrEmpty(line)) { Console.WriteLine(line); } This removes most of the blank lines, but not all. Remove the Empty Lines: Second Attempt If we think more, it could happen so, that a line begins or ends with a tag. Then this tag will be replaced with a single blank line and so at the beginning or at the end of the line we may get a blank line. This means that we should clean the empty rows at the beginning and at the end of each line. Here’s how we can make the cleaning: private static string TrimNewLines(string str) { int start = 0; while (start < str.Length && str[start] == '\n') { start++; } int end = str.Length - 1; while (end >= 0 && str[end] == '\n') { end--; } if (start > end) { return string.Empty; } string trimmed = str.Substring(start, end - start + 1); return trimmed; } The method works very simply: goes from left to right and skips all newline characters. Then passes from right to left and skips again all newline characters. If the left and right positions have passed each other, this means that the string is either empty or contains only newlines. Then the method returns an empty string. Otherwise it returns back everything to the right of the start position and to the left of the end position. Remove the Empty Lines: Test Again As always, we test whether the above method works correctly with several examples, including an empty string, no string breaks, string breaks left or right or both sides and a string with new lines. We make sure, that the method now works correctly. Now we have to modify the logic of processing the input file: while ((line = reader.ReadLine()) != null) { line = RemoveAllTags(line); line = RemoveDoubleNewLines(line); line = TrimNewLines(line); if (!string.IsNullOrEmpty(line)) { Console.WriteLine(line); } } Step 4 – Print Results in a File It remains to print the results in the output file. To print the results in the output file we will use the StreamWriter. This step is trivial. We must only consider that writing to a file can cause an exception and that’s why we need to change the logic for error handling slightly, opening and closing the flow of input and output to the file. Here is what we finally get as a complete source code of the program: HtmlTagRemover.cs using System; using System.IO; using System.Text; using System.Text.RegularExpressions; class HtmlTagRemover { private const string InputFileName = "Problem1.html"; private const string OutputFileName = "Problem1.txt"; private const string Charset = "windows-1251"; static void Main() { if (!File.Exists(InputFileName)) { Console.WriteLine( "File " + InputFileName + " not found."); return; } StreamReader reader = null; StreamWriter writer = null; try { Encoding encoding = Encoding.GetEncoding(Charset); reader = new StreamReader(InputFileName, encoding); writer = new StreamWriter(OutputFileName, false, encoding); string line; while ((line = reader.ReadLine()) != null) { line = RemoveAllTags(line); line = RemoveDoubleNewLines(line); line = TrimNewLines(line); if (!string.IsNullOrEmpty(line)) { writer.WriteLine(line); } } } catch (IOException) { Console.WriteLine( "Can not read file " + InputFileName + "."); } finally { if (reader != null) { reader.Close(); } if (writer != null) { writer.Close(); } } } ///

/// Replaces every tag with new line ///

private static string RemoveAllTags(string str) { string strWithoutTags = Regex.Replace(str, "<[^>]*>", "\n"); return strWithoutTags; } ///

/// Replaces sequence of new lines with only one new line ///

private static string RemoveDoubleNewLines(string str) { string pattern = "[\n]+"; return Regex.Replace(str, pattern, "\n"); } ///

/// Removes new lines from start and end of string ///

private static string TrimNewLines(string str) { int start = 0; while (start < str.Length && str[start] == '\n') { start++; } int end = str.Length - 1; while (end >= 0 && str[end] == '\n') { end--; } if (start > end) { return string.Empty; } string trimmed = str.Substring(start, end - start + 1); return trimmed; } } Testing the Solution Until now, we were testing the individual steps for the solution of the task. Through the tests of individual steps we reduced the possibility of errors, but that does not mean that we should not test the whole solution. We may have missed something, right? Now let’s thoroughly test the code. Test with the sample input file from the problem statement. Everything works correctly. Test our "complex" example. Everything works fine. Test the border cases and run an output test. We test with a blank file. Output is correct – an empty file. Test with a file that contains only one word "Hello" and does not contain tags. The result is correct – the output contains only the word "Hello". Test with a file that contains only tags and no text. The result is again correct – an empty file. Try to put blank lines of at the most amazing places in the input file. These empty lines should all be removed. For example we can run the following test: Hello

I am here I am not here The result is as follows: Hello I am here I am not Here It seems we found a small defect. There is a space at the beginning of some of the lines. Fixing the Leading Spaces Defect Under the problem description it is not clear whether this is a defect but let’s try to fix it. We could add the following code when processing the next line of the input file: line = line.Trim(); The defect is fixed, but only from the first line. We run the debugger and we notice why it is so. The reason is that we print into the output file a string of characters with value "I\n am here" and so we get a space after a blank line. We can correct the defect, by replacing all blank lines, followed by white space (blank lines, spaces, tabs, etc.) with a single blank line. Here is the correction: private static string RemoveDoubleNewLines(string str) { string pattern = "\n\\s+"; return Regex.Replace(str, pattern, "\n"); } We fixed that error too. Now we have only to change this name to a more appropriate one, for example RemoveNewLinesWithWhiteSpace(…). Now we need to test again after the “fixes” in the code (regression test). We put new lines and spaces scattered randomly and make sure that everything works correctly now. Performance Test One last test remains: performance. We can create easily create a large input file. We open a site, for example http://www.microsoft.com, grab the source code and copy it 1000 times. We get a large enough input file. In our case, we get a 44 MB file with 947,000 lines. Processing it takes under 10 seconds, which is a perfectly acceptable speed. When we test the solution we should not forget that the processing of the file depends on our hardware (our test was performed in 2009 on an average fast laptop). Taking a look at the result, however, we notice a very troublesome problem. There are parts of a tag. More precisely, we see the following: It quickly becomes clear that we missed a very interesting case. In an HTML tag can be closed few lines after its opening, e.g. a single tag may span several consecutive lines. That was exactly our case: we have a comment tag that contains JavaScript code. If the program worked correctly, it would have cut the entire tag rather than keep it in the source file. Did you see how testing is useful and how testing is important? In some big companies (like Microsoft) having a solution without tests is considered as only 50% of the work. This means that if you write code for 2 hours, you should spend on testing (manual or automated) at least 2 more hours! This is the only way to create high-quality software. What a pity that we discovered the problem just now, instead of at the beginning, when we were checking whether our idea for the task is correct, before we wrote the program. Sometimes it happens, unfortunately. How to Fix the Problem with the Tag at Two Lines? The first idea that occurs to us is to load in memory the entire input file and process it as one big string rather than row by row. This is an idea that seems to work but will run slow and consume large amounts of memory. Let’s look for another idea. A New Idea: Processing the Text Char by Char Obviously we cannot read the file line by line. Can we read it character by character? If yes, how we will treat tags? It occurs to us that if we read the file character by character, we can know at any moment, whether we are in or outside of a tag, and if we are outside the tag, we can print everything that we read (followed by a new line). We need to avoid adding new lines, as well as and trailing whitespace. We will get something like this: bool inTag = false; while (! ) { char ch = (read the next character); if (ch == '<') { inTag = true; } else if (ch == '>') { inTag = false; } else { if (!inTag) { PrintBuffer(ch); } } } Implementing the New Idea The idea is very simple and easy to implement. If we implement it directly, we will have a problem with empty lines and the problem of merging text from adjacent tags. To solve this problem, we can accumulate the text in the StringBuilder and print it at the end of file or when switching from text to a tag. We will get something like this: bool inTag = false; StringBuilder buffer = new StringBuilder(); while (! ) { char ch = (read the next character); if (ch == '<') { if (!inTag) { PrintBuffer(buffer); } buffer.Clear(); inTag = true; } else if (ch == '>') { inTag = false; } else { if (!inTag) { buffer.Append(ch); } } } PrintBuffer(buffer); The missing PrintBuffer(…) method should clean the whitespace from the text in the buffer and print it in the output followed by a new line. Exception is when we have whitespace only in the buffer (it should not be printed). We already have most of the code, so step-by-step implementation mat not be necessary. We can just replace the pieces of wrong old code with the new code implementing the new idea. If we add the logic for avoiding empty lines as well as reading input and writing the result we obtain is a complete solution to the task with the new algorithm: SimpleHtmlTagRemover.cs using System; using System.IO; using System.Text; using System.Text.RegularExpressions; public class SimpleHtmlTagRemover { private const string InputFileName = "Problem1.html"; private const string OutputFileName = "Problem1.txt"; private const string Charset = "windows-1251"; private static Regex regexWhitespace = new Regex("\n\\s+"); static void Main() { if (!File.Exists(InputFileName)) { Console.WriteLine( "File " + InputFileName + " not found."); return; } StreamReader reader = null; StreamWriter writer = null; try { Encoding encoding = Encoding.GetEncoding(Charset); reader = new StreamReader(InputFileName, encoding); writer = new StreamWriter(OutputFileName, false, encoding); RemoveHtmlTags(reader, writer); } catch (IOException) { Console.WriteLine( "Cannot read file " + InputFileName + "."); } finally { if (reader != null) { reader.Close(); } if (writer != null) { writer.Close(); } } } ///

Removes the tags from a HTML text

/// Input text /// Output text (result) private static void RemoveHtmlTags( StreamReader reader, StreamWriter writer) { StringBuilder buffer = new StringBuilder(); bool inTag = false; while (true) { int nextChar = reader.Read(); if (nextChar == -1) { // End of file reached PrintBuffer(writer, buffer); break; } char ch = (char)nextChar; if (ch == '<') { if (!inTag) { PrintBuffer(writer, buffer); } buffer.Clear(); inTag = true; } else if (ch == '>') { inTag = false; } else { // We have other character (not "<" or ">") if (!inTag) { buffer.Append(ch); } } } } ///

Removes the whitespace and prints the buffer /// in a file

/// the result file /// the input for processing private static void PrintBuffer( StreamWriter writer, StringBuilder buffer) { string str = buffer.ToString(); string trimmed = str.Trim(); string textOnly = regexWhitespace.Replace(trimmed, "\n"); if (!string.IsNullOrEmpty(textOnly)) { writer.WriteLine(textOnly); } } } The input file is read character by character with the class StreamReader. Originally the buffer for accumulating of text is empty. In the main loop we analyze each read character. We have the following cases: If we get to the end of file, we print whatever is in the buffer and the algorithm ends. When we encounter the character "<" (start tag) we first print the buffer (if we find that the transition is from text to tag). Then we clear the buffer and set inTag = true. When we encounter the character ">" (end tag) we set inTag = false. This will allow the next characters after the tag to accumulate in the buffer. When we encounter another character (text or blank space), it is added to the buffer, if we are outside tags. If we are in a tag the character is ignored. Printing of the buffer takes care of removing empty lines in text and clearing the empty space at the beginning and end of text (trimming the leading and trailing whitespace). How exactly we do this, we already discussed in the previous solution of the problem. In the second solution the processing of the buffer is much lighter and shorter, so the buffer is processed immediately before printing. In the previous solution of the task we used regular expressions for replacing with the static methods of the class Regex. For improved performance now we create the regular expression object just once (as a static field). Thus the regular expression pattern is compiled just once to a state machine. Testing the New Solution It remains to test thoroughly the new solution. We have to perform all tests conducted on the previous solution. Add test with tags, which are spread over several lines. Again, test performance with the Microsoft website copied 1000 times. Assure that the program works correctly and is even faster. Let’s try with another site, such as the official website of this book – http://www.introprogramming.info (as of April 2011). Again, take the source code of the site and run the solution of our task with it. After carefully reviewing the input data (source code on the website of the book) and the output file, we notice that there is a problem again. Some content of this tag is printed in the output file: Where Is the Problem? The problem seems to occur when one tag meets another tag, before the first tag is closed. This can happen in HTML comments. Here’s how to get to the error: 624205-393701. InTag = true 00 1. InTag = true visit it maze[row, column] = 'x'; Cell cell = new Cell(row, column, distance); visitedCells.Enqueue(cell); } } Checking after Step 3 Before the next step, we must test, to check our algorithm. We must try the normal case and the border cases, when there is no exit, when we step on an exit, when the input file doesn’t exist or the square matrix is with size of 0. Only then can we start doing the next step. Let’s start with testing the normal (typical) case. We create the following code to quickly test it: static void Main() { Maze maze = new Maze(); maze.ReadFromFile("Problem2.in"); Console.WriteLine(maze.FindShortestPath()); } We run the above code over the sample input file from the problem description and it works. The code correctly returns the length of the shortest path to the nearest exit: 9 Now let’s test the border cases, e.g. a labyrinth of size 0. Unfortunately we get the following result: Unhandled Exception: System.NullReferenceException: Object reference not set to an instance of an object. at Maze.FindShortestPath() We’ve made a mistake. The problem is when the variable, in which we keep the initial cell, is initialized with null. This can happen in many scenarios. If the labyrinth has no cells (e.g. size of 0) or the initial cell is missing, the result that the program should return is -1, but not an exception. To fix the bug we just found we can add a check in the beginning of the FindShortestPath() method: public int FindShortestPath() { if (this.startCell == null) { // Start cell is missing -> no path return -1; } … We retest the code with the typical and the border cases. After the fix it seems the algorithm works correctly now. Step 4 – Writing the Result to a File It remains to write the result of the FindShortestPath() to the output file. This is a trivial problem: public void SaveResult(String fileName, int result) { using (StreamWriter writer = new StreamWriter(fileName)) { writer.WriteLine("The shortest way is: " + result); } } Here is how the complete source code of the solution looks: Maze.cs using System; using System.IO; using System.Collections.Generic; public class Maze { private const string InputFileName = "Problem2.in"; private const string OutputFileName = "Problem2.out"; public class Cell { public int Row { get; set; } public int Column { get; set; } public int Distance { get; set; } public Cell(int row, int column, int distance) { this.Row = row; this.Column = column; this.Distance = distance; } } private char[,] maze; private int size; private Cell startCell = null; public void ReadFromFile(string fileName) { using (StreamReader reader = new StreamReader(fileName)) { // Read maze size and create maze this.size = int.Parse(reader.ReadLine()); this.maze = new char[this.size, this.size]; // Read the maze cells from the file for (int row = 0; row < this.size; row++) { string line = reader.ReadLine(); for (int col = 0; col < this.size; col++) { this.maze[row, col] = line[col]; if (line[col] == '*') { this.startCell = new Cell(row, col, 0); } } } } } public int FindShortestPath() { if (this.startCell == null) { // Start cell is missing -> no path return -1; } // Queue for traversing the cells in the maze Queue visitedCells = new Queue(); VisitCell(visitedCells, this.startCell.Row, this.startCell.Column, 0); // Perform Breath-First-Search (BFS) while (visitedCells.Count > 0) { Cell currentCell = visitedCells.Dequeue(); int row = currentCell.Row; int column = currentCell.Column; int distance = currentCell.Distance; if ((row == 0) || (row == size - 1) || (column == 0) || (column == size - 1)) { // We are at the maze border return distance + 1; } VisitCell(visitedCells, row, column + 1, distance + 1); VisitCell(visitedCells, row, column - 1, distance + 1); VisitCell(visitedCells, row + 1, column, distance + 1); VisitCell(visitedCells, row - 1, column, distance + 1); } // We didn't reach any cell at the maze border -> no path return -1; } private void VisitCell(Queue visitedCells, int row, int column, int distance) { if (this.maze[row, column] != 'x') { // The cell is free --> visit it maze[row, column] = 'x'; Cell cell = new Cell(row, column, distance); visitedCells.Enqueue(cell); } } public void SaveResult(string fileName, int result) { using (StreamWriter writer = new StreamWriter(fileName)) { writer.WriteLine(result); } } static void Main() { Maze maze = new Maze(); maze.ReadFromFile(InputFileName); int pathLength = maze.FindShortestPath(); maze.SaveResult(OutputFileName, pathLength); } } Testing the Complete Solution of the Problem After we have a solution of the problem we must test it. We have already tested the typical case and the border cases (like missing exit or when the initial position stays at the labyrinth edge). We will execute these tests again to get convinced that the algorithm behaves correctly: Input Output Input Output Input Output Input Output 0 -1 2 00 xx -1 3 0x0 x*x 0x0 -1 3 000 000 00* 1 The algorithm works correctly. The output for each of the test is correct. It remains to test with a large labyrinth (performance test), for example 1000 x 1000. We can make such a labyrinth very easy – with copy / paste. We perform the test and we convince ourselves the program is working correctly for the big test and works extremely fast – there is no delay. While testing we should try every way to break our solution. We run a few more difficult examples (for example a labyrinth with passable cells in the form of spiral). We can put large labyrinth with a lot of paths, but without exit. We can try whatever else we wish. At the end we make sure, that we have a correct solution and we pass to the next problem from the exam. Problem 3: Store for Car Parts A company is planning to create a system for managing a store for auto parts. A single part can be used for different car models and it has following characteristics: code, name, category (e.g. suspension, tires and wheels, engine, accessories and etc.), purchase price, sale price, list of car models, with which it is compatible (each car is described with brand, model and year of manufacture, e. g. Mercedes C320, 2008) and manufacturing company. Manufacturing companies are described with name, country, address, phone and fax. Design a set of classes with relationships between them, which model the data for the store. Write a demonstration program, which demonstrates the classes and their all functionality work correctly with some sample data. Inventing an Idea for Solution We have a non-algorithmic problem which is intended to check whether the students at the exam know how to use object-oriented programming (OOP), how to design classes and relationships between them to model real-world objects (object-oriented analysis and design) and how to use appropriate data structures to hold collections of objects. We are required to create an aggregation of classes and relationships between them, which have to describe the data of the store. We have to find which nouns are important for solving the problem. They are objects from the real world, which correspond to classes. Which are these nouns that interest us? We have a store, car parts, cars and manufacturing companies. We have to create a class defining a store. It could be named Shop. Other classes are Part, Car and Manufacturer. In the requirements of the problem there are other nouns too, like code for one part or year of manufacturing of given car. For these nouns we are not creating individual classes, but instead these will be fields in the already created classes. For example in the Part class there will be let’s say a field code of string type. We already know which will be our classes, and fields to describe them. We have to identify the relationships between the objects. Checking the Idea We will not check the idea because there is nothing to be proven with examples and counterexamples or checked whether it will work. We need to write few classes to model a real-world situation: a store for car parts. What Data Structures to Use to Describe the Relationship between Two Classes? The data structures, needed for this problem, are of two main groups: classes and relationships between the classes. The interesting part is how to describe relationships. To describe a relationship (link) between two classes we can use an array. With an array we have access of its elements by index, but once it is created we can’t change its length. This makes it uncomfortable for our problem, because we don’t know how many parts we will have in the store and more parts can be delivered or somebody can buy parts so we have to delete or change the data. List is more comfortable. It has the advantages of an array and also is with variable length and it is easy to add or delete elements. So far it seems List is the most appropriate for holding aggregations of objects inside another object. To be convinced we will analyze a few more data structures. For example hash-table – it is not appropriate in this case, because the structure “parts” is not of the key-value type. It would be appropriate if each of the parts in the store has unique number (e.g. barcode) and we needed to search them by this unique number. Structures like stack and queue are inappropriate. The structure “set” and its implementation HashSet is used when we have uniqueness for given key. It would be good sometimes to use this structure to avoid duplicates. We must recall that HashSet requires the methods GetHashCode() and Equals(…) to be correctly defined by the T type. Our final decision is to use List for the aggregations and HashSet for the aggregations which require uniqueness. Dividing the Task into Subtasks Now we have to think from where to start writing the code. If we start to write the Shop class, we will need the Part class. This reminds us we will have to start with a class, which does not depend on others. We will divide the writing of each class to ? subtask, and we will start from the independent classes: Class describing a car – Car Class describing manufacturer of parts – Manufacturer Class or enumeration for the categories of the parts – PartCategory Class describing part for a car – Part Class for the store – Shop Class for testing rest of the classes with sample data – TestShop Implementation: Step by Step We start writing classes, which we described in our idea. We will create them in the same sequence as in the list above. Step 1: The Class Car We start solving the problem by defining the class Car. In the definition we have three fields, which keep the manufacturer, the model and the year of manufacturing of the car and the standard method ToString(), which returns a human-readable string holding the information about the car. We define the class Car in the following way: Car.cs public class Car { private string brand; private string model; private int productionYear; public Car(string brand, string model, int productionYear) { this.brand = brand; this.model = model; this.productionYear = productionYear; } public override string ToString() { return "<" + this.brand + "," + this.model + "," + this.productionYear + ">"; } } Note that the class Car is designed to be immutable. This means that once created, the car’s properties cannot be later modified. This design is not always the best choice. Sometimes we want the class properties to be freely modifiable; sometimes. For our case the immutable design will work well. Testing the Class Car Once we have the class Car, we could test it by the following code: Car bmw316i = new Car("BMW", "316i", 1994); Console.WriteLine(bmw316i); The result is as expected: We are convinced the class Car is correct so far and we can continue with the other classes. Step 2: The Class Manufacturer We have to implement the definition of the class Manufacturer, which describes the manufacturer for given part. It will have five fields – name, country, address, phone number and fax. The class will be immutable, because we will not need to change its members after creation. We also define the standard method ToString() for representing the object as human-readable string. Manufacturer.cs public class Manufacturer { private string name; private string country; private string address; private string phoneNumber; private string fax; public Manufacturer(string name, string country, string address, string phoneNumber, string fax) { this.name = name; this.country = country; this.address = address; this.phoneNumber = phoneNumber; this.fax = fax; } public override string ToString() { return this.name + " <" + this.country + "," + this.address + "," + this.phoneNumber + "," + this.fax + ">"; } } Testing the Class Manufacturer We test the class Manufacturer just like we tested the class Car. It works. Step 3: The Part Category Enumeration Part categories are fixes set of values and do not have additional details (like name, code and description). This makes them perfect to be modeled as enumeration: PartCategory.cs public enum PartCategory { Engine, Tires, Exhaust, Suspention, Brakes } Step 4: The Class Part Now we have to define the class Part. Its definition will include the following fields: name, code, category, list with cars, where we can use the given part, starting and closing price and manufacturer. Here we will use the data structure HashSet to hold all compatible cars. The field that keeps the manufacturer of the part will be of Manufacturer class, because the task requires us to keep additional information about the manufacturer. If it was required to keep only the name of the manufacturer (as in the case with class Car) this class should not be necessary. We would have a field of string type. We need a method for adding a car (object of type Car) to the list of cars (in HashSet). It will be named AddSupportedCar(Car car). Below is the code of the class Part which is also designed as set of immutable fields (except that it accepts adding cars): Part.cs public class Part { private string name; private string code; private PartCategory category; private HashSet supportedCars; private decimal buyPrice; private decimal sellPrice; private Manufacturer manufacturer; public Part(string name, decimal buyPrice, decimal sellPrice, Manufacturer manufacturer, string code, PartCategory category) { this.name = name; this.buyPrice = buyPrice; this.sellPrice = sellPrice; this.manufacturer = manufacturer; this.code = code; this.category = category; this.supportedCars = new HashSet(); } public void AddSupportedCar(Car car) { this.supportedCars.Add(car); } public override string ToString() { StringBuilder result = new StringBuilder(); result.Append("Part: " + this.name + "\n"); result.Append("-code: " + this.code + "\n"); result.Append("-category: " + this.category + "\n"); result.Append("-buyPrice: " + this.buyPrice + "\n"); result.Append("-sellPrice: " + this.sellPrice + "\n"); result.Append("-manufacturer: " + this.manufacturer +"\n"); result.Append("---Supported cars---" + "\n"); foreach (Car car in this.supportedCars) { result.Append(car); result.Append("\n"); } result.Append("----------------------\n"); return result.ToString(); } } In the class Part we use HashSet so it is necessary to redefine the methods Equals(…) and GetHashCode() for the class Car: // The Equals(…) and GetHashCode() methods for the class Car public override bool Equals(object obj) { Car otherCar = obj as Car; if (otherCar == null) { return false; } bool equals = object.Equals(this.brand, otherCar.brand) && object.Equals(this.model, otherCar.model) && object.Equals(this.productionYear,otherCar.productionYear); return equals; } public override int GetHashCode() { const int prime = 31; int result = 1; result = prime * result + ((this.brand == null) ? 0 : this.brand.GetHashCode()); result = prime * result + ((this.model == null) ? 0 : this.model.GetHashCode()); result = prime * result + this.productionYear; return result; } Testing the Class Part We test the class Part. It is a bit more complicated than when testing the classes Car and Manufacturer, because Part it is more complex class. We can create a part, assign all its properties and print it: Manufacturer bmw = new Manufacturer("BWM", "Germany", "Bavaria", "665544", "876666"); Part partEngineOil = new Part("BMW Engine Oil", 633.17m, 670.0m, bmw, "Oil431", PartCategory.Engine); Car bmw316i = new Car("BMW", "316i", 1994); partEngineOil.AddSupportedCar(bmw316i); Car mazdaMX5 = new Car("Mazda", "MX5", 1999); partEngineOil.AddSupportedCar(mazdaMX5); Console.WriteLine(partEngineOil); Seems like the result is correct: Part: BMW Engine Oil -code: Oil431 -category: Engine -buyPrice: 633.17 -sellPrice: 670.0 -manufacturer: BWM ---Supported cars--- ---------------------- Before we can continue with the next class, we could test for duplicated cars in the set of supported cars for certain part. Duplicates are not allowed by design and we should check whether this is enforced: Manufacturer bmw = new Manufacturer("BWM", "Germany", "Bavaria", "665544", "876666"); Part partEngineOil = new Part("BMW Engine Oil", 633.17m, 670.0m, bmw, "Oil431", PartCategory.Engine); partEngineOil.AddSupportedCar(new Car("BMW", "316i", 1994)); partEngineOil.AddSupportedCar(new Car("BMW", "X5", 2006)); partEngineOil.AddSupportedCar(new Car("BMW", "X5", 2007)); partEngineOil.AddSupportedCar(new Car("BMW", "X5", 2006)); partEngineOil.AddSupportedCar(new Car("BMW", "316i", 1994)); Console.WriteLine(partEngineOil); The result is correct. The duplicated cars are taken into account only once: Part: BMW Engine Oil -code: Oil431 -category: Engine -buyPrice: 633.17 -sellPrice: 670.0 -manufacturer: BWM ---Supported cars--- ---------------------- Step 5: The Class Shop We already have all needed classes for creating the class Shop. It will have two fields: name and list of parts, which are for sale. The list will be List. We will add the method AddPart(Part part), with which we will add new parts. With a redefined ToString() we will print the name of the shop and the parts in it. Here is an example of implementation of our class Shop holding the catalog of auto parts (its name is immutable but it can add parts): Shop.cs public class Shop { private string name; private List parts; public Shop(string name) { this.name = name; this.parts = new List(); } public void AddPart(Part part) { this.parts.Add(part); } public override string ToString() { StringBuilder result = new StringBuilder(); result.Append("Shop: " + this.name + "\n\n"); foreach (Part part in this.parts) { result.Append(part); result.Append("\n"); } return result.ToString(); } } It might be a subject of discussion whether we should use List or Set for the parts in the car shop. The set data structure has an advantage that it avoids any duplicates. Thus if we have for example few tires of certain model, they will be found only once in the set. To use set we need to be sure the parts are uniquely identified by their code or by some other unique identifier. In our case we assume we could have parts with exactly the same code, name, etc. which come at different buy and sell prices (e.g. if the prices change over the time). So we need to allow duplicated parts and thus using a set will not be appropriate. Parts in the shop will be kept in List. We will test the class Shop though the especially written class TestShop. Step 6: The Class TestShop We created all classes we need. We have to create one more, with which we will have to demonstrate the usage of the rest of the classes. It will be named TestShop. In the Main() method we will create two manufacturers and a few cars. We will add them to two parts. We will add the parts to the Shop. At the end we will print everything on the console. TestShop.cs public class TestShop { static void Main() { Manufacturer bmw = new Manufacturer("BWM", "Germany", "Bavaria", "665544", "876666"); Manufacturer lada = new Manufacturer("Lada", "Russia", "Moscow", "653443", "893321"); Car bmw316i = new Car("BMW", "316i", 1994); Car ladaSamara = new Car("Lada", "Samara", 1987); Car mazdaMX5 = new Car("Mazda", "MX5", 1999); Car mercedesC500 = new Car("Mercedes", "C500", 2008); Car trabant = new Car("Trabant", "super", 1966); Car opelAstra = new Car("Opel", "Astra", 1997); Part cheapPart = new Part("Tires 165/50/R13", 302.36m, 345.58m, lada, "T332", PartCategory.Tires); cheapPart.AddSupportedCar(ladaSamara); cheapPart.AddSupportedCar(trabant); Part expensivePart = new Part("Universal Car Engine", 6733.17m, 6800.0m, bmw, "EU33", PartCategory.Engine); expensivePart.AddSupportedCar(bmw316i); expensivePart.AddSupportedCar(mazdaMX5); expensivePart.AddSupportedCar(mercedesC500); expensivePart.AddSupportedCar(opelAstra); Shop newShop = new Shop("Tuning Pro Shop"); newShop.AddPart(cheapPart); newShop.AddPart(expensivePart); Console.WriteLine(newShop); } } This is the result of the execution of the above code: Shop: Tuning Pro Shop Part: Tires 165/50/R13 -code: T332 -category: Tires -buyPrice: 302.36 -sellPrice: 345.58 -manufacturer: Lada ---Supported cars--- ---------------------- Part: Universal Car Engine -code: EU33 -category: Engine -buyPrice: 6733.17 -sellPrice: 6800.0 -manufacturer: BWM ---Supported cars--- ---------------------- Testing the Solution At the end we need to test our code. In fact we have done this in the class TestShop. This doesn’t mean that we have tested entirely our problem. We have to check the border cases, for example when some of the lists are empty. Let’s make a little change of the code in Main() method, to start the program with an empty list: static void Main() { Shop emptyShop = new Shop("Empty Shop"); Console.WriteLine(emptyShop); Manufacturer lada = new Manufacturer("Lada", "Russia", "Moscow", "653443", "893321"); Part tires = new Part("Tires 165/50/R13", 302.36m, 345.58m, lada, "T332", PartCategory.Tires); Manufacturer bmw = new Manufacturer("BWM", "Germany", "Bavaria", "665544", "876666"); Part engineOil = new Part("BMW Engine Oil", 633.17m, 670.0m, bmw, "Oil431", PartCategory.Engine); engineOil.AddSupportedCar(new Car("BMW", "316i", 1994)); Shop ultraTuningShop = new Shop("Ultra Tuning Shop"); ultraTuningShop.AddPart(tires); ultraTuningShop.AddPart(engineOil); Console.WriteLine(ultraTuningShop); } The result of this test is: Shop: Empty Shop Shop: Ultra Tuning Shop Part: Tires 165/50/R13 -code: T332 -category: Tires -buyPrice: 302.36 -sellPrice: 345.58 -manufacturer: Lada ---Supported cars--- ---------------------- Part: BMW Engine Oil -code: Oil431 -category: Engine -buyPrice: 633.17 -sellPrice: 670.0 -manufacturer: BWM ---Supported cars--- ---------------------- From the result it seems the first shop is empty and in the second shop the list of cars for the first part is empty. This is the correct output. Therefore our program works correctly with the border case of empty lists. We can continue testing with other border cases (e.g. missing part name, missing price, missing manufacturer, etc.), as well as with some kind of performance test (e.g. shop with 300,000 parts for 5,000 cars and 200 manufacturers). We will leave this for the readers. Exercises You are given an input file mails.txt, which contains names of users and their email addresses. Each line of the file looks like this: @. There is a requirement for email addresses – can be a sequence of Latin letters (a-z, A-Z) and underscore (_), is a sequence of lower Latin letters (a-z), and has a limit of 2 to 4 lower Latin letters (a-z). Following the guidelines for problem solving write a program, which finds the valid email addresses and writes them together with the names of the users (in the same format as in the input) to an output file valid-mails.txt. Sample input file (mails.txt): Steve Smith steven_smith@yahoo.com Peter Miller pm<5.gmail.com Svetlana Green svetlana_green@hotmail.com Mike Johnson mike*j@888.com Larry Cutts larry.cutts@gmail.com Angela Hurd angel&7@freemail.hut.fi Output file (valid-mails.txt): Steve Smith steven_smith@yahoo.com Svetlana Green svetlana_green@hotmail.com Larry Cutts larry.cutts@gmail.com You are given a labyrinth, which consists of N x N squares, and each of them can be passable (0) or not (x). In one of the squares our hero Jack (*) is positioned. Two squares are neighbors, if they have a common wall. At one step Jack can pass from one passable square to its neighboring passable square. Write a program, which prints the number of possible exits from given labyrinth. At the figure below we have 7 possible exits, reachable from the start position. x x x 0 x x 0 x 0 0 0 0 * 0 x 0 0 x x x x 0 x 0 0 0 0 0 x 0 x 0 x x 0 The input data is read from a text file named Labyrinth.in. At the first line in the file is the number N (2 < N < 1000). At the next N lines there are N characters, each either "0" or "x" or "*". The output is a single number and should be printed in the file Labyrinth.out. You are given a labyrinth, which consists of N x N squares, each of it can be passable or not. Passable cells consist of lower Latin letter between "a" and "z", and the non-passable – '#'. In one of the squares is Jack. It is marked with "*". Two squares are neighbors, if they have common wall. At one step Jack can pass from one passable square to its neighboring passable square. When Jack passes through passable squares, he writes down the letters from each square. At each exit he gets a word. Write a program, which from a given labyrinth prints the words, which Jack gets from all the possible exits. At the example below Jack can get 10 different words corresponding to its 10 possible paths he could find to some of the exits: a, az, aza, madk, madkm, madam, madamk, dir, did, difid. a # # k m # z # a d a # a * m # # # # d # # # # r i f i d # # d # d # t The input data is read from a text file named Labyrinth.in. At the first line in the file there is the number N (2 < N < 10). At each of the next N lines there are N characters, each of them is either Latin letter between "a" and "z" or "#" (impassable wall) or "*" (Jack). The output must be printed in the file Labyrinth.out. A company plans to create a system for managing of a sound recording company. The sound recording company has a name, address, owner and performers. Each performer has name, nickname and created albums. Albums are described with name, genre, year of creation, number of sold copies and list of songs. The songs are described with name and duration. Design a set of classes with relationships between each other, which models the data of the record company. Implement a test class, which demonstrates the work of rest of the classes. A company plans on creating of a system for managing a company for real estates. The company has name, owner, tax ID, employees and has a list of estates for sale. Employees are described with name, work position and experience. The company sells several types of estates: apartments, houses, undeveloped areas and shops. All of them are characterized with area, price of square meters and location. For some of them there is additional information. For the apartments there is data about the number of the floor, whether there is an elevator in the block, and if it is furnished. For the houses the data is – square meters for the undeveloped area and for the developed (yard), how many floors it has and whether it is furnished. Design a set of classes with relationships between them, which model the data for the company. Implement a test class, which demonstrates the work of the rest of the classes. Solutions and Guidelines The problem is similar to the first problem from our sample exam. Again we can read line by line the input file and with appropriate regular expression to check the email addresses. Test the solution carefully before you go to the next problem. Possible exits from the labyrinth are all the cells, which are positioned at the border of the labyrinth and are reachable from the initial cell. The problem could be solved using BFS with just little modification of the solution of the “Escape from Labyrinth”. Test your solution carefully! The problem is similar to the previous one, but all possible paths to the exit are required. You can do recursive search with backtracking (DFS) and keep in a StringBuilder the letters to the exit, to create the words, which you have to print. With bigger labyrinths the problem has no optimal solution (there is no way to print all the paths, without generating all of them, but they grow exponentially to the labyrinth size). Test carefully your solution and think of special cases that need special care. You must write the required classes: MusicCompany, Artist, Album, Song. Think of the links between classes and what data structures to use for them. For the printing redefine the method ToString() from System.Object. Test all methods and the border cases. The classes you must write are EstateCompany, Employee, Apartment, House, Shop and UndevelopedArea. Export all shared characteristics in separate abstract base class Estate. Encapsulate all fields with properties. Override the method ToString(), which to collect the data of the corresponding class and print it to the console. Test all methods and special border cases (like missing property values).