TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: Mark on March 11, 2005, 08:35:01 AM

Title: (Challenge) Closest integer to n
Post by: Mark on March 11, 2005, 08:35:01 AM
Write a function that returns the closest integer to n given a list of integers.

Example:
Code: [Select]

(setq lst '(45 23 63 5 8 56 74 32 96 144 95))

return the number closest to 10;
answer = 8.

Have fun. :D
Title: (Challenge) Closest integer to n
Post by: MP on March 11, 2005, 09:14:23 AM
Oops.
Title: (Challenge) Closest integer to n
Post by: whdjr on March 11, 2005, 10:13:25 AM
Rules? 8)
Title: (Challenge) Closest integer to n
Post by: Mark on March 11, 2005, 10:27:41 AM
Quote from: whdjr
Rules?

Nope!! Go for it, let's see what ya got. :D

commence posting, post at will..............
Title: (Challenge) Closest integer to n
Post by: whdjr on March 11, 2005, 10:38:06 AM
Quote from: Mark Thomas
commence posting, post at will..............

NO! NO! NOT AT ME!   :lol:  :lol:

Seriously.

Here's mine:
Code: [Select]
(setq lst '(45 23 63 5 8 56 74 32 96 144 95))

(defun closest (nlst / int pos)
  (initget (+ 1 4))
  (setq int (getint "\nEnter a number: "))
  (setq pos (vl-position
     0
     (vl-sort-i (mapcar '(lambda (n) (abs (- n int))) nlst) '>)
   )
  )
  (princ (strcat "The number closest to "
(itoa int)
" is "
(itoa (nth pos nlst))
"."
)
  )
)
Title: (Challenge) Closest integer to n
Post by: whdjr on March 11, 2005, 11:50:29 AM
Here's one that works with negatives as well:
Code: [Select]
(setq lst2 '(-45 -23 -63 5 -8 56 74 32 -96 -144 95))

(defun closest2 (nlst / int pos)
  (initget 1)
  (setq int (getint "\nEnter a number: "))
  (setq pos (vl-position
     (apply 'min
    (setq pos (mapcar 'abs (mapcar '(lambda (n) (- n int)) nlst)))
     )
     pos
   )
  )
  (princ (strcat "The number closest to "
(itoa int)
" is "
(itoa (nth pos nlst))
"."
)
  )
)
Title: (Challenge) Closest integer to n
Post by: CAB on March 11, 2005, 12:43:20 PM
I came up with two versions.
Code: [Select]
;;  version one
(defun nearest (num lst / a)
  (foreach x lst
    (if (or (null a)
            (< (abs(- num x)) (car a))
        )
      (setq a (list (abs(- num x)) x))
    )
  )
  (cadr a)
)


and after some thought version 2
Code: [Select]
(defun nearest2 (num lst / a)
  (car (vl-sort lst '(lambda (x y) (< (abs(- num x)) (abs(- num y)) ))))
)
Title: Re: (Challenge) Closest integer to n
Post by: Kerry on February 02, 2010, 02:59:04 AM
< ... >
and after some thought version 2
Code: [Select]
(defun nearest2 (num lst / a)
  (car (vl-sort lst '(lambda (x y) (< (abs(- num x)) (abs(- num y)) ))))
)

That is SO pretty !!
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 02, 2010, 03:46:55 AM
so there is less computation
Code: [Select]
(defun test (n l)
 (nth (car (vl-sort-i (mapcar '(lambda (a) (abs (- n a))) l) '<)) l)
)
Title: Re: (Challenge) Closest integer to n
Post by: Joe Burke on February 02, 2010, 06:17:21 AM
Seems to me this could return zero or two. IOW, both answers are correct within context.

Command: (nearest2 1 '(0 2 3))
0
Title: Re: (Challenge) Closest integer to n
Post by: CAB on February 02, 2010, 08:08:09 AM
Thanks Kerry.

As always very nice Evgeniy.

That appears to be correct Joe.
Title: Re: (Challenge) Closest integer to n
Post by: Joe Burke on February 02, 2010, 10:28:31 AM
I would probably use a genric function like this.

(defun round (value to)
  (if (zerop to) value
    (* (atoi (rtos (/ (float value) to) 2 0)) to)))

It works works with integer or real values passed. Plus it's numerically correct rounding. Not a qurirk of code rounding.
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 02, 2010, 10:46:21 AM
I think Evgeniy has put this one to bed  :wink:
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 02, 2010, 11:27:22 AM
ugly but should be the fastest in most cases
Code: [Select]
(defun nearest133 (num lst / a b c)
  (setq b (car lst)
a (abs (- num b))
  )
  (while (setq lst (cdr lst))
    (if (< (setq c (abs (- num (car lst)))) a)
      (setq b (car lst)
    a c
      )
    )
  )
  b
)
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 02, 2010, 01:35:40 PM
Late entry, really just a modification of Will's   :-P

Code: [Select]
(defun Closest-LEEMAC (num lst / vlst)
  (nth
    (vl-position
      (apply (function min)
        (setq vlst
          (mapcar
            (function
              (lambda (x) (abs (- x num)))) lst))) vlst) lst))
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 02, 2010, 01:41:15 PM
My bet is on VovKa  :wink:  While wins in 9/10 cases...
Title: Re: (Challenge) Closest integer to n
Post by: wizman on February 02, 2010, 01:55:33 PM
Here's my entry:

Code: [Select]
(defun wiz-near (n lst / b c d)
    (setq a (list n n)
          b 1e6
    )
    (mapcar '(lambda (x)
                 (if (<= (setq c (distance a (list n x))) b)
                     (setq b c
                           d x
                     )
                 )
             )
            lst
    )
    d
)
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 02, 2010, 01:59:00 PM
Very original Wizman I like it!

This is what I get:

Code: [Select]
Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST133-VOVKA 10 LST).....1263 / 2.77 <fastest>
    (CLOSEST-LEEMAC 10 LST).......1388 / 2.52
    (WIZ-NEAR 10 LST).............1435 / 2.43
    (CLOSEST2-WHDJR 10 LST).......1451 / 2.41
    (NEAREST-CAB 10 LST)..........1497 / 2.33
    (TEST-EVGENIY 10 LST).........1841 / 1.90
    (NEAREST2-CAB 10 LST).........3494 / 1.00 <slowest>
Title: Re: (Challenge) Closest integer to n
Post by: wizman on February 02, 2010, 02:09:57 PM
Thanks Lee, good solution by all too:


edit:  just seen others works on reals too, got to rest now
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 02, 2010, 02:20:55 PM
A quick (and poor) attempt to be clever  :wink:

Code: [Select]
#include <iostream>
#include <cstdlib>
using namespace std;

// C++ Attempt!
int main( )
{
  float lst[11] = {45,23,63,5,8,56,74,32,96,144,95}, n=10, a, b;
  int   i;

  a = abs(n-lst[0]);

  for (i=1; i<11; i++)
    if (abs(n-lst[i]) < a) a = lst[i];

  cout << a;
 
  return 0;
}

Have no idea how to time it to compare with the others though...
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 02, 2010, 02:48:48 PM
only , benchmark...

Code: [Select]
(defun test1 (n l )
 (setq l (vl-sort l (function <)))
 (while (< (cadr l) n) (setq l (cdr l)))
 (if (< (abs (- n (car l))) (abs (- n (cadr l))))
  (car l)
  (cadr l)
 )
)

Code: [Select]
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

    (TEST1 N L)..........1329 / 1.08 <fastest>
    (NEAREST133 N L).....1438 / 1 <slowest>
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 02, 2010, 02:54:29 PM
Haha! Cheeky trick  :-)  Get rid of the values that just clutter the list  ;-)
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 02, 2010, 03:02:00 PM
Code: [Select]
(defun test1 (n l )
 (setq l (vl-sort l (function <)))
 (while (< (cadr l) n) (setq l (cdr l)))
 (if (< (abs (- n (car l))) (abs (- n (cadr l))))
  (car l)
  (cadr l)
 )
)
i just knew that Evgeniy would beat us all :)
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 02, 2010, 03:04:39 PM
although...
(test1 5 '(1 2 3))
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 02, 2010, 03:12:51 PM
although...
(test1 5 '(1 2 3))

fix:
Code: [Select]
(defun test1 (n l )
 (setq l (vl-sort l (function <)))
 (while (and (cddr l)(< (cadr l) n)) (setq l (cdr l)))
 (if (< (abs (- n (car l))) (abs (- n (cadr l))))
  (car l)
  (cadr l)
 )
)

comparison
Code: [Select]
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

    (TEST1 N L)..........1359 / 1.06 <fastest>
    (NEAREST133 N L).....1437 / 1 <slowest>

 
_$
 
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

    (TEST1 N L)..........1453 / 1.09 <fastest>
    (NEAREST133 N L).....1578 / 1 <slowest>
Title: Re: (Challenge) Closest integer to n
Post by: wizman on February 02, 2010, 03:16:12 PM


Code: [Select]
(defun wiz-near2 (n lst / b c d)
    (setq  b 1e6)
    (mapcar (function(lambda (x)
                 (if (< (setq c (abs (- n x ))) b)
                     (setq b c
                           d x
                     )
                 )
             ))
            lst
    )
    d
)
Title: Re: (Challenge) Closest integer to n
Post by: It's Alive! on February 02, 2010, 07:40:59 PM
A quick (and poor) attempt to be clever  :wink:

nice  8-)

Code: [Select]
static bool closesTo10 ( int elem1, int elem2)
 {
   return abs(elem1 - 10) < abs(elem2 -10);
 }
 static void ArxBlockExt_doit(void)
 {
   int a[] = {45,23,63,5,8,56,74,32,96,144,95};
   std::sort(a, a + sizeof(a) / sizeof(a[0]),closesTo10);
   acutPrintf(_T("\n%d"),a[0]);
 }
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 02, 2010, 07:46:38 PM
A quick (and poor) attempt to be clever  :wink:

nice  8-)

Thanks Daniel - but amateur compared to yours....  :-)
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 03, 2010, 04:47:12 AM
i had a dream last night :)
Code: [Select]
(defun nearest41 (num lst / p a b)
  (cond ((vl-position num lst) num)
((zerop (setq lst (vl-sort (cons num lst) '<)
     p  (vl-position num lst) ; faster than Evgeniy's when (> p 2)
)
)
(cadr lst)
)
((= (last lst) num) (nth (1- p) lst))
((> (- (setq a (nth (1+ p) lst)) num) (- num (setq b (nth (1- p) lst)))) b)
(t a)
  )
)
Code: [Select]
(setq lst '(10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170)
      num 31 ;and above
)
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 03, 2010, 04:56:34 AM
i had a dream last night :)

It was colored dream? :)

