Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #15916 > unrolled thread
| Started by | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| First post | 2022-11-21 20:45 +0000 |
| Last post | 2022-12-01 06:51 -0800 |
| Articles | 4 on this page of 84 — 9 participants |
Back to article view | Back to comp.programming
A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-21 20:45 +0000
Re: A little puzzle. David Brown <david.brown@hesbynett.no> - 2022-11-21 22:06 +0100
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-21 21:21 +0000
Re: A little puzzle. David Brown <david.brown@hesbynett.no> - 2022-11-22 09:17 +0100
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-11-22 11:07 +0000
Re: A little puzzle. David Brown <david.brown@hesbynett.no> - 2022-11-22 15:17 +0100
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-22 11:40 +0000
Re: A little puzzle. David Brown <david.brown@hesbynett.no> - 2022-11-22 15:26 +0100
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-22 15:28 +0000
Re: A little puzzle. David Brown <david.brown@hesbynett.no> - 2022-11-22 16:30 +0100
Re: A little puzzle. David Brown <david.brown@hesbynett.no> - 2022-11-22 09:23 +0100
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-11-22 11:08 +0000
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-22 12:54 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-21 17:39 -0800
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-22 13:00 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-22 05:31 -0800
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-11-22 11:04 +0000
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-22 12:53 +0000
Re: A little puzzle. Paul N <gw7rib@aol.com> - 2022-11-22 05:01 -0800
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-22 05:48 -0800
Re: A little puzzle. David Brown <david.brown@hesbynett.no> - 2022-11-22 15:31 +0100
FFs [was Re: A little puzzle] Richard Harnden <richard.nospam@gmail.com> - 2022-11-22 16:29 +0000
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-12-14 13:57 +0000
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-12-14 13:58 +0000
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-12-14 16:22 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-22 05:24 -0800
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-22 15:23 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-23 08:04 -0800
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-24 00:06 +0000
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-11-24 04:06 +0000
Re: A little puzzle. David Brown <david.brown@hesbynett.no> - 2022-11-24 09:29 +0100
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-24 13:23 +0000
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-24 13:14 +0000
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-11-24 14:00 +0000
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-24 14:59 +0000
Re: A little puzzle. Richard Harnden <richard.nospam@gmail.com> - 2022-11-24 19:00 +0000
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-24 20:36 +0000
Re: A little puzzle. Andreas <nobody@me.com> - 2022-11-27 00:38 +0100
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-27 00:11 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-24 14:51 -0800
Re: A little puzzle. "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-11-25 09:30 +0100
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-25 01:16 -0800
Re: A little puzzle. "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-11-25 11:11 +0100
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-25 06:26 -0800
Re: A little puzzle. "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-11-25 15:59 +0100
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-26 16:25 +0000
Re: A little puzzle. "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-11-26 19:36 +0100
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-27 02:03 +0000
Re: A little puzzle. "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-11-27 11:02 +0100
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-01 04:30 -0800
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-02 00:22 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-02 22:30 -0800
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-12-03 02:43 -0800
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-27 18:38 -0800
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-11-27 02:27 -0800
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-27 19:23 -0800
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-11-27 22:59 -0800
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-11-27 23:03 -0800
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-28 07:22 -0800
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-11-28 10:20 -0800
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-29 04:29 -0800
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-11-29 04:50 -0800
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-11-29 14:47 +0000
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-29 17:23 +0000
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-11-29 09:50 -0800
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-30 01:39 -0800
Re: A little puzzle. Richard Heathfield <rjh@cpax.org.uk> - 2022-11-30 11:10 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-30 02:24 -0800
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-11-30 06:28 -0800
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-01 06:55 -0800
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-12-02 01:54 -0800
Re: A little puzzle. Richard Harnden <richard.nospam@gmail.com> - 2022-11-28 11:20 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-28 07:30 -0800
Re: A little puzzle. Richard Harnden <richard.nospam@gmail.com> - 2022-11-28 17:15 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-29 04:03 -0800
Re: A little puzzle. Richard Harnden <richard.nospam@gmail.com> - 2022-11-29 15:03 +0000
Re: A little puzzle. "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-11-29 16:13 +0100
Re: A little puzzle. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-11-29 17:37 +0000
Re: A little puzzle. "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2022-11-29 19:02 +0100
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-11-29 10:10 -0800
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-30 03:32 -0800
Re: A little puzzle. Julio Di Egidio <julio@diegidio.name> - 2022-11-30 06:36 -0800
Re: A little puzzle. Richard Harnden <richard.nospam@gmail.com> - 2022-11-30 15:21 +0000
Re: A little puzzle. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-01 06:51 -0800
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-11-30 03:32 -0800 |
| Message-ID | <861qpk7k5f.fsf@linuxsc.com> |
| In reply to | #15993 |
Richard Harnden <richard.nospam@gmail.com> 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.
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.
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'?
The expressions 'check <= end' should be 'check < end' to conform to
the problem statement that the interval being considered excludes
the end value.
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.
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
;
(I hope you will excuse my tendency to try to simplify almost any
code that I see. I appreciate what you've done here.)
> 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.
[toc] | [prev] | [next] | [standalone]
| From | Julio Di Egidio <julio@diegidio.name> |
|---|---|
| Date | 2022-11-30 06:36 -0800 |
| Message-ID | <ebd3d9c4-fc49-4e29-9640-51ffe49e89a1n@googlegroups.com> |
| In reply to | #16012 |
On Wednesday, 30 November 2022 at 12:32:18 UTC+1, Tim Rentsch wrote: > 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 These threads are typically just *full* of misunderstandings and malpractices, and I won't even begin listing them all. For example, *that*, to the letter, is a recipe for *guaranteed disaster*. I know of a company that used to build robots like that, just assume all inputs are valid by a protocol, and at the first signal invalid by the protocol, the robots simply destroy whatever is range... or crash a plane or what have you... And that's a good place to stop. (EOD) Julio
[toc] | [prev] | [next] | [standalone]
| From | Richard Harnden <richard.nospam@gmail.com> |
|---|---|
| Date | 2022-11-30 15:21 +0000 |
| Message-ID | <tm7sdq$2i6bi$2@dont-email.me> |
| In reply to | #16012 |
On 30/11/2022 11:32, Tim Rentsch wrote:
> Richard Harnden <richard.nospam@gmail.com> 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.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-12-01 06:51 -0800 |
| Message-ID | <86sfhz5g9j.fsf@linuxsc.com> |
| In reply to | #16015 |
Richard Harnden <richard.nospam@gmail.com> writes:
> On 30/11/2022 11:32, Tim Rentsch wrote:
[...]
>> 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 (?)
Mathematically equivalent (my code used different operand orders).
Notice though that my derivation above simply started with your
code and went forward. I wasn't re-engineering the problem, just
revising what you had written to put it in an easier-to-understand
form. (I should add that I did modify the end boundary condition
test, but that is incidental.) That the result was equivalent to
what I wrote shows that your original code has the same behavior
as mine, and only that; I didn't mean to compare them or offer
any sort of correction (and in fact I wasn't thinking of what
I had written while I was replying to your posting).
>> (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.
When I say "simplify" I don't mean make shorter but make it easier
for me to convince myself that the code is correct. A lot of
times shorter code is easier to understand, but shortness is not
the metric for simplicity. Code that makes it easier for me to
convince myself that the code is correct is simpler, no matter
how condensed or compact it is. What motivated me here was that
the original code made it hard for me to convince myself that the
code was correct.
>> [...]
> Thanks for taking your time.
Thank you, it's always pleasing to hear appreciation for my
efforts.
[toc] | [prev] | [standalone]
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
Back to top | Article view | comp.programming
csiph-web