## 11376 - Tilt!

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

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### 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 : )...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
This problem is quite interesting, but I keep getting RTE and have no clue where the problem is. Anyone provide good i/o?

EDIT: Question are the grids square? The problem doesn't exactly specify if the grid is a square one.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
CMG wrote:Question are the grids square? The problem doesn't exactly specify if the grid is a square one.
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
RTE might be caused by looking for walls when there are none?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
If you mean the size of the maze, then it is N * N, with 2 <= N <= 10, as explained in the problem statement.
It isn't explained anywhere.
It's only hinted at in the constraint on blue squares' coordinates, but it'd better be more explicit than that.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Oh yes, I forgot to mention that the maze is a square... So I should have instead:
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

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
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:

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
``````
My code took around 8 minutes to find the answer.

Code: Select all

``````ENWSESEWSWNENENESESNWSWSEWNWSWNWNESWSESENWNSENWSWSESW
``````
But when I do:

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
``````
This runs under 0.05s

Code: Select all

``````NWNSENESWNSESNWNEWSEWNE
ESENWNEWSES
ESWNENWSE
``````
Last edited by CMG on Mon Dec 31, 2007 1:34 am, edited 3 times in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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.
Last edited by mf on Mon Dec 31, 2007 1:42 am, edited 1 time in total.

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
The maze for the first case is as follows. Is (5,9) in reference from 0 to N-1 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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Row 5, column 9, 1-based.

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
``````
I get the output "ENWSESEWSWNENENESESNWSWSEWNWSWNWNESWSESENWNSENWSWSESW" in 0.7 seconds.

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
I went ahead and edited my post swaping the points on all inputs Guess that was one place I messed up in on reading the problem. Ill have to put more thought into saving states I just don't know exactly the best way to do it.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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^2-1), and a bitmask of visited squares (0..2^25-1).

You can futher pack both of them into a single 32-bit integer, because they need 7 and 25 bits, which is 32 in total. That's what I used as a key for std::map.

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
Ok that makes some sense, but then how do you check that at a certain point its worthwhile to continue on, or maybe I don't quite understand your algorithm.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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* (iterative-deepening A*). Basically, it consists of a few iterations, each of which is a simple depth-first 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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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*.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org