Splitting a rectangular chocolate bar

Question

I'm having trouble with my school homework. I have a chocolate bar that consists of either black, white or black&white (mixed) squares. I'm supposed to divide it in two groups, one that has only white or black&white pieces and the other that has only black or black&white pieces. Dividing the chocolate bar means cracking it either horizontally or vertically along the line that separates individual squares.

Given a layout of a chocolate bar, I am to find an optimal division which separates dark and white pieces and results in the smallest possible number of pieces, the chocolate bar being not bigger than 50x50 squares.

The chocolate bar is defined on the standard input like this:

• first line consists of two integers M (number of rows in chocolate bar) and N (no. of columns)
• then there follow M lines, each consisting of N characters symbolizing individual squares
  (0 ⇒ black, 1 ⇒ white, 2 ⇒ mixed)

My problem is that I managed to work out a solution, but the algorithm I'm using isn't fast enough, if the chocolate bar is big like this for example:

40 40
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 2 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 2 1 2 1 2 0 0 1 2 2 0 0 0 0 0 0 0 0 1 1 2 1 2 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 2 0 1 1 1 1 1 0 0 1 2 2 0 0 0 0 0 1 0 0 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 2 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 1 2 2 0 0 0 1 2 2 1 2 1 0 0 0 0 0 1 2 1 2 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 2 2 1 2 0 0 0 0 0 2 1 2 2 0 0 0 0 0 2 1 2 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 2 2 1 1 0 0 0 0 0 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0
0 2 1 2 1 0 2 2 2 2 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 2 0 2 2 1 0 0 0 0 0 0
0 2 2 1 2 0 1 2 2 1 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0
0 2 2 1 2 0 0 0 0 2 1 2 1 2 1 1 2 0 2 0 0 0 0 0 0 0 1 2 2 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2 2 2 2 1 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 2 1 1 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 0 0 0 0
0 0 0 0 0 0 0 2 1 2 0 0 2 2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 2 2 1 0 0 0 0 2 0 1 1 1 2 1 2 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 2 1 2 2 2 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 1 2 1 1 2 2 0 0 0 0 0
0 0 0 0 0 0 1 2 1 2 2 1 0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 0 2 1 2 0 0 0 0 0
0 0 0 0 0 0 1 2 2 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 0 0 0 0 2 1 1 0 0
0 0 0 0 0 0 1 1 1 1 1 2 2 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0
0 0 0 0 0 0 1 2 2 2 1 1 1 0 0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 0 0 2 2 2 1 0
0 0 0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 1 1 1 2 2 0 0 0 0 0 0 0 0 0 1 2 1 1 0
0 0 0 2 1 1 2 2 0 1 2 1 1 0 0 0 0 0 2 2 1 2 2 1 2 2 0 0 0 0 0 0 0 0 0 1 2 2 2 0
0 0 0 2 2 2 1 1 0 0 1 2 2 2 0 0 0 0 2 2 2 1 1 2 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 1 2 2 1 1 0 2 1 2 1 2 1 2 1 1 2 1 1 1 1 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 2 2 2 2 1 0 1 1 1 1 1 1 2 1 1 2 2 1 0 1 2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 2 1 1 1 2 1 2 0 0 1 2 1 2 1 2 2 0 0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 2 2 1 1 2 2 1 1 1 1 1 1 1 2 1 0 0 0 0 0 0 0 2 2 2 0 0 0
0 0 0 0 0 0 0 1 1 1 2 0 0 1 1 1 2 2 1 2 2 2 1 0 0 0 1 1 1 0 0 0 0 0 1 2 1 0 0 0
0 0 0 0 0 0 0 2 1 1 2 0 0 0 0 0 0 2 2 2 1 1 1 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 2 1 1 1 2 0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 1 2 0 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 1 2 1 0 0
0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 1 2 1 0 0
0 0 0 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

then it takes minutes for my program to solve it (correct solution for that one is 126).

My algorithm works roughly with some minor optimization like this: iterate through all possible lines where it's possible to cut and then recursively do the same for the 2 newly emerged rectangles, if they cannot be divided anymore, then return 1.

The function memoizes its results: after it iterates through all the possible cuts, always returns the minimum; once the minimum is found then store it and if I'd happen to need to solve this rectangle again then just return the value.

