Wieviele Steine passen in eine Fläche?

MontyPerl · Feb 1, 2009

Ich hab mich mal drangesetzt.

Als Optimierungen ist folgende Prämisse eingeflossen:
Optimale Platzausnutzung kann (nur) erreicht werden, wenn die Steine zusammenhängend platziert werden (also keine "freistehenden" Steine existieren).

Der Algorithmus ist aber immernoch ziemlich langsam (Er schafft das 13x14 Feld mit 3x5 Bausteinen Beispiel unter einer Minute. Vor der Optimierung lief der stundenlang fröhlich vor sich hin...). Das "Urbeispiel" (200x250 Feld mit 15x10 Bausteinen) würde wahrscheinlich seeeeeehr lange laufen.... Ohne weitere intelligente Optimierungen ist der Algo einfach zu langsam für solche Dimensionen.. (@weitere Optimierungen: Sowas wie beim Damenproblem beispielsweise. Das Hauptproblem in immer kleinere Teilprobleme zerteilen und am Ende wieder alles zusammenführen. Oder eine Art von caching ausarbeiten. Aber das war mir jetzt zu "fancy"

Bin froh das es überhaupt funktioniert.)

Ich komm insgesamt auf 451 Zeilen Code (stdlib.h und stdio.h nicht mitgezählt).
Naja, dafür hab ich on-the-way auch noch das maximal-rectangle-problem gelöst (getBiggestFree()), ohne das es direkt was mit der Aufgabenstellung zu tun hätte. (Wird auch nicht im Algorithmus verwendet.)

Erstmal das Hauptprogramm, beziehungsweise das userinterface, rect.c:

Code:

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

/*
 * Es soll ein Algorithmus entwickelt werden der die maximale Anzahl an
 * Bausteinen bestimmt die in eine bestimmte Fläche passen.
 *
 * z.B: ich gebe "ihm" eine Fläche von 2m x 2,5m vor und sage das ein Baustein 0,15m x 0.1m groß ist.
 * Nun soll der Algorithmus die Bausteine so anordnen das die Große Fläche möglichst vollständig
 * abgedeckt wird. und es so wenig wie möglich Lücken bleiben.
 *
 * Die anzahl de genutzten Bausteine und wenn möglich die Form in der die
 * Bausteine verlegt worden sind, sollen ausgegeben werden. 
 */

