Trying to calculate fastest algorithm.. you'll see

DaSilva

Ok, so here's the problem, there is a small graphic 4*7 pixels that contains a number from 0 -> 9 . The colours of the pixels that are part of the number are static and always the same colour, the "empty" pixels are random colours but never the same as the number colour.

Here is a pic showing which pixels in the 4*7 grid each number occupies.



So, I can only test one pixel at a time. So what is the least number of pixels I have to check for the specific colour to find out what the number is?

Martyr

i'll guess 6

hussey

there are 10 possible digits
and 28 different squares so a possible unique combination of 2^28

so you need to choose at least (in theory) 4 squares, as 2^3 = 6 < 10
2^4 > 10

Ghost Train

I can do it in 9 checks
Test grid 0,6 will check if its 2 if it is 2 then end now otherwise do next check etc

0,0 & 0,1 for 5 or 7
1,2 for 4
1,1 for 1
0,3 & 1,3 for 6 or 0
3,3 for 9
0,2 for 3 or 8

DaSilva

Ok, this is hell, maybe I'm just going about this the wrong way, what is the most straightforward way to make this image into a string

seamus

Break it up into its component images, then use eolhc's algorithm above.

Ghost Train

actually if you check the following 6 pixels
(0,3),(1,3),(3,3) 3 pixels on the 4th line
(0,6),(2,6),(3,6) 3 pixels on the 7th line
it should be unique for each digit
1=XXX011
2=XXX111
3=XXX010
4=100XXX
5=001XXX
6=110XXX
7=XXX000
8=010XXX
9=011XXX
0=101XXX

X can be light or dark, you can see the pattern and how each would test

MOH

You can do it in 4 tests, each test depending on the results of the previous.

To work out what they are, build a grid showing each pixel, and what digits contain that pixel (hope this formats OK).

	0	1	  2	      3
0	57	23567890  123456890   57
1	2356890	14	  14	      237890
2	56890	45	  1457	      23890
3	60	689	  12346789    590
4	4680	247	  14	      3456890
5	235680	7	  14	      356890
6	2	123567890 123456890  12

then work out which tests eliminate most digits.

IF 0, 2 THEN    /* 56890
   IF 0, 3 THEN   /* 60
      IF 3,3 THEN
         DIGIT = 0
      ELSE
         DIGIT = 6
      ENDIF
   ELSE            /* 589
      IF 3, 3 THEN
         IF 0, 0 THEN
            DIGIT = 5
         ELSE
            DIGIT = 9
         ENDIF
      ELSE
         DIGIT = 8
      ENDIF
   ENDIF
ELSE        /* 12347
   IF 2, 5 THEN  /*14
      IF 1, 2 THEN
         DIGIT = 1
      ELSE
         DIGIT = 4
      ENDIF
   ELSE           /*237
      IF 1, 5 THEN
         DIGIT = 7
      ELSE
         IF 0, 6 THEN
            DIGIT = 2
         ELSE
            DIGIT = 3
         ENDIF
      ENDIF
   ENDIF
ENDIF

I think I have that right. There's obviously other alternatives, but I don't think you can do it in less than 4 test, unless you find a way of logical ANDing two or more pixels to eliminate more digits in one go (e.g. if 0,3 and 1,3 then digit 6)

conceited

I can do it in 2

Martyr

You can do it in 4 tests, each test depending on the results of the previous.

well, then its more than 4 tests, no?

conceited

I better post code before you think I'm having a laugh.

Martyr

i can see way to do it with just 6 steps, but if can do in 2!! lets see
if each colour has a value, like 255 for white, or 0 for black, and DaSilva says part of the number is static, you could generate a checksum on 6 pixels based on their position in the grid..if might be done 5 steps, but i haven't checked either way, just a guess.

sicruise

Convert the image to an array of 1/0's where 1 defines the colour making up the number.

Then just do a comparison with known values?

ronivek

Assuming an array representation of the image then the IF solution seems to be about the most practical unless you require mind-bending performance or something to impress your algorithms lecturer.

If you're looking for something specific then maybe the language and a bit of context would help a bit.

DaSilva

When I was asked to do this for a friend I was told "speed is key" which is why I asked for help getting the fastest algorithm doing this, turns out the text changes fast and so needs to be grabbed quickly, I was told the code would need to be ridiculously fast. Turns out ridiculously fast = less than a two seconds. After spending hours trying to weed out bugs of the faster of the algorithm's (thanks btw some of them were really good), I got my hands on the app that I will actually be pulling the text from (previously I was just doing it from a screenshot). Anyway there is no need for such a fancy algorithm at all, and I decided to go the route of just scanning each pixel in the 7*4 square and making a string of 0's and 1's and it works great. Also realised now that I will also need to scan some text too so now on to the task of writing up each characters 10101 string :rolleyes:

conceited

14 redpixels = numbers 0,5,8
13 redpixels = 4,6,9
12 redpixels = 2
11 redpixels = 3
10 redpixels = 1,7

read pixel increment counter if it's red
compare the counter with 10,11,12,13,14
if it's 10 compare it with 0 for 1 if not then it is 7
etc etc etc

Thats my way of doing it. Thought I could do it in 2 pixels, I was mistaken it takes 3, haha joe

MOH

Average Joe wrote: »

well, then its more than 4 tests, no?

Well yeah, it's 12 or whatever tests, but you're only doing 4 of them for any one digit.