Find all and modify triplicates in an array

I have a 10x10 array of ones and zeros. I need to come up with a script that will search the array for any cases where a row, column, or diagonal in the array contains a triplicate (three of a kind) of either ones or zeros and replace the third number with the opposite value. For example, if row 1 is 0011100101 then because the 3rd, 4th, and 5th columns are all equal to one and as I stated previously, there can be no three of a kinds in the array, column 5 in the first row becomes 0. This then makes column 7 need to become 1 because we end up with another triplicate, and then we're done with that row. A similar process occurs with the search in the columns and diagonals. Is my code as simple as a nested for loop that says "if your current row and column equals the next column over and the next column over then the third column gets changed" and similar for the checking the columns and diagonals? Can't seem to figure this one out.

[jonas]

I feel that the problem is still ambiguous. Do you search for triplets from left to right? Do you always start with ones? Can you have more than three of a kind in a row?

[Image Analyst]

What's the use case for this? Why do you need to do it (provide context for this unusual thing)? Do they have to be integers? Can you just set every other one in a run of 3 or longer to 0?

[Morgan Clendennin]

I am working on this array for a project that I am working on. I know it's a weird thing to have to do but it is what I need for the project. Every run of three can be a combination of 110,011,101, 010, or 001. There is not allowed to be any span of ones or zeros greater than a what I described above i.e. no 1111, or 0000.

[Stephen23]

@Morgan Clendennin: how do you want to resolve conflicts? For example, a sequence like this:

1 1 1 0 0

When the third element is changed from 1 -> 0 it creates a new sequence of three 0's: does the third 0 need to be changed? What about:

      1
      1
  0 0 1

If we process the columns and change the third 1 -> 0, what about the three 0's in row?

[Morgan Clendennin]

Any time a triplet appears, one of the values needs to change. In the first case where the triplets are purely horizontal, the array would go from 11100 to 11001. In the second case, I guess I didn't see the problem when two opposite triplets intersect at a row and column intersection point. In this case, we could change the column to 110 but we would have to change one of the other places in the horizontal triplet (leading to either 010 or 100) as changing it to 001 would change back the vertical triplet. In keeping with changing the third (last) value of the triplet, I believe in the second case it should become

      1
      1
  1 0 0

Hopefully this makes sense.

[Stephen23]

@Morgan Clendennin: have you confirmed if these rules lead to a stable solution? It seems quite possible that you could end up with a kind of Game of Life situation.

Answer 1

[Malte Herrmann]

Here you go!

function [myArray, NChanges] = ChangeTripletsInArray(myArray)
  NChanges = 0;
  % Iterate over rows
  for idxr = 1:size(myArray, 1)
      % Iterate over columns
      for idxc = 1:size(myArray, 2)-2
          threevals = myArray(idxr, idxc:idxc+2);         % Take 3 values from array
          [threevals_new, flag, NChanges] = CheckTrips(threevals, NChanges);  
          if flag == 1 % Then changes have to be included in myArray
              myArray(idxr, idxc:idxc+2) = threevals_new;
          end % End of if flag == 1
      end % End of for idxc

    end % End of for idxr

    fprintf('%1.0f changes had to be made to the array.')

    %%%Subfunction CheckTrips
    function [self, flag, n] = CheckTrips(self, n)
        if mod(sum(self), 3) == 0 % e.g. sum([1,1,1])=3 mod(3,3)=0
                                  %      sum([0,0,0])=0 mod(0,3)=0
            self(end) = abs(self(end)-1); % e.g. abs(1-1) = 0
                                          %      abs(0-1) = 1
            flag = 1;
            n = n + 1;
        else
            flag = 0;
        end
    end % End of function CheckTrips
end % End of function ChangeTripletsInArray

[Morgan Clendennin]

Hi Malte! Thank you for your response. I have tried your provided function with a 10x10 array of ones that I passed it and changed every third one to a zero on every row. This passes the criteria of having every row and diagonal with no triplets however the criteria to have no column with triplets is not passed. Not sure what needs to be modified to fix this?

[Morgan Clendennin]

I tried my hand at writing something after breaking down how your code is working and I have a code that's working when I pass it a 10x10 array of ones but the catch is that it's only working for the rows and columns. It removes all triplets in some diagonals but not others (for example when a column triplet and row triplet intersect).