int main(int argc, char *argv[]) {
    if (argc != 5) {
        fprintf(stderr, "usage: %s <fieldxdim> <fieldydim> <rectxdim> <rectydim>\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    int xdim, ydim;
    xdim = atoi(argv[1]);
    ydim = atoi(argv[2]);
    field *f = createField(xdim, ydim);

    int rectxsize, rectysize;
    rectxsize = atoi(argv[3]);
    rectysize = atoi(argv[4]);
    rect *r = createRect(0, 0, rectxsize, rectysize);
    fillField(f, r);
    return EXIT_SUCCESS;
}

Dann die eigentliche Implementierung:

Code:

#include <stdio.h>
#include <stdlib.h>
#ifndef XALLOC_H
    #include "xalloc.h"
#endif
#include "voidStack.h"

typedef struct {
    int x1, y1, x2, y2;     /* with x2 > x1 and y2 > y1 */
} rect;

typedef struct {
    int **f;
    rect *r;        /* the rect describing the field */
    int xdim, ydim; /* redundant, since those infos are already contained within
                       the supplied rect, but it's easier to read that way.. */
} field;

void printField(field *f);

field *createField(int xdim, int ydim);
void delField(field *f);
void setField(field *f, rect *r, int val);
void copyField(field *src, field *dest);
int isFree(field *f, rect *r);      /* returns 1 if the area described by rect is all zeros in field */
int getFreeCount(field *f);
rect *getBiggestFree(field *f);     /* gets biggest free rect in field *f */
stack getAllFree(field *f, rect *r);
void fillField(field *f, rect *r);
int fillFieldRec(field *f, rect *r, int rectcount, int *max, field *sol);

rect *createRect(int startx, int starty, int xsize, int ysize);
void copyRect(rect *src, rect *dest);
void setRect(rect *r, int x1, int y1, int x2, int y2);
int getArea(rect *r);
void delRect(rect *r);
void moveRect(rect *r, int x, int y);
void resizeRect(rect *r, int xsize, int ysize);
void rotateRect(rect *r);           /* rotates *r by 90 degrees. (the top left corner will be the same) */
int isInRect(rect *r, int x, int y);
int isSubRect(rect *r, rect *sub);
int areCongruent(rect *r, rect *s);



void fillField(field *f, rect *r) {
    int max = 0;
    field *solution = createField(f->xdim, f->ydim);
    fillFieldRec(f, r, 1, &max, solution);
    printField(solution);
}

int fillFieldRec(field *f, rect *r, int rectcount, int *max, field *sol) {
    stack p = getAllFree(f, r);
    rect *new = shift(p);
    if (new == NULL) {
        destroyStack(p);
        if (rectcount > *max) {
            *max = rectcount;
            copyField(f, sol);
            if (getFreeCount(f) < getArea(r)) {
                return 1;
            }
            printField(f);  /* print intermediate solutions */
        }
        return 0;
    }
    while (new != NULL) {
        setField(f, new, rectcount);
        if (fillFieldRec(f, r, rectcount + 1, max, sol)) {
            return 1;
        }
        setField(f, new, 0);
        delRect(new);
        new = shift(p);
    }
    destroyStack(p);
    return 0;
}

rect *createRect(int startx, int starty, int xsize, int ysize) {
    rect *r = xmalloc(sizeof(rect));
    r->x1 = startx;
    r->y1 = starty;
    r->x2 = startx + xsize - 1;
    r->y2 = startx + ysize - 1;
    return r;
}

void delRect(rect *r) {
    free(r);
}

void setRect(rect *r, int x1, int y1, int x2, int y2) {
    r->x1 = x1;
    r->y1 = y1;
    r->x2 = x2;
    r->y2 = y2;
}

void copyRect(rect *src, rect *dest) {
    /* sets *dest to describe the same area as *src */
    dest->x1 = src->x1;
    dest->y1 = src->y1;
    dest->x2 = src->x2;
    dest->y2 = src->y2;
}

int getArea(rect *r) {
    return ( ((r->x2 - r->x1) + 1) * ((r->y2 - r->y1) + 1) );
}

void resizeRect(rect *r, int xsize, int ysize) {
    r->x2 = r->x1 + xsize;
    r->y2 = r->y1 + ysize;
}

void moveRect(rect *r, int x, int y) {
    int xsize, ysize;
    xsize = r->x2 - r->x1;
    ysize = r->y2 - r->y1;
    r->x1 = x;
    r->y1 = y;
    resizeRect(r, xsize, ysize);
}

void rotateRect(rect *r) {
    /* rotates *r by 90 degrees. (the top left corner will stay the same) */
    int xsize, ysize;
    xsize = r->x2 - r->x1;
    ysize = r->y2 - r->y1;
    resizeRect(r, ysize, xsize);
}

field *createField(int xdim, int ydim) {
    int *rows = xmalloc(xdim * ydim * sizeof(int));
    int **cols = xmalloc(ydim * sizeof(int *));
    int i;
    for (i = 0; i < ydim; i++) {
        cols[i] = &rows[i * xdim];
    }
    rect *r = xmalloc(sizeof(rect));
    r->x1 = 0;
    r->y1 = 0;
    r->x2 = xdim - 1;
    r->y2 = ydim - 1;
    field *f = xmalloc(sizeof(field));
    f->f = cols;
    f->r = r;
    f->xdim = xdim;
    f->ydim = ydim;
    setField(f, f->r, 0);
    return f;
}

void delField(field *f) {
    free(f->r);
    int i;
    for (i = 0; i < f->ydim; i++) {
        free(f->f[i]);
    }
    free(f->f);
    free(f);
}

void setField(field *f, rect *r, int val) {
    if (! isSubRect(f->r, r)) {
        return;
    }
    int x, y;
    for (y = r->y1; y <= r->y2; y++) {
        for (x = r->x1; x <= r->x2; x++) {
            f->f[y][x] = val;
        }
    }
}

void copyField(field *src, field *dest) {
    int x, y;
    for (y = 0; (y < src->ydim && y < dest->ydim); y++) {
        for (x = 0; (x < src->xdim && x < dest->xdim); x++) {
            dest->f[y][x] = src->f[y][x];
        }
    }
}

int isFree(field *f, rect *r) {
    /* returns true if the area described by *r is all zeros in *f */
    if (! isSubRect(f->r, r)) {
        return 0;
    }
    int x, y;
    for (y = r->y1; y <= r->y2; y++) {
        for (x = r->x1; x <= r->x2; x++) {
            if (f->f[y][x]) {
                /* nonzero */
                return 0;
            }
        }
    }
    return 1;
}

int getFreeCount(field *f) {
    int x, y, count = 0;
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            if (f->f[y][x] == 0) {
                count++;
            }
        }
    }
    return count;
}

