Figuring Algo for assignment

This is a discussion on Figuring Algo for assignment within the C++ Programming forums, part of the General Programming Boards category; Hey all, I just received my next assigment frommy data structures and discrete math class; I have a hunch on ...

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

    Figuring Algo for assignment

    Hey all, I just received my next assigment frommy data structures and discrete math class; I have a hunch on how to do it but I can't think of the base case...anyways here is roughly what I have to do:

    Title: Skyline problem
    There is a city with no hills and has a set of rectangular buildings. Suppose you are viewing the city from water. Leftmost position of city is used as reference point ( horiz position 0 ). This, a building can be speified by (l, h, w), where l gives the left boundary, h the height of the buildingsm and w its width.

    the program will take as input a set of n buildings, in no particular order. The program now has to extract the outline formed by the buildings. This skyline will be formed by a sequence of horizontal segments starting at position 0. It will be represented by a equence of pairs (h, w) where h is the height abd w the width.
    Code:
    So basically if the input from a file is:
    (13, 3 4), (3,6,6,), (1,2,9), (14, 2,5), (18,4,2)
    the corresponding output will be:
    (0,1), (2,2), (6,6), (2,1),(0,3),(3,4),(2,1),(4,2)
    there are some restirictions for the design: must use divide and conquer algorithm and must be linear time operation.

    I hope you guys understand what the qestion is asking for, i tried to "draw" a picture of what it supposed to be
    Code:
               __________
              |          |
          ____|_____     |
         |          |    |       ______
     ____|__________|____|______|______|
    0    a    b          c      d      e
       
            
               __________ 
    
          ____          
                                 ______
     ____ __________ ____ ______ ______ 
    0    a    b          c      d      e
    where all the red pieces would correspond to the output sequence of pairs (hi, wi)
    since it is a D&C algo, I was thinking of using a similar algo to merge sort, where I would break the n buildings into two groups of roughly equal size, and then recursively find the skyline of each group.

    The problem is that I'm not sure how it will work for a base case, ie. if the is only one building.

    any comments? suggestions on how to go about it?
    Last edited by axon; 10-30-2003 at 11:05 AM.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,702
    So is the program supposed to draw the skyline using ascii art (ie. with "-" and "|")?
    And by "command and conquer" do you mean divide and conquer?

    gg

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Hmmm... never thought of doing this as divide and conquer. I did this not too long ago by simply having an array that corresponded to each horizonatal point in the city and the value of each point corresponded to the height at that point initialized to zero, so the code looked something like this:
    Code:
    loop through each building
       for (x=beg position of building to ending position of building)
           if (height of building is greater than citypos[x])
                citypos[x]=height of building
    But I guess worst case scenario this wouldn't be considered linear.

    For D&C, I would probably have a function that merged two city lines, so if it was given
    Code:
     (0,1),(2,2),(0,6) and (0,2),(3,3),(0,4)
    it would return
    Code:
    (0,1),(2,1),(3,3),(0,4)
    and also have a function that returns the skyline for a single building, then your recursive function would look something like this:
    Code:
    string recursiveFunc(int start, int size)
    {
    // start is beginning of array of buildings passed to function and size is size the array
    if (size==1)
        return singleBuildingSkyline(Buildings[start]);
    else
        return mergeSkyline(recursiveFunc(start, size/2),recursiveFunc(start+size/2, size/2));
    }
    There might be some flaws with that and you'll have to account for round off errors, haven't thought it all the way through, but hopefully you get the idea.

  4. #4
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    Originally posted by Codeplug
    So is the program supposed to draw the skyline using ascii art (ie. with "-" and "|")?
    And by "command and conquer" do you mean divide and conquer?

    gg
    No, no, the program is not supposed to draw it, just output the segments' heights and widths.

    and yes, i did mean divide and conquer...lol...sorry

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  5. #5
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    PJYelton: thanks a lot,thats exactly what I was thinking (recursive example)...I just couldn't bring it down to the single building for some reason. I'll start coding the program shortly.

    One more question though; since the input is obtained from a text filewill it be mroe beneficial to store it into an array or a linked list? what would be the pros and cons of both?

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. flow control algo
    By Mr.Bit in forum C Programming
    Replies: 4
    Last Post: 04-28-2008, 11:32 AM
  2. Maze generation algo
    By VirtualAce in forum Game Programming
    Replies: 7
    Last Post: 03-01-2006, 05:03 AM
  3. DDA algo logic
    By vaibhav in forum Tech Board
    Replies: 2
    Last Post: 01-06-2006, 02:40 PM
  4. which algo to use? graph theory...
    By axon in forum C++ Programming
    Replies: 2
    Last Post: 04-04-2004, 11:44 PM
  5. base conversion algo
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 12-28-2001, 09:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21