7 Replies - 799 Views - Last Post: 06 November 2009 - 10:10 AM Rate Topic: -----

#1 diego_pmc  Icon User is offline

  • D.I.C Addict

Reputation: 81
  • View blog
  • Posts: 565
  • Joined: 13-May 09

Bridge between two points

Posted 04 November 2009 - 02:18 PM

I have recently finished writing an algorithm and would like to see how others would have done it. The algorithm is part of an olympiad exercise from previous years. Here's the relevant information about what you have to do in the exercise:

You have a map of the territories of three countries: R, G, B. R is represented by 1, G by 2, B by 3, and 0 means water. Here's an example of a map:

Quote

1000320
0110313
3333000
2033000
2203011
2000010


We say two elements of the map-matrix are neighbors if they have the same value and if they are consecutive on a line or a column. For example the three 1-s in the lower right corner of the matrix are "neighbors".

In a certain part of the program I have to write an algorithm to determine whether or not it is possible to build a bridge between two given points, and if so, return its length. A bridge is 'buildable' if it meets these conditions:
  • It must begin from a point filled with water that is next to the beginning point;
  • It must end in a point filled with water that is next to the ending point;
  • Any two consecutive elements of the bridge must be neighbors;
  • All elements of the bridge must be above an area covered by water.
In the example below I've marked the bridge between the point on line 1, column 6: (1, 6) = '1', and point (5, 0) = '2'. The bridge is marked by green zeroes:

Quote

1000320
0110313
3333000
2033000
2203011
2000010


Here's how I've done it. I'm curious as to how others would have approached this problem.

int Progress(int, int);

int BridgeLength(int y1, int x1, int y2, int x2, string* map)
{
/* 'y1' and 'x1' are the coordinates of the starting point, 
   'y2' and 'x2' are the coordinates of the ending point. */
    // Wiil return 0 if bridge is impossible.

    // First it has to be determined how to progress on the 
    //  X and Y axis in order to get from (x1, y1) to (x2, y2).
    const int prog_x = Progress(x1, x2);
    const int prog_y = Progress(y1, y2);

    int bridge = 0;

    while (true)
    {
        int impossible = 0;

        // THE X AXIS
        if (x1 != x2)
        {
            char ch = map[y1][x1+prog_x];
            if (ch == '0') {
                x1 += prog_x;
                bridge++;
            } else if ((x1 + prog_x == x2) && (y1 == y2)) {
                break;
            } else {
                impossible++;
            }
        } else impossible++;

        // THE Y AXIS
        if (y1 != y2)
        {
            char ch = map[y1+prog_y][x1];
            if (ch == '0') {
                y1 += prog_y;
                bridge++;
            } else if ((y1 + prog_y == y2) && (x1 == x2)) {
                break;
            } else {
                impossible++;
            }
        } else impossible++;

        // if we failed to move on both the x and the y axis 
        // it means the bridge is impossible to build
        if (impossible == 2) {
            bridge = 0;
            break;
        }
    }
    return bridge;
}

int Progress(int p1, int p2) {
    int prog;
    if      (p1 > p2)  prog = -1;
    else if (p1 < p2)  prog =  1;
    else if (p1 == p2) prog =  0;
    return prog;
}

(My first try was even uglier.)

This post has been edited by diego_pmc: 05 November 2009 - 12:32 PM


Is This A Good Question/Topic? 1
  • +

Replies To: Bridge between two points

#2 bsaunders  Icon User is offline

  • D.I.C Addict

Reputation: 44
  • View blog
  • Posts: 571
  • Joined: 18-January 09

Re: Bridge between two points

Posted 04 November 2009 - 09:26 PM

So, the bridge doesn't have to be straight?
Was This Post Helpful? 0
  • +
  • -

#3 diego_pmc  Icon User is offline

  • D.I.C Addict

Reputation: 81
  • View blog
  • Posts: 565
  • Joined: 13-May 09

Re: Bridge between two points

Posted 05 November 2009 - 04:57 AM

View Postbsaunders, on 4 Nov, 2009 - 08:26 PM, said:

So, the bridge doesn't have to be straight?

It does not specify that.
Was This Post Helpful? 0
  • +
  • -

#4 EdwinNameless  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 120
  • View blog
  • Posts: 710
  • Joined: 15-October 09

Re: Bridge between two points

Posted 05 November 2009 - 06:59 AM

Interesting. I haven't given much thought to it, but I imagine I would use backtracking.

I'm reading your code, but somehow I have the feeling this is not quite right. First, you seem to favour x over y. What if you have this situation?

Quote


1000020
0100013
3003000
2033000
2003111
2000010


