coordinate compression/graph reduction

[keepjumpin]

Hello. I'm trying to find information about how to reduce/compress a graph. The reason I want to do this is that the graph has potential to become quite large and I will need to search the entire thing which, without compression could take a while. Any help will be appreciated. Thanks

[magnificence7]

By graph, I think what you mean is, series of x and y values? I don't know why you would use compression to make you search faster. Maybe you can use a different data representation to speed up a certain process, probably like searching in your case. But we need to know how your data representation is like and what the process that you want to speed up is and how it works.

[keepjumpin]

I have a 2 dimensional array which represents say, an obstacle course. Some of the cells contain walls. A vehicle on the course can only move north and east in order to get to the exit which is in the north east corner. My goal is to analyze the course and determine how many cells will cause the vehicle to get stuck because of walls. I've read a few discussions about this problem and they've all mentioned using coordinate compression to reduce the size of the graph before counting the stuck squares. A possible solution I'm looking at is going through the grid recursively, starting at the exit, checking west and south, adding open cells to a queue, check their west and south neighbors and so forth until I've checked all the open cells. The potential number of rows >= 1, cols <= 10^6, walls <= 1000. This problem is from the 2010 acm international collegiate programming contest world finals.

I'm currently working on a different solution all together where I'm looking at only the wall intersections to determine the number of stuck squares. I am still interested in learning about coordinate compression. I hope things are more clear now. Thanks

[ne555]

If you can't reach a cell, does it count as an stuck square?

I think that you can "compress" the data like this:
1) Imagine that the sun is in the south. Look at the shadows of the obstacles in the north wall.
2) Imagine that the sun is in the west. Look at the shadows of the obstacles in the east wall.

You need to compute the area only where exists shadow that is adjacent with the last column/row. And you need to subtract the obstacles that are inside that area.

Especial case: a wall in the exit invalidates the entire room A path that connects the east and north walls, that invalidates everything except the area that encloses.

[kfmfe04]

Well, I would look at the problem in two steps.

1. Understand the problem and come up with an algorithm that should work, theoretically.
2. Find a more efficient algorithm.

Your looking at S and W neighbors is a start, but realize that you could have in between squares that have open squares in the "wrong" directions and still not be a stuck square. Imagine a path where you go away from the exit and then snake back towards the exit!

ne555's idea of a stuck square may help cut down on the problem - the paths that lead to a stuck square are obviously bad (at least the subpath from the last intersection). The problem is, there may not be so many such paths, depending on the maze.

Also consider the extreme cases where there are almost no walls or nearly full of walls - your algorithm must withstand these cases for 2. For example, with almost no walls, nearly any path would work! Your solution set would be huge - in fact, it may be easier to describe paths that do not work in that case.

This is definitely a challenging problem.

[ne555]

Output
For each test case, display one line of output containing the test case number followed by the number of stuck
squares in the given room

No need to count paths, only how many squares lead to fail.

kfmfe04 wrote:

Imagine a path where you go away from the exit and then snake back towards the exit!

The robot can only move east or north (if see it in reverse S or W). You can't snake (if you go away you never come back).

[kfmfe04]

The robot can only move east or north (if see it in reverse S or W). You can't snake (if you go away you never come back).

That actually makes the problem much more tractable.

Let N=0 and E=1, then you could describe a path from beginning to the end with just a string of bits.
Let a subpath be any string of these bits like 0110, etc...

A subpath may have the following characteristics: either it can reach the entrance or it can't, either it can reach the exit or it can't - the possibilities can be described in 2 bits: 00, 01, 11, 10 - we care about the 11's (can reach entrance AND can reach exit) and don't care about the rest.

These characteristics are transferrable. Say you have a subpath A which can reach the entrance and subpath B which is reachable from subpath A. Then subpath B can also reach the entrance.

Broken down in this way, the entire problem could actually be parallelized and run on multicores/multi-processors separately and then recombined.

-------------------------------------------------

Another, simpler way, to look at this is, if the exit is m squares to the North and n squares to the East, the robot must use up m North moves and n East moves.

If it does, it surely has reached the exit.

If it reaches a point where it cannot do any more North moves or East moves, it has reached a dead-end.

[keepjumpin]

Thanks everyone! I think I'm going to go with ne555's solution. It is the solution I mentioned concerning wall intersections. I'm still not seeing anything concerning coordinate compression in the way that I've seen it described elsewhere. With ne555's solution it would not be necessary but I'm still interested in it. The idea is that if there are 5 columns in the graph that are all open except for one row that has a wall which starts at the east edge and and is 4 columns wide, then the 4 columns which contain the wall could be represented as one column. So with this situation the 5 columns would become 2 columns.