Open Coding Challenge Idea

[Daklu]

This is a problem I've been thinking about for a while and as far as I know there aren't any canned routines to solve it, making it a potentially interesting Coding Challenge problem.

Imagine an XY plot of any number of points placed arbitrarily; something like a shotgun blast pattern. The goal is to find the maximum distance between any two points. Simple, eh? For 10 or 20 points, yes. For 100 points, not bad. What about 1,000 or 10,000 points? The brute force method is an O(n^2) function; can you find something better?

I'm thinking of throwing several random patterns with various numbers of points at each algorithm as well as having each person submit a pattern of their own choosing. It could be random or it could be created specifically to take advantage of weaknesses in other algorithms. For scoring I would probably advocate some sort of ranked based scoring as opposed to cumulative time.

Comments?

[Yuri33]

Off the top of my head, you can drastically reduce the amount of points you need to test by only using those that lie on the "convex hull" of the shotgun pattern. After that, it's probably a matter of determining the longest axis of this polygon and testing a few pairs. This approach would scale very well with vast numbers of points.

[shoneill]

QUOTE(Yuri33 @ Feb 15 2008, 08:16 AM)

Off the top of my head, you can drastically reduce the amount of points you need to test by only using those that lie on the "convex hull" of the shotgun pattern. After that, it's probably a matter of determining the longest axis of this polygon and testing a few pairs. This approach would scale very well with vast numbers of points.

I don't think that's what was meant. The algorithm is also called "the travelling salesman" and it's anything other than trivial. EACH point needs to be visited exactly once. There is only ONE optimal path.

Search for it on Wikipedia.

Shane.

[Francois Normandin]

QUOTE(shoneill @ Feb 15 2008, 07:00 AM)

The algorithm is also called "the travelling salesman" and it's anything other than trivial.

I agree that the traveling salesman problem is anything but trivial. However, I don't think this problem is an equivalent. The traveling salesman's solution is to find the shortest route possible to visit all points on a map. It's been extensively studied in many engineering problems such as reducing time to solder thousands of components on a circuit board. But if I understand Daku's problem, I tend to confirm Yuri33's assessment that we can discard any points in the middle as they will not give a result anywhere close to the maximum distance between any two points on the periphery.

[shoneill]

Oops,

Yeah, I re-read the post. It is indeed a different kettle of fish entirely......

I had looked into a similar problem regarding what was essentially the travelling salesman problem, and I kind of "recognised" that from the original post.

Darned Neurons, playing tricks on me again. I'll punish them by drinking copious amounts of beer!

Shane.

[Daklu]

Correct, this is not the travelling salesman problem. I didn't want to do something that had been analyzed to death.QUOTE(Yuri33 @ Feb 14 2008, 11:16 PM)

Off the top of my head, you can drastically reduce the amount of points you need to test by only using those that lie on the "convex hull" of the shotgun pattern. After that, it's probably a matter of determining the longest axis of this polygon and testing a few pairs. This approach would scale very well with vast numbers of points.

Well see, now you're spilling all your secrets. I suppose there are already algorithms on the internet to determine the convex hull, which makes the challenge less interesting. That's part of the reason I suggested having people submit crafted patterns; if you can create a pattern that confuses the common algorithms while making your own robust to it you have an advantage. Maybe this isn't so much a "coding challenge" as a "critical thinking challenge with coding." Can you identify weaknesses in the algorithm and overcome them to improve it?

Mostly though, I'd really just like to see another coding challenge--whatever it is. I got my start in Labview by stumbling across the Tic Tac Toe challenge on the internet in '06. I thought it was fun and find it a way to keep things fresh and interesting.

[Edit]

Eh... after googling "convex hull" I discovered I failed in my quest to choose something that hadn't been analyzed to death. The best thing about the internet is the amount of information instantly available. The worst thing about the internet is the amount of information instantly available. Have all the interesting problems (that don't require a PhD in mathematics) been solved?

[LAVA 1.0 Content]

QUOTE(Daklu @ Feb 15 2008, 12:18 PM)

