Solved

# maze-type of puzzle

Posted on 2006-05-25
590 Views
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 &#8804; N &#8804; 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).
0
Question by:davidlars99

LVL 33

Assisted Solution

Is it a requirement that every strawberry be covered?
0

LVL 13

Author Comment

yes, and only in a rectangular greenhouse which doesn't overlap...
0

LVL 35

Assisted Solution

Is this for a course?
0

LVL 22

Assisted Solution

First thing you need to do is create a function that evaluates a greenhouse scheme and tells you its cost, using the prescribed cost function (10 + width * height).  Include a parameter 'c' for the added cost of each strawberry that is not covered.

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

LVL 13

Author Comment

thanks Nova, I'll try as you say...

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

LVL 84

Assisted Solution

If every strawberry must be covered, the contribution of the  \$1 per unit of area covered is fixed,
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.
0

LVL 22

Assisted Solution

The greedy algorithm would be pretty simple.  You start with an empty greenhouse scheme, make a copy, apply 1 to a few random mutations to the copy, then compare the cost of the copy to the original.  If the solution has improved, replace the original with the mutated copy.  Loop until satisfied.

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 cost parameter.  If it is too big at the beginning, then it will just pick one huge greenhouse to cover up the whole field.  If it is too small at the end, then the greenhouses will not be covering all the strawberries.  So, start with a small cost (15 per missed strawberry or so), then slowly ramp it up (linearly? exponentially?  I don't know...) until it gets to be 10000 or so at the end, to make any incomplete solutions unlikely to survive.

0

LVL 22

Assisted Solution

As ozo said, you want to minimize the number of greenhouses.  That implies you want to make as many large greenhouses as possible.

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.

0

LVL 13

Author Comment

thank you all!

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.RegularExpressions;

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);
{
Regex rx = new Regex(@"\s+", RegexOptions.Multiline | RegexOptions.Compiled);

this.work_buffer = new char[this.main_buffer.Length];

this.dim.Width=0;
this.dim.Height=1;

for (int i=0; i<this.main_buffer.Length; i++)
{
if(this.main_buffer[i]=='\n')
this.dim.Height++;
else
this.dim.Width++;
this.work_buffer[i]=this.main_buffer[i];
}

this.alpha = new char[15] {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'};
this.dim.Width=this.main_buffer.Length/this.dim.Height;
this.Build();
}
}

void Build()
{
Console.WriteLine("{0}Width={1}, Height={2}, Total={3} {4}", "\n", this.dim.Width, this.dim.Height, (this.dim.Width*this.dim.Height), "\n");
this.Replace(1,0,this.alpha[0]);
Console.WriteLine(this.main_buffer);
}

void Replace(int rowIndex, int colIndex, char chr)
{
try
{
this.main_buffer[rowIndex*this.dim.Width+colIndex+rowIndex]=chr;
}
catch (IndexOutOfRangeException ex)
{
Console.WriteLine("Error: " + ex.Message);
}
}
}
}
0

LVL 39

Expert Comment

It could be cheaper to cover a non-strawberry than to only cover straberries
In this example:  (@=straberry, .=blank)
@.@
. @.
@.@

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

0

LVL 2

Assisted Solution

That 'C' greenhouse in the example does not look right according to the conditions stated. Are the walls allowed to warp? The Adam solution of one to cover the whole thing sounds best, except it should only extend to the strawberry edge limits. Of course if just one plant would hang outside to provoke an excessive extension, it may need some tweaks. It should have a routine to crunch the difference between one and two structures in a field like this:

@@@@@@@@@@@@@@
@@@@@@@@@@@@@@
@@@@@@@@@@@@@@
@@@@@@@@@@@@@@
@
0

LVL 39

Accepted Solution

What I would do is check every possible combination of greenhouses, and then select the cheapest one that covers all straberries.  This might not be very fast, but would work.

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_column<=width;start_column++) {
for(start_row=1;start_row<=height;start_row++) {
for(greenhousewidth=1;greenhousewidth<=width-start_row+1;greenhousewidth++) {
for(greenhouseheight=1;greenhouseheight<=height-start_column+1;greenhouseheight++) {
#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);
}
}
}
}
}
0

## Featured Post

### Suggested Solutions

Statistics & Data Sceicne 2 61
2k Power n formula 2 27
Probability Distribution 2 36
Interest rate formula 7 42
A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…
This video gives you a great overview about bandwidth monitoring with SNMP and WMI with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're looking for how to monitor bandwidth using netflow or packet s…