KöMaL Problems in Informatics, March 2009
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on April 15, 2009.
I. 208. Prepare a selection of poems in XML format from the works of at least two poets. For each poet, your properly formatted document should contain at least two poems with several verses. You should use the following tags: selection, poet, poetname, birthdate, birthplace, poem, poemtitle, verse, line, poemyear.
Your selection will be displayed in a browser. In order to enhance its format, you should create a CSS style sheet so that the document has a clear structure. (As a guideline, see the example -- however, you do not necessarily have to produce such format.)
Several poems can be found online at http://mek.oszk.hu/.
You should submit the document containing the selection of poems (i208.xml) together with its style sheet (i208.css).
I. 209. By using a spreadsheet application, prepare a version of the game MasterMind. (See, for example, http://en.wikipedia.org/wiki/Mastermind_(board_game), or http://egyszervolt.hu/jatek/mastermind.html where you can also play the game.) In our example, ``Rejtett'' means ``hidden'', ``Tippek'' is ``guesses'', ``Helyén van'' is ``in the correct place'', while ``Szerepel'' means ``present but out of place''.
Your solution should be similar to our example. Instead of colours, you should use the first 6 letters of the English alphabet. The game is played by two players: the code maker places four secret letters in the first 4 cells of row 2. The other player, the code breaker makes several guesses beginning with row 4.
The result of a guess in a given row should be displayed in columns E and F. Column E should contain the number of letters of the current guess that are in the correct place compared to the 4 secret letters, while column F should give the number of cells of the guess that contain letters being present among the 4 secret letters but are out of place. If the guess exactly matches the secret letters, the background should be changed and bold characters should be used. At the beginning of the game, 20 free rows should be reserved for the guesses.
For the enjoyable play, you should make sure that content of cells A2:D2 (if it is a valid code of 4 letters) should remain invisible. (For example, you can use the same text colour as background colour.) Moreover, evaluation in columns E and F should appear only after the code breaker has entered a syntactically correct guess of 4 letters.
The sheet (i209.xls, i209.ods, ...) together with a short documentation (i209.txt, i209.pdf, ...) should be submitted, also containing a brief description of your solution and the name and version number of the spreadsheet application.
I. 210. Linear search is a simple but slow algorithm to find the first occurrence of a given pattern in a text: the first character of the pattern is compared with successive characters of the text, that is, the pattern is shifted from the left to the right by 1 position until we find a complete match.
However, when the size of the alphabet is large compared to the length of the pattern, the following modification can speed up the algorithm considerably: the pattern is again shifted from left to right, but when a mismatch is found at a certain position, the pattern may be shifted to the right by more than one character, depending on the first character of the text following the pattern.
This is justified by observing that if the first character of the text just after the pattern is not contained in the pattern at all, then it is enough to continue pattern matching from the right neighbour of that character. If, on the other hand, the first character of the text just after the pattern is contained in the pattern, then the length of the right shift can be chosen to be the distance between these two occurrences.
In our examples, ``Szöveg'' is ``text'', ``minta'' is ``pattern'', ``különbség'' is ``mismatch'', while ``eltolás'' is ``shift''.
The execution can be made even faster, because the length of the shift can be computed in advance for each character of the text.
Write a program that determines the first occurrence of a pattern in a given text. The pattern (being at most 255 characters) is entered from the keyboard, while the text is found in a file specified as the command line argument. The sentence containing the first occurrence should be displayed on the screen. The beginning of this sentence is defined as the first non-space character following the nearest end of sentence punctuation mark (``.'', ``!'', ``?'' or beginning of the file) preceding the pattern, while the end of this sentence should be the first end of sentence punctuation mark or end-of-file mark succeeding the pattern. Upper and lowercase letters should be treated identically.
The source code of your program (i210.pas, i210.cpp, ...) and a short documentation (i210.txt, i210.pdf, ...) should be submitted, also describing your solution and specifying the name of the developer environment to use for compiling.
Problems with sign 'S'
Deadline expired on April 15, 2009.
S. 43. We are given a rectangular labyrinth. Its walls are unit squares and it has one entrance from which each square of the labyrinth can be reached. Corridors and walls are parallel with the outer walls, and it may be the case that there is more that one path between two given points.
We would like to illuminate each square of the labyrinth by placing lamps on the ceiling of the corridors. A lamp illuminates the complete horizontal or vertical corridor segments in which the lamp is located. Your task is to illuminate the complete labyrinth by using the minimal number of lamps.
In the example, ``Bemenet'' is ``input'', while ``Kimenet'' is ``output''.
The first command line argument of your program solving this problem is the name of the input text file containing the plan of the labyrinth, while the second command line argument is the name of the output text file that should contain the solution. The input file has at most 100 lines. Each line has the same number of consecutive 0s or 1s: 0 means corridor and 1 is wall. The structure of the output file should be similar, and the position of the lamps should be marked with X. The total number of lamps should also be displayed on the screen. When evaluating your solution, running time for various labyrinth sizes will be taken into account, and some points will be awarded for solutions with slightly more than optimal number of lamps.
The source code of your program (s43.pas, s43.cpp, ...) and a short documentation (s43.txt, s43.pdf, ...) should be submitted, also describing your solution and specifying the name of the developer environment to use for compiling.
Upload your solutions above