I thought that maybe If I happen to have already solved a particular rectangle and now I need to solve one that is one row or column bigger or smaller, then I could somehow use the solution I already have for that one and use it for the new one. But I really don't know how I would implement such a feature. Right now my algorithm treats it like a completely new unsolved rectangle.

My code so far:

#include <stdio.h>
#include <stdlib.h>

const int M, N;
int ****pieces;
int ****checked;
int inf;

int minbreaks(int **mat, int starti, int startj, int maxi, int maxj) {
    if (pieces[starti][startj][maxi][maxj] != 0) {
        return pieces[starti][startj][maxi][maxj];
    } else {
        int vbreaks[maxj - 1];
        int hbreaks[maxi - 1];
        for (int i = 0; i < maxj - 1; i++) {
            vbreaks[i] = inf;
        }
        for (int i = 0; i < maxi - 1; i++) {
            hbreaks[i] = inf;
        }
        int currentmin = inf;
        for (int i = starti; i < maxi; i++) {//vertical cracks
            for (int j = startj; j < maxj - 1; j++) {
                if (mat[i][j] != 2) {
                    for (int k = startj + 1; k < maxj; k++) {
                        if (vbreaks[k - 1] == inf) {
                            for (int z = starti; z < maxi; z++) {
                                if (!checked[i][j][z][k]) {
                                    if (mat[z][k] != 2 && mat[i][j] != mat[z][k]) {
                                        vbreaks[k - 1] = minbreaks(mat, starti, startj, maxi, k) + minbreaks(mat, starti, k, maxi, maxj);
                                        if (vbreaks[k - 1] < currentmin) {
                                            currentmin = vbreaks[k - 1];
                                        }
                                        break;
                                    }
                                    checked[i][j][z][k] = 1;
                                }
                            }
                        }
                    }
                }
            }
        }
        for (int i = starti; i < maxi - 1; i++) {//horizontal cracks
            for (int j = startj; j < maxj; j++) {
                if (mat[i][j] != 2) {
                    for (int k = starti + 1; k < maxi; k++) {
                        if (hbreaks[k - 1] == inf) {
                            for (int z = startj; z < maxj; z++) {
                                if (!checked[i][j][k][z]) {
                                    if (mat[k][z] != 2 && mat[i][j] != mat[k][z]) {
                                        hbreaks[k - 1] = minbreaks(mat, starti, startj, k, maxj) + minbreaks(mat, k, startj, maxi, maxj);
                                        if (hbreaks[k - 1] < currentmin) {
                                            currentmin = hbreaks[k - 1];
                                        }
                                        break;
                                    }
                                    checked[i][j][k][z] = 1;
                                }
                            }
                        }
                    }
                }
            }
        }
        if (currentmin == inf) {
            currentmin = 1;
        }
        pieces[starti][startj][maxi][maxj] = currentmin;
        return currentmin;
    }
}

void allocchecked(int i, int j) {
    checked[i][j] = malloc(sizeof (int*)*M);
    for (int y = 0; y < M; y++) {
        checked[i][j][y] = malloc(sizeof (int)*N);
        for (int x = 0; x < N; x++) {
            checked[i][j][y][x] = 0;
        }
    }
}

void allocpieces(int i, int j) {
    pieces[i][j] = malloc(sizeof (int*)*(M + 1));
    for (int y = i; y < M + 1; y++) {
        pieces[i][j][y] = malloc(sizeof (int)*(N + 1));
        for (int x = j; x < N + 1; x++) {
            pieces[i][j][y][x] = 0;
        }
    }
}

int main(void) {
    FILE *file = stdin;
    fscanf(file, "%d %d", &M, &N);

    int **mat = malloc(sizeof (int*)*M);
    pieces = malloc(sizeof (int***)*M);
    checked = malloc(sizeof (int***)*M);
    for (int i = 0; i < M; i++) {
        mat[i] = malloc(sizeof (int)*N);
        pieces[i] = malloc(sizeof (int**)*N);
        checked[i] = malloc(sizeof (int**)*N);
        for (int j = 0; j < N; j++) {
            int x;
            fscanf(file, "%d", &x);
            mat[i][j] = x;
            allocpieces(i, j);
            allocchecked(i, j);
        }
    }
    inf = M * (M + 1) * N * (N + 1) / 4 + 1;
    int result = minbreaks(mat, 0, 0, M, N);
    printf("%d\n", result);
    return (EXIT_SUCCESS);
}

Does anybody have any idea for improvements?

