10704 - Traffic!

[liulike]

It seems a search problem . But how to save status?

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

[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

[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!!!
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!

[..]

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.

[alex[LSD]]

Well in my tree the height is always equal to the number of blocks (if we measure the height in edges).

[Lijiganjun]

Please give me some testdata ,3x!

[alex[LSD]]

For me, only this case is worth mentioning
1
0 4
0
0
0
0

The answer is 1

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

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

[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

[little joey]

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.

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

[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

[Jan]

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.