Page 1 of 2

10704 - Traffic!

Posted: Mon Aug 30, 2004 9:09 am
by liulike
It seems a search problem . But how to save status?

:roll:

Posted: Mon Aug 30, 2004 10:06 am
by alex[LSD]
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 tree-like 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
*       *
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. :D

Posted: Tue Aug 31, 2004 7:32 am
by LittleJohn
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

Posted: Tue Aug 31, 2004 8:30 am
by alex[LSD]
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!!! :D
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! :lol:

Posted: Wed Sep 01, 2004 6:01 pm
by ..
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
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:
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.

Posted: Thu Sep 02, 2004 9:01 am
by alex[LSD]
Well in my tree the height is always equal to the number of blocks (if we measure the height in edges).

10704 - Traffic!

Posted: Tue Sep 07, 2004 3:27 pm
by Lijiganjun
Please give me some testdata ,3x!

Posted: Wed Sep 15, 2004 5:29 pm
by alex[LSD]
For me, only this case is worth mentioning
1
0 4
0
0
0
0

The answer is 1 8)

Posted: Tue Oct 05, 2004 10:24 pm
by Krzysztof Duleba
Could you tell me what's wrong with my output? Are there any special cases?
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
Output:
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.

Posted: Tue Oct 05, 2004 10:47 pm
by little joey
My program replies:

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

Posted: Wed Oct 06, 2004 12:21 am
by Krzysztof Duleba
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?
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
Output:
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

Posted: Wed Oct 06, 2004 7:45 am
by little joey
Krzysztof Duleba wrote:How do you know that left exit is illegal? There is nothing about it in the problem statement :-(
You are right about that, although the arrow in the picture is pointing right.
Your output is the same as mine.

Posted: Wed Oct 06, 2004 11:48 am
by Krzysztof Duleba
I've just found my mistake. In BFS, I only moved vertical and horizontal blocks, but never the white one. Now I got AC - thanks for help.

Posted: Sun Sep 30, 2007 5:18 am
by Mr.south
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

Posted: Mon Mar 03, 2008 10:54 pm
by Jan
Mr.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
(1) Yes
(2) I tried all possible moves at each step.
(3) No idea. But I think it can be.
(4) No.