dcsimg
www.webdeveloper.com
Results 1 to 9 of 9

Thread: Quickly fell down a code challenge hole....

  1. #1
    Join Date
    Oct 2008
    Location
    Seattle, Wa
    Posts
    700

    Quickly fell down a code challenge hole....

    Hey guys I ran into this question (and thought it would be "fun") and for the life of me I can't wrap my head around how to execute it. It turns out this is extremely challenging even after me doing PHP for 12~ years


    http://qa.geeksforgeeks.org/860/prog...-solving-using


    I got about this far, https://gist.github.com/ehime/125eecb6e3f602973a69

    I know its not a lot, but again this seems like a really fun project, I'm just not certain how to achieve it and was hoping for insight / help.

    So for starters I'm looking for this

    Code:
    $barren = New \Barren\Map([[0, 0], [10, 20]]);
    $barren->setCoords('{"1 3 5 3"}') // plot 1x to 3x (right), 3x to 5y(up), 5y to -3x(left), -3x to -1y(down) 
           ->graph()
           ->plot();
    Code:
    + - - - - - - - - - - - - - - - - - - - - +
    |                                         |
    |                                         |
    |                                         |
    |                                         |
    |                                         |
    | + - +                                   |
    | |   |                                   |
    | |   |                                   |
    | |   |                                   |
    | + - +                                   |
    + - - - - - - - - - - - - - - - - - - - - +
    Last edited by ehime; 11-16-2015 at 03:48 PM.
    _,-O
    O
    (_)) ubuntu -
    -`-O

  2. #2
    Join Date
    Aug 2004
    Location
    Ankh-Morpork
    Posts
    21,118
    Okay, so I read the "problem" in the first link, then your "solution" in the second, and there seems to be a disconnect for me: the problem seems to be to just take in n sets of coordinates and calculate their areas, while you seem to be working on actually displaying the specified rectangles in an ASCII graphics sort of way.
    "Please give us a simple answer, so that we don't have to think, because if we think, we might find answers that don't fit the way we want the world to be."
    ~ Terry Pratchett in Nation

    How to Ask Questions the Smart Way (not affiliated with this site, but well worth reading)

  3. #3
    Join Date
    Oct 2008
    Location
    Seattle, Wa
    Posts
    700
    Yeah I mean the root of the problem is being able to calculate the area of coordinates, the second input that you see is kind of a curve ball as what it is doing is pretty much drawing a hash mark # in the middle of the available mass, so you need to figure out how to calculate the outer mass around the hash (as it does NOT touch walls) and then whatever is inside the hash.

    I started down this way because honestly I was trying to visualize what I was doing as I don't (sanely) know a way of figuring out how to tell if an area is divided / sectioned off, making one or more areas to calculate.

    If there is a way mathematically to figure this out I'm more than fine as accepting that as a solution as I can figure out how to graph it out after I have the plotter coordinates in a 2d array, and know that there are one or more than one sections to count the mass of.

    BTW, congrats on becoming a mod, its been several years and glad to see they took you on the board =)
    _,-O
    O
    (_)) ubuntu -
    -`-O

  4. #4
    Join Date
    Aug 2004
    Location
    Ankh-Morpork
    Posts
    21,118
    Part of the problem for me is just figuring out what the actual "requirements" are. I *think* s/he wants to know the areas of the parts of the farm that are not covered by "barren" rectangles? If that's the case, it does get rather messy. E.g. there could be one contiguous area with completely separate barren patches in it, or some/all of the barren patches could overlap, they could bisect/trisect/whatever the farm into totally separate areas. The brute force solution that comes to mind is to create some sort of matrix (array? string?) with each "bit" initialized to 1, then set each corresponding "bit" to 0 for each point in each barren rectangle. Then at that point you could work with the "bits" that are still ones -- but I would hope there's a more elegant answer using some geometric formula?

    Oh, and I've been a mod for a long time (years) here. Don't remember when I first started, but then I retired for awhile, and then got talked back into it somehow.
    "Please give us a simple answer, so that we don't have to think, because if we think, we might find answers that don't fit the way we want the world to be."
    ~ Terry Pratchett in Nation

    How to Ask Questions the Smart Way (not affiliated with this site, but well worth reading)

  5. #5
    Join Date
    Oct 2008
    Location
    Seattle, Wa
    Posts
    700
    Here's how I see it (may be wrong). This was actually one of the appeals was it took me about 3 days to riddle out just wth they ment, much less thing about coding it....

    Think of the numbers they give as coordinates on a graph. 0 0 is the origin on the lower left, and 399 599 is the upper right corner of the graph. The first 2 and second 2 integers in each set represent the lower left and upper right corners (respectively) of a rectangle of barren land. The linked image is for the first example (not perfectly to scale). The black rectangle in the center is the barren land bound by the coordinates 0, 292 and 399, 307. The remaining holes (white area) have equal areas of 11600 m.


    http://imgur.com/kg6Jrp9

    The first and second barren areas are black, while the third and fourth areas are red. This leaves 2 white holes whose area need to be calculated. The box on the inside is 124 x 184 m = 22816. I assume the area on the outside is 192608 m. That is the total area of the usable land minus the area of the rectangles and minus the 22816 that is surrounded by the barren areas. I would assume that you don't double count the over lapping areas that are shown in dark red.


    http://imgur.com/Gy5gxGS

    So if you look at what is happening is they are sectioning off chunks to create smaller chunks of land, then sorting those by m. It gets VERY messy is the thing as the more "lines" you add the more land parcels you will need to account for (and that is personally one of my biggest issues is how do you tell a computer that a segment has been quarantined from the whole?). I had origionally started with a 2d array, which is my buildAtlas method. The issue is again how do you tell something is segmented, or pretty much counting the (bool) trues covered in (bool) falses.

    After understanding the problem (least i think i do now, lol), its some what maddening as there MUST be an answer.... I've been tossing it around my head for the greater part of 5 days now. Extremely extremely challenging I have to say.



    Anyway, yeah when I started here in 08 you were just floating around helping. Sent you that FB of the code I caught in our repo at work, I thought you'd get a chuckle out of it. I think it was one of the few times I audibly laughed at code. Good to see you're still stretching the grey matter after retirement, it's hard enough with me getting some time for challenges after work (case in point) than to do it repetitively.
    _,-O
    O
    (_)) ubuntu -
    -`-O

  6. #6
    Join Date
    Oct 2008
    Location
    Seattle, Wa
    Posts
    700
    Actually after quickly googling it again, I found a pdf that explains it a bit better. Let me know what you think after reading it?

    http://imgur.com/GigCPYc
    _,-O
    O
    (_)) ubuntu -
    -`-O

  7. #7
    Join Date
    Aug 2004
    Location
    Ankh-Morpork
    Posts
    21,118
    This is where things get ugly for me, e.g. a couple overlapping "barren" rectangles, so that the remaining arable land is really one contiguous area, that you would then have to break up into component sub-rectangles to figure out the area:
    Code:
    . . . . / / / / / / / . . . . .
    . . . . / / / / / / / . . . . .
    . . . . / / / / / / / . . . . .
    . . . . / / / / / / / . . . . .
    . . . . / / / / / / / . . . . .
    . . . . / / / / / / / . . . . .
    . . . . / / / X X X X \ \ . . .
    . . . . / / / X X X X \ \ . . .
    . . . . / / / X X X X \ \ . . .
    . . . . . . . \ \ \ \ \ \ . . .
    . . . . . . . \ \ \ \ \ \ . . .
    . . . . . . . \ \ \ \ \ \ . . .
    . . . . . . . \ \ \ \ \ \ . . .
    . . . . . . . \ \ \ \ \ \ . . .
    . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . .
    "Please give us a simple answer, so that we don't have to think, because if we think, we might find answers that don't fit the way we want the world to be."
    ~ Terry Pratchett in Nation

    How to Ask Questions the Smart Way (not affiliated with this site, but well worth reading)

  8. #8
    Join Date
    Oct 2008
    Location
    Seattle, Wa
    Posts
    700
    Ouch... that is a kick in the pants.... So what I think is that IF the area overlaps it is only counted as barren UNLESS there is a hole in that area.... not sure if that eases or complicates the problem... So if you look at the second example (the hash mark) all the area outside of the hash is being counted as it doesn't directly touch a border (therefore being counted as a single mass). BUT the INSIDE IS as it is considered quarantined off from any other touchable land.

    Code:
      1                           . 
              /     /             . 
              /     /             . 
              /     /             . 
              /     /             . 
              /     /             . 
      \ \ \ \ + \ \ + \ \ \ \ \   . 
              /   2 /             . 
              /     /             .
      \ \ \ \ + \ \ + \ \ \ \ \   . 
              /   3 /             .
          \ \ + \ \ + \ \         .  
                                  . 
                                  . 
    . . . . . . . . . . . . . . . .
                             
    
    
    1 would be largest (area around that doesn't "touch" anything)
    2 second largest
    3 third
    
    mind you rsort the above for the return value

    is that what you ment to count under overlap(?) Because I don't think if things overlap they "switch case". I believe the overlapped "barren" land as in yours is still just considered barren. If you look at what they're doing, they're just drawing lines to isolate areas.
    _,-O
    O
    (_)) ubuntu -
    -`-O

  9. #9
    Join Date
    Aug 2004
    Location
    Ankh-Morpork
    Posts
    21,118
    Yes, in my example, all the "." squares are part of one "hole" that is farm-able, while the "/" and "\" squares are two separate barren rectangles, that happen to overlap in the "X" areas. So in this one example, there's only one "hole", but it's a 12-sided irregular polygon with all 90-degree angles (or something like that ). I'm not seeing any single mathematical approach (or even multiple approaches) to determine how many separate "holes" there are, not to mention their areas -- other than a brute force approach I alluded to earlier, with some way of counting adjoining non-barren points; which would depend on raw processing power rather than clever math.
    "Please give us a simple answer, so that we don't have to think, because if we think, we might find answers that don't fit the way we want the world to be."
    ~ Terry Pratchett in Nation

    How to Ask Questions the Smart Way (not affiliated with this site, but well worth reading)

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center



Recent Articles