The idea here is that you'd follow the x axis only to end up in a dead-end. Does your piece work in this case?

Next, would this work too?

Quote


1000000
0101113
3203110
2200010
2113011
2000010


I have the feeling you increase x if x2>x1, and you increase y if y2>y1, missing situations like the one above but I could be wrong.

Edit: Oh, and what about constraints #1 and #2? I'll try to give my own solution if I have time! ;-)
Edit again: in my examples, I'm going from 2 to 1.

This post has been edited by EdwinNameless: 05 November 2009 - 07:07 AM

Was This Post Helpful? 0
  • +
  • -

#5 diego_pmc  Icon User is offline

  • D.I.C Addict

Reputation: 81
  • View blog
  • Posts: 565
  • Joined: 13-May 09

Re: Bridge between two points

Posted 05 November 2009 - 08:17 AM

View PostEdwinNameless, on 5 Nov, 2009 - 05:59 AM, said:

I'm reading your code, but somehow I have the feeling this is not quite right. First, you seem to favour x over y. [...] The idea here is that you'd follow the x axis only to end up in a dead-end. Does your piece work in this case?

Yes it does because the code is like this...
if (x1 != x2) // ...
if (y1 != y2) // ...


... and not...
if (x1 != x2) // ...
else if (y1 != y2) // ...

So the position will move both on the x and the y axis at the same time. If one of the axises reaches a dead end, then it will only try to move on the other one. If it fails on the second one as well, then the bridge is impossible to build.


View PostEdwinNameless, on 5 Nov, 2009 - 05:59 AM, said:

Next, would this work too?

Quote


1000000
0101113
3203110
2200010
2113011
2000010


I have the feeling you increase x if x2>x1, and you increase y if y2>y1, missing situations like the one above but I could be wrong.

No, I only covered the cases where the bridge can be built be moving in only one direction on either one of the axises. For example if I begin building the bridge from left–right I cannot change directions and start moving from right–left.

View PostEdwinNameless, on 5 Nov, 2009 - 05:59 AM, said:

Oh, and what about constraints #1 and #2? I'll try to give my own solution if I have time! ;-)

I covered them. I only read bridge++ if the area I'm trying to move towards is covered with water; if the area I'm trying to move towards is anything else but water I check if it is the ending point. If it is then I don't increment bridge and break the loop because I found the ending point.
char ch = map[y1][x1+prog_x];
if (ch == '0') {
    x1 += prog_x;
    bridge++;
} else if ((x1 + prog_x == x2) && (y1 == y2)) {
    // here I check if it's the ending point
    break;
} else {
    impossible++;
}


EDIT: I forgot. The bridge must also meet this condition (I didn't mention it the first time):

Quote

All elements of the bridge must be above an area covered by water.

This post has been edited by diego_pmc: 05 November 2009 - 12:20 PM

Was This Post Helpful? 0
  • +
  • -

#6 EdwinNameless  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 120
  • View blog
  • Posts: 710
  • Joined: 15-October 09

Re: Bridge between two points

Posted 05 November 2009 - 09:28 AM

View Postdiego_pmc, on 5 Nov, 2009 - 07:17 AM, said:

EDIT: I forgot. The bridge must also meet this condition (I didn't mention it the first time):

Quote

All elements of the bridge must be above an area covered by water.


Yes, I think that was implied.

Again, really interesting topic, thanks for sharing it!! Not as easy as it first looks.
Was This Post Helpful? 0
  • +
  • -

#7 diego_pmc  Icon User is offline

  • D.I.C Addict

Reputation: 81
  • View blog
  • Posts: 565
  • Joined: 13-May 09

Re: Bridge between two points

Posted 05 November 2009 - 12:54 PM

I made a small change. I removed bool ready and instead of setting it to true when I finish the bridge, then have an if statement which breaks the loop if the bool is true, I break the loop directly. That means this...
bool ready = false;
// ...
if ((x + x_prog == x2) && (y1 == y2)) ready = true;
// ...
if (ready) break;


... turned into this...
if((x + x_prog == x2) && (y1 == y2)) break;

Was This Post Helpful? 0
  • +
  • -

#8 EdwinNameless  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 120
  • View blog
  • Posts: 710
  • Joined: 15-October 09

Re: Bridge between two points

Posted 06 November 2009 - 10:10 AM

Hi Diego,

I have posted my own solution on my blog with a bit of explanation.

Edit: I haven't implemented the length of the bridge bit yet. I'm thinking of doing some serious reading on pathfinding first!!

This post has been edited by EdwinNameless: 06 November 2009 - 10:13 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1