calgorithmdynamic-programmingrectangles
finding minimum number of rectangular pieces in a rectangular chocolate bar, with a rule
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 cubes 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 M columns each consisting of N characters symbolizing individual squares (0-black, 1-white, 2-mixed)
Some examples of an optimal division, their inputs respectively (correct outputs are 3 and 7):
3 3
1 1 2
1 2 0
2 0 0
4 4
0 1 1 1
1 0 1 0
1 0 1 0
2 0 0 0
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 10 seconds for my program to solve it (correct solution for that one is 126 and I should be able to solve it in under 2 seconds!)
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 after it iterates trough 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 would i 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>
unsigned int M, N;
unsigned int ****pieces; ////already solved rectangles, the value of pieces[y0][x0][y1][x1] is the optimal number of pieces in which the particular rectangle(that has upperleft corner in [x0,y0] and bottomright corner in[x1,y1]) can be divided
int ****checked;
unsigned int inf;
unsigned int minbreaks(int mat[M][N], unsigned int starti, unsigned int startj, unsigned int maxi, unsigned int maxj) {
if (pieces[starti][startj][maxi][maxj] != 0) {
return pieces[starti][startj][maxi][maxj];
} else {
unsigned int vbreaks[maxj - 1];
unsigned int hbreaks[maxi - 1];
for (unsigned int i = 0; i < maxj - 1; i++) {
vbreaks[i] = inf;
}
for (unsigned int i = 0; i < maxi - 1; i++) {
hbreaks[i] = inf;
}
unsigned int currentmin = inf;
for (unsigned int i = starti; i < maxi; i++) {
for (unsigned int j = startj; j < maxj - 1; j++) {
if (mat[i][j] != 2) {
for (unsigned int k = startj + 1; k < maxj; k++) {
if (vbreaks[k - 1] == inf) {
for (unsigned 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 (unsigned int i = starti; i < maxi - 1; i++) {
for (unsigned int j = startj; j < maxj; j++) {
if (mat[i][j] != 2) {
for (unsigned int k = starti + 1; k < maxi; k++) {
if (hbreaks[k - 1] == inf) {
for (unsigned 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;
}
}
int main(void) {
FILE *file = stdin;
fscanf(file, "%u %u", &M, &N);
int mat[M][N];
pieces = malloc(sizeof (unsigned int***)*M);
checked = malloc(sizeof (int***)*M);
for (unsigned int i = 0; i < M; i++) {//initialize the pieces,checked and mat arrays.
pieces[i] = malloc(sizeof (unsigned int**)*N);
checked[i] = malloc(sizeof (int**)*N);
for (unsigned int j = 0; j < N; j++) {
int x;
fscanf(file, "%d", &x);
mat[i][j] = x;
pieces[i][j] = malloc(sizeof (unsigned int*)*(M + 1));
checked[i][j] = malloc(sizeof (int*)*M);
for (unsigned int y = i; y < M + 1; y++) {
pieces[i][j][y] = malloc(sizeof (unsigned int)*(N + 1));
for (unsigned int x = j; x < N + 1; x++) {
pieces[i][j][y][x] = 0;
}
}
for (unsigned int y = 0; y < M; y++) {
checked[i][j][y] = malloc(sizeof (int)*N);
for (unsigned int x = 0; x < N; x++) {
checked[i][j][y][x] = 0;
}
}
}
}
inf = M * N + 1; //number one bigger than maximal theoretically possible number of divisions
unsigned int result = minbreaks(mat, 0, 0, M, N);
printf("%u\n", result);
return (EXIT_SUCCESS);
}
So anybody has any idea for improvements?
Solution
Thanks to everybody who helped me, my mistake was that in those nested loops I tried to avoid some unnecessary breaks, like this for example
1 1 -> 1 | 1
1 1 1 | 1
1 1 1 | 1
thinking it would speed up the runtime but the correct approach was just simply breaking the chocolate bar always everywhere possible. Anyway for anyone interested here is my working code:
#include <stdio.h>
#include <stdlib.h>
unsigned int M, N;
unsigned int ****pieces; ////already solved rectangles, the value of pieces[y0][x0][y1][x1] is the optimal number of pieces in which the particular rectangle(that has upperleft corner in [x0,y0] and bottomright corner in[x1,y1]) can be divided
unsigned int inf;
int isOneColor(int mat[M][N], unsigned int starti, unsigned int startj, unsigned int maxi, unsigned int maxj) {
int c = 2;
for (unsigned int i = starti; i < maxi; i++) {
for (unsigned int j = startj; j < maxj; j++) {
if (c == 2) {
if (mat[i][j] != 2) {
c = mat[i][j];
}
} else if (c != mat[i][j] && mat[i][j] != 2) {
return 0;
}
}
}
return 1;
}
unsigned int minbreaks(int mat[M][N], unsigned int starti, unsigned int startj, unsigned int maxi, unsigned int maxj) {
if (pieces[starti][startj][maxi][maxj] != 0) {
return pieces[starti][startj][maxi][maxj];
} else if (isOneColor(mat, starti, startj, maxi, maxj)) {
return pieces[starti][startj][maxi][maxj] = 1;
} else {
unsigned int currentmin = inf;
for (unsigned int j = startj; j < maxj - 1; j++) {
unsigned int c = minbreaks(mat, starti, startj, maxi, j + 1) + minbreaks(mat, starti, j + 1, maxi, maxj);
if (c < currentmin) {
currentmin = c;
}
}
for (unsigned int i = starti; i < maxi - 1; i++) {
unsigned int c = minbreaks(mat, starti, startj, i + 1, maxj) + minbreaks(mat, i + 1, startj, maxi, maxj);
if (c < currentmin) {
currentmin = c;
}
}
pieces[starti][startj][maxi][maxj] = currentmin;
return currentmin;
}
}
int main(void) {
FILE *file = stdin;
//FILE *file = fopen("inputfile", "r");
fscanf(file, "%u %u", &M, &N);
int mat[M][N];
pieces = malloc(sizeof (unsigned int***)*M);
for (unsigned int i = 0; i < M; i++) {
pieces[i] = malloc(sizeof (unsigned int**)*N);
for (unsigned int j = 0; j < N; j++) {
int x;
fscanf(file, "%d", &x);
mat[i][j] = x;
pieces[i][j] = malloc(sizeof (unsigned int*)*(M + 1));
for (unsigned int y = i; y < M + 1; y++) {
pieces[i][j][y] = malloc(sizeof (unsigned int)*(N + 1));
for (unsigned int x = j; x < N + 1; x++) {
pieces[i][j][y][x] = 0;
}
}
}
}
inf = M * N + 1; //number that is bigger by one than maximal theoretically possible number of divisions
unsigned int result = minbreaks(mat, 0, 0, M, N);
printf("%u\n", result);
return (EXIT_SUCCESS);
}
- Simple frame by frame video decoder library
- GCC no longer implements <varargs.h>
- Contents of IO buffer unknown == unsafe?
- Avoiding strcpy overflow destination warning
- Sort program not working, not sure why
- Fast & accurate atan/arctan approximation algorithm
- What's the difference between strtok_r and strtok_s in C?
- How memory address for pointer to arrays is same as an element in 2D array?
- Which is the best way to suppress "unused variable" warning
- How to use ellipsis in c's case statement?
- How can I exclude non-numeric keys? CS50 Caesar Pset2
- Fast ceiling of an integer division in C / C++
- Is there an invalid pthread_t id?
- How to Implement Universal Setter/Getter Functions for Interrupt-Driven Variables in Embedded C?
- How does SIMD (avx) processing work? for example, if I want 10 32 bit floats how do i fit in a 256 bit avx vector?
- FDCAN problems on STM32G4
- How does the call macro enable mutual recursion between functions f and g in this Hanoi Tower implementation?
- Running test on Rocket core CPU - global variable initialized to 0 is unsuccessful, output wrong value instead
- Interacting with C arrays without knowing the size
- Combination of two strings
- carriage return by fgets
- How to use special characters in C?
- Why does 1.0/100.0 == 0.1/10.0 give True?
- Is it correct to compare pointers in C?
- Force free() to return malloc memory back to OS
- How can I print to standard error in C with 'printf'?
- What is the standard behavior of fread in C on Windows?
- How is strtok removing lines it shouldn't have access to?
- Using array as smart point in C
- Assigning string to malloced 2d char array not working as intended