Thread: The Great Wall Game - Help Needed!

1. 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. 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. Actually I am not getting how to approach this type of problems! Please help me!

4. 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. 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. Yes i have tried this long ago! But complexity is too high! Any other short solution please!

7. 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.

8. 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.

9. Originally Posted by anirban
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?

10. No no not a bet!!!!!!!!! Actually this is assignment for exam and I have few days left! That is why!

11. Originally Posted by anirban
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. 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.

13. 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?

14. Originally Posted by anon
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.

15. 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!

Popular pages Recent additions