I wonder if it would be good to state the number of bits you should expect, in the challenge description? In practice my algorithm found them all anyway, but I was concerned that I'd have no way of detecting any errors in my algorithm, and getting the scanning right is really the hard part here.
Actually, the main reason I was worried was that I didn't realise it was PNG-format data - doh. I was also reading the data from the wrong end, which didn't make any sense read as 8-bit bytes, and half-convinced myself that it might be best visualised as an 88-pixel-wide monochrome image - all totally wrong!
Spiral Bits
I wrote an algorithm that basically started at a point and made small steps in a given angle. At each step I did some tests to see how close to each edge of the spiral i was, and adjusted my direction of travel accordingly.
The only tricky parts were handling when the two sides of the spiral would touch any my algorithm would get thrown off.
So eventually I had add editing tools, and would have my algorithm generate a basic shape, and I would go back and correct the algorithm at certain points and have it continue.
After I had the a definition of the spiral's shape, I had a second algorithm go drop points along the path everytime it thought a new bit had started. This was also error proned to missing the border between the bits. So I had to go back and manually add bits or remove duplicates.
The PNG format helped me to know when I got it correct given the CRC at the end
The only tricky parts were handling when the two sides of the spiral would touch any my algorithm would get thrown off.
So eventually I had add editing tools, and would have my algorithm generate a basic shape, and I would go back and correct the algorithm at certain points and have it continue.
After I had the a definition of the spiral's shape, I had a second algorithm go drop points along the path everytime it thought a new bit had started. This was also error proned to missing the border between the bits. So I had to go back and manually add bits or remove duplicates.
The PNG format helped me to know when I got it correct given the CRC at the end
I identified the local bright pixels (which are at least as bright as all their neighbours), then joined them together in clusters, including diagonal neighbours. I ignored individual points (and black points), and calculated neighbour relationships between clusters, marking clusters as neighbours if they're within 4 pixels of each other (euclidean distance). Then find the biggest cluster, and walk from there; at each stage, walk from the current blob to the next blob by just picking up all of its neighbours which haven't already been processed.
It went wrong where the line gets too close to the next line in, but I fixed that by editing spiral.png and drawing in some black to separate the spirals a bit more.
Cheating.
Overall it only takes a minute or two to run, and I was kind of happy with how well it worked out.
It went wrong where the line gets too close to the next line in, but I fixed that by editing spiral.png and drawing in some black to separate the spirals a bit more.
Cheating.Overall it only takes a minute or two to run, and I was kind of happy with how well it worked out.
Hehe, my first try was also reading from the wrong direction, so my first data was also nonsense.
My approach is to do some pre-processing in photoshop to simplify my classification code: Segmentation by simple thresholding so that I only got 4 distinct colors in the image: background, 1-bit, 0-bit and transitions. Then I created a mask from the background and expanded it to produce a nice narrow band of colors (still in photoshop). My first idea was to create a 1-pixel-wide 1D-chain of pixels, but this would involve some kind of distance-transform which I was too lazy to code up. So I ended up with a simple kind of flood-fill that records the bits as it encounters each pixel (i.e. new color).
Oh - and I also seperated the narrow part of the spiral using photoshop - who's cheating?
Afterall, the segmentation and classification worked remarkably well here. The "Say It"-challenge seems to be much harder...
My approach is to do some pre-processing in photoshop to simplify my classification code: Segmentation by simple thresholding so that I only got 4 distinct colors in the image: background, 1-bit, 0-bit and transitions. Then I created a mask from the background and expanded it to produce a nice narrow band of colors (still in photoshop). My first idea was to create a 1-pixel-wide 1D-chain of pixels, but this would involve some kind of distance-transform which I was too lazy to code up. So I ended up with a simple kind of flood-fill that records the bits as it encounters each pixel (i.e. new color).
Oh - and I also seperated the narrow part of the spiral using photoshop - who's cheating?
Afterall, the segmentation and classification worked remarkably well here. The "Say It"-challenge seems to be much harder...
My approach was to mark one border of the spiral in red, the other in green. I also had
to do some editing at the places, where the two spirals met.
After that, a second program followed each border, and calculated the mid line, thereby
examining the bits.
BTW: I've started in the center, but also wasn't sure about the correct order. I assumed,
the spiral starts at the center, because:
* it's the way music records and CDs work.
* the spiral has been constructed starting at the center.
As I was unsure I've written several different files from the spiral bits.
to do some editing at the places, where the two spirals met.
After that, a second program followed each border, and calculated the mid line, thereby
examining the bits.
BTW: I've started in the center, but also wasn't sure about the correct order. I assumed,
the spiral starts at the center, because:
* it's the way music records and CDs work.
* the spiral has been constructed starting at the center.
As I was unsure I've written several different files from the spiral bits.
-
Allosentient
- Posts: 273
- Joined: Thu Apr 10, 2008 9:47 pm
I don't remember exactly what I did in great detail, but it involved a lot of spaghetti code since I needed to finish it fast. When I looked at it a second time I realized that a lot of the code I wrote was a big waste and could have been done in half the number of lines.
The first thing I did was change the image's colors to only include 8 possible color values, and then used each color value as a special category of space.
I used a filler to fill the number of pixels and count the number of pixels within a border, then used a debug breakpoint if that number deviated from the normal. I used angular paths to search for the next "fill area" based on the straight line that occurred between the last two points. After a lot of tweaking and debugging I got the answer with 0 errors and 0 manual edits of the image, though it was a pain.
The first thing I did was change the image's colors to only include 8 possible color values, and then used each color value as a special category of space.
I used a filler to fill the number of pixels and count the number of pixels within a border, then used a debug breakpoint if that number deviated from the normal. I used angular paths to search for the next "fill area" based on the straight line that occurred between the last two points. After a lot of tweaking and debugging I got the answer with 0 errors and 0 manual edits of the image, though it was a pain.
tog wrote:How did you do that? I guess not by hand?Mütze wrote:My approach was to mark one border of the spiral in red, the other in green.
No, I didn't do it by hand (except in the two places, where the spiral meets the next round).
For those places, I've used gimp.
I've picked a starting point in the center for the red line manually. I also chose an initial
direction. A program then did the following:
1. If the pixel in front (as defined by the current direction) of the current pixel is not black,
rotate the direction counterclockwise by 45 or 90 degrees.
2. If the pixel in front is black and the pixel to the right from it (also defined by the current
direction) is also black, try to rotate the direction clockwise by 45 or 90 degrees.
3. The pixel in front of the current pixel now should be black, and the pixel right from that
black pixel should not be black: If thats the case, paint the pixel in front red, set that pixel
as the current pixel and continue with 1.
This stopped at the places, where the spiral meets (as I haven't allowed turns of more than
90 degrees). I've selected some new starting pixels there. At the end of the spiral, (also a
manually chosen pixel), I switched the color to green.
mine can solve it ALMOST entirly automated, first it did the masking for black, green, or white, with anything too far from the "optimal green" defaulting to black... then i wrote my own form of flood fill that returned how much was filled and (using for example red) found orphan areas that were 1-3 pixles.(made them black, fyi dont floodfill in c# using recursion on a large area, stack overflow) THEN i took the image from the end of the spiral (i didnt know the order or the polarity of the colors, i just built 4 answer strings and spit out all 4 files) got the color, assembled the 4 possible strings, flood filled black, searched for next nearest non black, repeat
the problem was i got 8359 bits from this, to debug i spit out the result, saw one bit was indeed ignored... somehow the distance finder saw the very point of the crescent as closer to it, skiping the right bit, i had to manually edit the pixles a bit to make it work correctly... (mayby i needed to make my isgreen mask a tad less greedy)
from a challenge writers point of view, it would be easyer to spit out the string from the center first and spiral outward, but whoever did the adobe spiral wavey affect and saved it in jpeg before converting to png...grrr...hehehe. 3/4 of my time went into trying different ways to get a single point from constantly changing but similiar shapes
the problem was i got 8359 bits from this, to debug i spit out the result, saw one bit was indeed ignored... somehow the distance finder saw the very point of the crescent as closer to it, skiping the right bit, i had to manually edit the pixles a bit to make it work correctly... (mayby i needed to make my isgreen mask a tad less greedy)
from a challenge writers point of view, it would be easyer to spit out the string from the center first and spiral outward, but whoever did the adobe spiral wavey affect and saved it in jpeg before converting to png...grrr...hehehe. 3/4 of my time went into trying different ways to get a single point from constantly changing but similiar shapes
-
MyNameIsAlreadyTaken
- Posts: 31
- Joined: Sun Oct 17, 2010 10:21 am
- Location: Germany
This was the definitely _worst_ challenge of them all. Since I had absolutely no idea on how to write a program to read the values for me, I did everything by hand.
And since I didn't take care enough in the first run [2 bits were wrong, 7 missing], I had to do it all over again and compare my new values with the old ones.
I'm happy this challenge wasn't named "Spiral Bits Warmup".
And since I didn't take care enough in the first run [2 bits were wrong, 7 missing], I had to do it all over again and compare my new values with the old ones.
I'm happy this challenge wasn't named "Spiral Bits Warmup".
