NIO 2003 Exercise 3 - Printable Version +- Qbasicnews.com (http://qbasicnews.com/newforum) +-- Forum: QbasicNews.Com (http://qbasicnews.com/newforum/forum-3.html) +--- Forum: Challenges (http://qbasicnews.com/newforum/forum-10.html) +--- Thread: NIO 2003 Exercise 3 (/thread-4699.html) |
NIO 2003 Exercise 3 - Neo - 09-17-2004 Note: these examples are from the Dutch Informatics Olympiad, on very high level. I post them here because moneo finally found out that every challenge here is about games. Now, here come some very straightforward problems... Exercise 3. Recognising Letters. In this exercise you'll make a start with recognising letters. To limit us a bit with it, we'll only work with capital letters. These letters are shaped as a series of black boxes on a field of 8 by 7 squares. The patterns to compare these "characters" with must also been seen as a series of black boxes. Such a field of 8 by 7 boxes can also be displayed with 7 numbers. Every number indicates which boxes in that column are coloured. Every row of the field has a number and the numbers of the black boxes summed up return the total number of that column. The seven column numbers indicate how the character looks like. The rows are designated 128, 64, 32, 16, 8, 4, 2 and 1 from top to bottom. Here is an example of the capital letter A. The numbers on the bottom are the column numbers, unique to the character. Code: ...#... <row 128 File: There is a file patroon.dat (patroon is dutch for pattern) available with a description of all these patterns. The file has the same structure as all input files: The first line contains a number N, which indicates that there are N patterns in the file (in patroon.dat this obviously is 26). Then follow N lines with each 7 numbers k, with 0 <= k <= 255. On every line the column numbers of ONE pattern are displayed. The contents of the file patroon.dat is as follows: Code: 26 When in the exercises a pattern fits just as good with two or more letters, you choose for the letter which occurs most in the English language. The file vaakst.dat contains a line of text that exists of all 26 capital letters, ordered by occurance in the the English language, starting at the letter with the highest occurance. This is the contents of the vaakst.dat file: Code: ENATRDOISLGHVMKUWPCBZYFJXQ Input Your program will receive as input a file TEKST.IN (dutch for text), which has the same structure as the file patroon.dat. On the first line there is a number N, with 1 <= N <= 75. Next there are N lines of each 7 numbers, these seven numbers indicate a pattern that your program tries to recognise as a letter. Example: File tekst0.in Code: 3 Example files and testing There are files tekst0.in, tekst1.in up to and including tekst5.in available which you can test your program with. Overview Code: Subpart Program Output Timelimit Number of tests Points per test Total Exercise 3A: Draw the input as a picture Write a program nio3a that receives a file tekst.in as input. The program has to print to file 3a.out the patterns from the input file by means of points (.) and X's. The letters will be printed one after another, always followed by a blank line. Output with the give example (tekst0.in): Code: XXXXXXX Exercise 3B: Count the similarities Write a program nio3b that gets its input from a file tekst.in. The program will give as output a file 3b.out that contains ONE line of N capital letters. The text in the output file is the interpretation of the input patterns by means of the following algorithm. You compare every inputted pattern with the 26 character patterns from pattern.dat. For every letter you count the amount of boxes that are the same both in the character as in the pattern. With an ideal similarity this amount will be 56 (7x8). Your program chooses as interpretation for the pattern the letter with the highest number of equal boxes, in case these are more letters the letter first called in the file vaakst.dat is taken. Example output with the tekst0.in: Code: TAI Some problems When you compare a pattern with a standardized character using the above algorithm, of course things can go wrong. Two examples: - Letter thickness: Maybe the one whose letters are to be recognised makes his letters less or more bold. - Letter size: Maybe the letters to be recognised don't fill the entire area of 7x8 squares. Intermediate Patterns To avoid the problem of letter size we will limit us to the smallest rectangle which contains all black squares. In the input files for the exercises the letters will contain at least one black square. To also avoid letter thickness, we have to look at color-intermediates. A way to do this is as follows: 1. Write the pattern by means of W and B (white and Black), for example the 2nd letter from tekst0.in: Code: BBBBB Code: B This process can be repeated for the columns, from top to bottom. The number of lines that remain of the rows we call rowlines, and the number of lines that remain of the columns we call columnlines. Here is an application to the A from pattern.dat (pattern b) and a smaller a-pattern (pattern p). Code: ...X... Code: .X. Exercise 3C: Detemining Intermediate Patterns Write a program nio3c that gets its input from a file tekst.in and writes its output to a file 3c.out. The output consists of the intermediate patterns of the inputted patterns. In the example beneath is the output format. Note that in the format the rows come before the columns and that each is started by a number indicating the number of lines. After each pattern there is a blank line. Output with the example input (tekst0.in): Code: Pattern 1: Comparing by means of intermediate patterns To determine the amount of similarities between two intermediate patterns, you'll go as follows. Both for the rows as for the columns you go look for the longest series of lines that occur in both intermediate patterns, in the same order. In above example these are the 3 lines of the rows and all lines of the columns of the second pattern. The number of common rowlines Rg and the number of common Cg you use in the next formula, that is a measurement of the amount of equality between two patterns: O(b, p) = Rg / Rp + Rg / Rb + Cg / Cp + Cg / Cb In the example the amount of equality is: 3/4+3/5+3/3+3/5 = 59/20 = 2.95 Obviously, you now choose as interpretation of a pattern the letter for which this number is as high as possible. Exercise 3D: Comparing with Intermediate Patterns Write a program nio3d that gets its input from a file tekst.in. The program outputs a file 3d.out that contains ONE line of N capital letters. The text in the output file is the interpretation of the inputted patterns, according to above algorithm based upon the amount of equality of two patterns. Output with the given example (tekst0.in): Code: TEL If you're able to complete these exercises, you're on your way to understand a bit about OCR... About me, I got for 3A 16 points, for 3B 20 points, for 3C 24 points and for 3D 0 (!) points, for a total of 60 out of 100, which I got 3rd place with, as you can see here. The reason for me to get 0 points at exercise 3D was that I had little time left to finish it completely: During the competition, you had about 1 hour and 15 minutes for all these 4 small exercises! Have fun I'd say! (I already made them last year :king NIO 2003 Exercise 3 - oracle - 09-18-2004 Aah, a *real* challenge . Thus, you'll probably get no entries What language did you write it in? NIO 2003 Exercise 3 - whitetiger0990 - 09-18-2004 Unless I totally misunderstood it then I should have one done by tommorow (in qbasic) NIO 2003 Exercise 3 - na_th_an - 09-19-2004 Aw - this is the kind of problems I had on my exams... Too many bad memories NIO 2003 Exercise 3 - Neo - 09-19-2004 Quote:Aah, a *real* challenge . Thus, you'll probably get no entries... :roll: A *real* challenge -> no entries Do you imply that no one here can make it? lol I wrote it in QB of course ... Quote:Unless I totally misunderstood it then I should have one done by tommorow (in qbasic)No, I just mentioned that I only had 1.25 hours to make it. You can have all the time you want Quote:Aw - this is the kind of problems I had on my exams... Too many bad memoriesThen you can finally overcome the memories by entering some code So... it may be a *real* challenge, but I didn't sit here 2 hours translating the problem from dutch to english for nothing... So... moneo, it won't take any time (at max about 2 hours or so!). So... nathan, oracle, white, try to write some So... the rest, where are you? NIO 2003 Exercise 3 - whitetiger0990 - 09-19-2004 Quote:No, I just mentioned that I only had 1.25 hours to make it. You can have all the time you want Ok. I shall work on it in my spare time. NIO 2003 Exercise 3 - potato - 09-19-2004 I stopped reading when I saw the word TEKST. What an eyeful! NIO 2003 Exercise 3 - na_th_an - 09-19-2004 I almost finished college and... NO MORE EXAM PROBLEMS Real life problems are far more easy than exam problems NIO 2003 Exercise 3 - TheBigBasicQ - 09-19-2004 Quote:Real life problems are far more easy than exam problems I beg to differ. Real life problems can be exponentially tough than exam problems. Neo: quite a cool challenge there. I wanted to enter. But unfortunately I have exams now... :???: NIO 2003 Exercise 3 - oracle - 09-20-2004 Okay, I'll take up the challenge, though I might just write it in java to annoy you I've only got free time on Tuesday (which might not be free time, I have to code an airport simulation in java for COMP then), and on Friday. So we'll see what I've done around then |