11376  Tilt!
Moderator: Board moderators
11376  Tilt!
I just put the clarification notice (pls refer to contest clarification board) here.

Coordinates of each blue square are given on a separate line, i.e. one line with two numbers for a square.

The problem description in online judge will probably be changed later.
I'm sorry for my mistake. This task is written several years ago (I know it is not an excuse, but : )...

Coordinates of each blue square are given on a separate line, i.e. one line with two numbers for a square.

The problem description in online judge will probably be changed later.
I'm sorry for my mistake. This task is written several years ago (I know it is not an excuse, but : )...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Sorry, I don't really understand your question. If you mean the size of the maze, then it is N * N, with 2 <= N <= 10, as explained in the problem statement.CMG wrote:Question are the grids square? The problem doesn't exactly specify if the grid is a square one.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Oh yes, I forgot to mention that the maze is a square... So I should have instead:
[EDIT] I have sent the admins another mail containing the modified problem description HTML file.
I shall ask the admins to add that. Thanks.There are then N lines, each with N hexadecimal numbers, representing the line pattern of each cell.
[EDIT] I have sent the admins another mail containing the modified problem description HTML file.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Thanks for clarifying. I fixed the RTE, but with a case I found on the net my code takes way to much time to solve. It does fine with mazes with only a few blue squares but has trouble with a high amount of blue squares.
If any of you have a tips on how to optimize the search I would love to hear it. I use backtracking starting at the red ball and try the directions E,N,S,W when possible and when the ball stops moving in that direction I repeat that process. As the ball moves I set the direction bit at that point and set the opposite direction bit as well for every point after the initial one. And like I said this works great for cases with small amounts of blue squares. The case that tricked me up is as follows:
My code took around 8 minutes to find the answer.
But when I do:
This runs under 0.05s
If any of you have a tips on how to optimize the search I would love to hear it. I use backtracking starting at the red ball and try the directions E,N,S,W when possible and when the ball stops moving in that direction I repeat that process. As the ball moves I set the direction bit at that point and set the opposite direction bit as well for every point after the initial one. And like I said this works great for cases with small amounts of blue squares. The case that tricked me up is as follows:
Code: Select all
10
9C9C9A8C9C
12410A0204
3C100C1865
9061004184
5180610245
1453841A06
3008020C5D
9041080024
12006530C5
3A26B2A226
5 6
4 1
8 1
2 2
6 2
9 2
3 3
10 3
1 4
4 4
7 4
5 5
9 5
3 6
8 6
6 7
10 7
1 8
4 8
7 8
3 9
9 9
1 10
5 10
8 10
0
Code: Select all
ENWSESEWSWNENENESESNWSWSEWNWSWNWNESWSESENWNSENWSWSESW
Code: Select all
8
9A88CB8C
18610824
30804184
90430004
10080457
1430000C
53800245
3A263A26
6 4
4 1
8 1
2 2
7 3
4 4
1 5
7 5
5 6
3 7
8 7
2 8
4 8
6
98E98E
30A00C
908047
10430C
710804
B63677
4 1
1 3
3 6
5
9AC9C
18006
5120C
12806
3A63E
1 1
5 5
0
Code: Select all
NWNSENESWNSESNWNEWSEWNE
ESENWNEWSES
ESWNENWSE
Last edited by CMG on Mon Dec 31, 2007 1:34 am, edited 3 times in total.
Hmm, my program crashes (due to an assert()) on your inputs because it can't find path from starting position to some squares. In the first input the unreachable square is (5, 9). Are you sure the walls are encoded correctly in your cases?
I used simple IDA* with the obvious heuristic  maximum distance from current position to any yet unvisited square, and also memoized which states and at which depth have been already visited in an std::map. This gets accepted in 0.9 seconds on judge's tests.
I used simple IDA* with the obvious heuristic  maximum distance from current position to any yet unvisited square, and also memoized which states and at which depth have been already visited in an std::map. This gets accepted in 0.9 seconds on judge's tests.
Last edited by mf on Mon Dec 31, 2007 1:42 am, edited 1 time in total.
The maze for the first case is as follows. Is (5,9) in reference from 0 to N1 or 1 to N? Cause I looked over a few of the last encoded lines and they look good.
Code: Select all
_____________________________________________________________
    
  X  X  X 
   _____  
  
 X  
 _____  _____ _____ 
    
  X X  X  