rect *getBiggestFree(field *f) {
    int x1, y1, x2, y2, size, maxsize;
    rect *tmp = createRect(0, 0, 1, 1);
    rect *max = createRect(0, 0, 1, 1);
    maxsize = 0;
    for (x1 = 0; x1 < f->xdim; x1++) {
    for (y1 = 0; y1 < f->ydim; y1++) {
    for (x2 = x1; x2 < f->xdim; x2++) {
    for (y2 = y1; y2 < f->ydim; y2++) {
        setRect(tmp, x1, y1, x2, y2);
        size = getArea(tmp);
        if (size > maxsize && isFree(f, tmp)) {
            maxsize = size;
            copyRect(tmp, max);    /* max now describes the same rect as tmp */
        }
    }
    }
    }
    }
    delRect(tmp);
    if (getArea(max) == 1) {
        delRect(max);
        return NULL;
    }
    return max;
}

stack getAllFree(field *f, rect *r) {
    /* gets free areas within *f where *r fits (actually not all, see optimization below) */
    int x1, y1, x2, y2;
    stack s = newStack(2);
    rect *tmp = createRect(0, 0, 1, 1);
    int xmin, ymin;
    xmin = r->x2 - r->x1;
    ymin = r->y2 - r->y1;
    for (x1 = 0; x1 < f->xdim; x1++) {
    for (y1 = 0; y1 < f->ydim; y1++) {
    for (x2 = x1; x2 < f->xdim; x2++) {
    for (y2 = y1; y2 < f->ydim; y2++) {
        if (         
            ((x1 == 0) || f->f[y1][x1-1])   /* only allow "continuous" placement */
         && ((y1 == 0) || f->f[y1-1][x1])
        ) { 
            setRect(tmp, x1, y1, x2, y2);
            if (areCongruent(tmp, r) && isFree(f, tmp)) {
                push(s, tmp);
                tmp = createRect(0, 0, 1, 1); 
            }   
        }   
    }   
    }   
    }
    }
    push(s, NULL);
    return s;
}

void printField(field *f) {
    int x, y;
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            printf("%c ", f->f[y][x] ? f->f[y][x] + 64 : '.');
        }
        printf("\n");
    }
    printf("-- \n");
}

int isInRect(rect *r, int x, int y) {
    if (x >= r->x1 && x <= r->x2 && y >= r->y1 && y <= r->y2) {
        return 1;
    }
    return 0;
}

int isSubRect(rect *r, rect *sub) {
    if (isInRect(r, sub->x1, sub->y1) && isInRect(r, sub->x2, sub->y2)) {
        return 1;
    }
    return 0;
}