Good job VovKa!
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 03, 2010, 05:01:17 AM
Quote
It was colored dream?
yeah, parenthesis were red, functions - blue, variables - black :)
Title: Re: (Challenge) Closest integer to n
Post by: CAB on February 03, 2010, 08:41:32 AM
 :-D  Wish all mine were like that.
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 03, 2010, 08:54:33 AM
Very nice VovKa!  8-)
Title: Re: (Challenge) Closest integer to n
Post by: wizman on February 03, 2010, 08:58:08 AM
Good Work vovka, good sleep + good code  :-)
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 03, 2010, 11:07:01 AM
I get this result:

Code: [Select]
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (TEST1-EVGENIY 10 LST)........1217 / 2.91 <fastest>
    (NEAREST41-VOVKA 10 LST)......1232 / 2.87
    (NEAREST133-VOVKA 10 LST).....1280 / 2.77
    (CLOSEST-LEEMAC 10 LST).......1341 / 2.64
    (WIZ-NEAR2 10 LST)............1373 / 2.58
    (WIZ-NEAR 10 LST).............1435 / 2.47
    (CLOSEST2-WHDJR 10 LST).......1451 / 2.44
    (NEAREST-CAB 10 LST)..........1513 / 2.34
    (TEST-EVGENIY 10 LST).........1841 / 1.92
    (NEAREST2-CAB 10 LST).........3541 / 1.00 <slowest>
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 03, 2010, 11:41:00 AM
Lee, we both will be happier if you benchmark the above with 100 instead of 10 :)
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 03, 2010, 11:49:34 AM
Lee, we both will be happier if you benchmark the above with 100 instead of 10 :)

