Thread: Stabilizing Array 2D-ON

  1. #16
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by Salem View Post
    > what about this input?
    Have you specified what should happen when 1 and 0 are opposite one another?
    mmm specified in my third example in my description, but doesn't matter I will explain it, when 1 and 0 are opposite one another then if there's a free space for one that's opposite to 0 I will assign it over the free space while in the same time ensuring matrix stabilized.

    for example:
    1 1 1
    - - -
    - - 0
    output:
    printf("there's no possibility for stabilizing this matrix")
    because
    1 1 0
    1 1 1
    1 1 0
    will never be stabilized but if I have matrix 4*4 for example
    1 1 1 1
    - - - -
    - - - -
    - - 0 0
    the output: here we have much free spaces which can ensure stabilization of the matrix
    1 1 1 1
    - - 1 1
    1 1 1 1
    1 1 0 0
    this is the maximum matrix that I can fill with 1 to be stabilized .. "we need always maximum number of ones to fill for stabilizing the matrix"


    So? thanks alot

  2. #17
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Another example to clarify more, in the same aspect of previous comment:
    input:
    1 1 - -
    - - - -
    - - - -
    - - 0 0
    the output should be for getting maximum stabilized matrix:
    1 1 1 1
    - - 1 1
    1 1 1 1
    1 1 0 0

    the free spaces not filled ..because if filled with 1 so the matrix will be not stable ... can assume implicitly in that case the "-" is 0
    "-" is 0 ..

  3. #18
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,607
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #19
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by Salem View Post
    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 ....
    Last edited by RyanC; 05-02-2019 at 10:38 AM.

  5. #20
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,607
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #21
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by Salem View Post
    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!!!!!
    Last edited by RyanC; 05-02-2019 at 12:10 PM.

  7. #22
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,607
    You need to read it again, because the example is right there in front of you.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #23
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by Salem View Post
    You need to read it again, because the example is right there in front of you.
    thanks understood.


    Very meaningful!!

  9. #24
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by Salem View Post
    You need to read it again, because the example is right there in front of you.
    Hi salem ! I "think" not sure that your algorithm is still not working .

    for example if I have like this matrix:

    1 1 1
    - - -
    1 0 1

    then in this case the matrix isn't stable because the side of top and the side of bottom the numbers of ones aren't equal so immediately the matrix isn't stable .. your algorithm isn't working on that case ..

  10. #25
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,607
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #26
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Alright, thanks alot for your help !!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 12
    Last Post: 07-31-2013, 12:15 AM
  2. Replies: 4
    Last Post: 05-30-2013, 05:45 PM
  3. Replies: 2
    Last Post: 03-20-2012, 08:41 AM
  4. Replies: 9
    Last Post: 08-23-2010, 02:31 PM
  5. Replies: 6
    Last Post: 11-09-2006, 03:28 AM

Tags for this Thread