11163 - Jaguar King

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

11163 - Jaguar King

Post by paulmcvn » Mon Jan 22, 2007 4:02 pm

Could anyone give me an idea for this problem?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Re: 11163 Jaguar King

Post by Per » Wed Jan 24, 2007 10:09 pm

paulmcvn wrote:Could anyone give me an idea for this problem?
I used IDA* search. The judge I/O is very kind, there are many cases where my solution is hopelessly slow.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Thu Jan 25, 2007 5:23 pm

Could you please post links with more info about IDA*? it is kind of a hard one to find in google.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Jan 25, 2007 5:31 pm

I haven't attempted this problem, but the idea is pretty much the same as an old problem called "Constrained Exchange Sort" (can't remember the number). Or maybe 15-puzzle. The key is to find a good heuristic function h(x). I think it shouldn't be hard.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Thu Jan 25, 2007 5:35 pm

first problem I get into where I have to use heuristics, awesome, anyways thanks. Now that I think about it a good heuristic is possible because of the pretty odd jump rules.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Jan 25, 2007 5:37 pm

I think something like the famous "Manhattan distance" (as in solving 15-puzzle) should do.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Jan 26, 2007 6:50 am

Oh... my IDA* gets TLE... :wink: Manhattan distance isn't very good in some cases......

What good heuristics do you guys have? How long does your program take to solve the following cases?

Code: Select all

12
1 11 12 10 9 8 7 6 5 4 3 2
16
9 11 12 10 5 8 7 6 13 4 3 2 1 14 15 16
28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27
40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27 29 30 31 32 33 34 35 36 38 37 40 39
0
Thanks.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Jan 26, 2007 7:37 am

I used IDA* with Manhattan distance.

For your test case 1 ~ 3, my code takes 0.125 sec, and doesn't come back with the 4th case.
The 4th test case might be invalid(not reachable from init sequence), or just a hard case.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Jan 26, 2007 8:33 am

Thank you.

I think the 4-th case is valid, since the following case is solvable:

Code: Select all

8
1 2 3 4 6 5 8 7
I think your program must be very well optimized. My third case (with N = 28) should give Manhattan distance = 4, which is waaaay less than the minimum number of moves... Or do you also consider the moves the "king" shall take to reach the "wrongly placed ones" in your heuristic function?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Jan 26, 2007 9:04 am

I think your program must be very well optimized. My third case (with N = 28 ) should give Manhattan distance = 4, which is waaaay less than the minimum number of moves... Or do you also consider the moves the "king" shall take to reach the "wrongly placed ones" in your heuristic function?
I'm not considering the move of king (becuase it becomes very complex). I also got Manhattan distance = 4 for the 3rd case, so I think our heuristic function is same.

So I think the problem is in your IDA* implementation.
Heres the optimization I did. If you haven't tried yet, I think its worth trying.

1.If the kings position moved from a to b, don't move back (b to a) at the next step.
2.Don't calculate the whole heuristic value every time. Just calculate the difference.

ADD : If you feel my post SPOILic, tell me. I'll edit it.
----
Sory for my poor English..

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Jan 26, 2007 2:24 pm

Yes, there were some flaws in my old code, so it didn't work as I expected... I've got Accepted. Thanks~ :D

Right now my code doesn't have the "optimizations" you mentioned implemented well, so my runtime is slow (> 3 sec). Will try to improve that. :P
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Feb 14, 2007 10:39 am

I think I don't understand how to use manhattan distance heristic properly as I'm getting non optimal solutions.

consider

Code: Select all

4
4 2 3 1
If I use the definition of manhattan distance, then it is |4-1|+|2-2|+|3-3|+|1-4|, which is 6, and it is much over the optimal solution.

I think I need to modify it so that I don't count the king, and that I allow for steps of size at most 4 in one move, but it makes the heristic too complicated.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Feb 14, 2007 11:40 am

You could think this problem as a cylindrical 4xN puzzle.
One roll has four pieces.

Numbering the position from 0 :
Position 0 adjacents to 1(same roll), 3(same roll) and 4(adjacent roll).
Position 5 adjacents to 4(same roll), 6(same roll), 1(adjacent roll) and 9(adjacent roll).

The Manhattan distance of position i, j could be defined as below.

Code: Select all

int Md(int i, int j) {
   int a = abs(i/4 - j/4);   // need moves to the same roll
   int b = abs(i%4 - j%4);
   if (b == 3) b = 1;  // in the same roll, distance 3 == 1,
   return a + b;
}
I didn't calculated the kings Manhattan distance as I didn't calculate the Manhattan distance of the hole in 15-puzzle.
----
It is too hard to explain this problem with my poor English. I hope you understand my English.
ADD: Am I SPOILing ? If you feel so, tell me. I'll edit my post.

Rings
New poster
Posts: 3
Joined: Sat Aug 09, 2008 1:01 pm

Re:

Post by Rings » Mon Dec 08, 2008 4:09 pm

Observer wrote:Oh... my IDA* gets TLE... :wink: Manhattan distance isn't very good in some cases......

What good heuristics do you guys have? How long does your program take to solve the following cases?

Code: Select all

12
1 11 12 10 9 8 7 6 5 4 3 2
16
9 11 12 10 5 8 7 6 13 4 3 2 1 14 15 16
28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27
40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27 29 30 31 32 33 34 35 36 38 37 40 39
0
Thanks.
I got WA...
Who can give me these tests' answers,I need help...


EDIT: I find a mistake,AC now.

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

Re: 11163 - Jaguar King

Post by shiplu_1320 » Fri Aug 20, 2010 9:45 pm

I am getting WA.
Please someone give the answers of these test case , stated above.

Thanx in advance.:)

Edit: ACCEPTED.
A learner......

Post Reply

Return to “Volume 111 (11100-11199)”