Nice one  :wink:

Code: [Select]
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST133-VOVKA 100 LST).....1248 / 2.75 <fastest>
    (NEAREST41-VOVKA 100 LST)......1264 / 2.72
    (CLOSEST-LEEMAC 100 LST).......1342 / 2.56
    (WIZ-NEAR2 100 LST)............1342 / 2.56
    (CLOSEST2-WHDJR 100 LST).......1404 / 2.45
    (TEST1-EVGENIY 100 LST)........1451 / 2.37
    (WIZ-NEAR 100 LST).............1466 / 2.34
    (NEAREST-CAB 100 LST)..........1514 / 2.27
    (TEST-EVGENIY 100 LST).........1747 / 1.97
    (NEAREST2-CAB 100 LST).........3433 / 1.00 <slowest>
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 03, 2010, 12:13:46 PM
i have different results
Code: [Select]
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST41 100 LST)..........1656 / 1.19 <fastest>
    (CLOSEST-LEEMAC 100 LST).....1734 / 1.14
    (NEAREST133 100 LST).........1750 / 1.13
    (WIZ-NEAR2 100 LST)..........1812 / 1.09
    (TEST1 100 LST)..............1969 / 1.00 <slowest>
it looks like autolisp code's speed is cpu dependant
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 03, 2010, 12:24:29 PM
>VovKa, Lee Mac

