11376 - Tilt!

CMG · Post by **CMG** » Mon Dec 31, 2007 5:39 am

Interesting read on wiki. Ill see if I can't figure out how to implement such a system. If not I might have to ask for some more help

Observer · Post by **Observer** » Mon Dec 31, 2007 5:58 am

I search in Google and find this paper:
https:// drum.umd.edu/dspace/bitstream/1903/702/2/CS-TR-3420.pdf
(I don't want to be accused of "deep-linking", so I break up the link above with a space. Sorry.)

You can find a pseudocode of IDA* on page 5.

(My own IDA* handles "z' = infinity" somewhat differently.)

CMG · Post by **CMG** » Mon Dec 31, 2007 6:26 am

Thanks for the article. Always nice to learn something new, not the greatest expert in CS. More of a hobby

Observer · Post by **Observer** » Mon Dec 31, 2007 6:41 am

My major subject is also not Computer Science la...

Programming is a great hobby~

CMG · Post by **CMG** » Mon Dec 31, 2007 11:31 pm

Ok I have a decent understanding of how A* works. Another helpful site I found was http://www.policyalmanac.org/games/aStarTutorial.htm . The problem I am having now is figuring out how to use it for multiple goals, which I don't see being easy to do.

mf · Post by mf » Mon Dec 31, 2007 11:47 pm

You don't have to modify the A* algorithm in any way for multiple goals. Just make sure that your heuristic is still admissible in this case (doesn't overestimate the distance to the closest goal state), and everything should work fine.

Alternatively, you can look at the problem in the following way. Let's add an extra move to the game: if all blue squares are taken, then you're allowed to remove the ball off the maze. The new state, corresponding to the ball after it has been removed, will be the new, unique goal state.

Darko · Post by **Darko** » Wed Jan 02, 2008 6:23 am

BFS is enough for this particular problem. I was thinking of using "meet-in-the-middle" if my solution timed out, but it didn't. I might try it just to see if it can catch up to mf's solution.

Observer · Post by **Observer** » Wed Jan 02, 2008 7:01 am

I don't have a BFS judge solution. But I think heuristic search is not so hard to code for this problem. And such an idea is also not hard to come up with. Of course, to get a better timing for this particular problem, you can add the heuristic function to your BFS, since it is given that you won't need >53 steps for each case.

If one is thinking of using "meet-in-the-middle" (which is by no means easy to code), then I think they'd better try heuristic searches... But it is always fun experimenting with different approaches~

Darko · Post by **Darko** » Wed Jan 02, 2008 7:47 am

In this case "meet-in-the-middle" doesn't work. At least for me it doesn't.

I seem to be doing something wrong (printing?) but, regardless, I don't think you can gain much going backwards. I realized I needed some sort of heuristic going the other way

CMG · Post by **CMG** » Wed Jan 02, 2008 8:36 am

Well I improved upon my program, and made a BFS solution that can solve the 53 step maze in ~11s. Not sure if Ill be able to improve it without fully understanding how to add the hueristic function into my program without killing it

(I have tried adding some hueristic but so far it doesn't work in my program)

EDIT: Thanks to help from Darko I got my program accepted

I might try and work on a hueristic approach now. I also made a c++ version, which runs slightly faster than the java version.

Observer · Post by **Observer** » Fri Jan 04, 2008 3:34 pm

I think it is about time for me to change the test cases a bit. As you may guess the 53-step maze mentioned in previous posts can be found in the judge input.

So I think I need to change the input file so future solvers cannot cheat.

Jan · Post by **Jan** » Fri Jan 04, 2008 7:43 pm

First of all, thanks for the nice set! And I specially liked this problem very much. But a complain

. Why this line was added?

All except two test cases can be solved within 35 steps. One of the two harder cases takes at least 49 steps to solve, and the other 53.

It could be...

There is no case which takes more than 53 steps.

Thanks again...

rio · Post by **rio** » Sat Jan 05, 2008 4:40 am

I got AC using BFS. I also tried IDA*, but couldn't find a strictly enough heuristic to avoid TLE.
How could I get a good heuristic for this problem ?

Thanks in advance.
-----
Rio

CMG · Post by **CMG** » Sat Jan 05, 2008 8:09 am

I also tried but the hueristic I came up with only reduced the end node count by about 3%. Not enough to improve time by much, specially since it takes extra implementation to add in the hueristic.

CMG · Post by **CMG** » Tue Jan 08, 2008 4:18 am

Kinda weird, but my code keeps getting RTE now. I have changed my code to make it A*, and im fairly certain it works. Has the input set changed at all? And if it has is there an error in it? Can you guys submit again to see if you get RTE as well?