Connect the dots

This is a discussion on Connect the dots within the Contests Board forums, part of the Community Boards category; Originally Posted by brewbuck Why not just specify that the input points are read from stdin and let the programmer ...

  1. #16
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by brewbuck View Post
    Why not just specify that the input points are read from stdin and let the programmer deal with the representation? In other words, why are you requiring that input come from an array, and output go to an array? So you can drop it into some project you're doing?

    Because if you're going to take this code and use it for something I would like to know.
    No this will not be used in a project or for any purpose other than this contest, I just wanted it that way to facilitate timing the execution. I also need to check the results to make sure none of your lines cross one another, much easier if the data in in an array which I can then pass to a verification function.
    Last edited by abachler; 04-04-2008 at 10:08 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  2. #17
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by zacs7 View Post
    I agree.

    As for the machine, how many CPUs does it have?

    Is the domain and range restricted from -1.0 to 1.0?
    Don't assume that, even if the provided sample did fit into that domain. I just copied and pasted a big array of doubles. I added a 0.0 to the end.

    The machine I will probably run it on has a single P4 with hyperthreading.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  3. #18
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    This polygon looks ugly but I think I solved it.

    I will post code later, it's kinda ugly. If you'd zoom this thing in enough, it would look like a nice polygon.
    Attached Images Attached Images  
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  4. #19
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by maxorator View Post
    This polygon looks ugly but I think I solved it.

    I will post code later, it's kinda ugly. If you'd zoom this thing in enough, it would look like a nice polygon.
    "I see what you did there..."

    After seeing that it hardly looks like a challenge anymore. Unless abachler changes the rules to disallow this sort of solution.

  5. #20
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    That solution is perfectly valid. I took a different route, but that one works just as well.

    Since there is a valid solution now, Ill go ahead and explain the method I used.

    1. Find the geometric center of all the points. This is the origin.
    2. Start at theta 0.0 and go clockwise (or CCW). The first point you find is the start of the polygon, now contuinue to increment theta and add each point to the polygon until you get back to the first point.
    Last edited by abachler; 04-04-2008 at 11:02 AM. Reason: typso
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  6. #21
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    Well the code has very confusing variable names, that's usually something I never think about when coding. My code is not usually readable to other people.

    That happens when I try to code quickly.

    Attention! Only look at the code if you want to get a headache!
    Attached Files Attached Files
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  7. #22
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    Quote Originally Posted by abachler View Post
    That solution is perfectly valid. I took a different route, but that one works just as well.

    Since there is a valid solution now, Ill go ahead and explain the method I used.

    1. Find the geometric center of all the points. This is the origin.
    2. Start at theta 0.0 and go clockwise (or CCW). The first point you find is the start of the polygon, now contuinue to increment theta and add each point to the polygon until you get back to the first point.
    Could you post a screenshot what your solution looks like?
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  8. #23
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Sure, soon as I write it , we just worked out the algorithm so far, I'll implement it tonight though. I'd post a pic of the whiteboard solution, but theres other stuff on it atm too. Let me ge that stuff written down adn cleared off then Ill post it.
    Last edited by abachler; 04-04-2008 at 02:32 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  9. #24
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    My dots are the same as yours, our coordinates systems were just different. I flipped mine around and drew a couple lines (manually) to show the image.

    Good idea to just progress through the values from one end of the range to the other.
    Attached Images Attached Images  
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  10. #25
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    How about a twist on this competition?

    You have to draw a circle using the points. Who ever draws the shape closest to a circle wins (efficiency taken into consideration also).

  11. #26
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    Quote Originally Posted by zacs7 View Post
    How about a twist on this competition?

    You have to draw a circle using the points. Who ever draws the shape closest to a circle wins (efficiency taken into consideration also).
    It would work something like:
    1) Find the area with the highest density of dots.
    2) Make a dummy circle there.
    3) Find points that are close enough to the circle.
    4) Put those dots in the right order.
    5) Connect them.

    I may be too lazy to try this though.
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  12. #27
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Sorry, had to work on something else this weekend. I will post the code a soon as I get it finished.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  13. #28
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    My solution might be what abachler was suggesting, not sure.
    Attached Images Attached Images  
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  14. #29
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    This looks pretty trivial.
    Code:
    #include <cstddef>
    #include <cmath>
    #include <algorithm>
    
    const std::size_t NUM_POINTS = (sizeof(xy) / sizeof(xy[0]) - 1) / 2;
    struct point_with_theta
    {
      double x, y, theta;
    
      void set(double ax, double ay) {
        x = ax;
        y = ay;
        theta = (x == 0 && y == 0) ? M_PI : std::atan2(y, x);
      }
      bool operator <(const point_with_theta &o) const {
        return theta < o.theta;
      }
    };
    point_with_theta points[NUM_POINTS];
    
    int main()
    {
      for(std::size_t i = 0; i < NUM_POINTS; ++i) {
        points[i].set(xy[i*2], xy[i*2+1]);
      }
      std::sort(points, points+NUM_POINTS);
      // Points are now in the correct order. Feel free to split them into two arrays or plot them.
    }
    You may have to define M_PI yourself - I always forget if it's predefined.

    May not be the fastest solution, but it's probably one of the shortest. Complexity is O(N*log(N)). Cache coherency during sorting depends on the std::sort implementation, but should generally be quite nice, since quicksort is pretty good at that stuff. Cache coherency during the copying should be excellent, unless atan2 needs all the cache for itself.
    It may be possible to speed up the copying with some SIMD, but copying the values out is tricky with the interleaved format, so it may not be worth it. (Also, the three doubles are inappropriately aligned for SIMD.) In addition, the x87 FPU directly supports atan, while the SSE engine doesn't. An interesting variation would be to split the three components into separate arrays, but this requires you to write your own sort algorithm or a writable zip_iterator (Boost's zip_iterator isn't writable). If you have the parallel arrays, you can SIMD-walk over them to calculate theta, assuming you can write a proper atan2 with SIMD instructions. The case distinction necessary may make this difficult.
    If you use the FPATAN x87 instruction, you can omit the zero-check, as the result of that operation is defined for all-zero arguments.
    Last edited by CornedBee; 04-14-2008 at 04:49 AM.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  15. #30
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by Cactus_Hugger View Post
    My solution might be what abachler was suggesting, not sure.
    That looks a lot like the results we got on the whiteboard.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Non-blocking connect()?
    By pobri19 in forum Networking/Device Communication
    Replies: 9
    Last Post: 04-22-2009, 03:40 PM
  2. connect timeout
    By X PaYnE X in forum Networking/Device Communication
    Replies: 8
    Last Post: 05-14-2005, 09:30 PM
  3. Client timed-out once on connect(), can never connect() again
    By registering in forum Networking/Device Communication
    Replies: 6
    Last Post: 10-28-2003, 02:46 PM
  4. MySQL Connect from Outside Computer
    By juschillin in forum Windows Programming
    Replies: 0
    Last Post: 09-27-2002, 08:02 AM
  5. Advanced connect four game
    By Ion Blade in forum C++ Programming
    Replies: 10
    Last Post: 07-28-2002, 07:52 AM

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