MC: Closest Integer in a List

The Challenge

From: <danli97@ite.mh.se> (Daniel Lidstrom)
Subject: Need subroutine
Date: Thu, 05 Mar 1998 08:43:44 -0600

I need a subroutine to find the closest integer in a list to a given number.
For example, given { 1 4 9 6 } 2 we would get the 1. I need a small B*T.

Daniel Lidström,
danli97@ite.mh.se
http://www.ite.mh.se/~danli97/

The Entries
Scroll down a few lines if you really want to see the entries

From: <avenar_j@epita.fr> (Jean-Yves Avenard)
Subject: Re: Need subroutine
Date: Fri, 6 Mar 1998 12:26:41 +1000

Hello

Please find here a small program than do that:
I run the program in two steps:
First, I check if the real you want to find is already in the list. If yes,
then I just put the real you gave at the beginning, on the stack

Otherwise, I do a LIST->, and parse the stack; here is the stack state:

n: real1
...
4: real n-1
3: real n
2: The last closest real
1: Last smallest difference

Here is the program, I'm 100% sure, than someone will find a faster way to
do it, (what about a MC ?)

<<
 -> X <<
 DUP X POS
IF THEN DROP X
ELSE LIST-> 0 MAXR ->NUM 1 4 ROLL
START
  3 PICK X - ABS DUP2
  IF > THEN SWAP DROP SWAP
  ELSE 4 ROLL DROP END
  DROP
NEXT
DROP
END
>>
>>

Hope this will help

Jean-Yves

From: <boettcher@cmu.edu> (Peter W Boettcher)
Subject: Re: Need subroutine
Date: Fri,  6 Mar 1998 00:15:55 -0500

How about:

\<< OVER SWAP - ABS DUP SORT HEAD POS GET \>>
#D816h
38.5

I didn't time it... the sort will make it slow.  Here's a better
way to find the minimum element of a list than SORT HEAD:

\<< DUP2 < ROT ROT IFTE \>> STREAM 

So the new program looks like:

\<< 
   OVER SWAP - ABS DUP
   \<< DUP2 < ROT ROT IFTE \>> 
   STREAM POS GET
\>>
# A6ECh
58

Much bigger, but I'm sure it runs much faster.  Approximate time to run
for a 200 element random list is 7.5s

Pete Boettcher
boettcher@cmu.edu

From: <boettcher@cmu.edu> (Peter W Boettcher)
Subject: Re: Need subroutine
Date: Fri,  6 Mar 1998 00:48:57 -0500

Whoops!  I somehow missed the builtin MIN.  Now it's:

\<< 
  OVER SWAP - ABS DUP
  \<< MIN \>>
  STREAM POS GET
\>>
# 9A3h
48

It now takes ~5s on a 200 element random list.

Pete Boettcher
boettcher@cmu.edu