10704 - Traffic!

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

Moderator: Board moderators

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

10704 - Traffic!

Post by liulike » Mon Aug 30, 2004 9:09 am

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

:roll:

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Mon Aug 30, 2004 10:06 am

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
The more contests are held, the happier I am.

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

Post by LittleJohn » Tue Aug 31, 2004 7:32 am

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]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Tue Aug 31, 2004 8:30 am

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:
The more contests are held, the happier I am.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Wed Sep 01, 2004 6:01 pm

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

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Thu Sep 02, 2004 9:01 am

Well in my tree the height is always equal to the number of blocks (if we measure the height in edges).
The more contests are held, the happier I am.

Lijiganjun
New poster
Posts: 5
Joined: Tue Dec 16, 2003 4:10 pm
Location: China
Contact:

10704 - Traffic!

Post by Lijiganjun » Tue Sep 07, 2004 3:27 pm

Please give me some testdata ,3x!
Hello ,everyone!

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Wed Sep 15, 2004 5:29 pm

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

The answer is 1 8)
The more contests are held, the happier I am.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Oct 05, 2004 10:24 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Oct 05, 2004 10:47 pm

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Oct 06, 2004 12:21 am

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Oct 06, 2004 7:45 am

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Oct 06, 2004 11:48 am

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
New poster
Posts: 11
Joined: Thu Jan 25, 2007 1:45 pm

Post by Mr.south » Sun Sep 30, 2007 5:18 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Mar 03, 2008 10:54 pm

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.

Post Reply

Return to “Volume 107 (10700-10799)”