Author Topic: (Challenge) Closest integer to n  (Read 11835 times)

0 Members and 1 Guest are viewing this topic.

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: (Challenge) Closest integer to n
« Reply #60 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-)

cadabyss

  • Guest
Re: (Challenge) Closest integer to n
« Reply #61 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
  )
)

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: (Challenge) Closest integer to n
« Reply #62 on: February 04, 2010, 09:12:26 PM »

Nice solution Steve !
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

cadabyss

  • Guest
Re: (Challenge) Closest integer to n
« Reply #63 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 !

pkohut

  • Guest
Re: (Challenge) Closest integer to n
« Reply #64 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;
}

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: (Challenge) Closest integer to n
« Reply #65 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.

pkohut

  • Guest
Re: (Challenge) Closest integer to n
« Reply #66 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

pkohut

  • Guest
Re: (Challenge) Closest integer to n
« Reply #67 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;
}