int areCongruent(rect *r, rect *s) {
    int rxsize, rysize, sxsize, sysize, success = 0;
    rxsize = r->x2 - r->x1;
    rysize = r->y2 - r->y1;
    sxsize = s->x2 - s->x1;
    sysize = s->y2 - s->y1;
    if (
        (rxsize == sxsize && rysize == sysize)
     || (rxsize == sysize && rysize == sxsize)
    ) {
        success = 1;
    }
    return success;
}

Der Header für den "typenlosen" void pointer Stack:

Code:

#include <stdio.h>
#include <stdlib.h>
#ifndef XALLOC_H
    #include "xalloc.h"
#endif

#define POP_EMPTY NULL

typedef struct stackStruct {
    void **ptr;
    int pos;
    int size;
} *stack;

stack newStack(int size);
void destroyStackDeep(stack s);
void destroyStack(stack s);
void push(stack s, void *ptr);
void *pop(stack s);
void *top(stack s);
void *shift(stack s);

stack newStack(int size) {
    stack stck = xmalloc(sizeof(struct stackStruct));
    void **ptr = xmalloc(size * sizeof(void *));
    stck->ptr = ptr;
    stck->pos = 0;
    stck->size = size;
    return stck;
}

void destroyStack(stack s) {
    free(s->ptr);
    free(s);
}

void destroyStackDeep(stack s) {
    void *ptr = pop(s);
    while (ptr != NULL) {
        free(ptr);  /* make sure the ptrs in the stack are actually free()able if you call this method */
        ptr = pop(s);
    }
    destroyStack(s);
}


void push(stack s, void *ptr) {
    if (s->pos == s->size - 1) {
        s->size *= 2;
        s->ptr = xrealloc(s->ptr, s->size * sizeof(void *));
    }
    s->ptr[s->pos] = ptr;
    s->pos++;
}

void *pop(stack s) {
    if (s->pos == 0) {
      return POP_EMPTY;
    }
    s->pos--;
    return s->ptr[s->pos+1];
}

void *top(stack s) {
    return s->ptr[s->pos];
}

void *shift(stack s) {
    void *retptr = s->ptr[0];
    int i;
    for (i = 1; i < s->size; i++) {
        s->ptr[i-1] = s->ptr[i];
    }
    return retptr;
}

Und zu guter letzt für die *alloc() Familie mit automatischem Errorchecking:

Code:

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

#define XALLOC_H 1