Show the arguments with which you have received your results.
I have several options, which in various cases faster your.
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 03, 2010, 12:58:20 PM
>VovKa, Lee Mac

Show the arguments with which you have received your results.
I have several options, which in various cases faster your.

Evgeniy,

I have just used the list as Mark posted in the first post  :-)
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 03, 2010, 01:10:01 PM
Ok  :-)

Code: [Select]
(defun test3 (n l / a b)
 (if (vl-position n l)
  n
  (cond ((not (setq l (vl-sort (cons n l) (function <))
                    a (cadr (member n l))
              ) ;_  setq
         ) ;_  not
         (cadr (member n (reverse l)))
        )
        ((not (setq b (cadr (member n (reverse l)))))a)
        ((if(< (abs (- n a)) (abs (- n b))) a b))
  ) ;_  cond
 ) ;_  if
)

Code: [Select]
(setq l '(45 23 63 5 8 56 74 32 96 144 95) n 100)
(BenchMark '((nearest41 n l)(Closest-LEEMAC n l)(test3 n l)))

Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

    (TEST3 N L)..............1500 / 1.22 <fastest>
    (NEAREST41 N L)..........1531 / 1.19
    (CLOSEST-LEEMAC N L).....1829 / 1 <slowest>

 
_$
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

    (TEST3 N L)..............1532 / 1.2 <fastest>
    (NEAREST41 N L)..........1547 / 1.19
    (CLOSEST-LEEMAC N L).....1844 / 1 <slowest>

 
_$
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

    (TEST3 N L)..............1515 / 1.21 <fastest>
    (NEAREST41 N L)..........1531 / 1.19
    (CLOSEST-LEEMAC N L).....1829 / 1 <slowest>

 
_$
Title: Re: (Challenge) Closest integer to n
Post by: wizman on February 03, 2010, 02:19:07 PM
Code: [Select]
(defun wiz-near3 (n lst / a d e)
    (cond ((vl-position n lst) n)
          ((setq lst (vl-sort (cons n lst) (function >))
                 lst (cons -1e6 (reverse (cons 1e6 lst)))
                 a   (vl-position n lst)
           )
           (if (< (abs (- (setq d (nth (1+ a) lst)) n))
                  (abs (- (setq e (nth (1- a) lst)) n))
               )
               d
               e
           )

          )
    )
)
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 03, 2010, 02:25:16 PM
You guys want to verify this?

Code: [Select]
Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (WIZ-NEAR3 100 LST)...........1201 / 1.12 <fastest>
    (NEAREST41-VOVKA 100 LST).....1216 / 1.10
    (TEST3-EVGENIY 100 LST).......1280 / 1.05
    (CLOSEST-LEEMAC 100 LST)......1342 / 1.00 <slowest>

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (WIZ-NEAR3 100 LST)...........1185 / 1.15 <fastest>
    (NEAREST41-VOVKA 100 LST).....1232 / 1.10
    (TEST3-EVGENIY 100 LST).......1264 / 1.07
    (CLOSEST-LEEMAC 100 LST)......1357 / 1.00 <slowest>

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (WIZ-NEAR3 100 LST)...........1170 / 1.15 <fastest>
    (NEAREST41-VOVKA 100 LST).....1201 / 1.12
    (TEST3-EVGENIY 100 LST).......1264 / 1.06
    (CLOSEST-LEEMAC 100 LST)......1341 / 1.00 <slowest>
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 03, 2010, 03:31:04 PM
upgraded cond to ifs
Code: [Select]
(defun nearest42 (num lst / p a b)
  (if (vl-position num lst)
    num
    (if (zerop (setq lst (vl-sort (cons num lst) (function <))
    p (vl-position num lst) ; faster than Evgeniy's when (> p 2)
                                                    ; faster than wizman's when (not (equal p (length lst) 3))
      )
)
      (cadr lst)
      (if (= (last lst) num)
(nth (1- p) lst)
(if (> (- (setq a (nth (1+ p) lst)) num) (- num (setq b (nth (1- p) lst))))
 b
 a
)
      )
    )
  )
)
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 03, 2010, 03:55:59 PM
Code: [Select]
(setq lst '(10 20 30 40 50 60 70 80 90 100))
(foreach num lst
  (print (setq num (1+ num)))
  (benchmark '((wiz-near3 num lst) (nearest42 num lst)))
)

Code: [Select]
11 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST42 NUM LST).....1485 / 1.03 <fastest>
    (WIZ-NEAR3 NUM LST).....1531 / 1.00 <slowest>

21 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST42 NUM LST).....1500 / 1.04 <fastest>
    (WIZ-NEAR3 NUM LST).....1562 / 1.00 <slowest>

31 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST42 NUM LST).....1500 / 1.02 <fastest>
    (WIZ-NEAR3 NUM LST).....1531 / 1.00 <slowest>

41 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST42 NUM LST).....1516 / 1.03 <fastest>
    (WIZ-NEAR3 NUM LST).....1562 / 1.00 <slowest>

