4
\$\begingroup\$

I'm implementing a clone of 2048 in C with SDL, and I have the following function for performing a movement on a column vector/array

/**
 * collapseVector: Collapse a vector "2048" style, flush the cells in one direction, joining them if legal.
 * @param _vector 1-D array to be collapsed
 * @param _score Score counter
 * @param invert Whether or not to inverse-flush vector. Useful for Up(false) vs. Down(true), and so on
 */
void collapseVector(int _vector[MAX_BOARD_POS], int **_score, bool invert) {
    int idx;
    int buf[MAX_BOARD_POS] ={0};
    if (invert) {
        idx = MAX_BOARD_POS - 1;
        for (int i = MAX_BOARD_POS - 1; (MAX_BOARD_POS - i) < MAX_BOARD_POS + 1; --i){
            if(!_vector[i]){
                continue;
            }
            if(!buf[idx]){
                buf[idx] = _vector[i];
            }else if(_vector[i] == buf[idx]){
                ++buf[idx];
                **_score += 1 << buf[idx];
            }else{
                buf[--idx] = _vector[i];
            }
        }

    } else {
        idx = 0;
        for (int i = 0; i < MAX_BOARD_POS; ++i) {
            // If it's an empty cell (0) ignore it. The buf vector is zero-filled anyway
            if (!_vector[i]) {
                continue;
            }
            // Special case for filling in the first cell of buffer
            if (!buf[idx]) {
                buf[idx] = _vector[i];
            } else if (_vector[i] == buf[idx]) {
                // If we have identical neighbouring cells join them
                ++buf[idx];
                // Add 2^buf[idx] to our score counter.
                **_score += 1 << buf[idx];
            } else {
                // Flush cells to the end of vector
                buf[++idx] = _vector[i];
            }
        }
    }
    memcpy(_vector, buf, MAX_BOARD_POS * sizeof(*_vector));
}

This code works perfectly, but it's long and repetitive. How can I improve this? The two for loops in here are very similar and I wonder whether I could join them perhaps.

\$\endgroup\$
2
\$\begingroup\$

Complicated loop condition

I had to stare for a long time at this loop termination condition from your first loop:

(MAX_BOARD_POS - i) < MAX_BOARD_POS + 1

Eventually, I turned to mathematics to figure it out:

  1. Subtract MAX_BOARD_POS from both sides: -i < 1
  2. Add i to both sides: 0 < i + 1
  3. Subtract 1 from both sides: -1 < i
  4. Reverse the inequality: i > -1
  5. Use >= instead of >: i >= 0

So in other words, your loop was actually the simple downward loop of:

for (int i = MAX_BOARD_POS - 1; i >= 0; --i)

Now it made perfect sense!

Combining the loops

So one loop goes from N-1 to 0, and the other goes from 0 to N-1. One way of combining the loops is to make three variables: start, end, and delta, where end is one past the end of the loop. That way, you can do:

for (i = start; i != end; i += delta) {
    ...
}

Now all you have to do is initialize those three variables to the correct values, depending on whether invert is true or false. There are a couple of other places that need adjustment depending on invert as well, but those are easy to change.

Sample rewrite

Here is how I would have written your function using only one loop:

void collapseVector(int _vector[MAX_BOARD_POS], int **_score, bool invert)
{
    int buf[MAX_BOARD_POS] = {0};
    int start = invert ? MAX_BOARD_POS - 1 : 0;
    int end   = invert ? -1                : MAX_BOARD_POS;
    int delta = invert ? -1                : 1;
    int idx   = start;

    for (int i = start; i != end; i += delta) {
        if (!_vector[i]) {
            // If it's an empty cell (0) ignore it. The buf vector is
            // zero-filled anyway.
            continue;
        }
        if (!buf[idx]) {
            // Special case for filling in the first cell of buffer.
            buf[idx] = _vector[i];
        } else if (_vector[i] == buf[idx]) {
            // If we have identical neighbouring cells join them.
            ++buf[idx];
            // Add 2^buf[idx] to our score counter.
            **_score += 1 << buf[idx];
        } else {
            // Flush cells to the end of vector.
            idx += delta;
            buf[idx] = _vector[i];
        }
    }
    memcpy(_vector, buf, MAX_BOARD_POS * sizeof(*_vector));
}
\$\endgroup\$
3
\$\begingroup\$

Don't repeat yourself

The two loops can be joined pretty easily. We basically just need to factor out the (few) pieces that are different between the two, and pull those pieces out of the loop. The loops are just short enough, however, that the result may not be a whole lot shorter than the two loops are right now (so if you care more about short code than lack of repetition, you may not want to do this).

Comments

Right now, you've provided comments for what the loop does in one of the loops, but not the other. By collapsing the loops together, we can eliminate this inconsistency. That leaves the question of whether to include the comments or not. In general, I'd rather write the code to be self-documenting instead. See below for at least some of how to do that.

Symbolic names

Instead of writing the code to explicitly state the an empty cell contains the value 0, I'd prefer to give that a name:

#define EMPTY 0

// ...

if (_vector[i] == EMPTY)
   // ...

This (probably) eliminates any requirement for a comment to tell us that we're checking whether that cell is empty.

Unnecessary Indirection

It appears that you can pass _score as a pointer to int rather than a pointer to pointer to int as you're doing now. At least as far as I can see, the extra level of indirection isn't accomplishing anything useful at all.

Bool Parameters

I generally discourage using bools as function parameters. I'd rather use an enumeration that directly states what you want to express:

enum { UP, DOWN };

collapseVector(..., UP);

...seems much more meaningful than:

collapsVector(..., true);

Final Code

One possibility would be something on this general order:

#define EMPTY 0

bool down(int a, int b) {
    return a < b;
}

bool up(int a, int b) {
    return b < a;
}

enum direction { UP, DOWN };

/**
* collapseVector: Collapse a vector "2048" style, flush the cells in one direction, joining them if legal.
* @param _vector 1-D array to be collapsed
* @param _score Score counter
* @param invert Whether or not to inverse-flush vector. Useful for Up(false) vs. Down(true), and so on
*/
void collapseVector(int _vector[MAX_BOARD_POS], int *_score, direction dir) {
    int idx = 0;
    int buf[MAX_BOARD_POS] = { 0 };
    int start = 0;
    int end = MAX_BOARD_POS;
    int inc = 1;
    bool (* cmp)(int, int) = down;

    if (dir == UP) {
        idx = start = MAX_BOARD_POS - 1;
        end = 0; // Not sure if this is quite right, but I think it's at least close
        inc = -1;
        cmp = up;
    }

    for (int i = start; cmp(i, end); i += inc) {
            if (_vector[i] == EMPTY) {
                continue;
            }
            if (buf[idx] == EMPTY) {
                buf[idx] = _vector[i];
            }
            else if (_vector[i] == buf[idx]) {
                ++buf[idx];
                *_score += 1 << buf[idx];
            }
            else {
                buf[idx += inc] = _vector[i];
            }
        }
    }
    memcpy(_vector, buf, MAX_BOARD_POS * sizeof(*_vector));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.