ACM PKU Eight Puzzle

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

ACM PKU Eight Puzzle

Post by fushar » Tue Apr 21, 2009 10:18 am

http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
For anyone that has got accepted in this problem, please help me! I got WAs so many... what else I might miss? I just used A* with priority_queue. It works for all TC I created myself....

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: ACM PKU Eight Puzzle

Post by mf » Tue Apr 21, 2009 12:39 pm

Just do a simple breadth-first search.

You can find some I/O from the original ACM contest here:
http://www.acm.inf.ethz.ch/ProblemSetAr ... hCen/1998/

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: ACM PKU Eight Puzzle

Post by fushar » Tue Apr 21, 2009 12:50 pm

DId you mean that I should do BFS from final state to ALL reachable states?
Oh one more, how did you mark a state as visited?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: ACM PKU Eight Puzzle

Post by mf » Tue Apr 21, 2009 12:55 pm

fushar wrote:DId you mean that I should do BFS from final state to ALL reachable states?
There's only about 9!/2 = 181440 reachable states. 1 second is more than enough time to check them all.
Oh one more, how did you mark a state as visited?
Convert permutation into an integer in any way, and store them in std::set<int>.
(Or a boolean array, if you're not lazy, and the range of integers is small enough)

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: ACM PKU Eight Puzzle

Post by fushar » Tue Apr 21, 2009 1:03 pm

Oh, I see. So if the queried state is not visited, then I should output "unsolvable". Right?
Anyway thanks for your help. I'll try to recode my solution. :wink:

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: ACM PKU Eight Puzzle

Post by fushar » Tue Apr 21, 2009 1:24 pm

Uh, I just used plain BFS without heuristic, and got TLE....

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: ACM PKU Eight Puzzle

Post by mf » Tue Apr 21, 2009 1:35 pm

My old BFS solution for UVa's problem 652 gets accepted at pku, running 0.438 seconds.

It doesn't use STL, though as I was coding in C - it converts each permutation into its sequential number (from 0 to 9!-1) and uses a boolean array to mark visited states.

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: ACM PKU Eight Puzzle

Post by fushar » Tue Apr 21, 2009 1:40 pm

How did you do the conversion?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: ACM PKU Eight Puzzle

Post by mf » Tue Apr 21, 2009 2:05 pm

Like this:

Code: Select all

int fact[10];  // a table of factorials

int encode(int a[9]) {
	int c[10], i, k, r;
	for (i = 0; i < 9; i++) c[i] = i;
	for (r = 0, k = 0; k < 9; k++) {
		r += c[a[k]] * fact[8 - k];
		for (i = a[k]; i < 9; i++) c[i]--;
	}
	return r + 1;
}

void decode(int a[9], int r) {
	int c[10], i, k;
	for (i = 0; i < 9; i++) c[i] = i;
	for (r--, k = 0; k < 9; k++) {
		i = r / fact[8 - k];
		r %= fact[8 - k];
		a[k] = c[i];
		for (; i < 9; i++) c[i] = c[i + 1];
	}
}

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: ACM PKU Eight Puzzle

Post by fushar » Tue Apr 21, 2009 2:34 pm

Hey thank you so much.......!!!!!

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: ACM PKU Eight Puzzle

Post by fushar » Tue Apr 21, 2009 4:17 pm

I'm so tired getting WAs, what's wrong with my code?

Code: Select all

Deleted AC code
Last edited by fushar on Tue Apr 21, 2009 5:23 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: ACM PKU Eight Puzzle

Post by mf » Tue Apr 21, 2009 5:04 pm

Your program prints \0 character at the beginning of output:

Code: Select all

user@localhost:/tmp$ g++ -o p p.cc && ./p >output
2 3 4 1 5 x 7 6 8
user@localhost:/tmp$ hexdump -C output 
00000000  00 75 6c 6c 64 64 72 75  72 64 6c 6c 75 72 64 72  |.ullddrurdllurdr|
00000010  75 6c 64 72 0a                                    |uldr.|
00000015
user@localhost:/tmp$

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: ACM PKU Eight Puzzle

Post by fushar » Tue Apr 21, 2009 5:17 pm

What a silly bug..
Just changed

Code: Select all

if (x != -2)
	{
		trace(P[x]);
		printf("%c", M[x]);
	}
to

Code: Select all

if (P[x] != -2)
	{
		trace(P[x]);
		printf("%c", M[x]);
	}
and got AC!!!!!!!
Thanks mf!!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: ACM PKU Eight Puzzle

Post by Angeh » Tue Sep 01, 2009 1:04 am

mf wrote:Like this:

Code: Select all

int fact[10];  // a table of factorials

int encode(int a[9]) {
	int c[10], i, k, r;
	for (i = 0; i < 9; i++) c[i] = i;
	for (r = 0, k = 0; k < 9; k++) {
		r += c[a[k]] * fact[8 - k];
		for (i = a[k]; i < 9; i++) c[i]--;
	}
	return r + 1;
}

void decode(int a[9], int r) {
	int c[10], i, k;
	for (i = 0; i < 9; i++) c[i] = i;
	for (r--, k = 0; k < 9; k++) {
		i = r / fact[8 - k];
		r %= fact[8 - k];
		a[k] = c[i];
		for (; i < 9; i++) c[i] = c[i + 1];
	}
}
is this a Known Algorithm? can you explain more why to code like this ?:)
Last edited by Angeh on Wed Sep 02, 2009 12:17 am, edited 1 time in total.
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

User avatar
fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: ACM PKU Eight Puzzle

Post by fushar » Tue Sep 01, 2009 1:18 am

It's just a simple algorithm to convert a permutation into its index (from 0 to 9!-1) and vice versa.

Post Reply

Return to “Other words”