... Have all the interesting problems (that don't require a PhD in mathematics) been solved?

Judging by the fact that someone got their PHD for studying the ergonomics of toilet seats, I supect the answer to your question is "Yes!".

Ben

[Aristos Queue]

QUOTE(Daklu @ Feb 15 2008, 11:18 AM)

Have all the interesting problems (that don't require a PhD in mathematics) been solved?

Some of http://en.wikipedia.org/wiki/Millennium_Prize_Problems' target="_blank">the interesting unsolved problems require a PhD in physics, not math. :-)

[crelf]

QUOTE(neB @ Feb 15 2008, 12:36 PM)

Judging by the fact that someone got their PHD for studying the ergonomics of toilet seats...

My opinion is that it should be one of the most comfortable seats in the house... QUOTE(Aristos Queue @ Feb 15 2008, 02:21 PM)

Some of

the interesting unsolved problems

require a PhD in physics, not math. :-)

Besides, maths is just a tool that Physicists use, right?

[LAVA 1.0 Content]

Back to the topic of challenges...

Daklu,

The lack of LV Challenges has been mainly due to the lack of a sponsor. If you are willing to sponsor the challenge (write rules, evaluate results, etc) we* can get you incontact with someone inside NI that can make it official.

PM us if you are interested in sponsoring a challenge!

Ben

* "we" = Any of the LabVIEW Champions

[Daklu]

QUOTE(neB)

we* can get you incontact with someone inside NI that can make it official.

Official? And here I thought it was just a loose, casual competition between forummers. You're going to scare me away with talk of 'officialness.'

QUOTE(neB)

If you are willing to sponsor the challenge (write rules, evaluate results, etc)...

I'll sponser it but it will take me a bit of time to formulate the rules. I'll try to have it ready for kickoff by the end of the month. Off the top of my head here are a few things I am thinking. ('Contestant' refers to the person submitting the VI; 'Competitor' refers to the VI itself.)

• Have two classes for competitors. An open class where anything goes (Wikipedia here I come!) that I'm guessing will end up being a contest of who can squeeze the most performance out of their VI, and a limited class which will include some sort of restrictions that require us to use less optimal solutions. Maybe only allowing a certain number of sub VIs or structures, or ... ? (Consider this a request for ideas.)
  
• Patterns will consist of a few randomly generated patterns created by me at the time of the contest and crafted patterns submitted by each contestant. Open patterns and limited patterns will be kept separate. I will publish the random pattern generator prior to the contest.
  
• Each contestant will be allowed multiple competitors in either class, however each contestant is only allowed to submit two crafted patterns per class.
  
• No special sequences allowed to identify your own patterns. Your VI must evaluate your patterns honestly.
  
• Scoring will be rank based with points awarded to roughly the top half of the competitors. VIs that do not produce the correct answer will not be eligible for points.
  
• An upper time limit will be imposed based on a general brute force algorithm. Any competitor that does not finish within the time limit will not be eligible for points.
  

The number of points in each pattern is a open question. I have no idea how long these VIs will take to run. Ideally the easy patterns will be ~5 seconds with the difficult patterns in the 30 second range. I also have nothing to offer as a prize. I might be able to create a trophy icon or some such thing, but it's unlikely to be anything a person would be proud to put in their sig.

[orko]

QUOTE(crelf @ Feb 15 2008, 11:26 AM)

My opinion is that it should be one of the most comfortable seats in the house...

That's hilarious...I actually used this exact picture on a magazine project for college. I believe the main caption read, "Working too hard? -- Employees speak out about lack of breaks" or something to that effect.

Thanks for making me smile again, Crelf It's nice to come up for air once and a while.

[crelf]

QUOTE(orko @ Feb 20 2008, 01:03 AM)

Thanks for making me smile again, Crelf It's nice to come up for air once and a while.

My work here is done

[Daklu]

Just in case anyone was waiting for this to start... I've decided this idea isn't a worthy Labview challenge. It was ridiculously easy for me, a certified Labview noob, to implement a Graham scan and find the convex hull. Optimization techniques might be a bit interesting, but then I have to worry about differences being lost in the noise and perhaps optimizations working better on some computers than others. The Graham scan was so easy to implement any attempt to created a "Limited" class would be like running a Formula 1 race with no tires. Boring.

Ah well, I keep thinking about the Labview challenge... maybe something good will come to mind.

[Yuri33]

I don't know what problem would be most appropriate, but perhaps you might be willing to sponser a LabVIEW "golf" challenge. That is, instead of trying to optimize based on speed, you optimize based on some metric that measures the size of the program. In a text-based language, this typically involves counting the number of characters in the program. For LV, it's a little more complicated, but I guess the metric could # of nodes or perhaps just the size (in kb) of the program. The winning entry would be the program with the smallest "size" that still performed the propsed task.