void *xmalloc(int size) {
    void *ptr = malloc(size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

void *xcalloc(int nitems, int size) {
    void *ptr = calloc(nitems, size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

void *xrealloc(void *ptr, int size) {
    ptr = realloc(ptr, size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

Test:

Code:

$ time ./rect 13 14 3 5
A A A D D D G G G I I I . 
A A A D D D G G G I I I . 
A A A D D D G G G I I I . 
A A A D D D G G G I I I . 
A A A D D D G G G I I I . 
B B B E E E H H H J J J . 
B B B E E E H H H J J J . 
B B B E E E H H H J J J . 
B B B E E E H H H J J J . 
B B B E E E H H H J J J . 
C C C C C F F F F F . . . 
C C C C C F F F F F . . . 
C C C C C F F F F F . . . 
. . . . . . . . . . . . . 
-- 
A A A C C C C C H H H H H 
A A A C C C C C H H H H H 
A A A C C C C C H H H H H 
A A A D D D D D I I I I I 
A A A D D D D D I I I I I 
B B B D D D D D I I I I I 
B B B E E E E E J J J J J 
B B B E E E E E J J J J J 
B B B E E E E E J J J J J 
B B B F F F G G G K K K . 
. . . F F F G G G K K K . 
. . . F F F G G G K K K . 
. . . F F F G G G K K K . 
. . . F F F G G G K K K . 
-- 
A A A C C C C C H H H H H 
A A A C C C C C H H H H H 
A A A C C C C C H H H H H 
A A A D D D D D I I I I I 
A A A D D D D D I I I I I 
B B B D D D D D I I I I I 
B B B E E E E E J J J J J 
B B B E E E E E J J J J J 
B B B E E E E E J J J J J 
B B B F F F G G G K K K . 
. . . F F F G G G K K K . 
. . . F F F G G G K K K . 
. . . F F F G G G K K K . 
. . . F F F G G G K K K . 
-- 

real    0m47.021s
user    0m44.408s
sys     0m0.008s

Da er Zwischenlösungen ausgibt wird die Lösung bereits wenige Millisekunden nach dem Start ausgegeben, allerdings braucht er dann noch ne Weile um festzustellen, ob das wirklich die Beste Lösung ist.. (Btw kann man (wenn man denn will) am Anfang der fillFieldRec() Funktion einfach ein printField(f); hinpacken und sich die Ausgabe dann animiert mittles desselben Perl-Skripts vom Springerproblemthread ausgeben lassen.)

goflo · Feb 24, 2009

ja, mir war langweilig...

Code:

package de.hackerboard.programmieraufgaben.steine_in_feld;

public class StoneCalculator {
	public static void main(String[] args) {
		System.out.println("es passen " + calcualte(20, 20, 6, 1) + " Steine ins Feld...");
		System.out.println("es passen " + calcualte(20, 20, 6, 2) + " Steine ins Feld...");
		System.out.println("es passen " + calcualte(10, 20, 12, 1) + " Steine ins Feld...");
		System.out.println("es passen " + calcualte(8, 20, 12, 10) + " Steine ins Feld...");
	}
	
	public static int calcualte(double fieldWidth, double fieldLength,
								double stoneWidth, double stoneLength) {
		int rows = 0;
		int cols = 0;
		int rotatedStones = 0;
		double r = 0.0;
		
		if ((stoneWidth > fieldWidth) || (stoneLength > fieldLength)) {
			double temp = stoneWidth;
			stoneWidth = stoneLength;
			stoneLength = temp;
		}
		
		cols = (int)(fieldWidth / stoneWidth);
		r = fieldWidth % stoneWidth;
		if ((stoneLength <= r) && (stoneWidth <= fieldLength)) {
			rotatedStones = calcualte(r, fieldLength, stoneLength, stoneWidth);
		}
		
		rows = (int)(fieldLength / stoneLength);
		r = fieldLength % stoneLength;
		if ((stoneWidth <= r) && (stoneLength <= fieldWidth)) {
			rotatedStones += calcualte(fieldLength, r, stoneWidth, stoneLength);
		}
		
		return cols*rows + rotatedStones;
	}
}

Wie von 'AlterHacker' angemerkt werden Steine auch gedreht wenn Sie denn in die übrig bleibende Fläche passen.

//EDIT: da ich dabei bin mich mit Python/Jython anzufreunden auch noch eine passende Lösung dazu. Algorithmus ist der selbe!

Code:

if __name__ == '__main__':
    from SteineInFeld import calcStones
    
    print 'Feld: 20x20  -  Stein: 6x1    --> %i' % (calcStones(20,20,6,1))
    print 'Feld: 20x20  -  Stein: 6x2    --> %i' % (calcStones(20,20,6,2))
    print 'Feld: 10x20  -  Stein: 12x1   --> %i' % (calcStones(10,20,12,1))
    print 'Feld: 8x20   -  Stein: 12x10  --> %i' % (calcStones(8,20,12,10))

Code:

def calcStones(fieldW, fieldL, stoneW, stoneL):
    if ((stoneW > fieldW) or (stoneL > fieldL)):
        temp = stoneW
        stoneW = stoneL
        stoneL = temp
        
    rotatedStones = 0
    cols = (int)(fieldW / stoneW)
    r = fieldW % stoneW
    if ((stoneL <= r) and (stoneW <= fieldL)):
        rotatedStones = calcStones(r, fieldL, stoneL, stoneW)

    
    rows = (int)(fieldL / stoneL)
    r = fieldL % stoneL
    if ((stoneW <= r) and (stoneL <= fieldW)):
        rotatedStones += calcStones(fieldL, r, stoneW, stoneL)
    
    return cols * rows + rotatedStones

Wieviele Steine passen in eine Fläche?

MontyPerl

0

goflo

0