From: tr.17687@z991.linuxsc.com   
      
   Ben Bacarisse  writes:   
      
   > Tim Rentsch  writes:   
   >   
   >> Ben Bacarisse  writes:   
   >>   
   >> [...]   
   >>   
   >>> Consider any ordered measure that "wraps round" -- bearings in degrees,   
   >>> minutes in the hour, indeed hours in either the 12 or 24 hour clock.   
   >>> The problem is to determine if a given value is in the sub-range   
   >>> specified by a start and an [end] value.   
   >>>   
   >>> I was specifically concerned with integer values where the sub-range   
   >>> includes the start value but excludes the end value.   
   >>>   
   >>> Though I am not sure this merits the term "puzzle", I suggest that   
   >>> solutions be posted with some spoiler protection.   
   >>   
   >> My answer below (forgive me for resorting to "low tech" spoiler   
   >> protection)...   
   >   
   > I think this is the safest option.   
   >   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >> (spoiler alert)   
   >>   
   >> /* is_circularly_between( a, b, c ) -   
   >>  *     1 if b is circularly between a and c,   
   >>  *     0 otherwise   
   >>  *     the interval of interest [ a, c ) is understood to be   
   >>  *         closed at the 'a' end, and   
   >>  *         open at the 'c' end   
   >>  *   
   >>  *     The parameters a, b, and c are all of a single type T,   
   >>  *     where T allows relational (ordering) comparisons.   
   >>  *   
   >>  *     Assumes a, b, and c all have legitimate values.   
   >>  */   
   >>   
   >> int   
   >> is_circularly_between( T a, T b, T c ){   
   >>     return  a <= c    ?  a <= b  &&  b < c    :  a <= b  ||  b < c;   
   >> }   
   >   
   > I am sure you know this is correct!  My version is recursive, because I   
   > think it adds some clarity, but whether it really does add anything   
   > probably depends on how one arrives at the answer.  [parameters in a   
   > different order to help with currying]   
   >   
   >   bool is_circularly_between(T start, T end, T i) {   
   >       return start <= end ? start <= i && i < end   
   >                           : !is_circularly_between(end, start, i);   
   >   }   
      
   Very clever!  It never occurred to me to consider the complement   
   of the interval.  This idea works only because the interval is   
   half open, which means its complement is also half open.  I'm not   
   sure which approach is "more obvious";  I think both formulations   
   need some not-completely-trivial thinking to see how (and that)   
   they work.  I think I find it easier to convince myself that the   
   non-recursive version works, but of course that's the one I   
   thought of so naturally I would be likely to think it's easier.   
      
   > The only reason I thought it worth mentioning was my failure!  For   
   > the best part of an hour I thought the size of the circular range   
   > (the modulus) had to be involved.   
      
   Now I see the important point of your earlier comment.  My   
   attempt at clarifying the problem did not have a parameter for   
   the modulus, implicitly giving away that the modulus is not   
   needed.  Probably I should have tried to define the interface   
   first, and then discover a solution, rather than coding up a   
   solution and then asking about its interface.  I'll try to   
   remember that for future reference.   
      
   In my case, where I started was thinking of ranges in an unsigned   
   type, with some upper bound M.  Then we can simply add M-start to   
   the 'i' and 'end' parameters (using your names), and compare the   
   residues:   
      
       unsigned delta = M - start;   
       return  (i+delta)%M < (end+delta)%M;   
      
   Unfortunately this idea doesn't work if M is too close to the   
   upper limit of the type used.  I briefly considered at a few   
   variations using comparisons, subtractions, the range of the   
   type, and so forth, but it was all getting too messy.  Then I   
   thought, well, either the upper bound is above the lower bound or   
   it isn't, and I know how to do the case when it is, now how about   
   the case then it isn't?  I wondered about how to deal with the   
   potential problem of values (either 'start' or 'end' or 'i')   
   being "out of range", and finally decided not to care, at which   
   point I realized that the range matters only for validity   
   checking, not for getting an answer.  Thus I arrived at the   
   answer shown above.   
      
   I think this problem would make a good interview question,   
   provided care were taken to phrase it so the subtleties were   
   still there, but possible points of confusion were reduced.   
   Not that I know how to do that... :)   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)