for i=1:size(A,1)-2;
    for k=1:size(A,2)-2;
        if A(i,k) == A(i,k+1);
            if A(i,k) == A(i,k+2);
                A(i,k+2)=abs(A(i,k+2)-1);
            end
        end
        if A(i,k) == A(i+1,k);
            if A(i,k) == A(i+2,k);
                A(i+2,k)=abs(A(i+2,k)-1);
            end
        end
        if A(i,k) == A(i+1,k+1);
            if A(i,k) == A(i+2,k+2);
                A(i+2,k+2)=abs(A(i+2,k+2)-1);
            end
        end
    end
end

Maybe I need a way to iterate (a while loop maybe) until all conditions are met?

[Malte Herrmann]

Hi there! I obviously was reading too fast, had only the rows in mind. Sorry for the confusion! I'm quite busy this week, so I don't think I'll be able to sit on this for a longer time, but it seems to be a real brain teaser! Hopefully you'll be able to figure it out, extending this to vertical and diagonal surely will be quite difficult, especially if the code is supposed to work efficiently. But in a first try, looping until all conditions are fulfilled sounds like it will lead to a good solution!

[Morgan Clendennin]

Hi Malte, I understand and I will keep working on it myself as well. Hopefully you will notice my comment above but just in case I can repeat it here. for cases like 11100 where the triplet is purely in one direction, we can easily have the code say to change the third element of the first triplet to a zero, creating a second triplet and then change the third element of the second triplet to one. This would change 11100 to 11001. In the case where we have a triplet in the row such as this:

      1
      1
  0 0 1

Changing the third element in the column creates a triplet in the intersecting third row. Now there are 3 ways this could be accomplished. The first, changing the third element in the triplet to a 1, would re-violate the column triplet check and throw us into a never ending loop. The other two acceptable solutions are changing either the first or second element in the triple to a one, creating 100 or 010. In keeping with the pattern of change the third element, it makes sense for this condition to change the first element creating 110 on the column and 100 on the interesecting row.

[Morgan Clendennin]

Just me again, I realized kinda by accident that if you take the output of your ChangeTripletsInArray function and transpose it and then put it back in to the function, that takes care of the columns as if they were rows. This is again testing this all with a 10x10 ones matrix as my test case. This now creates the same problem that my code has where if we change the diagonal triplets by the third value, we would create new triplets again on the rows/columns. Going to test it if we change the first member of the diagonal triplets. I'm getting closer!!

[Morgan Clendennin]

Hi Malte, have you been able to look more into this?

Answer 2

[Stephen23]

This is a simple example of how you could approach this problem. I have not dealt with the edge cases: this is a simple proof-of-concept demonstration which you can tailor as required. Note that your rules do not seem to guarantee any fixed solution in a finite number of iterations.

I = logical(randi(0:1,10));
imh = image(I,'CDataMapping','scaled');
while true
    idx = I(1:8,:)&I(2:9,:)&I(3:10,:); % rows
    I(idx) = ~I(idx);
    set(imh,'CData',I)
    pause(0.5)
    idx = I(:,1:8)&I(:,2:9)&I(:,3:10); % columns
    I(idx) = ~I(idx);
    set(imh,'CData',I)
    pause(0.5)
    idx = I(1:8,1:8)&I(2:9,2:9)&I(3:10,3:10); % diag
    I(idx) = ~I(idx);
    set(imh,'CData',I)
    pause(0.5)
    idx = I(1:8,3:10)&I(2:9,2:9)&I(3:10,1:8); % antidiag
    I(idx) = ~I(idx);
    set(imh,'CData',I)
    pause(0.5)
end

[Morgan Clendennin]

Hi Stephen, I ran your provided code on the randomized "I" array that you provided as well as on a 10x10 array of ones. The 10x10 array of ones just kept flashing between the original matrix and a solution which only changes the left 3-4 columns to the opposite value. Your provided I array has a few different solutions that it shows but it infinitely loops as a correct solution where the three conditions is never met.

[Stephen23]

" Your provided I array has a few different solutions that it shows but it infinitely loops as a correct solution where the three conditions is never met."

So far your rules do not guarantee that there is any solution. While there might be alternative ways to approach this (e.g. .using a some kind of global optimization routine to find a minimum energy state, which may or my not have triples), so far there is nothing in your rules that prevents conflict situations oscillating indefinitely, if you use a simple iterative method.

[Morgan Clendennin]

How would you do it, if not an iterative method? Also, what if we were to change the location of the replacement in the triplet to be randomized? i.e. 111 could be replaced with either 110, 101, or 011.