51 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST42 NUM LST).....1500 / 1.03 <fastest>
    (WIZ-NEAR3 NUM LST).....1547 / 1.00 <slowest>

61 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST42 NUM LST).....1515 / 1.03 <fastest>
    (WIZ-NEAR3 NUM LST).....1563 / 1.00 <slowest>

71 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST42 NUM LST).....1531 / 1.02 <fastest>
    (WIZ-NEAR3 NUM LST).....1563 / 1.00 <slowest>

81 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST42 NUM LST).....1546 / 1.01 <fastest>
    (WIZ-NEAR3 NUM LST).....1563 / 1.00 <slowest>

91 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (WIZ-NEAR3 NUM LST).....1547 / 1.00 <fastest>
    (NEAREST42 NUM LST).....1547 / 1.00 <slowest>

101 Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

    (NEAREST42 NUM LST).....1484 / 1.06 <fastest>
    (WIZ-NEAR3 NUM LST).....1578 / 1.00 <slowest>
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 03, 2010, 04:06:24 PM
Ok  :-)
Code: [Select]
(defun test3 (n l / a b)
 (if (vl-position n l)
  n
  (cond ((not (setq l (vl-sort (cons n l) (function <))
                    a (cadr (member n l))
              ) ;_  setq
         ) ;_  not
         (cadr (member n (reverse l)))
        )
        ((not (setq b (cadr (member n (reverse l)))))a)
        ((if(< (abs (- n a)) (abs (- n b))) a b))
  ) ;_  cond
 ) ;_  if
)
Evgeniy, i tested your code and got the same results as Lee did
i just can't see how member can outrun vl-position
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 03, 2010, 04:47:03 PM
Quote
Evgeniy, i tested your code and got the same results as Lee did
i just can't see how member can outrun vl-position

Indeed, now I got the results that are similar to yours.
Perhaps I was wrong.
I'm sorry, I'm sorry.

I have a new idea :

Code: [Select]
(defun test4 (n l / a b i)
 (cond ((not (setq l (vl-sort (cons (float n) l) (function <))
                   i (vl-position (float n) l)
                   a (nth (1- i) l)
             ) ;_  setq
        ) ;_  not
        (nth (1+ i) l)
       )
       ((not (setq b (nth (1+ i) l))) a)
       ((if (< (abs (- n a)) (abs (- n b)))
         a
         b
        ) ;_  if
       )
 ) ;_  cond
)
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 03, 2010, 05:04:54 PM
Evgeniy, excelent move with float :)
now it's faster than mine
but bad news for (test4 1 '(1 2 3))
Title: Re: (Challenge) Closest integer to n
Post by: wizman on February 03, 2010, 05:29:57 PM
Code: [Select]
(defun wiz-near4 (n lst / a d e f g)
    (if (vl-position n lst)
        n
        (setq lst (vl-sort (cons n lst) (function >))
              lst (cons -1e6 (reverse (cons 1e6 lst)))
              a   (vl-position n lst)
              d   (nth (1+ a) lst)
              e   (nth (1- a) lst)
              f   (- d n)
              g   (if (equal e n f)
                      e
                      d
                  )
        )
    )
)

..be back tom..
Title: Re: (Challenge) Closest integer to n
Post by: cmwade77 on February 03, 2010, 06:38:15 PM
I am sure that there are far faster and better on here, but I thought I would try my hand at it before reading the entier thread, so here is my entry:
Code: [Select]
(defun c:inttst (/ a lst ct b c d e)
(setq a (getint "\nEnter integer: ")
      lst '(45 23 63 5 8 56 74 32 96 144 95)
  ct 0
  ct2 (- (length lst) 1)
  lst (vl-sort lst '<)
  pos (vl-position a lst)
  b (nth 0 lst)
  d (- b a)
  c (nth ct2 lst)
  e (- a c))
(cond
((/= pos nil)
(princ (strcat "\nThere was an exact match: " (itoa (nth pos lst))))
)
(T
(while (< ct (length lst))
(cond
((> (nth ct lst) a)
(setq b (nth ct lst)
      d (- b a))
)
)
(setq ct (+ ct 1))
)
(while (> ct2 -1)
(cond
((< (nth ct2 lst) a)
(setq c (nth ct2 lst)
      e (- a c))
)
)
(setq ct2 (- ct2 1))
)
(if (< d e)
(princ (strcat "\nThe closest number to " (itoa a) " is: " (itoa (nth (- ct 1) lst))))
(princ (strcat "\nThe closest number to " (itoa a) " is: " (itoa (nth (+ ct2 1) lst))))
)
)
)
(princ)
)
It works, but now I am going to go through the thread and see if there is one that looks like it will run faster. This is actually something that can be helpful in some routines that I am working on.
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 03, 2010, 07:19:09 PM
Chris,

It'd be better if your function took two arguments (the number and lst), and didn't have user input/print out - then it can be tested in a benchmarking function  :-)
Title: Re: (Challenge) Closest integer to n
Post by: SomeCallMeDave on February 03, 2010, 08:31:01 PM
Any room for some Ruby?

Code: [Select]
class Array
  def nearest(input)
    self.sort_by{|x| (x-input).abs}.first
  end
end

numbers = [45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95]

input = 10

puts numbers.nearest input   # returns 8


puts [1,2,3].nearest 5 #returns 3 

Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 04, 2010, 12:39:45 AM
Evgeniy, excelent move with float :)
now it's faster than mine
but bad news for (test4 1 '(1 2 3))


Code: [Select]
(defun test4 (n l / a b i)
 (cond ((zerop (setq l (vl-sort (cons (float n) l) (function <))
                     i (vl-position (float n) l)
               )
        )
        (cadr l)
       )
       ((not (setq a (nth (1- i) l)
                   b (nth (1+ i) l)
             )
        )
        a
       )
       ((if (< (abs (- n a)) (abs (- n b)))
         a
         b
        )
       )
 )
)
Title: Re: (Challenge) Closest integer to n
Post by: Kerry on February 04, 2010, 03:05:11 AM

:)