Answer 1

Readability and understandability of the code is (usually) much more important that some 'clever' algorithm. This is because almost all code needs to be debugged, modified, updated, understood by others than the original writer.

For the above reasons:

1. Insert appropriate horizontal space: inside parens, after commas, after semicolons, around C operators.

2. Separate code blocks (for, if, else, while, do...while, switch, case, default) with a single blank line.

3. Separate code into 'well defined' functions.

4. Separate functions via 2 or 3 blank lines (be consistent).

5. Honor the right margin of the printed page (usually column 72 or 80) by breaking long statements into multiple lines and indenting all but the first line.

6. When calling any of the heap allocation functions, always check (!=NULL) the returned value to assure the operation was successful.

   If not successful, call perror() to output the enclosed text AND the reason the system thinks the operation failed to stderr.

7. Variable names (and parameter names) should indicate content or usage. Parameter names like i and j or variable names like N and M and inf are meaningless, even in the current context.

8. File-scope variables like inf are (almost) always a bad idea. Rather, declare the variable in some function, like main(), and pass the variable where it's needed.

9. The parameter to malloc() should be size_t to avoid implicit conversions and having the compiler output warnings about those implicit conversions.

10. When calling any of the scanf() family of functions, always check the returned value (not the parameter values) to assure the operation was successful.

11. The recursive calls to minbreaks() will use a huge amount of stack space.

12. It is a poor programming practice to let the OS clean up after a program exits. Much better for the program to perform the clean-up. In the current scenario, that means passing every pointer to allocated memory to free(), before exiting the program.

13. For cryptic statements like: inf = M * (M + 1) * N * (N + 1) / 4 + 1; include a comment about the objective of that calculation.

14. The first couple of statements in minbreaks() will return immediately with a value of 0.

15. The allocation in main() of pieces[][][][] and checked[][][][] and then performing even more allocation in the functions: allocpieces() and allocchecked() is spreading the allocation work all over the program rather than keeping it 'together'. This makes the program much more difficult to understand, debug, etc.

16. This kind of code block: FILE *file = stdin; fscanf(file, "%d %d", &M, &N); is obscure and unnecessary. I suggest scanf( "%d %d", &M, &N ); (and remember my point, above, about checking the returned value: in this case, anything but 2 is a failure and the program should be exited).

17. The data M and N are declared as constant, so cannot be changed. However the statement fscanf(file, "%d %d", &M, &N); is trying to change them.

Answer 2

The code is very, very hard to read. The variable names are quite cryptic, and the algorithm is densely packed into a single, uncommented method. Credit for separating out the allocation (but the deallocation function seems to be missing).

Consider a suitable data structure to represent a bar or a view of part of the bar:

struct Bar
{
    size_t width;
    size_t height;
    size_t stride;
    char *data;
};

This allows us to use functions such as

Bar *create_bar(size_t width, size_t height);

void free_bar(Bar *bar);

char read(Bar const *bar, size_t x, size_t y);

void write(Bar *bar, size_t x, size_t y, char value);

Bar *sub_bar(Bar const *bar, size_t width, size_t height,
             size_t x_offset, size_t y_offset);

The stride member is needed when we create a sub-bar, as the stride is copied from the parent bar so we don't need to copy the data.

Using these abstractions, we can end up with a clearer view of what we're doing, and then start to work on an improved implementation.

Answer 3

Algorithmic improvements

As this is homework, I'm not going to do it all for you, but just present a hint.

The current algorithm is a simple brute-force search. We can do better using a heuristic metric to suggest a most-productive order in which to search for results. For this example, a heuristic I might try would be to consider every possible cut (horizontal and vertical), and look at whether each part of that cut separates two similar or dissimilar squares.

You can then use an ordered list of potential cuts to try the highest-ranked ones first. Once you have a candidate solution, you can discard any partial solutions that reach the value (number of cuts) of your current best candidate without evaluating them to the end.

A couple of things to consider when creating a heuristic:

1. For a non-square bar (say 5×2 units), we'll want a score system that works with the different lengths of horizontal and vertical cut. Perhaps the best metric is the number of like pairs separated, rather than the number of unlike pairs? (We'd then attempt cuts with the lowest metric first).
2. What do we do with the mixed-colour pieces? Your options include (but are not limited to) treating them always as "like" or "unlike", or extending to find the nearest solid colour or edge in that direction.