Thread: Stabilizing Array 2D-ON

Given this input
1 0 - -
- - - -
- - - -
- - - -

Which of these are valid?
1 0 1 1
1 1 1 1
1 1 - 1
1 1 1 1

1 0 1 1
1 1 1 1
1 1 1 -
1 1 1 1

1 0 1 1
1 1 1 1
1 1 1 1
1 1 - 1

1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 -

Or any of the same 4 combinations with a zero in place of the don't care.

Originally Posted by Salem

Given this input
1 0 - -
- - - -
- - - -
- - - -

Which of these are valid?
1 0 1 1
1 1 1 1
1 1 - 1
1 1 1 1

1 0 1 1
1 1 1 1
1 1 1 -
1 1 1 1

1 0 1 1
1 1 1 1
1 1 1 1
1 1 - 1

1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 -

Or any of the same 4 combinations with a zero in place of the don't care.

Oh sorry didn't specify about that, they are 4 combinations valid, it doesn't matter which one of 4combinations would be , the purpose is any stable matrix that has maximum number of ones, in your example, all four combinations have maximum number of ones to stabilize the matrix, so anyone of them would be valid ..doesn't matter while all 4 combinations are having "maximum" number of ones to stabilize. (the output is , printing the maximum stable matrix that has maximum number of ones to stabilize it)

my question which algorithm you used? and how should I start with the concept? your previous suggestion doesn't work on that example ....

Well my previous simplistic algorithm doesn't work in all cases.

But given this,
1 0 - -
- - - -
- - - -
- - - -
I would compute the min and max values that each quadrant could contain.
So red has a min of 1 and a max of 3
All the others have a min of 0 and a max of 4

The number of 1's you need to put in red and cyan quadrants is
min(max(red),max(cyan))
Which in this example is 3.

The number of 1's you need to put in green and blue quadrants is
min(max(green),max(blue))
Which in this example is 4.

Originally Posted by Salem

Well my previous simplistic algorithm doesn't work in all cases.

But given this,
1 0 - -
- - - -
- - - -
- - - -
I would compute the min and max values that each quadrant could contain.
So red has a min of 1 and a max of 3
All the others have a min of 0 and a max of 4

The number of 1's you need to put in red and cyan quadrants is
min(max(red),max(cyan))
Which in this example is 3.

The number of 1's you need to put in green and blue quadrants is
min(max(green),max(blue))
Which in this example is 4.

Hi salem; first I would thank you very very much for your explanation and cooperative to me; I'm still a lil confused if I understand you very well or not(Sorry for my low ..)
May you explain the equation min(max) by a critical example step by step on matrix 4*4 and doesn't matter what inputs you choose; the matter for me to elaborate the steps to arrive to the output with maximum number of ones that stabilize the matrix.


Second off; your recent algorithm would work for all cases yeah? If not; correct me.


Much appreciated!!!!!

You need to read it again, because the example is right there in front of you.

You said it yourself, not every matrix has a solution.

Look, I've shown you how to approach the problem.

It's up to you now to pick up the ball and start doing some of your own analysis.

I'm not going to drip-feed the rest of the analysis to you, only to then drip-feed the code to you later on.