and who said dead threads shouldn't be resurrected  :?
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 04, 2010, 03:07:46 AM

:)


and who said dead threads shouldn't be resurrected  :?

I love all threads *Challenge*  :-)
Title: Re: (Challenge) Closest integer to n
Post by: VovKa on February 04, 2010, 04:50:18 AM
i've changed cond to ifs and stolen wizman's equal
Code: [Select]
(defun test413 (n l / a b i)
  (if (zerop (setq l (vl-sort (cons (float n) l) (function <))
   i (vl-position (float n) l)
     )
      )
    (cadr l)
    (if (or (not (setq a (nth (1- i) l)
       b (nth (1+ i) l)
)
    )
    (equal n a (- b n))
)
      a
      b
    )
  )
)
Title: Re: (Challenge) Closest integer to n
Post by: wizman on February 04, 2010, 04:56:03 AM
i think that would be it Vovka, i like also EE's float: (vl-position 1.0 '(1 1 1 1.0)) ;3
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 04, 2010, 05:48:42 AM
ever useful to you:

Code: [Select]
(vl-sort '(0 1 2 0 1 2)'<)       ;; =>> '(1 2 3)
but
(vl-sort '(0. 1. 2. 0. 1. 2.)'<) ;; =>> '(0.0 1.0 1.0 2.0 2.0)
Title: Re: (Challenge) Closest integer to n
Post by: Kerry on February 04, 2010, 05:53:40 AM
ever useful to you:

Code: [Select]
(vl-sort '(0 1 2 0 1 2)'<)       ;; =>> '(1 2 3)
< .. >


uhmmm ...  that's (0 1 2) , yes ?
Title: Re: (Challenge) Closest integer to n
Post by: ElpanovEvgeniy on February 04, 2010, 06:25:45 AM
uhmmm ...  that's (0 1 2) , yes ?

I was not sufficiently attentive.
Thank you!
Title: Re: (Challenge) Closest integer to n
Post by: Lee Mac on February 04, 2010, 08:14:10 PM

:)


and who said dead threads shouldn't be resurrected  :?

I love all threads *Challenge*  :-)

Me too  :-)   8-)
Title: Re: (Challenge) Closest integer to n
Post by: cadabyss on February 04, 2010, 08:52:41 PM
An alternate approach, just for fun.

