Permanent Programming #6

Put your programming skills to the test in these challenges.

Permanent Programming #6

Post by MrRubix on Thu Jun 26, 2008 11:48 pm
([msg=5896]see Permanent Programming #6[/msg])

I'm shocked that there isn't a topic for this one out here already, haha.

This mission's a killer! I'm doing this one in Python even though I could probably do it much more easily in C#. It correctly extracts all the letters and so far correctly identifies A's and F's... so I'm getting there :P

I don't know what to think anymore as to which is harder between this challenge and #3. Both are pretty tough.


Anyways, some advice:

1. Note that the center of the black "hole" in the middle is not necessarily the center of the entire spiral if you plan on going for the "rotate and extract" approach.
2. Ensure that you aren't totally mangling your image quality. Being able to keep things in two main colors (black and the 128G green) is useful.
3. The more you crop, the easier things will likely be as a result of having to account for fewer exceptions. You'll see what I mean when you get there.
4. Also note that the method of creating the spiral IS in the source, if you'd rather avoid capturing the image directly.
5. Taking a screenshot of the entire screen and then cropping the crap out of things from there is a good way to go.
6. The tighter your OCR scan regions are, the better. It's not only faster to execute (albeit likely negligible), but it's really annoying to assume "Hey, if this section of the letter has green, it must be an F" only to find that there are a few other letters that happen to have a few green pixels creep into your scan regions. If you can identify a letter with tighter scanning regions, you'll encounter far fewer overlaps between letters. Also, if you've cropped things well, this is an easier step to perform.
MrRubix
New User
New User
 
Posts: 17
Joined: Sun Jun 15, 2008 5:15 pm
Blog: View Blog (0)


Re: Permanent Programming #6

Post by MrRubix on Wed Jul 09, 2008 2:39 am
([msg=6929]see Re: Permanent Programming #6[/msg])

FINALLY got this beast of a program to work! That took me ages! This is, in my opinion, the hardest challenge on this entire site. I did it entirely in Python, and used only the picture to derive the answer (which is, really, what you'd expect to find in reality. You don't always have the image generation data at hand like you do in this mission).

If I had to give one piece of further advice, it would be to ensure that your early-program stages work 100% before venturing onward. That is, don't begin reading characters until you've got the spiral where you want it. Don't begin analyzing 10 characters if you don't know if you can analyze 3. Make sure each subcomponent works as you go and you'll fare better. In other words, work smarter, not harder :P Definitely a test of my patience, but I suppose lesson learned.

My first approach to this problem took me over a week, and I never got very far with it -- only made it down to about 8 errors on average. My rotators/croppers were shoddy and I never bothered to ensure they worked as consistently as they needed to.

So, I scrapped it and started again today. Literally -- when I got back from work, I started all over. I made sure each piece worked correctly before moving on to the next. At the end of it all, it worked :)
MrRubix
New User
New User
 
Posts: 17
Joined: Sun Jun 15, 2008 5:15 pm
Blog: View Blog (0)


Re: Permanent Programming #6

Post by dwmead03 on Tue Mar 24, 2009 9:08 pm
([msg=20487]see Re: Permanent Programming #6[/msg])

I believe MrRubix was correct in saying this is the hardest mission on the entire site! I am very curious as to how the one's who have solved have solved it as well as the number of people that have solved it. Just writing a program to find the center of the spiral and rotate to grab each letter in 30 seconds is a programming challenge in itself! Not to mention the actual OCR!

I have a few generalized questions about this mission because I trying multiple ways to solve this one. Currently, I think the way I'm going is to screen shot the image and find center point and rotate and extract. I am using C# and using the GDI to draw the bitmap to the form, rotating, then using the copy from screen method of the graphics class. The rotation seems to distort the characters quite a bit, again increasing the difficulty of this mission. Not to mention the fact that the actual characters aren't being drawn identically every time.

I was also wondering if most people wrote their own OCR or used an API or SDK of an already developed OCR. If so, which ones? Also, did you somehow solve this mission by figuring what character is being drawn by sorting the array of data in the source? I mostly concerned about the general methods that different people successfully completed this mission with.
User avatar
dwmead03
New User
New User
 
Posts: 30
Joined: Mon Apr 14, 2008 11:34 pm
Location: KY
Blog: View Blog (0)


Re: Permanent Programming #6

Post by acskurucz on Thu Mar 26, 2009 6:08 pm
([msg=20626]see Re: Permanent Programming #6[/msg])

dwmead03,
i didn't do anything with the "picture". You can do it just by analysing the html. You can write an ocr, but i think that is slower, but if you can do... try it!
acskurucz
New User
New User
 
Posts: 29
Joined: Wed Jan 14, 2009 8:31 am
Blog: View Blog (0)


Re: Permanent Programming #6

Post by Defience on Fri Mar 27, 2009 8:58 am
([msg=20684]see Re: Permanent Programming #6[/msg])

dwmead03 wrote:I believe MrRubix was correct in saying this is the hardest mission on the entire site! I am very curious as to how the one's who have solved have solved it as well as the number of people that have solved it. Just writing a program to find the center of the spiral and rotate to grab each letter in 30 seconds is a programming challenge in itself! Not to mention the actual OCR!

I have a few generalized questions about this mission because I trying multiple ways to solve this one. Currently, I think the way I'm going is to screen shot the image and find center point and rotate and extract. I am using C# and using the GDI to draw the bitmap to the form, rotating, then using the copy from screen method of the graphics class. The rotation seems to distort the characters quite a bit, again increasing the difficulty of this mission. Not to mention the fact that the actual characters aren't being drawn identically every time.

I was also wondering if most people wrote their own OCR or used an API or SDK of an already developed OCR. If so, which ones? Also, did you somehow solve this mission by figuring what character is being drawn by sorting the array of data in the source? I mostly concerned about the general methods that different people successfully completed this mission with.


I initially tried using Python's OCR (pytesser) but it won't work for this. In some initial testing, I had the screen shot down and cropped just the first row or chars to test with it and that worked well. I assumed it would work for the whole thing so I wrote out my program to crop each row (actually just one crop & rotated the image into it) and then to sort the chars from each of the 36 rows and submit them in order. In theory this worked but pytesser won't read ALL of the chars accurately. As far as the screen shot goes, if you do not have exact center of the spiral then when it rotates, the characters will distort. This also makes it difficult to try the 'counting pixels' method, which fails, although Nines found a way to do it like that. Keep in mind that the center of the page is not the center of the spiral. Also, with the screen shot if you plan on cropping each character as MrRubix did, the have to be exact so a neighboring pixel doesn't interfere.
I ended up having to use the data from the source as acskurucz did and figure out which numbers made lines and which ones made arcs and how they relate to each other. So.... you can screen shot, crop and rotate and write your own OCR, try counting pixels (some chars will have the same amounts so you'll have to find away around this) or figure out the math portion of the data. Good luck, and I agree that it's the hardest :shock:
User avatar
Defience
Addict
Addict
 
Posts: 1265
Joined: Thu Jun 12, 2008 3:16 pm
Blog: View Blog (0)


Re: Permanent Programming #6

Post by acskurucz on Fri Mar 27, 2009 9:25 am
([msg=20685]see Re: Permanent Programming #6[/msg])

Yes, it is the hardest. And anyway i tried rotate,crop,pytesser too with no luck, and it was slower, but there are some OCR methods u can use for it successfully, but the rotates take too much time.
Last edited by acskurucz on Fri Apr 03, 2009 11:38 am, edited 1 time in total.
acskurucz
New User
New User
 
Posts: 29
Joined: Wed Jan 14, 2009 8:31 am
Blog: View Blog (0)


Re: Permanent Programming #6

Post by Chaosmaster on Fri Apr 03, 2009 9:11 am
([msg=21100]see Re: Permanent Programming #6[/msg])

I wonder if anyone managed to to this with php,
I am using the OCR approach, everything is working fine (even though it doesn't always get each and every character correctly).
as acskurucz said I have one major problem, it takes too long to rotate the image.
I only rotate the image 8 times, but it takes at least 10 seconds for each rotation, this way I'm never gonna get done in 30 seconds.
If someone has an idea, please spill it out.
Chaosmaster
New User
New User
 
Posts: 4
Joined: Wed Feb 25, 2009 3:58 am
Blog: View Blog (0)


Re: Permanent Programming #6

Post by dwmead03 on Fri Apr 03, 2009 10:59 pm
([msg=21136]see Re: Permanent Programming #6[/msg])

Chaosmaster wrote:I wonder if anyone managed to to this with php,
I am using the OCR approach, everything is working fine (even though it doesn't always get each and every character correctly).
as acskurucz said I have one major problem, it takes too long to rotate the image.
I only rotate the image 8 times, but it takes at least 10 seconds for each rotation, this way I'm never gonna get done in 30 seconds.
If someone has an idea, please spill it out.


Use a different language? I'm using C# and it's definitely faster than that. Can it make 36 revolutions in the time limit? I believe so.
User avatar
dwmead03
New User
New User
 
Posts: 30
Joined: Mon Apr 14, 2008 11:34 pm
Location: KY
Blog: View Blog (0)


Re: Permanent Programming #6

Post by Chaosmaster on Sun Apr 05, 2009 7:59 am
([msg=21176]see Re: Permanent Programming #6[/msg])

I wan't asking it it was possible in another language, I was asking if there's a way to speed it up in php.
Why would you need 36 rotations anyway? I only need 8, but it still takes too long.
Chaosmaster
New User
New User
 
Posts: 4
Joined: Wed Feb 25, 2009 3:58 am
Blog: View Blog (0)


Re: Permanent Programming #6

Post by Nines on Sun Apr 05, 2009 9:09 am
([msg=21179]see Re: Permanent Programming #6[/msg])

Just for the record I did this in Python, using OCR and rotating the image 35 times. It rotates, crops characters, analyses and gives me the answer in about 3 seconds.
User avatar
Nines
Poster
Poster
 
Posts: 191
Joined: Sun Apr 13, 2008 5:57 pm
Blog: View Blog (0)


Next

Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests