The Great Wall Game - Help Needed!

This is a discussion on The Great Wall Game - Help Needed! within the C Programming forums, part of the General Programming Boards category; I am in desperate need for the solution of this problem. Can anyone help me please! http://acmicpc-live-archive.uva.es/n...lem.php?p=3276...

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    The Great Wall Game - Help Needed!

    I am in desperate need for the solution of this problem. Can anyone help me please!
    http://acmicpc-live-archive.uva.es/n...lem.php?p=3276

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    The purpose of these problems is to gain experience and test your ability. Do it yourself. If you have a specific question about it, then ask that.

  3. #3
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Actually I am not getting how to approach this type of problems! Please help me!

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Work on solving it on paper. From there write your solution down in explicit English or an equivalent natural language. Then translate the results of the last step into C.

    Before you can do any of that, you need to understand the problem. Study the question so you understand it well.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I wouldn't say this was "THE" answer, but it would perhaps be my way of approaching the problem:

    Possible answers include just 12 final positions: 5 vertical column "walls"+ 5 horizontal row walls + 2 diagonal walls.

    Now do a retrograde analysis on it, and work backwards from each of the possible solutions. Keep track of the solution and the number of moves required to reach it, and update that whenever you find a solution that requires a lower number of moves.

    It's important to stop working on any attempt once it exceeds the lowest minimum number of moves already found, or your program may be seriously slowed down, especially if the board becomes larger than 5 X 5.

    I have no idea if this would be the best answer or not. I'm a hobby programmer, and the best answer for this jumps over my math capabilities.

    Good luck.

  6. #6
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Yes i have tried this long ago! But complexity is too high! Any other short solution please!

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Wait, this is some sort of programming challenge and you are asking for a simple nice solution?

    What's the point of doing the challenge after all? Challenge yourself?

    I mean, if you don't have any idea how to do it, don't torture yourself. Look around. There's bound to be equally interesting challenges that might be more suitable for you.

    You may come back to this one if you have more experience with this sort of things.
    Last edited by anon; 07-29-2007 at 09:35 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    If you're not able to solve it then leave it and come back to it in 6 months, 1 year, or two years later.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by anirban View Post
    Yes i have tried this long ago! But complexity is too high! Any other short solution please!
    It may seem very complex, but it's not too bad. No, you can't do this program in two lines of code!

    Since you might be a real beginner, may I suggest an easier puzzle to solve? Tic-Tac-Toe might be a good start - it can be done using many algorithms, from easy to very hard.

    Things like that would give you a background and experience that would be very valuable with a puzzle like this Wall Game.

    Did you make a bet with someone that you could solve this particular Wall Game challenge or what?
    Last edited by Adak; 07-29-2007 at 05:44 PM.

  10. #10
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    No no not a bet!!!!!!!!! Actually this is assignment for exam and I have few days left! That is why!

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by anirban View Post
    No no not a bet!!!!!!!!! Actually this is assignment for exam and I have few days left! That is why!
    I don't know an easier way to solve this. Whether you program it going "forward", or retrograde (backward), it appears about the same amount of work.

    Did you instructor or book not have any recommendations for how to start on this or similar problems?

    I haven't seen a problem like this before, and I don't consider it to be a trivial one. I would recommend immediately seeking assistance from either the instructor, the instructor's assistant (if he/she has one), or one of the best students in the class with a helpful spirit.

    If you have a specific problem with logic or syntax, please post it. I just don't have the time to code up a program from scratch, for you.

  12. #12
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    You might find some tips here http://www.topcoder.com/tc?module=St...s&d2=alg_index These are the tutorials listed on topcoder that give ideas on how to tackle certain kinds of problems.
    Last edited by manofsteel972; 07-30-2007 at 03:39 PM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  13. #13
    The larch
    Join Date
    May 2006
    Posts
    3,573
    That seems actually quite interesting. I'd work from Adak's proposal. A possible "heuristics" to speed things up might be to order final placements by the order of how many dots are already in place.

    Not sure, but the whole thing looks so deterministic at first glance that you may not need to do any complexes searches at all and go straight for the optimum number of moves by somehow mapping destinations to closest dots and then resolving conflicts. Then again, these kinds of challenges tend to be full of surprises...

    This is not an exam for some introductory course to programming, more like algorithms or some other advanced stuff? How come you have no idea?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by anon View Post
    This is not an exam for some introductory course to programming, more like algorithms or some other advanced stuff? How come you have no idea?
    Most likely because he's always asking people on various web forums to solve everything for him

    Seriously, I haven't seen a scrap of code posted yet, so don't expect the slightest bit of help from many us of.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    By the who told you all i am from an introductory course? I am studying Master of Science in Computer Science! This is my assignment out of many like this! As I did not crack this type of problem earlier so I wanted your help! Even if I got a slightest clue from you all I would develop the code myself! I wanted the logic only!

    @iMalc
    You call yourself Algorithm Dissector and no help in this topic. Moreover you are pinching on me. I wanted the logic not any code. If I have the logic I can do the program quite well! The logic which I have thought is of high time complexity! Thats why I wanted to find out a smarter algorithm with lower complexity!

    @anon
    Well thanks, let me proceed with your logic. This is my Msc assignment. Did not apply this type of tricky game logic earlier. So if I get a slightest clue I would definitely try the logic myself!

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 20q game problems
    By Nexus-ZERO in forum C Programming
    Replies: 24
    Last Post: 12-17-2008, 04:48 PM
  2. Need book to program game into multiplayer...
    By edomingox in forum Game Programming
    Replies: 3
    Last Post: 10-02-2008, 09:26 AM
  3. Battleship Game (Win32 EXP Needed)
    By ElWhapo in forum Projects and Job Recruitment
    Replies: 2
    Last Post: 01-15-2005, 09:10 PM
  4. HELP!wanting to make full screen game windowed
    By rented in forum Game Programming
    Replies: 3
    Last Post: 06-11-2004, 04:19 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21