Solved

Posted on 2006-05-25

Hi,

I came across one puzzle, which I can't seem to find the right solution to start... could anyone give a suggestion please? I want to create a c# program to do that.

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).

I came across one puzzle, which I can't seem to find the right solution to start... could anyone give a suggestion please? I want to create a c# program to do that.

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).

12 Comments

Create another function that adds a random greenhouse to a greenhouse scheme. It has to make sure the greenhouse doesn't overlap other greenhouses, and make sure you don't add any beyond the maximum allowed number.

Create another function that deletes a random greenhouse from a greenhouse scheme. If the scheme is already empty, don't worry about it.

Create another function that tweaks a random greenhouse, moving one of its edges by one unit. If it would cause an invalid greenhouse (zero area) or an overlapping greenhouse, then just don't do it.

Now you're ready to do a simple nondeterministic greedy method to find a decent solution.

mrichmon, we have a new team lead developer joining our team and our IT manager gave him this puzzle, so I was wondering myself...

and only the $10 cost of each greenhouse can change, so the best number of greenhouses to build is the minimum possible.

You can start trying to cover everything with 1 rectangle, then with 2 rectangles, etc. stopping as soon as you succeed.

To determine whether it is possible to cover everything with n rectangles without overlap,

it suffices to check every combination of upper left corners and lower right corners.

Some speedups to this may occur to you too.

Those functions I outlined would also be a good foundation for a genetic algorithm implementation. That would be similar to the greedy algorithm, except you keep many originals instead of just one, and probabilistically weed out the higher-cost schemes.

I'm also thinking that it would make sense to slowly ramp up the cost-per-missed-strawberry

One idea might be to first se what the largest greenhouse is that you can make, then repeat that again and again.

One way to find the largest greenhouse is to try starting at every x,y where these is a strawberry, see if you can stretch as far as you can to the right and down while still enclosing all strawberrys. Note the size and go to the next x,y. When you've scanned them all, choose the largest greenhouse and mark all those spots. Repeat the whole deal until all the strawberrys are covered.

There may be a better way, or flaws in this method, but that's the best I can dream up right now.

I started with a little parsing mechanism and index pointer function (Replace(...)) to find and replace character at the specified location in an char array, which works fine... All I have left is to implement a deterministic function to build the actual greenhouses.

any other suggestions?

using System;

using System.IO;

using System.Text.RegularExpress

namespace StrawberryFields

{

class GreenHouse

{

char[] main_buffer = null;

char[] work_buffer = null;

char[] alpha = null;

Dimension dim;

private enum Direction

{

RIGHT,

LEFT,

UP,

DOWN

}

struct Dimension

{

public int Width;

public int Height;

}

internal GreenHouse(string src)

{

dim = new Dimension();

//FileInfo f = new FileInfo(src);

using (StreamReader fs = new StreamReader(src))

{

Regex rx = new Regex(@"\s+", RegexOptions.Multiline | RegexOptions.Compiled);

this.main_buffer = rx.Replace(fs.ReadToEnd().

this.work_buffer = new char[this.main_buffer.Leng

this.dim.Width=0;

this.dim.Height=1;

for (int i=0; i<this.main_buffer.Length;

{

if(this.main_buffer[i]=='\

this.dim.Height++;

else

this.dim.Width++;

this.work_buffer[i]=this.m

}

this.alpha = new char[15] {'A','B','C','D','E','F','

this.dim.Width=this.main_b

this.Build();

}

}

void Build()

{

Console.WriteLine("{0}Widt

this.Replace(1,0,this.alph

Console.WriteLine(this.mai

}

void Replace(int rowIndex, int colIndex, char chr)

{

try

{

this.main_buffer[rowIndex*

}

catch (IndexOutOfRangeException ex)

{

Console.WriteLine("Error: " + ex.Message);

}

}

}

}

In this example: (@=straberry, .=blank)

@.@

. @.

@.@

1 greenhouse covering the whole thing is cheapest, even though it covers non-strawberries.

@@@@@@@@@@@@@@

@@@@@@@@@@@@@@

@@@@@@@@@@@@@@

@@@@@@@@@@@@@@

@

Probably use a recursive function. In a loop, it would try to place a greenhouse in every space, of every size, and recursively call itself to repeat.

place_greenhouse (Map as greenhouse_map) {

#If all strawberries are covered, save this map

if(success(Map)) {

push good_maps, Map;

return;

}

for(start_column=1;start_c

for(start_row=1;start_row<

for(greenhousewidth=1;gree

for(greenhouseheight=1;gre

#Skip if this greenhouse overlaps existing greenhouses

next if overlap(Map, start_column, start_row, greenhousewidth, greenhouseheight);

thismap=make_map(Map, start_column, start_row, greenhousewidth, greenhouseheight);

place_greenhouse(thismap);

}

}

}

}

}

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

Statistics & Data Sceicne | 2 | 61 | |

2k Power n formula | 2 | 27 | |

Probability Distribution | 2 | 36 | |

Interest rate formula | 7 | 42 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**18** Experts available now in Live!