10704  Traffic!
Moderator: Board moderators
10704  Traffic!
It seems a search problem . But how to save status?

 Learning poster
 Posts: 53
 Joined: Sat Jan 24, 2004 9:22 pm
 Location: Tomsk, Siberia, RUSSIA
 Contact:
I ve solved it yesterday. It's a simple "find the shortest path in graph", but it's tough to implement.
What you have to remember.
1. Every block has its column or row (depending on the type of the block). So to store a status you need to remember at most 18 numbers in the range [0..4] (there cant be more than 18 blocks). Plus, you need to remember the "weight" of the situation, its just one more integer.
2. The most interesting part for me was the structure that helps me find out weather a situation has already occured (therefore it shouldn't be considered). I used a treelike structure for that. Lets say we have 3 blocks, and we've encountered only two situations : (0,2,4) and (0,2,2). the tree will look like this :
If you come to the end of the tree the situation is not interesting, otherwise it is.
Hope this helps. I can also send my Pascal solution. Good Luck.
What you have to remember.
1. Every block has its column or row (depending on the type of the block). So to store a status you need to remember at most 18 numbers in the range [0..4] (there cant be more than 18 blocks). Plus, you need to remember the "weight" of the situation, its just one more integer.
2. The most interesting part for me was the structure that helps me find out weather a situation has already occured (therefore it shouldn't be considered). I used a treelike structure for that. Lets say we have 3 blocks, and we've encountered only two situations : (0,2,4) and (0,2,2). the tree will look like this :
Code: Select all
*

0
*

2
*
/ \
2/ \4
* *
Hope this helps. I can also send my Pascal solution. Good Luck.
The more contests are held, the happier I am.

 Learning poster
 Posts: 83
 Joined: Wed Feb 27, 2002 2:00 am
 Location: Taiwan

 Learning poster
 Posts: 53
 Joined: Sat Jan 24, 2004 9:22 pm
 Location: Tomsk, Siberia, RUSSIA
 Contact:
No I never proved an upper bound. When I think of a 6x6 field I just don't believe that there is A WHOLE LOT of possible situations.
But since you asked me about it and its an interesting question, let's put it this way:
1. there are 12 lines in total, vertical and horizontal.
2. we can put 1 block in a line 5 different ways
we can put 2 blocks in a line 6 different ways
we can put 3 blocks in a line 1 different way
My rough upper bound 6^12 = 2176782336. But we must realize that two blocks in one line don't give much space for others to move around. Just think 12*2*2=48 cells occupied by our imaginary blocks. And the field is only 6*6=36!!!
And if we have one block in a line we get 5^12 = 24 million. Which is almost REAL.
P.S. You can write a recursive program and COUNT THEM ALL!
But since you asked me about it and its an interesting question, let's put it this way:
1. there are 12 lines in total, vertical and horizontal.
2. we can put 1 block in a line 5 different ways
we can put 2 blocks in a line 6 different ways
we can put 3 blocks in a line 1 different way
My rough upper bound 6^12 = 2176782336. But we must realize that two blocks in one line don't give much space for others to move around. Just think 12*2*2=48 cells occupied by our imaginary blocks. And the field is only 6*6=36!!!
And if we have one block in a line we get 5^12 = 24 million. Which is almost REAL.
P.S. You can write a recursive program and COUNT THEM ALL!
The more contests are held, the happier I am.
I use hashing to solve this problem. I think it is possible to assume the tree will not grow up so rapidly. The argument is like this:LittleJohn wrote:Hi alex,
In the worst case, there're roughly 5^18=3814697265625 states. Did you assume that the tree will not grow up so rapidly, or you have proved an upper bound?
Thanks
If there are a few blocks in the board, there are many possible move at each step. However, if the number of blocks is small, it should require small number of step to solve the puzzle, that is, the height of tree should be small.
If there are many number of blocks, although number of step is large, there are few possible move at each step. The number of state visited should be small in both case.
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.

 New poster
 Posts: 5
 Joined: Tue Dec 16, 2003 4:10 pm
 Location: China
 Contact:
 Krzysztof Duleba
 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
Could you tell me what's wrong with my output? Are there any special cases?
Output:13
4 1
4 0 1 0 2 4 3 0 0
1 3 0
6 3 2 1 3 2 1 2 3 0 3 5 1
0
4 1
1 4 0
0
6 3 0 5 2 4 3 0 0 0 2 3 2
2 1 0 2 2
1 1
2 1 3 1 0
0
3 4 1 3 0 2 1
3 0 1 3 2 5 1
2 1
1 3 1
1 1 0
4 0 3 0 1 2 3 3 3
1 5 1
0 1
2 0 3 4 3
1 0 0
4 4 0 5 1 3 3 1 1
2 3 0 2 2
3 1
3 4 2 1 3 2 0
0
5 0 1 3 3 4 0 4 3 5 3
1 1 0
4 1
0
1 3 0
4 1 0 2 2 3 1 4 3
2 1 2 5 2
1 1
1 1 3
3 0 0 3 1 3 0
4 4 3 3 2 2 1 0 2
1 5 2
4 2
0
1 0 0
4 3 2 5 3 1 3 3 0
2 2 1 0 2
5 1
3 1 3 1 0 0 2
1 3 0
1 5 3
1 3 2
2 1
1 2 3
1 0 0
3 0 1 4 2 5 1
2 1 2 3 0
4 2
0
0
0
0
4 1
3 4 3 3 0 1 0
0
4 0 0 3 3 0 2 1 2
2 2 1 5 0
The minimal number of moves to solve puzzle 1 is 4.
The minimal number of moves to solve puzzle 2 is 4.
The minimal number of moves to solve puzzle 3 is 4.
The minimal number of moves to solve puzzle 4 is 2.
The minimal number of moves to solve puzzle 5 is 4.
The minimal number of moves to solve puzzle 6 is 5.
The minimal number of moves to solve puzzle 7 is 4.
The minimal number of moves to solve puzzle 8 is 3.
The minimal number of moves to solve puzzle 9 is 1.
The minimal number of moves to solve puzzle 10 is 3.
The minimal number of moves to solve puzzle 11 is 3.
The minimal number of moves to solve puzzle 12 is 1.
The minimal number of moves to solve puzzle 13 is 5.
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
My program replies:
Where "NOT FOUND" is the unofficial reply it gives when it finishes the BFS without finding the exit.
In studying your second case, you either exit the field on the left side, or let another car exit first. Both are illegal.
Haven't looked at your other cases.
Code: Select all
The minimal number of moves to solve puzzle 1 is 4.
NOT FOUND
NOT FOUND
NOT FOUND
The minimal number of moves to solve puzzle 5 is 7.
NOT FOUND
NOT FOUND
The minimal number of moves to solve puzzle 8 is 3.
The minimal number of moves to solve puzzle 9 is 1.
NOT FOUND
The minimal number of moves to solve puzzle 11 is 3.
The minimal number of moves to solve puzzle 12 is 1.
The minimal number of moves to solve puzzle 13 is 7.
In studying your second case, you either exit the field on the left side, or let another car exit first. Both are illegal.
Haven't looked at your other cases.
 Krzysztof Duleba
 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
Thank you for reply. How do you know that left exit is illegal? There is nothing about it in the problem statement
Anyway, I changed my code to fit it to your output, but still no luck. Are there any special cases? What about those?
Anyway, I changed my code to fit it to your output, but still no luck. Are there any special cases? What about those?
Output:19
2 1
2 4 3 0 0
0
6 0 1 3 3 5 0 3 1 4 0 2 3
1 1 2
2 1
3 0 2 0 0 2 3
0
2 3 0 4 2
0
2 1
1 2 3
1 3 1
2 5 2 4 2
0
4 1
2 4 0 4 3
2 1 0 0 1
2 1 2 3 3
1 0 2
2 1
2 3 0 2 3
1 3 1
0
1 1 0
2 1
1 0 3
0
3 0 1 2 3 3 0
3 3 2 5 2 4 1
1 1
4 3 3 1 0 4 2 1 3
1 3 1
0
0
0 1
1 3 3
1 1 0
6 0 3 5 1 1 3 3 1 2 3 4 1
0
4 1
2 0 2 3 0
2 0 1 0 0
1 4 3
0
3 1
3 2 3 4 1 4 2
1 3 0
2 1 0 2 1
1 0 1
5 1
5 0 3 3 3 4 0 0 1 0 2
1 0 0
3 2 3 4 1 5 3
1 3 0
2 1
3 3 1 2 3 3 0
1 0 0
5 1 2 0 3 5 1 0 1 5 3
1 4 2
3 1
1 1 2
2 2 0 0 1
5 3 3 0 2 2 3 1 3 5 1
1 4 2
4 1
0
1 2 0
1 4 3
1 0 2
4 1
0
0
3 4 3 3 2 1 1
1 2 1
4 1
2 1 1 0 0
1 2 0
5 1 3 5 1 4 3 3 2 2 2
1 0 1
2 1
1 2 3
1 3 1
2 0 0 1 0
1 1 2
0 1
3 2 0 1 3 3 2
1 3 1
5 2 1 4 3 1 1 5 3 0 3
0
0 1
1 1 1
1 1 0
1 0 3
5 3 1 1 2 5 1 2 2 4 2
NOT FOUND
The minimal number of moves to solve puzzle 2 is 2.
The minimal number of moves to solve puzzle 3 is 2.
The minimal number of moves to solve puzzle 4 is 3.
The minimal number of moves to solve puzzle 5 is 2.
NOT FOUND
The minimal number of moves to solve puzzle 7 is 3.
NOT FOUND
NOT FOUND
The minimal number of moves to solve puzzle 10 is 2.
NOT FOUND
The minimal number of moves to solve puzzle 12 is 4.
NOT FOUND
NOT FOUND
NOT FOUND
NOT FOUND
The minimal number of moves to solve puzzle 17 is 2.
NOT FOUND
NOT FOUND
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
 Krzysztof Duleba
 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
I got some problem from 10704
(1). is the exit always at right side?
(2). when you use BFS, do you use the branch :
1 position to the right, 2 positions to the right, or 3 positions to the right
or
you directly move the block to the bottom?
(3). Is there exist any solution that I need to move a block more than twice?
(4). you told that in your WA case you never move the white block, is the white block only moved at the last step?
thanks for answering my question
(1). is the exit always at right side?
(2). when you use BFS, do you use the branch :
1 position to the right, 2 positions to the right, or 3 positions to the right
or
you directly move the block to the bottom?
(3). Is there exist any solution that I need to move a block more than twice?
(4). you told that in your WA case you never move the white block, is the white block only moved at the last step?
thanks for answering my question
(1) YesMr.south wrote:I got some problem from 10704
(1). is the exit always at right side?
(2). when you use BFS, do you use the branch :
1 position to the right, 2 positions to the right, or 3 positions to the right
or
you directly move the block to the bottom?
(3). Is there exist any solution that I need to move a block more than twice?
(4). you told that in your WA case you never move the white block, is the white block only moved at the last step?
thanks for answering my question
(2) I tried all possible moves at each step.
(3) No idea. But I think it can be.
(4) No.