Topic: Themes for new topics -={Challenge}=-

[ElpanovEvgeniy]

We rarely created thread CHALLENGE.
Many of them are not very interesting.
Propose in this section to discuss and propose a new task for the CHALLENGE.

I love topics CHALLENGE! 

[CAB]

Most of my challenges were born out of my need to solve a problem. Some of which I had already solved but thought to share the experience.
There are always interesting results as other people came up with different methods and approaches to the problem.

[ElpanovEvgeniy]

I learn a lot when comparing different approaches to solving problems.
Very interesting to compare the different algorithms and ideas.

[ElpanovEvgeniy]

Most of my challenges were born out of my need to solve a problem. Some of which I had already solved but thought to share the experience.
There are always interesting results as other people came up with different methods and approaches to the problem.

Totally agree!
Difficult to think of a good topic to compare ideas.

[LE3]

This sound good.

As long the proposals are not (hidden as) homework.


To bad in my own personal case, that I do not write or are good in autolisp/vlisp anymore and when I tried to participate using other programming languages, none or maybe just the minority here (if happens) end up testing the binary (uploaded) files. And in other cases I see no interest in learning any other language (End up as a waste of time and efforts).... so that can stop someone... even with that I normally will try put my grain of salt ------------ my 0.02pesos.


LE!

[Jeremy]

Looking for a fun challenge? How about this one. Write an algorithm for finding the minimal circle that will just enclose a set of circles of random radii and random centers. You are not allowed to approximate the circles with points but must use the circle data. Of course we assume that all the circles lie on the XY-plane.

[Lee Mac]

Looking for a fun challenge? How about this one. Write an algorithm for finding the minimal circle that will just enclose a set of circles of random radii and random centers. You are not allowed to approximate the circles with points but must use the circle data. Of course we assume that all the circles lie on the XY-plane.

Similar to an Apollonian Gasket, but the internal circles can intersect each other?

[LE3]

Also, how about the usage?, where the algorithm can be used?, or implemented cases (if possible), apply on real world problems?, etc.... not just math or fancy geometry stuff, that it is great (have doneeeeeeeeeeeeeeeeeeeeeee a lot of that) --- but more that can be use on the ground.

another 0.02pesos. 

[divtiply]

Please consider k-d tree autolisp implementation. Can be used e.g. in nearest point seach.

[ElpanovEvgeniy]

Please consider k-d tree autolisp implementation. Can be used e.g. in nearest point seach.

I think it is necessary to give a full description of what and how the program is supposed to do.
Just be aware that a very complex task, it is not a matter of competition, it's more commercial projects.
These topics should be educational material!
 

ps. I looked at the "terrible formula" for working with k-d trees - looks difficult... 

[divtiply]

I think it is necessary to give a full description of what and how the program is supposed to do.

I need a faster version of this:

Code: [Select]

(defun nearest-point (pt ptlst / mindst dst npt)
  (setq npt (car ptlst)
        mindst (distance2d npt pt))
  (foreach p (cdr ptlst)
    (if (< (setq dst (distance2d p pt)) mindst)
      (setq mindst dst
            npt p)))
  npt)


[ElpanovEvgeniy]

I need a faster version of this:

pt = ??
ptlst = ??
distance2d = ??
Your post is not a technical specification for the new program.
But it is good that you have specified quality criteria - speed!


I think it's time to describe the basic requirements for the placement of tasks.
 

[divtiply]

pt = ??
ptlst = ??
distance2d = ??
Your post is not a technical specification for the new program.

Sorry,
pt is a 2d/3d point, e.g. '(134.76 42.78) or '(134.76 42.78 33.22);
ptlst is a candidate points list, format of each element is the same as pt;
distance2d is a 2d (horizontal) distance function;
return is point from ptlst nearest to pt.

[Marc'Antonio Alessi]

I need a faster version of this:

I have this, I do not know if it is faster.

Code: [Select]

; Function: ALE_SortClosestOrFarToPoint
;
; Version 1.00 - 12/04/2005
;
; Description:
;   Sort a list of points respect the distance from a point
;
; Arguments:
;   In_Pnt:  test point
;   PntLst:  points list
;   ClsFar:   '< = Closest     '> = Far
;
; Return Values: list of points sorted by Closest or Far
;
; Example:
;   (ALE_SortClosestOrFarToPoint
;    '(0.0 0.0 0.0) '((37.0 18.0 0.0) (48.0 18.0 0.0) (95.0 20.0 0.0)) '<
;   )
;
(defun ALE_SortClosestOrFarToPoint (In_Pnt PntLst ClsFar)
  (vl-sort
    PntLst
   '(lambda (Pnt001 Pnt002)
      ((eval ClsFar) (distance Pnt001 In_Pnt) (distance Pnt002 In_Pnt))
    )
  )
)
;
; Copyright ©2005 - Marc'Antonio Alessi, Italy - All rights reserved
; http://xoomer.virgilio.it/alessi
;
; Function: ALE_LowLeftCLosestPnts
;
; Version 1.00 - 12/04/2005
;
; Description:
;   Sort a list of points respect the distance from the lower left point
;
; Arguments:
;   PntLst:  points list
;
; Return Values: list of points sorted
;
; Example:
;   (ALE_LowLeftCLosestPnts
;    '((37.0 18.0 0.0) (48.0 18.0 0.0) (95.0 20.0 0.0))
;   )
;
(defun ALE_LowLeftCLosestPnts (PtsLst / LwrLft)
  (setq LwrLft (getvar "EXTMIN"))
  (vl-sort
    PtsLst
   '(lambda (Pnt001 Pnt002)
      (< (distance Pnt001 LwrLft) (distance Pnt002 LwrLft))
    )
  )
)

[Marc'Antonio Alessi]

This is from Tony Tanzillo:

Code: [Select]

If you're only looking for the first point in the
list that's within a given 'fuzz", then you can
use this:

(defun find-within (ptlist testpt fuzz)
   (vl-some
     '(lambda (pt)
         (if (>= fuzz (distance pt testpt)) pt)
      )
      ptlist
   )
)


[Jeremy]

Looking for a fun challenge? How about this one. Write an algorithm for finding the minimal circle that will just enclose a set of circles of random radii and random centers. You are not allowed to approximate the circles with points but must use the circle data. Of course we assume that all the circles lie on the XY-plane.

Similar to an Apollonian Gasket, but the internal circles can intersect each other?

Yes, the circles can cross each other. It seems however that everyone is chasing the nearest point now, a separate challenge for another day?

[Mark]

I like these type of challenges. Although that particular one is not all that great.

[CAB]

I think it is necessary to give a full description of what and how the program is supposed to do.

I need a faster version of this:

Code: [Select]

(defun nearest-point (pt ptlst / mindst dst npt)
  (setq npt (car ptlst)
        mindst (distance2d npt pt))
  (foreach p (cdr ptlst)
    (if (< (setq dst (distance2d p pt)) mindst)
      (setq mindst dst
            npt p)))
  npt)


http://www.theswamp.org/index.php?topic=40592.msg474213#msg474213

[Jeff H]

Project Euler
TopCoder
Google Code Jam
CodeKata

[CAB]

Interesting links Jeff 

[ElpanovEvgeniy]

CodeKata

Thank you!
That's what I think!