Loop problem - identified + need solution

[joseph mcgratton]

hello,

i am currently writing a program that contains alot of simple deterministic algorithms.i have a problem with one of the algorithms. I know what this problem is so hopefullysomeone here can help. first let me set the scene by showing a test scenario with limitedoptions.

- there is a grid of squares. The left 3 columns are filled blue or yellow.
- Randomly generated somewhere on the grid is a red square.
- a simple algorithm "finds" the red square.
- this algoritm then fills all squares left of the red square orange until rules/constraints are met

- A) the line stops when it hits a blue square
- B) each orange square can either
B1) remain the same
B2) turn white + the square above turns orange

B1 + B2 are constrained (constraint 1) in that the square above must be white.
B1 + B2 are constrained (constraint 2)in that only four squares can be moved up.
This "maximum of four squares works as follows. If a square is moved up one place, a "counter" (orangeUp)becomes orangeUp+1, and then the next orange square is looked at.

Now here is the problem. if the algorithm reaches the last orange square that has a white square below or above (ie constraint 1), and orangeUp has not reached 4 (constraint 2), the algoritm repeats until constraint 2 has reached 4. This means that instead of the orange square moving up once, it moves up 1 - 4 times. this is an example. (w = white, o = orange, b = blue)

Bwwwwwww Bowwwwww
Bwwwwwww Bwwwwwww
Bwwwwwww Bwwwwwww
Bwooooww Bwwwwwww
Bowwwwor Bwooooor
Bwwwwwww Bwwwwwww
Bwwwwwww Bwwwwwww

example 1 example2

in example 1, the algoritm works - 4 squares are moved up. this is because the algoritm started near the beginning of the orange trail.

in example 2, the algoritm doesnt work - the last square moves up 4 spaces. this is because the algorithm started at the last viable orange square. Going through constraint 2, orangeUp must reach 4.

here is the small snippet of code involved. Please note that i am aware some syntax is missing in this snippet, but in the full code its all there.

            int orangeUp = 0;
   
            for (int row = 0; row < MAX_ROWS; row++) {
                for (int col = 0; col < MAX_COLS; col++) {
           
                   if ( OrangeUp < 4 &&
                      Color.orange == grid[row][col].getBackground()
                      && Color.white == grid[row-1][col].getBackground()){
              
 
                       grid[row][col].setBackground(Color.white);
                       grid[row - 1][col].setBackground(Color.orange);
                       orangeUp++;}}} 

i hope you understand this. At least ive identified the problem.
im sure it can be solved in 1 line of code but i need suggestions! thankyou for reading.

Joseph

[Jimmy Die]

Hi,


This is difficult to follow, and question might be better placed in algorithm form.

My problems understanding are this

1.Why are left 3 columns Blue or Yellow, Is it my choice? If this point is trivial I might suggest to just leave out the optional color of yellow. In my experience I have more success leaving out the unnecessary details as it often distracts a person from the problem. Also why are not the left three columns Blue or yellow, is this by design and running of the algorithm?
2.By not including all of your code one can onl guess what you have. You mention that

 - B) each orange square can either 
 

the word 'can' tells me that it is optional if constraint 1 and 2 are met. So constraint 1 tells me that if the square above it is white and if the orange count is < 4 then the orange square has the option to move up. It cannot be optional so I assume that you have some more logic to carry this out or that you statment

- B) each orange square can either

should not read 'can' but is directly dependant upon the constraints 1 & 2.

I'm sure that your right in saying that it can probably be solved in 1 line of code. I think that some of the reasons you havn't had any responses have something to do with what I've mentioned. Yes, I have an idea for what your asking. Respectfully the burden of explaining is on you, more than assumptions on my part.


Cheers,



[ March 03, 2005: Message edited by: Jimmy Die ]
[ March 03, 2005: Message edited by: Jimmy Die ]