Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 24 of 24

Thread: This one is really hard

  1. #1
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Post This one is really hard

    Check out this link:-

    http://www.iarcs.org.in/inoi/2003/in...er/chamber.pdf

    I'm having problem in this particular problem. Before anyone asks what have you tried, my answer is everything I could. I have tried to think of every possible logic I could use, but in vain. Some help would be gladly accepted. I have done many other difficult programs, but none like this. Please help.


  2. #2
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    897
    Thanks
    0
    Thanked 166 Times in 148 Posts

    Default Re: This one is really hard

    Maybe you would like to copy the contents of your link and insert them in your post.
    Some people might be driven away from this thread because they do not like to follow unknown links.

  3. #3
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Lightbulb Re: This one is really hard

    The link contains some diagrams I can't copy. Don't worry, it's a PDF file.
    Here, open this one.
    Attached Files Attached Files

  4. #4
    Junior Member
    Join Date
    Apr 2014
    Posts
    15
    Thanks
    4
    Thanked 2 Times in 2 Posts

    Default Re: This one is really hard

    Hello, so if you tried
    ..everything I could. I have tried to think of every possible logic I could use, but in vain...
    maybe there is no sollution. Unless there is something you didnt tried.

    I would want to know what have you tried, so I dont have to post something that is already tested and prooved as not working. Maybe we the answerers will see only small error in your attempt and correct you so you can continue with it. If you are not willing to show us your attempts, why should we post you the whole sollution?

  5. #5
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Lightbulb Re: This one is really hard

    Quote Originally Posted by Zavael View Post
    Hello, so if you tried

    maybe there is no sollution. Unless there is something you didnt tried.

    I would want to know what have you tried, so I dont have to post something that is already tested and prooved as not working. Maybe we the answerers will see only small error in your attempt and correct you so you can continue with it. If you are not willing to show us your attempts, why should we post you the whole sollution?
    I said I tried "Everything I could", not everything possible in this world. Obviously there is something I missed (meaning a logic I didn't think maybe). That's why I posted the problem. And this question is solvable, it's just bloody difficult. For your information, this question came in INOI 2003 (Indian National Olympiad of Informatics, 2003) and only 22 students of the 100 selected from all over India could do this program. I have solved other question papers from 2004 to 2013, but this one I cant.

    Still, if you want to know what I really tried, then I should let you know.

    Once, I tried going along the walls i.e. create a pointer to go along the walls (cells containing value 1) starting from bottom left corner. If while going along the pointer found two routes from its position containing 1's (junction of walls), the I used recursion to go along both one by one and call the same method if another junction is found. In this way, I could count the no. of times the pointer reaches back to its initial position and that would be the no. of chambers. But that posed a problem for chambers in the middle with no contact with the outer walls. Also, counting the area of each chamber is very difficult. I need an Authentic solution for this program. No need for whole programs, just explanation and logic would be very helpful and gladly accepted. Looking forward for answers.


    Thank you.

  6. #6
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,607
    My Mood
    Hungover
    Thanks
    145
    Thanked 658 Times in 563 Posts

    Default Re: This one is really hard

    Nobody is going to go to an external link and simply tell you how to do it.

    You need to break your problem down into smaller steps. This is the essence of problem solving while programming, and it's what your assignment is trying to teach you. Simply telling you what to do will rob you of that lesson.

    Which **part** of the assignment are you stuck on? Where is your MCVE? What is your specific technical question?

    "I tried X, expected Y, but got Z instead" is a lot easier to help you with than "I don't know how to do this."
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  7. #7
    Junior Member
    Join Date
    Jun 2014
    Posts
    16
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: This one is really hard

    This is a very old problem sometimes called 'the ponds and islands problem'.

    The solution will become clear to you if you can visualize the data objects and how they interact. Think like a DBA to see the data schema. This one is simple. There are not many object types. If you use a functional decomposition approach, the problem will become far more difficult.

  8. #8
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Default Re: This one is really hard

    I'm sorry, but I didn't understand what you are trying to say.

    --- Update ---

    I know its an old problem but not too old be become obsolete. INOI gives logical problems for which you mostly need basic programming knowledge, but need the logical thinking of a genius. I solved other papers of INOI (2004 - 2013) in less than 40 minutes (average, each program), but this one I'm stuck for 14 days. And it really frustrates when you cant do a program for 14 days. Believe me, it does.

  9. #9
    Junior Member
    Join Date
    Jun 2014
    Posts
    16
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: This one is really hard

    There is more than one decomposition strategy to solve any computing problem. The strategy I see used most often in industry and taught in academia is 'functional decomposition'. You can google this to learn what it means.

    This particular problem is difficult to solve using functional decomposition. There is another method of decomposition that will solve this problem. That method is often called data domain decomposition. You can google this too.

    Data decomposition is the analysis method used by data modelers to represent any problem. DBA's often use this methodology. The entity relationship diagram (ERD) used to represent a relational database schema is an expression of this thinking model.

    Build a data model for this castle / chamber problem. Then map that into Java classes. I would suggest you start with the Castle. What is the Castle? It is either an extension or aggregation of a collection tiles. Yes? Moreover, the problem statement constrain the geometry of this collection. It is a rectangular array of Tiles not less that 1 x 1 or greater than 500 x 500 elements.
    The same thinking can be applied to a Tile. The problem statement says a Tile is either a wall or open space and each Tile has a unique location in the Castle. Tiles may have neighbors. This gets a little more complex. In the trivial case, a 1x1 castle, that tile has 0 neighbors and must be a wall! In the 1x2 and 2x1 cases, each tile has 1 neighbor which must also be a wall. ... In the most general case a Tile may have up to 4 adjacent neighbors which themselves may be either walls or spaces. Each Tile which is a space is a member of exactly one Chamber.
    A Chamber is a contiguous adjacency of Tiles that are spaces.


    Does this help you?

  10. #10
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Default Re: This one is really hard

    I now understand what you are trying to say, but that's all good for theory. It was one of my ideas, but then the problem comes:- how do I implement it in code. Still thank you for your advice. It did help me a bit. By the way, I didn't know what was data domain decomposition and functional decomposition. It wasn't taught at school. Thank you.

  11. #11
    Junior Member
    Join Date
    Jun 2014
    Posts
    16
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: This one is really hard

    I had guessed your schooling did not teach this. My prior experience with east asian developers indicated to me that education there was not covering these topics. I was intending to teach you how to get the data model into code. Are you interested in learning how to do this?

    The next step is to map the ERD into a UML class diagram, which maps to code.

  12. #12
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Lightbulb Re: This one is really hard

    Quote Originally Posted by DarthBane View Post
    The next step is to map the ERD into a UML class diagram, which maps to code.
    Please Explain.

    Quote Originally Posted by DarthBane View Post
    I was intending to teach you how to get the data model into code. Are you interested in learning how to do this?
    Yes, please do. You are very much welcome.

  13. #13
    Junior Member
    Join Date
    Jun 2014
    Posts
    16
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: This one is really hard

    ERD = Entity Relationship Diagram. These are the large charts you see the DBA's using. google to see what these are and how they work. We already talked about the three top level entities that are going to be represented on this, Castle, Chamber and Tile. An ERD shows the objects, their attributes and their relationships. It does not represent anything of process, that is, no methods.

    Enter the class diagram. This is a UML construct. google this to learn about it. It diagrams classes, their relationships, attributes and methods. This is where process begins to enter the picture. The classes, attributes and relationships come directly from the ERD. You will add the methods. A class diagram can go directly to code without a lot of other analysis if the model is simple enough. This problem is a simple candidate.

    First step for you : construct your ERD and I will review it with you.

  14. #14
    Junior Member
    Join Date
    Apr 2014
    Posts
    15
    Thanks
    4
    Thanked 2 Times in 2 Posts

    Default Re: This one is really hard

    As you tried to go by the walls, i would try to count the space cells instead of walls. I think it could be done without object oriented programming, but it could be really harder.

    In OOP it could be done in the way that you create a Castle as object, that can store Chamber objects. Chamber stores reference to "open space" Tiles that belongs to it. Tile has position on the floor and the information if it is gouped to specific chamber (= "chambered") or not yet - and if it is, it knows what the chamber it is from castle's chambers.
    The castle can create a new chamber and can merge two chambers into one and preserving all the Tiles from both chambers into that one that remains (or new one with deleting the two others). The castle has the floor plan (maybe two dimensional array of Tiles).
    The chamber can add a Tile to its Tiles.

    Now with this prototype structure (maybe I missed something that will be needed), you can iterate over all tiles and play around with these rules:

    1. If the current Tile is not "chambered" in castle (ie no chamber hold it) check for the 4 neighbour Tiles (if they exist) and if any of the neighbour is already "chambered", associate the current Tile to that chamber.
    2. If no neighbour tile is "chambered" create a new chamber in the castle and add the Tile to it. (when you go to the next Tile it will be associated to the same chamber as stated in rule 1)
    3. If on one Tile there will be more than one neighbour Tiles "chambered", merge all the chambers in the castle together and add the Tile to them.

    The rules shouldnt be hard to implement.
    At the end, now in your castle object you know how many chambers do you have and how many Tiles has each of them. I hope this can help.

    EDITED - but i would suggest you to go trough the whole process with DarthBane it will teach you a lot more

  15. #15
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Lightbulb Re: This one is really hard

    From now, 2 days I will be offline (I have some work, so I wont be home). I will try to be back on Monday if possible. So don't bother to ask for my posts/replies.

    To DarthBane :-

    I will try to make the class diagram ASAP (As Soon As Possible). But remember this - its not an easy task for someone who is learning UML construct, ERD, etc. for the first time. And that too from google. So while I try, I must ask if there is a simpler method to do this program. Because I have done other harder programs form INOI in much easier ways. So please, while I'm out, try to post any simpler method(s) you can find. Your posts are highly appreciated.

    Thank you.

    And thank you too Zavael for your useful post.
    Last edited by Abhilash; June 6th, 2014 at 11:10 AM. Reason: spelling mistake

  16. #16
    Junior Member
    Join Date
    Jun 2014
    Posts
    16
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: This one is really hard

    Of course it can be done without OOP but it is much cleaner, elegant, and more maintainable if it is solved using object technology. I once wrote the solution to this problem is PL1!

    One can also write a procedural solution to the problem in Java or C++, but I would argue that is a misapplication of those languages.

    --- Update ---

    I know this is a lot to learn, but I am trying to teach you how to think about the problem in the data domain instead of the process domain. When you master this mode of thinking you will no longer need to draw the diagrams for simple problems like this one. It will come to you just like your process domain solutions do now.

  17. #17
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Default Re: This one is really hard

    Hey, I'm back. Just wanted to ask something to DarthBane. Is there a way to solve this problem without constructing an ERD, because frankly speaking, I've never constructed an ERD before and I have solved every problem I have encountered without constructing an ERD with ease (except this). Please help. Moreover, I need a way to solve this kind of problem within 40 minutes, for the competitions. Your posts are highly appreciated.

    Thank You.

  18. #18
    Junior Member
    Join Date
    Jun 2014
    Posts
    16
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: This one is really hard

    Quote Originally Posted by Abhilash View Post
    Hey, I'm back. Just wanted to ask something to DarthBane. Is there a way to solve this problem without constructing an ERD, because frankly speaking, I've never constructed an ERD before and I have solved every problem I have encountered without constructing an ERD with ease (except this). Please help. Moreover, I need a way to solve this kind of problem within 40 minutes, for the competitions. Your posts are highly appreciated.

    Thank You.
    I am trying to teach you how to think about the problem so you can solve it quickly. It is clear to me from your posts that you are trying to apply functional decomposition to these problems. That approach can theoretically solve any problem, but some problems, like this one, can present great difficulty using that method. You want to solve this quickly? Learn how to think in the data domain.

    The purpose for working through an ERD is to learn how to think in the data domain first. As I said earlier, once you have mastered this technique, the solutions to simple problems like Castle/Chamber will not require you to construct an ERD on paper. They will come to you just as the functional decomposition solutions do today. It is simply a matter of training your mind how to think about these problems as data relationships instead of sequences of processing steps.

    Your call. Do you want to get any better at this or do you want to continue to pursue a methodology that is shown to be inadequate in all situations?

  19. #19
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Default Re: This one is really hard

    Quote Originally Posted by DarthBane View Post
    I am trying to teach you how to think about the problem so you can solve it quickly. It is clear to me from your posts that you are trying to apply functional decomposition to these problems. That approach can theoretically solve any problem, but some problems, like this one, can present great difficulty using that method. You want to solve this quickly? Learn how to think in the data domain.

    The purpose for working through an ERD is to learn how to think in the data domain first. As I said earlier, once you have mastered this technique, the solutions to simple problems like Castle/Chamber will not require you to construct an ERD on paper. They will come to you just as the functional decomposition solutions do today. It is simply a matter of training your mind how to think about these problems as data relationships instead of sequences of processing steps.

    Your call. Do you want to get any better at this or do you want to continue to pursue a methodology that is shown to be inadequate in all situations?
    I know I have to use data domain decomposition method, which I am trying to, but is it absolutely necessary to construct ERD?

  20. #20
    Junior Member
    Join Date
    Jun 2014
    Posts
    16
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: This one is really hard

    Quote Originally Posted by Abhilash View Post
    I know I have to use data domain decomposition method, which I am trying to, but is it absolutely necessary to construct ERD?
    The fact that you are stymied by the problem suggests the ERD will help you see the data pattern more clearly. That is what ERD's are for, visualization of data schema. As an added bonus, you will most certainly encounter these if you ever work professionally with a DataBase Architect, a common working arrangement among Java server developers.

    Lets look at the Castle object again. A Castle is comprised of Tiles. It contains some number of Chambers each of which shares some number of Tiles with its Castle. No Tile is a member of more than one Chamber. This tells you a great deal about the ERD data relationships.

  21. #21
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Default Re: This one is really hard

    Let me try.

  22. #22
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Default Re: This one is really hard

    After one and a......... sorry 2 months, I finally got the answer.
    Thank you.

  23. #23
    Junior Member
    Join Date
    Jun 2014
    Posts
    16
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: This one is really hard

    Quote Originally Posted by Abhilash View Post
    After one and a......... sorry 2 months, I finally got the answer.
    Thank you.
    What method led you to the solution?

  24. #24
    Member Abhilash's Avatar
    Join Date
    Jun 2014
    Location
    Kolkata, West Bengal, INDIA
    Posts
    108
    My Mood
    Busy
    Thanks
    5
    Thanked 10 Times in 10 Posts

    Default Re: This one is really hard

    The very same method which solves all problems. A method taught to students at high school while programming which helps solving many problems which would require extensive logic just by the use of simple ideas. RECURSION.

    Of course, I knew I had to use it, but then the question was the idea. Finally I got the idea a week before my competition(you can see about the competition in my member introduction. You will know which one. It is in one of the replies in my thread.)

    The idea was "explore a tile and convert it to a wall". First, I used two for loops to run through the 2D array in the main function. The moment I got a space tile (i.e. cell with value 0), I sent its coordinates(or location) to the 'explore'. There I converted the 0 to 1 (i.e. space to wall) and then checked the neighboring tiles for zeros(space). Each time I got one I again sent its location to the very same explore function(hence, recursion) and the process got repeated. For zeros in multiple directions, I gave preference in the order of down, right, up and left. If no 0 found in any direction, the method would return back to where it was last called from - itself, but with the previous value now which it had used to call itself. Only this time, it would try in some other direction other than the path followed previously. That is the main advantage of using recursion. Ultimately, since it cannot jump squares but only follow the path of zeros, it stays confined in a particular chamber and converts the white tiles to black ones. When all done, it ultimately returns back to the main function, but this doesn't end still. Remember that we are in a loop that runs through the grid, checking for zeros. With one chamber practically erased and its size(area) stored, the loop finds another zero in another chamber(if present) and explore starts from there.

    Thus, the program does this to every chamber one by one until no chamber is left. Also while this, I am also calculating the area, incrementing it in a chamber for every 0 converted to 1. After the chamber vanished, I compare it with the previous value found. If greater, I store it in the variable which I compared with just now(this is to find the largest area). The program also keeps count of the chambers. And this is how I did it.

    Thank you again.

Similar Threads

  1. [SOLVED] This shouldn't be too hard.
    By MR bruto in forum What's Wrong With My Code?
    Replies: 2
    Last Post: May 10th, 2013, 12:36 PM
  2. Hard time understanding.
    By Bantertrix in forum Java Theory & Questions
    Replies: 1
    Last Post: April 15th, 2013, 08:31 AM
  3. Trying hard(im just a beginne)
    By riddick_charel in forum What's Wrong With My Code?
    Replies: 2
    Last Post: February 27th, 2013, 09:20 AM
  4. How hard would this be to write for a Beginner?
    By Bgriesh in forum Java Theory & Questions
    Replies: 7
    Last Post: August 11th, 2012, 02:30 AM
  5. I am having a hard time with my code
    By SandeeBee in forum What's Wrong With My Code?
    Replies: 14
    Last Post: November 12th, 2011, 09:34 AM