Path: csiph.com!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.programming Subject: Re: A little puzzle. Date: Wed, 23 Nov 2022 08:04:34 -0800 Organization: A noiseless patient Spider Lines: 149 Message-ID: <86sfi98xnx.fsf@linuxsc.com> References: <875yf8nijb.fsf@bsb.me.uk> <865yf79l66.fsf@linuxsc.com> <87wn7nj9mb.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader01.eternal-september.org; posting-host="94e00b43f70ad6e10e29a03234503c3e"; logging-data="438279"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/An8r8VRIBXxFr01M1/Vj7SZmNBp5zAlA=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:u6MljuHj3uCFvVqLk1PcEEVLFLQ= sha1:LXBdK99DffShKfONl9wZCmZ15xw= Xref: csiph.com comp.programming:15951 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... :)