Code: [Select]
(defun ClosestInt (n lst / tmp)
  ;; Returns first closest number in list
  (nth (vl-position
         (eval
           (cons 'min
                 (setq tmp (mapcar '(lambda (x) (abs (- n x))) lst))
           )
         )
         tmp
       )
       lst
  )
)
Title: Re: (Challenge) Closest integer to n
Post by: Kerry on February 04, 2010, 09:12:26 PM

Nice solution Steve !
Title: Re: (Challenge) Closest integer to n
Post by: cadabyss on February 05, 2010, 12:08:13 AM
Thanks Kerry.  I had not read solutions posted by others until now.  Just noticed whdjr posted a very similar solution.  : )


Nice solution Steve !
Title: Re: (Challenge) Closest integer to n
Post by: pkohut on February 05, 2010, 04:51:23 AM
A flexible C++ Template method from the attached Playground3.cpp file.

Templates closeToMethod1, 2, and 3 are implemented in Playground1.cpp,
and closeToMethod4, 5, 6 are in Playground2.cpp.  Each template is implemented
slightly different so I could look at the disassembled code of the release builds.

Overall generated code is very similar amongst 1, 2, 3, and 6.  3 and 6 require
external linkage of the array, while the rest can use local arrays.  4 and 5 did
not inline the calls to closestTo, probably because arr was unknown to the
template at compile time.

Hm, also, for 1, 2, and 3 I noticed that the loops where unrolled for 8 or
less array elements, and also unrolled for 10 and 12 elements, didn't check any
others.

Code: [Select]
#include "stdafx.h"
#include <iostream>

template<int N, int nArraySize, const int * aar>
struct closeToMethod3 {
    static int op(void) {
        int nVal = INT_MIN;
        for(int i = 0; i < nArraySize; i++) {
            nVal = closestTo(aar[i], nVal);
        }
        return nVal;
    }
    static int closestTo (const int elem1, const int elem2)
    {
        return abs(elem1 - N) < abs(elem2 - N) ? elem1 : elem2;
    }
};

extern int g_array[] = {45,23,63,5,8,56,74,32,96,144,95};

int _tmain(int argc, _TCHAR* argv[])
{
    using namespace std;
    const int aVal1 = closeToMethod3<10, sizeof(g_array) / sizeof(g_array[0]), g_array>::op();
    const int aVal2 = closeToMethod3<20, sizeof(g_array) / sizeof(g_array[0]), g_array>::op();
    const int aVal3 = closeToMethod3<30, sizeof(g_array) / sizeof(g_array[0]), g_array>::op();

    cout << aVal1 << endl;
    cout << aVal2 << endl;
    cout << aVal3 << endl;

    cout << closeToMethod3<40, sizeof(g_array) / sizeof(g_array[0]), g_array>::op() << endl;

    return 0;
}
Title: Re: (Challenge) Closest integer to n
Post by: It's Alive! on February 05, 2010, 06:35:54 PM
A flexible C++ Template method from the attached Playground3.cpp file.

Nice!  8-)
Templates are next on my list to learn.
Title: Re: (Challenge) Closest integer to n
Post by: pkohut on February 05, 2010, 07:58:31 PM
A flexible C++ Template method from the attached Playground3.cpp file.

Nice!  8-)
Templates are next on my list to learn.

I spent all day yesterday trying to make a templated version that would get the
answer at compile time (0 runtime overhead).  Long story short, templale
programming has a very strict set of rules, don't go looking for loop holes
cause you (me -->  :|  <--) won't find ANY, ie. you cannot get to elements of an
array or string with template metaprogramming, but you can fake it with
boost MPL.

Wish I'd found this page earlier
http://www.boost.org/development/int_const_guidelines.html
Title: Re: (Challenge) Closest integer to n
Post by: pkohut on February 09, 2010, 08:59:32 PM
Answer computed at compile time (C++), 0 runtime overhead.

First the compiler generated code
Code: [Select]
; 147  :     // Given a set of elements, find the one closest to the 1st element
; 148  :     // ie, closest to 10
; 149  :     int nNearest = ClosestInt_11<10, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
mov DWORD PTR _nNearest$[ebp], 8
; 150  :     // more values to test with
; 151  :     nNearest = ClosestInt_11<-4, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
mov DWORD PTR _nNearest$[ebp], 5
; 152  :     nNearest = ClosestInt_11<144, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
mov DWORD PTR _nNearest$[ebp], 144 ; 00000090H
; 153  :     nNearest = ClosestInt_11<30, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
mov DWORD PTR _nNearest$[ebp], 32 ; 00000020H

and the C++ Template code.  Since TMP is new to me and they can't operate on array elements, ie no way to do recursion with array or string contents, this is a pretty heavy handed solution.  Boost MPL makes this much easier to do.

Code: [Select]
#include "stdafx.h"

//////////////////////////////////////////////////////////////////////////
// Compile time IF THEN ELSE conditional
//////////////////////////////////////////////////////////////////////////
template<bool condition, int Then, int Else>
struct IF_THEN_ {
    enum { value = Then };
};

