HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Find the area of the bounding box of a robot's moves on a grid

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
robotthemovesgridboundingfindboxarea

Problem

Given a string of directions (example: "LLRUDDULRDRU") find the area of the rectangle defined by the lowest-left point (minx, miny) and the highest-right point (maxx, maxy) the robot was in.

The canonical solution I think would be.

int area(char* directions) {
    char * c = directions;
    int x=0, y=0, minx=0, maxx=0, miny=0, maxy=0;
    while (*c) {
        if (*c == 'U') {
            y++;
        } else if (*c == 'D') {
            y--;
        } else if (*c == 'R') {
            x++;
        } else if (*c == 'L') {
            x--;
        }

        if (y  maxy)
            maxy = y;
        if (x > maxx)
            maxx = x;

        c++;
    }
    return (maxx - minx) * (maxy - miny);
}


The problem I see with this is that the indentation is switched often making it hard to read. That's why I tend to exploit the fact C's logical operators return numbers 1 or 0.

int area(char * directions) {
    char * c = direction;
    int x=0, y=0, minx=0, maxx=0, miny=0, maxy=0;
    while (*c) {
        y += (*c == 'U') - (*c == 'D');
        x += (*c == 'R') - (*c == 'L');

        minx = (x  maxx) ? x : maxx;
        maxy = (y > maxy) ? y : maxy;

        c++;
    }

     return (maxx - minx) * (maxy - miny);
}


However doing this feels 'too hacky'.

Is doing this a good practice at all?

Solution

Function signature

It appears you're only reading from directions, so pass that as a pointer to const.

while loop

You initialize c before the while loop and increment it at the end of each iteration. Writing it as for will convey the intent more clearly.

Chained conditions

Your first if/else if chain is always testing the same variable, so a switch statement seems more appropriate:

switch (*c) {
    case 'U': ++y; break;
    case 'D': --y; break;
    case 'R': ++x; break;
    case 'L': --x; break;
    }


You might want to add a default case to indicate when malformed input is received. I can't tell from the context whether it would be appropriate to print something to stderr or to return an error code (perhaps as a negative return value), so I'll leave that to you.

Don't test all bounds each time

We can now observe that we only need to check y against maxy if we've incremented y, so we can move that test into the switch; similarly with the other cases:

int area(char const *directions)
{
    int x=0, y=0,
        minx=0, maxx=0,
        miny=0, maxy=0;
    for (char const *c = directions;  *c;  ++c) {
        switch (*c) {
        case 'U':
            ++y;
            if (y > maxy) maxy = y;
            break;
        case 'D':
            --y;
            if (y  maxx) maxx = x;
            break;
        case 'L':
            --x;
            if (x < minx) minx = x;
            break;
        }
    }
    return (maxx - minx) * (maxy - miny);
}


You might want to consider using a max() function to re-write ++x; if (x > maxx) maxx = x; as maxx = max(maxx, ++x);, but I can't really say that one is better than the other - too close to call. Similarly, you might decide that returning an unsigned type is more appropriate, but that really depends on the code you're calling it from.

Code Snippets

switch (*c) {
    case 'U': ++y; break;
    case 'D': --y; break;
    case 'R': ++x; break;
    case 'L': --x; break;
    }
int area(char const *directions)
{
    int x=0, y=0,
        minx=0, maxx=0,
        miny=0, maxy=0;
    for (char const *c = directions;  *c;  ++c) {
        switch (*c) {
        case 'U':
            ++y;
            if (y > maxy) maxy = y;
            break;
        case 'D':
            --y;
            if (y < miny) miny = y;
            break;
        case 'R':
            ++x;
            if (x > maxx) maxx = x;
            break;
        case 'L':
            --x;
            if (x < minx) minx = x;
            break;
        }
    }
    return (maxx - minx) * (maxy - miny);
}

Context

StackExchange Code Review Q#156128, answer score: 6

Revisions (0)

No revisions yet.