This is a basic heuristic approach to solving this problem:
-- A randomly sized house is added to a random location within the field.
-- It is reduced in size until it has no "useless" (edges that cover no strawberries) portions
-- repeat...each house that is added is checked to see if it can join with a previously existing house
I first wrote it in perl, but I decided that it was far too slow to get any testing done on it, so I rewrote it in C. Compiled using full optimization, with the latest version of gcc, it ran 10000 iterations per field in about 16 minutes on a P4 1.8 GHz running Fedora Core 2.
There are a number of improvements that could be made, but I don't want to spend my whole life on this problem right now :)
- Instead of picking a random sized house, in a random location, a Metropolis algorithm could be used to give more weight to picking a size and location that are more conducive to covering the fields. This would have muddied the code (and made it a LOT longer, so I left this out).
- I could determine if a solution is optimal (for simple fields) so all iterations don't need to be performed for the simplest fields, but these are the best performing anyway, so it's not a big performance hit.
- I'm sure there's a number of spots where a faster algorithm could be used, but I generally took the approach of the code being readable instead.
I compiled using gcc version 3.3.3 20040412:
$>gcc -O3 -o strawberry_fields strawberry_fields.c
And ran:
$>strawberry_fields rectangles.txt 10000
/*
Strawberries are growing in a rectangular field of length and width at most 50. You want to build greenhouses to enclose the strawberries. Greenhouses are rectangular, axis-aligned with the field (i.e., not diagonal), and may not overlap. The cost of each greenhouse is $10 plus $1 per unit of area covered.
Write a program that chooses the best number of greenhouses to build, and their locations, so as to enclose all the strawberries as cheaply as possible. Heuristic solutions that may not always produce the lowest possible cost will be accepted: seek a reasonable tradeoff of efficiency and optimality.
Your program must read a small integer 1 . N . 10 representing the maximum number of greenhouses to consider, and a matrix representation of the field, in which the '@' symbol represents a strawberry. Output must be a copy of the original matrix with letters used to represent greenhouses, preceded by the covering's cost. Here is an example input-output pair:
Input Output
4
..@@@@@...............
..@@@@@@........@@@...
.....@@@@@......@@@...
.......@@@@@@@@@@@@...
.........@@@@@........
.........@@@@@........
90
..AAAAAAAA............
..AAAAAAAA....CCCCC...
..AAAAAAAA....CCCCC...
.......BBBBBBBCCCCC...
.......BBBBBBB........
.......BBBBBBB........
In this example, the solution cost of $90 is computed as (10+8*3) + (10+7*3) + (10+5*3).
Run your program on the 9 sample inputs found in this file and report the total cost of the 9 solutions found by your program, as well as each individual solution.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define MAX_HOUSES 10
//#define ITERATIONS 2000
enum edge {
TOP,
BOTTOM,
LEFT,
RIGHT
};
enum direction {
VERTICAL,
HORIZONTAL
};
struct _field
{
char field[50][50];
int length;
int width;
} typedef FIELD;
struct _orig_field
{
FIELD field;
int max_houses;
struct _orig_field *next;
} typedef ORIG_FIELD;
struct _housed_field
{
FIELD field;
int cost;
} typedef HOUSED_FIELD;
struct _house
{
int x;
int y;
int width;
int length;
} typedef HOUSE;
/* prototypes */
void print_field(const FIELD *);
void copy_field(const FIELD *, FIELD *);
int min(int, int);
int max(int, int);
int check_field(const FIELD *);
void cover_field(FIELD *, int);
void get_random_house(HOUSE *, const FIELD *);
int trim_house_edge(const FIELD *, FIELD *, const int, const int);
void convert_to_letters(FIELD *);
int trim_house(FIELD *,
const FIELD *,
const int,
const int,
const int,
const int);
int get_house(HOUSE *, const FIELD *, const int);
void join_houses(FIELD *);
void add_house(FIELD *field, const HOUSE *, const int);
main(int argc, char *argv[])
{
FILE *rectangles;
long file_length;
char *all_fields;
ORIG_FIELD *head;
ORIG_FIELD *tail;
ORIG_FIELD *field;
char *field_token_ptr=0;
int row_index;
HOUSED_FIELD hfield;
HOUSED_FIELD win_field;
int i,x,y;
int iterations;
int new_cost;
if(argc != 3)
{
printf("Usage\n"
"\tsf <file> <iterations>\n");
return -1;
}
iterations=atoi(argv[2]);
printf("iterations: %d\n", iterations);
/* first, read the entire file into memory */
if((rectangles = fopen(argv[1], "r")) == NULL)
{
printf("Error opening file\n");
return -1;
}
fseek(rectangles, 0L, SEEK_END); /* Position to end of file */
file_length = ftell(rectangles); /* Get file length */
rewind(rectangles); /* Back to start of file */
all_fields = (char *)calloc(file_length + 1, sizeof(char));
if(all_fields == NULL )
{
printf("\nInsufficient memory to read file.\n");
return -1;
}
fread(all_fields, file_length, 1, rectangles); /* Read the entire file */
fclose(rectangles);
/**********************************************************************
* Get all of the fields into a linked list *
**********************************************************************/
if((field = (ORIG_FIELD *)malloc(sizeof(ORIG_FIELD))) == NULL)
{
printf("\nInsufficient memory.\n");
return -1;
}
/* init linked list */
head=field;
tail=field;
field->next=NULL;
/* *all_fields contains all of the field "images" */
field_token_ptr = (char *)strtok(all_fields, "\n");
field->max_houses = atoi(field_token_ptr);
field_token_ptr = (char *)strtok(NULL, "\n");
/* move the pointer to the beginning of the next field */
row_index=0;
while(field_token_ptr != NULL && !isdigit(*field_token_ptr))
{
field->field.width=strlen(field_token_ptr);
strcpy(field->field.field[row_index], field_token_ptr);
row_index++;
field_token_ptr = (char *)strtok(NULL, "\n");
}
field->field.length=row_index;
/* go through each field and place it into it's own data object then place it on the end of the list */
while(field_token_ptr != NULL)
{
if((field = (ORIG_FIELD *)malloc(sizeof(ORIG_FIELD))) == NULL)
{
printf("\nInsufficient memory.\n");
return -1;
}
tail->next = field;
field->next = NULL;
tail=field;
field->max_houses = atoi(field_token_ptr);
field_token_ptr = (char *)strtok(NULL, "\n");
row_index=0;
while(field_token_ptr != NULL && !isdigit(*field_token_ptr))
{
field->field.width=strlen(field_token_ptr);
strcpy(field->field.field[row_index], field_token_ptr);
row_index++;
field_token_ptr = (char *)strtok(NULL, "\n");
}
field->field.length=row_index;
}
free(all_fields);
/**********************************************************************
* all fields are in a linked list *
**********************************************************************/
/* seed the random number generator */
srand((unsigned)time(NULL));
field = head;
/* do each field */
while(field != NULL)
{
/* copy the field to a working field */
copy_field(&field->field, &(hfield.field));
/* start with one huge house over the whole field */
for(y=0; y<hfield.field.length; y++)
for(x=0; x<hfield.field.width; x++)
hfield.field.field[y][x] = '1';
win_field.cost = get_field_cost(&hfield.field);
/* win_field stores the best housing scheme so far */
copy_field(&(hfield.field), &win_field.field);
/* try a new housing scheme for each iteration */
for(i=0; i<iterations; i++)
{
/* get the field we're working on */
copy_field(&field->field, &(hfield.field));
/* get a housing scheme (may not cover everything) */
cover_field(&hfield.field, field->max_houses);
if(check_field(&hfield.field))
{ /* if it covers all strawberries, join any houses can be joined */
join_houses(&hfield.field);
/* see if it's the new best field */
new_cost = get_field_cost(&hfield);
if(new_cost < win_field.cost)
{
win_field.cost = new_cost;
copy_field(&(hfield.field), &win_field.field);
}
}
else
{
/* only count it as an itereation if it came up with a solution */
/* this reduces the time spent on easy ones */
i--;
}
}
/*printf("\n\n"); */
/*print_field(&(field->field)); */
/* one last attempt to minimize for good measure (hardly affects performance) */
join_houses(&win_field.field);
/* print out results */
printf("\n%d\n", get_field_cost(&win_field.field));
convert_to_letters(&win_field.field);
print_field(&(win_field.field));
/* free that field and onto the next! */
field = field->next;
free(head);
head = field;
}
return 0;
}
/* joins any adjacent houses together.
this isn't foolproof as a complicated set that could be joined together will get pased over,
although it does make amends for that. the best is could do with this:
8744.....
1544..... is this: 5544.....
2222..... 5544.....
......... 2222.....
.........
*/
void join_houses(FIELD *field)
{
HOUSE house1;
HOUSE house2;
int i,j;
int temp;
for(i=0; i<MAX_HOUSES; i++)
for(j=0; j<MAX_HOUSES; j++)
if(i!=j)
{
if(get_house(&house1, field, i) && get_house(&house2, field, j))
{
if(house1.x == house2.x &&
house1.width == house2.width)
{ /* they are aligned...let's see it they are adjacent */
if(house1.y == house2.y+house2.length)
add_house(field, &house1, j);
else if(house2.y == house1.y+house1.length)
add_house(field, &house1, j);
}
else if(house1.y == house2.y &&
house1.length == house2.length)
{
if(house1.x == house2.x+house2.width)
add_house(field, &house1, j);
else if(house2.x == house1.x+house1.width)
add_house(field, &house1, j);
}
}
}
}
/* writes specified house into specified field */
void add_house(FIELD *field, const HOUSE *house, const int house_num)
{
int x,y;
for(y=house->y; y<house->y+house->length; y++)
for(x=house->x; x<house->x+house->width; x++)
field->field[y][x]=(char)(house_num+48);
}
/* gets the specifed house out of the specified field */
/* returns 1 if house exists, 0 if not; */
int get_house(HOUSE *house, const FIELD *field, const int house_num)
{
int x,y;
int house_width_pos, house_len_pos;
house->x=field->width+1;
house->y=field->length+1;
house_width_pos=-1;
house_len_pos=-1;
for(y=0; y<field->length; y++)
for(x=0; x<field->width; x++)
if(field->field[y][x] == house_num+48)
{
house->x=min(house->x, x);
house->y=min(house->y, y);
house_width_pos=max(house_width_pos, x);
house_len_pos=max(house_len_pos, y);
}
house->width=1+house_width_pos-house->x;
house->length=1+house_len_pos-house->y;
if(house->length>0 && house->width>0)
return 1;
else
return 0;
}
/* convert my numbers to your letters */
void convert_to_letters(FIELD *field)
{
int x,y;
for(y=0; y<field->length; y++)
for(x=0; x<field->width; x++)
switch(field->field[y][x]-48)
{
case 0:
field->field[y][x]='A';
break;
case 1:
field->field[y][x]='B';
break;
case 2:
field->field[y][x]='C';
break;
case 3:
field->field[y][x]='D';
break;
case 4:
field->field[y][x]='E';
break;
case 5:
field->field[y][x]='F';
break;
case 6:
field->field[y][x]='G';
break;
case 7:
field->field[y][x]='H';
break;
case 8:
field->field[y][x]='I';
break;
case 9:
field->field[y][x]='J';
break;
default:
break;
}
}
/* the main workhorse */
/* continues adding houses until it runs out of houses or all strawberries */
/* are covered. */
void cover_field(FIELD *field, int max_houses)
{
int house_number=0;
FIELD field_copy;
HOUSE house;
int i,x,y;
int trimming_flag;
copy_field(field, &field_copy);
while(!check_field(field) && house_number < max_houses)
{
get_random_house(&house, field);
while(!check_if_house_fits(&house, field))
{
get_random_house(&house, field);
}
add_house(field, &house, house_number);
/* 4 sides, trim each edge */
for(i=0; i<4; i++)
{
/* it is possible to heavily optimize the detection algorithm here by not allowing it */
/* to continue unless it can find a place to put a house, but this leads to some horribly */
/* bad performing runs as it tends to only get into trouble here when it has a bad starting */
/* position and that one tends to get tossed anyway */
/*if(!trim_house_edge(&field_copy, field, house_number, i) && i==3) */
/* { */
/* house_number--; */
/* } */
trim_house_edge(&field_copy, field, house_number, i);
}
house_number++;
}
}
/* cut off useless edges of houses - this also as the effect of removing a useless house */
/* return 1 if the house still exists afterward 0, 0 if it's gone */
int trim_house_edge(const FIELD *orig_field, FIELD *hfield, const int house_number, const int edge)
{
int trimming_flag=1;
HOUSE house;
int x,y;
while(trimming_flag)
{
get_house(&house, hfield, house_number);
if(house.width <= 0 || house.length <= 0)
{
return 0;
}
else
switch(edge)
{
case TOP:
trimming_flag=trim_house(hfield, orig_field, house.x, house.x+house.width, house.y, HORIZONTAL);
break;
case BOTTOM:
trimming_flag=trim_house(hfield, orig_field, house.x, house.x+house.width, house.y+house.length-1, HORIZONTAL);
break;
case LEFT:
trimming_flag=trim_house(hfield, orig_field, house.y, house.y+house.length, house.x, VERTICAL);
break;
case RIGHT:
trimming_flag=trim_house(hfield, orig_field, house.y, house.y+house.length, house.x+house.width-1, VERTICAL);
break;
default:
exit(-1);
}
}
return 1;
}
/* do the acutal trimming (shrinking a house so that it only covers the minimum it needs to */
int trim_house(FIELD *field,
const FIELD *ref_field,
const int start,
const int end,
const int fixed,
const int direction)
{
int i;
int trimming_flag=1;
if(direction == VERTICAL)
{
for(i=start; i<end; i++)
{
if(ref_field->field[i][fixed] == '@')
trimming_flag=0;
}
if(trimming_flag)
{
for(i=start; i<end; i++)
field->field[i][fixed] = '.';
}
}
else
{
for(i=start; i<end; i++)
{
if(ref_field->field[fixed][i] == '@')
trimming_flag=0;
}
if(trimming_flag)
{
for(i=start; i<end; i++)
field->field[fixed][i] = '.';
}
}
return trimming_flag;
}
/* boolean function to determine if a house can be added to a field */
int check_if_house_fits(const HOUSE *house, const FIELD *field)
{
int x,y;
/* check the dimensions of the house to see if it overlaps another house */
for(y=house->y; y<house->y+house->length; y++)
for(x=house->x; x<house->x+house->width; x++)
if(isdigit(field->field[y][x]))
{
return 0;
}
return 1;
}
/* returns a random house that will fit in the specified field */
void get_random_house(HOUSE *house, const FIELD *field)
{
house->width = 1+((int)field->width*(rand()/(RAND_MAX + 1.0)));
house->length = 1+((int)field->length*(rand()/(RAND_MAX + 1.0)));
house->x=(int)((1+field->width-house->width)*(rand()/(RAND_MAX + 1.0)));
house->y=(int)((1+field->length-house->length)*(rand()/(RAND_MAX + 1.0)));
}
/* boolean function to determine if all strawberies are covered */
int check_field(const FIELD *field)
{
int x,y;
for(y=0; y<field->length; y++)
for(x=0; x<field->width; x++)
if(field->field[y][x] == '@')
{
return 0;
}
return 1;
}
/* output the field to the screen */
void print_field(const FIELD *field)
{
int x,y;
for(y=0; y<field->length; y++)
{
for(x=0; x<field->width; x++)
{
printf("%c", field->field[y][x]);
}
printf("\n");
}
}
/* copy one field to another */
void copy_field(const FIELD *original, FIELD *new)
{
int x,y;
for(y=0; y<original->length; y++)
for(x=0; x<original->width; x++)
new->field[y][x] = original->field[y][x];
new->length=original->length;
new->width=original->width;
}
/* determine the cost of the greenhouses on a field */
int get_field_cost(const FIELD *field)
{
int total=0;
int x,y;
int houses[MAX_HOUSES];
for(x=0; x<MAX_HOUSES; x++)
{
houses[x]=0;
}
for(y=0; y<field->length; y++)
for(x=0; x<field->width; x++)
if(isdigit(field->field[y][x]))
{
/* a char - 48 is the actual number */
houses[(int)(field->field[y][x] - 48)]++;
}
for(x=0; x<MAX_HOUSES; x++)
{
if(houses[x])
{
total += 10 + houses[x];
}
}
return total;
}
/* min and max functions */
int min(int x, int y)
{
if(x>y)
return y;
else
return x;
}
int max(int x, int y)
{
if(x<y)
return y;
else
return x;
}
/* test data
FIELD foo;
foo.length=8;
foo.width=9;
foo.field[0][0]='8';
foo.field[0][1]='7';
foo.field[0][2]='4';
foo.field[0][3]='4';
foo.field[0][4]='.';
foo.field[0][5]='.';
foo.field[0][6]='.';
foo.field[0][7]='.';
foo.field[0][8]='.';
foo.field[1][0]='1';
foo.field[1][1]='5';
foo.field[1][2]='4';
foo.field[1][3]='4';
foo.field[1][4]='.';
foo.field[1][5]='.';
foo.field[1][6]='.';
foo.field[1][7]='.';
foo.field[1][8]='.';
foo.field[2][0]='2';
foo.field[2][1]='2';
foo.field[2][2]='2';
foo.field[2][3]='2';
foo.field[2][4]='.';
foo.field[2][5]='.';
foo.field[2][6]='.';
foo.field[2][7]='.';
foo.field[2][8]='.';
foo.field[3][0]='.';
foo.field[3][1]='.';
foo.field[3][2]='.';
foo.field[3][3]='.';
foo.field[3][4]='.';
foo.field[3][5]='.';
foo.field[3][6]='.';
foo.field[3][7]='.';
foo.field[3][8]='.';
foo.field[4][0]='.';
foo.field[4][1]='.';
foo.field[4][2]='.';
foo.field[4][3]='.';
foo.field[4][4]='.';
foo.field[4][5]='.';
foo.field[4][6]='.';
foo.field[4][7]='.';
foo.field[4][8]='.';
foo.field[5][0]='.';
foo.field[5][1]='.';
foo.field[5][2]='.';
foo.field[5][3]='.';
foo.field[5][4]='.';
foo.field[5][5]='.';
foo.field[5][6]='.';
foo.field[5][7]='.';
foo.field[5][8]='.';
foo.field[6][0]='.';
foo.field[6][1]='.';
foo.field[6][2]='.';
foo.field[6][3]='.';
foo.field[6][4]='.';
foo.field[6][5]='.';
foo.field[6][6]='.';
foo.field[6][7]='.';
foo.field[6][8]='.';
foo.field[7][0]='.';
foo.field[7][1]='.';
foo.field[7][2]='.';
foo.field[7][3]='.';
foo.field[7][4]='.';
foo.field[7][5]='.';
foo.field[7][6]='.';
foo.field[7][7]='.';
foo.field[7][8]='.';
print_field(&foo);
printf("\n\n");
join_houses(&foo);
print_field(&foo);
return -1;
*/
No comments:
Post a Comment