template<int Then, int Else>
struct IF_THEN_<false, Then, Else> {
    enum { value = Else };
};

//////////////////////////////////////////////////////////////////////////
// Compile time absolute value
//////////////////////////////////////////////////////////////////////////
template<int N>
struct ABS_
{
    enum {
        value = IF_THEN_<(N < 0), -N, N>::value
    };
};

//////////////////////////////////////////////////////////////////////////
// Given N which is closer? n1 or n2
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2>
struct ClosestInt_2
{
    enum {
        /** Easier to read
        //v1 = ABS_<n1 - N>::value,
        //v2 = ABS_<n2 - N>::value,
        //value = IF_THEN_<v1 < v2, n1, n2>::value
        */
        // but probably more efficent
        value = IF_THEN_< ABS_<n1 - N>::value < ABS_<n2 - N>::value, n1, n2 >::value
    };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3>
struct ClosestInt_3
{
    enum { value = ClosestInt_2<N, n1, ClosestInt_2<N, n2, n3>::value>::value };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4>
struct ClosestInt_4
{
    enum {
        value =
        ClosestInt_2<N, n4, ClosestInt_2<N, n2,
        ClosestInt_2<N, n2, n1>
        ::value>::value>::value
    };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5>
struct ClosestInt_5
{
    enum {
        value =
        ClosestInt_2<N, n5, ClosestInt_2<N, n4, ClosestInt_2<N, n2,
        ClosestInt_2<N, n2, n1>
        ::value>::value>::value>::value
    };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6>
struct ClosestInt_6
{
    enum {
        value =
        ClosestInt_2<N, n6, ClosestInt_2<N, n5, ClosestInt_2<N, n4,
        ClosestInt_2<N, n2, ClosestInt_2<N, n2, n1>
        ::value>::value>::value>::value>::value
    };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7>
struct ClosestInt_7
{
    enum {
        value =
        ClosestInt_2<N, n7, ClosestInt_2<N, n6, ClosestInt_2<N, n5,
        ClosestInt_2<N, n4, ClosestInt_2<N, n2, ClosestInt_2<N, n2, n1>
        ::value>::value>::value>::value>::value>::value
    };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7, int n8>
struct ClosestInt_8
{
    enum {
        value =
        ClosestInt_2<N, n8, ClosestInt_2<N, n7, ClosestInt_2<N, n6,
        ClosestInt_2<N, n5, ClosestInt_2<N, n4, ClosestInt_2<N, n2,
        ClosestInt_2<N, n2, n1>
        ::value>::value>::value>::value>::value>::value>::value
    };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7, int n8, int n9>
struct ClosestInt_9
{
    enum {
        value =
        ClosestInt_2<N, n9, ClosestInt_2<N, n8, ClosestInt_2<N, n7,
        ClosestInt_2<N, n6, ClosestInt_2<N, n5, ClosestInt_2<N, n4,
        ClosestInt_2<N, n2, ClosestInt_2<N, n2, n1>
        ::value>::value>::value>::value>::value>::value>::value>::value
    };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7, int n8, int n9, int n10>
struct ClosestInt_10
{
    enum {
        value =
        ClosestInt_2<N, n10, ClosestInt_2<N, n9, ClosestInt_2<N, n8,
        ClosestInt_2<N, n7, ClosestInt_2<N, n6, ClosestInt_2<N, n5,
        ClosestInt_2<N, n4, ClosestInt_2<N, n2, ClosestInt_2<N, n2, n1>
        ::value>::value>::value>::value>::value>::value>::value>::value>::value
    };
};
//////////////////////////////////////////////////////////////////////////
template<int N, int n1, int n2, int n3, int n4, int n5, int n6, int n7, int n8, int n9, int n10, int n11>
struct ClosestInt_11
{
    enum {
        value =
        ClosestInt_2<N, n11, ClosestInt_2<N, n10, ClosestInt_2<N, n9,
        ClosestInt_2<N, n8,  ClosestInt_2<N, n7, ClosestInt_2<N, n6,
        ClosestInt_2<N, n5,  ClosestInt_2<N, n4, ClosestInt_2<N, n2,
        ClosestInt_2<N, n2, n1>
        ::value>::value>::value>::value>::value>::value>::value>::value>::value>::value
    };
};



void main()
{
    // Given a set of elements, find the one closest to the 1st element
    // ie, closest to 10
    int nNearest = ClosestInt_11<10, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
    // more values to test with
    nNearest = ClosestInt_11<-4, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
    nNearest = ClosestInt_11<144, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
    nNearest = ClosestInt_11<30, 45, 23, 63, 5, 8, 56, 74, 32, 96, 144, 95>::value;
}