_____   _____ 
   
 X  X  X 
 _____  
    
  X  O  X 
  _____ _____  
    
 X    X 
  _____  _____ _____
   
 X X   
_____ _____   
  
 X  X X 
  _____ 
    
 X X   X  
 _____ _____ _____  
  
 X  X 
__________________________________________________________
Last edited by CMG on Mon Dec 31, 2007 1:28 am, edited 1 time in total.
Row 5, column 9, 1based.
Apparently you have swapped rows and columns in the description of squares. On this input:
I get the output "ENWSESEWSWNENENESESNWSWSEWNWSWNWNESWSESENWNSENWSWSESW" in 0.7 seconds.
Apparently you have swapped rows and columns in the description of squares. On this input:
Code: Select all
10
9C9C9A8C9C
12410A0204
3C100C1865
9061004184
5180610245
1453841A06
3008020C5D
9041080024
12006530C5
3A26B2A226
5 6
4 1
8 1
2 2
6 2
9 2
3 3
10 3
1 4
4 4
7 4
5 5
9 5
3 6
8 6
6 7
10 7
1 8
4 8
7 8
3 9
9 9
1 10
5 10
8 10
0
State is just the current position of the ball, and a bitmask of visited blue squares.
I represented it as a pair of integers  index of current position (between 0 and N^21), and a bitmask of visited squares (0..2^251).
You can futher pack both of them into a single 32bit integer, because they need 7 and 25 bits, which is 32 in total. That's what I used as a key for std::map.
I represented it as a pair of integers  index of current position (between 0 and N^21), and a bitmask of visited squares (0..2^251).
You can futher pack both of them into a single 32bit integer, because they need 7 and 25 bits, which is 32 in total. That's what I used as a key for std::map.
A* algorithm together with the heuristic, which I mentioned above, handles that part. You can read about the algorithm in Wikipedia or any AI book.
I've actually used a variant of A*  IDA* (iterativedeepening A*). Basically, it consists of a few iterations, each of which is a simple depthfirst search which explores all states x such that f(x) = (depth of x) + h(x) <= current iteration's limit, where h(x) is a heuristic estimate of the distance from x to a goal state. If the goal wasn't reached, the next iteration will have a higher limit, equal to min {f(x) : x was reached and f(x) > limit}. Iterations continue until you reach the goal. If h(x) never overestimates the distances, then it can be proved that you'll get a shortest path.
Edit:
in pseudocode it is:
I've actually used a variant of A*  IDA* (iterativedeepening A*). Basically, it consists of a few iterations, each of which is a simple depthfirst search which explores all states x such that f(x) = (depth of x) + h(x) <= current iteration's limit, where h(x) is a heuristic estimate of the distance from x to a goal state. If the goal wasn't reached, the next iteration will have a higher limit, equal to min {f(x) : x was reached and f(x) > limit}. Iterations continue until you reach the goal. If h(x) never overestimates the distances, then it can be proved that you'll get a shortest path.
Edit:
in pseudocode it is:
Code: Select all
int limit, nextLimit;
bool search(state s, int depth) {
h = estimate of distance from s to a "solved" state
if (depth + h > limit) {
nextLimit = min(nextLimit, depth + h);
return false;
} else if (s is a solved state) {
we've found the optimal path, print it and
return true;
} else {
for each possible move s>t, do
if (search(t, depth + 1)) return true;
return false;
}
}
...
nextLimit = 1;
do { limit = nextLimit; nextLimit = infinity; } while (!search(sourceState, 0));
Last edited by mf on Mon Dec 31, 2007 8:46 am, edited 2 times in total.
If you only want to solve the cases in judge input, you need nothing more than just using the heuristic function (mentioned by mf) in your backtracking (you can call that A*), because you are given what the "infinities" are. : )
But if you want your program to solve any tilt mazes, you had better study IDA*.
But if you want your program to solve any tilt mazes, you had better study IDA*.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org