From: richard.nospam@gmail.com
On 30/11/2022 11:32, Tim Rentsch wrote:
> Richard Harnden writes:
>
> [edited for brevity]
>
>> On 29/11/2022 12:03, Tim Rentsch wrote:
>
>> ..> On 21/11/2022 20:45, Ben Bacarisse wrote:
>> ..>
>> ..>> 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 en value.
>> ..>>
>> ..>> I was specifically concerned with integer values where the
>> ..>> sub-range includes the start value but excludes the end value.
>
>>> [responding to an earlier proposed solution] This assumption
>>> doesn't match the problem statement (emphasis added):
>>>
>>> Consider >> any << ordered measure that "wraps round"
>>>
>>> What's being asked for is a function that will work with any
>>> ordered measure (that wraps), not just some such measures. An
>>> example of such a measure is longitude, which goes from -180
>>> to +180 (with one of the two extreme values omitted). Similarly >
>>> there is no reason not to allow a measure that is only positive
>>> integers but does not include zero. An important part of the
>>> challenge is to come up with a solution that handles these cases
>>> as well as the more obvious ones.
>>
>> Okay, so how about this ... ?
>>
>> int in_subrange(int_fast64_t range_min, int_fast64_t range_max,
>> int_fast64_t start, int_fast64_t end, int_fast64_t check)
>> {
>> while ( check < range_min )
>> check += range_max - range_min;
>>
>> while ( check > range_max )
>> check -= range_max - range_min;
>>
>> if ( ( end < start && (
>> ( check > range_min && check <= end )
>> || (check >= start && check < range_max)
>> )
>> )
>> || ( check >= start && check <= end )
>> )
>> return 1;
>>
>> return 0
>> }
>
> Several things stand out to me.
>
> The code seems confused about whether range_min and range_max are
> legal values or just outside of legal values. Normally I would
> expect them to be legal values, since the "just outside of legal
> values" choice might fall outside the range of the type being used.
I think >= min and < max, so if min were 0 then mod max would be a valid
value.
>
> Assuming range_min and range_max are legal values, the code has an
> off-by-one error, namely, it should be range_max - range_min + 1
> that is added or subtracted to bring 'check' into the legal range.
Yes, Dmitry pointed this out too.
>
> There is still the problem of potential overflow, because the value
> of the expression 'range_max - range_min' might exceed the bounds of
> the type being used.
>
> Minor comment: the choice of 'int_fast64_t' for the parameter type
> is kind of surprising. Why not 'int_least64_t' or maybe even just
> 'long long'?
Yes, int_least64_t is probably better.
>
> The expressions 'check <= end' should be 'check < end' to conform to
> the problem statement that the interval being considered excludes
> the end value.
Okay.
>
> If range_min and range_max are legal values, the tests for 'check'
> being inside the range become superfluous.
>
> Incidentally, since the problem statement doesn't say, to my way of
> thinking it would be fine simply to exclude values of 'check' that
> fall outside the legal range
>
> if( check < range_min || check > range_max ) return 0;
>
> which has the nice by-product of avoiding the overflow problem.
Yes, that could/should be moved outside the function.
>
> Let's look again at the key test, simplified so as not to do the
> range tests (some redundant parentheses retained):
>
> if(
> (end < start && (check <= end || check >= start))
> || (check >= start && check <= end)
> ){
> return 1;
> }
>
> I think the logic of this test is right, but the form of it makes me
> nervous. The reason for that is the second line depends on the
> condition 'start <= end' being true, but that condition is not
> explicitly tested. The condition is /implied/ by the tests that are
> done against 'check', but that result is not immediately obvious. I
> think a better writing would be to use a ?: operator, as for example
>
> if(
> end < start
> ? start <= check || check < end
> : start <= check && check < end
> ){
> return 1;
> }
>
> Now it is immediately obvious that the two cases are mutually
> exclusive.
>
> Finally, consider the last two statements. Since the penultimate
> statement conditionally returns 1 (true) and the last statement
> simply returns 0 (false), these two statements can be combined into
> a single 'return' statement:
>
> return
> end < start
> ? start <= check || check < end
> : start <= check && check < end
> ;
And I think that is the solution you orignally gave (?)
>
> (I hope you will excuse my tendency to try to simplify almost any
> code that I see. I appreciate what you've done here.)
For me, vebose is simple and I'd only condense it down once I understand
it / know its correct.
>
>> It's okay for check to have 'clocked', range_min, range_max, start
>> and end have sensible values.
>
> What I think you mean by this is that 'start' and 'end' can be
> assumed to have values within the legal range, and that range_min
> and range_max have sensible values (so range_min <= range_max),
> and that 'check' might fall outside the legal range, and that
> possibility must be accounted for. That makes sense.
That is what I meant, yes.
Thanks for taking your time.
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
