Spiral Bits
-
MyNameIsAlreadyTaken
- Posts: 31
- Joined: Sun Oct 17, 2010 10:21 am
- Location: Germany
"Spiral Bits" was a hard challenge for me, too. Finally, I solved it by converting the png image into an xpm image which was easier to handle. Nowadays, I would use some appropriate library or module to access the png image data. There are a number around.
Actually, I would not call "Spiral Bits" a warmup challenge. However, there might be some bigger spiral stuff here and there ...
Actually, I would not call "Spiral Bits" a warmup challenge. However, there might be some bigger spiral stuff here and there ...
There is at least one very similar challenge... even though you can't reuse your code for this one.
BTW: I did the same as MyNameIsAlreadyTaken. The manual approach was working faster for me than trying to develop an algorithm. I had to do it also twice, but after that I was lucky: I guessed the right colors for 0 and 1 and "accidentally
" started from the middle.
BTW: I did the same as MyNameIsAlreadyTaken. The manual approach was working faster for me than trying to develop an algorithm. I had to do it also twice, but after that I was lucky: I guessed the right colors for 0 and 1 and "accidentally
" started from the middle.-
MyNameIsAlreadyTaken
- Posts: 31
- Joined: Sun Oct 17, 2010 10:21 am
- Location: Germany
I don't think it's fair to complain that the challenge is too tedious to solve by hand - the whole point is to write a program. Having to do it a second time is exactly the reason you should always automate tedious tasks anyway, even if you don't expect to need to repeat the job.
But having said that, I've solved 323 levels of Mortal Coil by hand so far. I really should finish automating it.
But having said that, I've solved 323 levels of Mortal Coil by hand so far. I really should finish automating it.
-
harvestsnow
- Posts: 8
- Joined: Mon Nov 21, 2011 9:15 pm
Well, that was a nice challenge! Interesting combination of data analysis and programming ideas. In the end I certainly spent more time on it than if I had done it manually, but that's not really the point.
I used a simple approach. First repaint the image in three colors. I decided that a pixel was "black" if the sum of the absolute differences for each component between that pixel and [35,182,153] was less that 30. Same thing for "white", using [255,255,255]. Everything else is null.
I also dropped the areas of less than 4 contiguous pixels. With this rule, each bit is represented by exactly one bloc of diagonally contiguous pixels, and no areas are in contact.
Then I explored the image, starting with the central bit, each time erasing the bloc and searching for its nearest neighbour (search at distance 1 for each pixel of the blocs, then distance 2, etc). It seems to be very close to tog's method.
I had no problem with the touching cycles of the spiral, I suppose this was pure luck.
And actually this wasn't so simple, because first I only kept areas of identical pixel values, which turned out not to be always contiguous, so I spent an indecent amount of time manually "debugging" the image and deciding for each 2- or 3-pixel value wether it was or wasn't a separate bit, and the process yielded 8367 bits, and I wrote a python brute-forcer to decide which bits should be dropped based on zlib's error, and this was incredibly dirty and didn't work. But I got enough of the file to see that there were three K's and an L in the word and guessed it, and there was much rejoicing. Then I took a few minutes, reworked my code, and got the full image.
Thanks to whoever did this. I won't post my code, since it's not very beautiful and I understand it might spoil other challenges. Let me know if I already said too much.
I used a simple approach. First repaint the image in three colors. I decided that a pixel was "black" if the sum of the absolute differences for each component between that pixel and [35,182,153] was less that 30. Same thing for "white", using [255,255,255]. Everything else is null.
I also dropped the areas of less than 4 contiguous pixels. With this rule, each bit is represented by exactly one bloc of diagonally contiguous pixels, and no areas are in contact.
Then I explored the image, starting with the central bit, each time erasing the bloc and searching for its nearest neighbour (search at distance 1 for each pixel of the blocs, then distance 2, etc). It seems to be very close to tog's method.
I had no problem with the touching cycles of the spiral, I suppose this was pure luck.
And actually this wasn't so simple, because first I only kept areas of identical pixel values, which turned out not to be always contiguous, so I spent an indecent amount of time manually "debugging" the image and deciding for each 2- or 3-pixel value wether it was or wasn't a separate bit, and the process yielded 8367 bits, and I wrote a python brute-forcer to decide which bits should be dropped based on zlib's error, and this was incredibly dirty and didn't work. But I got enough of the file to see that there were three K's and an L in the word and guessed it, and there was much rejoicing. Then I took a few minutes, reworked my code, and got the full image.
Thanks to whoever did this. I won't post my code, since it's not very beautiful and I understand it might spoil other challenges. Let me know if I already said too much.
-
dangermouse
- Posts: 89
- Joined: Sun Jun 05, 2011 8:14 pm
- Location: deep space computing AG
- Contact:
I also spent more time on it, as I would have done it by hand, but I knew that I am too imprecise to get it working by hand.
I tried first to model the spiral as Archimedean spiral with a formula, but this did not work out, as I was not able to reproduce the fluctuations. Then, I focused on the encoding part. By hand I could decode part of the tEXt part, so I knew it was ASCII. Only later, when reading the forum, I realised what I was looking for.
I think, the best part of my Freepascal solver was the spiral following algorithm:
c_x := 510;
c_y := 511;
gamma := Pi/7 - 2*Pi/25; // current direction
registerStep(c_x, c_y, gamma);
r:=1/RESOLUTION;
for i:=1 to TO_BE_DECODED*RESOLUTION do
begin
findMaxAngle(c_x, c_y, gamma,1, maxangle1);
findMaxAngle(c_x, c_y, gamma,-1, maxangle2);
gamma := ((maxangle2+maxangle1) / 2);
c_x := c_x + r * cos(gamma);
c_y := c_y + r * sin(gamma);
registerStep(c_x, c_y, gamma);
end; // for
I modeled it as a robot with two sensors at 90 degrees in respect to the direction of movement. The sensors were like arms and lied in the black part of the picture. The robot slowly turned itself on the right, until the left sensor noticed the spiral and recorded the angle of touching the spiral.
It did the same for the right sensor, but it turned on the left. The average of the two angles was the direction to proceed.
The worst part was the bit decoding algorithm: I did not think of the clustering approach, I only took one pixel and tried to reduce colors with simple formulas.
This did not work out well, my solution had many mistakes (by nature I tend to create wrong
solutions and then I have to refine them). I spent a week tweaking parameters and got a solution
with the header somehow okay.
I then turned my Lazarus GUI into a complete editor, with a lens and a palette of tools to insert
bits, delete them, find them and flip them. I had markers for bits which were too close or too far of the average. I also added a feature to recompute subpath with slightly different entry angles, which did work out only to find where I already edited the bits.
I was for giving up, as for the header part it is easy to see some progress, but for the data part
it was very difficult to see progress. Until I found that GIMP was able to show partial results. I
saw the first 10 lines of the solution and this gave me new forces.
I estimated where the error could lie, and finally brought it to 14 lines, which was enough to guess
the solution
Thanks hacker.org for training me! If I will have to control a path following robot, I might choose
the algorithm above
I tried first to model the spiral as Archimedean spiral with a formula, but this did not work out, as I was not able to reproduce the fluctuations. Then, I focused on the encoding part. By hand I could decode part of the tEXt part, so I knew it was ASCII. Only later, when reading the forum, I realised what I was looking for.
I think, the best part of my Freepascal solver was the spiral following algorithm:
c_x := 510;
c_y := 511;
gamma := Pi/7 - 2*Pi/25; // current direction
registerStep(c_x, c_y, gamma);
r:=1/RESOLUTION;
for i:=1 to TO_BE_DECODED*RESOLUTION do
begin
findMaxAngle(c_x, c_y, gamma,1, maxangle1);
findMaxAngle(c_x, c_y, gamma,-1, maxangle2);
gamma := ((maxangle2+maxangle1) / 2);
c_x := c_x + r * cos(gamma);
c_y := c_y + r * sin(gamma);
registerStep(c_x, c_y, gamma);
end; // for
I modeled it as a robot with two sensors at 90 degrees in respect to the direction of movement. The sensors were like arms and lied in the black part of the picture. The robot slowly turned itself on the right, until the left sensor noticed the spiral and recorded the angle of touching the spiral.
It did the same for the right sensor, but it turned on the left. The average of the two angles was the direction to proceed.
The worst part was the bit decoding algorithm: I did not think of the clustering approach, I only took one pixel and tried to reduce colors with simple formulas.
This did not work out well, my solution had many mistakes (by nature I tend to create wrong
solutions and then I have to refine them). I spent a week tweaking parameters and got a solution
with the header somehow okay.
I then turned my Lazarus GUI into a complete editor, with a lens and a palette of tools to insert
bits, delete them, find them and flip them. I had markers for bits which were too close or too far of the average. I also added a feature to recompute subpath with slightly different entry angles, which did work out only to find where I already edited the bits.
I was for giving up, as for the header part it is easy to see some progress, but for the data part
it was very difficult to see progress. Until I found that GIMP was able to show partial results. I
saw the first 10 lines of the solution and this gave me new forces.
I estimated where the error could lie, and finally brought it to 14 lines, which was enough to guess
the solution
Thanks hacker.org for training me! If I will have to control a path following robot, I might choose
the algorithm above
yeah! finally! ... this was a tough one especially because i am not good in algorithms. what i did is:
- repaint the image in exactly three colors.
- writing a tool which replaced every spot in the image with a single pixel (algorithms involved: a filter, a custom flood-fill, and calculation of the center of a spot)
- collecting all single pixels (which had been reduced to 8360 with the method above), starting with one of the ends and walking the path by finding the closest pixel using point distance calculation.
the only thing that i did not on my own was repainting, because the image was too blurry. i used toyviewer (a good image manipulation software for osx) to separate the spots by contrast, reducing both images to two colors and merging them again.
- repaint the image in exactly three colors.
- writing a tool which replaced every spot in the image with a single pixel (algorithms involved: a filter, a custom flood-fill, and calculation of the center of a spot)
- collecting all single pixels (which had been reduced to 8360 with the method above), starting with one of the ends and walking the path by finding the closest pixel using point distance calculation.
the only thing that i did not on my own was repainting, because the image was too blurry. i used toyviewer (a good image manipulation software for osx) to separate the spots by contrast, reducing both images to two colors and merging them again.
-
contagious
- Posts: 35
- Joined: Tue May 12, 2009 6:08 pm
- Location: Greece
I really thought I wouldn't be able to solve something like that.
However, after trying to work it out step by step I found a good way to approach it.
It wasn't anything fancy, very similar to what some of you have done.
My approach consisted of:
* Using GIMP to identify RGB values.
* Process the map so that there are 3 kind of pixels and clear any isolated pixels.
* From a starting point, search for the nearest cluster of pixels and delete it. Repeat.
I was surprised how well this worked out. It nearly found every pixel.
In particular, my program found 8365 pixels. I knew that I had 5 extra bits because in the way my program worked (search in a very small area) the only thing that could happen is to count more bits. So I visually scanned the processed image for oddities. It was not that hard because you could
easily identify the malformed clusters.
Fun challenge overall!
However, after trying to work it out step by step I found a good way to approach it.
It wasn't anything fancy, very similar to what some of you have done.
My approach consisted of:
* Using GIMP to identify RGB values.
* Process the map so that there are 3 kind of pixels and clear any isolated pixels.
* From a starting point, search for the nearest cluster of pixels and delete it. Repeat.
I was surprised how well this worked out. It nearly found every pixel.
In particular, my program found 8365 pixels. I knew that I had 5 extra bits because in the way my program worked (search in a very small area) the only thing that could happen is to count more bits. So I visually scanned the processed image for oddities. It was not that hard because you could
easily identify the malformed clusters.
Fun challenge overall!
Last edited by contagious on Sun Sep 20, 2015 10:32 am, edited 6 times in total.
My math is weak, so I did this like a true graphics hacker. I actually think this was a relatively easy challenge -- I think messing around with huge numbers and complicated mathematics is way harder than simply doing some intuitive/basic checks on a bunch of pixels...
Took the main image, blew it up to twice the size (to increase error margins and make edge detection easier), tweaked it in photoshop: used replace and select color to make the green dots pure red and the white ones pure green. Then I did some further filter tweaks to sharpen and darken the edges.
The detection 'algorithm' is pretty simple. It uses the direction taken from the previous dot it found, then compares several circle-shaped areas (excluding the previously marked content) to check how 'green' or 'red' they are and where the edge is likely to be. Then it picks the best candidate and so forth. Required a bit of tweaking, and my PHP (don't laugh) solution took minutes to do the whole thing, but it worked after some tweaking sessions.
The final version got the whole thing without needing any manual checks or fixes.
Here's the detection result, if anyone's interested:
http://www.tabun.nl/tmp/spiral_bits_out.png
Colorized for debugging, so it's easy to see the individual 'bits'.
I also got the start point correct, because you can tell that's how the image was created: a dot is drawn, then the next one on top of that, and so on. The first dot is therefore overlapped, the last one is last one written, so it's the one that isn't overlapped by anything else. The other way around makes no sense to me. -- besides, if you'd want the easiest way to draw a spiral, wouldn't you always start in the middle?
Took the main image, blew it up to twice the size (to increase error margins and make edge detection easier), tweaked it in photoshop: used replace and select color to make the green dots pure red and the white ones pure green. Then I did some further filter tweaks to sharpen and darken the edges.
The detection 'algorithm' is pretty simple. It uses the direction taken from the previous dot it found, then compares several circle-shaped areas (excluding the previously marked content) to check how 'green' or 'red' they are and where the edge is likely to be. Then it picks the best candidate and so forth. Required a bit of tweaking, and my PHP (don't laugh) solution took minutes to do the whole thing, but it worked after some tweaking sessions.
The final version got the whole thing without needing any manual checks or fixes.
Here's the detection result, if anyone's interested:
http://www.tabun.nl/tmp/spiral_bits_out.png
Colorized for debugging, so it's easy to see the individual 'bits'.
I also got the start point correct, because you can tell that's how the image was created: a dot is drawn, then the next one on top of that, and so on. The first dot is therefore overlapped, the last one is last one written, so it's the one that isn't overlapped by anything else. The other way around makes no sense to me. -- besides, if you'd want the easiest way to draw a spiral, wouldn't you always start in the middle?
Uff, long time I have ignored this challenge, but as I have decided to find a path to quine, I was forced to solve it ... navigation through the picture required about 20 tries. My original attempts expected circle centers on noninteger coordinates. When I found it performs much better at places where it is integral, I have simplified the code and it start work better ...
I have used java ... my first java work with images ... I have done debug by creating modified spiral2.png with debug info pictured.
I got bit's negated ... fortunatelly I have decided to try both possibilities
.
I have used java ... my first java work with images ... I have done debug by creating modified spiral2.png with debug info pictured.
I got bit's negated ... fortunatelly I have decided to try both possibilities
.Code: Select all
private static int centerEval(double x, double y, boolean markIt) {
int res=100;
for(int lx=(int) Math.round(x-radius-1);lx<=(int) Math.round(x+radius+1);lx++) {
for(int ly=(int) Math.round(y-radius-1);ly<=(int) Math.round(y+radius+1);ly++) {
if ((lx-x)*(lx-x)+(ly-y)*(ly-y)<(lx-prevX)*(lx-prevX)+(ly-prevY)*(ly-prevY)) {
if (Math.abs((lx-x)*(lx-x)+(ly-y)*(ly-y)-radius*radius)<1.2*radius) {
int pixel=spBits.getRGB(lx,ly);
if ((pixel&0xff)==0xff) {
res+=4;
if (markIt) {
spBits.setRGB(lx,ly,((progress*0x3800)&0xff00)|0x0080);
}
}
if ((pixel&0xff)==0x00) {
res--;
}
}
}
}
}
//System.out.printf(Double.toString(x)+" "+Double.toString(y)+" "+res+"\n");
return res;
}
private static void correctCenter() {
int bestEval=0,bestX=0,bestY=0;
for(int x=-4;x<=4;x++) {
for(int y=-4;y<=4;y++) {
if (Math.abs((x+dX)*(x+dX)+(y+dY)*(y+dY)-9)<8) {
int eval=centerEval(curX+x,curY+y,false);
System.out.printf(eval+"\n");
if (eval>bestEval) {
bestX=x;bestY=y;bestEval=eval;
}
}
}
}
curX=curX+bestX;curY=curY+bestY;centerEval(curX,curY,true);
for(int x=curX-1;x<=curX+1;x++) {
for(int y=curY-1;y<=curY+1;y++) {
if ((curX-x)*(curX-x)+(curY-y)*(curY-y)<=1) {
spBits.setRGB(x,y,((progress*0x3800)&0xff00)|0x0080);
}
}
}
}
private static String processSpBits() {
for(int x=0;x<spBits.getWidth();x++) {
for(int y=0;y<spBits.getHeight();y++) {
int pixel = spBits.getRGB(x,y);int R=(pixel>>16)&0xff, G=(pixel>>8)&0xff, B=pixel&0xff;
if ((pixel&0xffffff)==0) {spBits.setRGB(x,y,0xff000000);
} else if ((R>35) && (G>182) && (B>153)) {
spBits.setRGB(x,y,0xffff0000);
} else if (R<36 & B>100) {
spBits.setRGB(x,y,0xff00ff00);
} else {
spBits.setRGB(x,y,0xff0000ff);
}
}
}
correctCenter();
String result = "1";
while (true) {
progress++;
//System.out.println(curX+" "+curY);
prevX=curX;prevY=curY;
curX+=dX;curY+=dY;
correctCenter();
dX=curX-prevX;dY=curY-prevY;
double norm=Math.sqrt(dX*dX+dY*dY);
System.out.print(norm+"\n");
dX=(int) Math.round(3*dX/norm);dY=(int) Math.round(3*dY/norm);
int zeroVote=0,oneVote=0;
for(int x=curX-radius+1;x<=curX+radius-1;x++) {
for(int y=curY-radius+1;y<=curY+radius-1;y++) {
if ((x-curX)*(x-curX)+(y-curY)*(y-curY)<(radius-1)*(radius-1)) {
if ((x-prevX)*(x-prevX)+(y-prevY)*(y-prevY)>(radius*radius)) {
int pixel=spBits.getRGB(x,y);
if ((pixel&0xffffff)==0xff0000) {
zeroVote++;
} else if ((pixel&0xffffff)==0x00ff00) {
oneVote++;
}
}
}
}
}
if (zeroVote>0 && oneVote>0) {
System.out.printf("Not sure with "+progress+" "+zeroVote+" "+oneVote+"\n");
result=result+"2";
break;
} else if (zeroVote>0) {
result="1"+result;
} else if (oneVote>0) {
result="0"+result;
} else {
//result=result+"E";
break;
}
if ((curX<10)||(curX>1014)||(curY<10)||(curY>1014)) {
break;
}
}
//processedCircle(curX,curY);
return result;
}