• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 611
  • Last Modified:

maze-type of puzzle

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).
0
davidlars99
Asked:
davidlars99
  • 3
  • 2
  • 2
  • +5
8 Solutions
 
snoyes_jwCommented:
Is it a requirement that every strawberry be covered?
0
 
davidlars99Author Commented:
yes, and only in a rectangular greenhouse which doesn't overlap...
0
 
mrichmonCommented:
Is this for a course?
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
NovaDenizenCommented:
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
 
davidlars99Author Commented:
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
 
ozoCommented:
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
 
NovaDenizenCommented:
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
 
grg99Commented:
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
 
davidlars99Author Commented:
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);
                  using (StreamReader fs = new StreamReader(src))
                  {                        
                        Regex rx = new Regex(@"\s+", RegexOptions.Multiline | RegexOptions.Compiled);
                        
                        this.main_buffer = rx.Replace(fs.ReadToEnd().Trim(), "\n").ToCharArray();      
                        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
 
Adam314Commented:
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
 
Aramis11Commented:
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
 
Adam314Commented:
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

How to Use the Help Bell

Need to boost the visibility of your question for solutions? Use the Experts Exchange Help Bell to confirm priority levels and contact subject-matter experts for question attention.  Check out this how-to article for more information.

  • 3
  • 2
  • 2
  • +5
Tackle projects and never again get stuck behind a technical roadblock.
Join Now