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 | 20 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 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2022-11-22 15:31 +0100 |
| Message-ID | <tlimf9$3u8n$2@dont-email.me> |
| In reply to | #15938 |
On 22/11/2022 14:48, Tim Rentsch wrote:
> Paul N <gw7rib@aol.com> writes:
>
>> On Tuesday, November 22, 2022 at 12:53:47 PM UTC, Ben Bacarisse wrote:
>>
>>> Richard Heathfield <r...@cpax.org.uk> writes:
>
> [...]
>
>>>> although of course in C the problem would be far better solved as:
>>>>
>>>> int inrange(int lo, int hi, int k)
>>>> {
>>>> return (lo <= k) && (k < hi);
>>>> }
>>>>
>>>> or even as a macro.
>>>>
>>>> I must confess I'm not entirely certain I have correctly interpreted
>>>> your puzzle, which I have taken to mean "is this a given value in the
>>>> given range", but this seems just a bit too easy for you to make a
>>>> hash of, but I'm sure I've made hashes of worse. I've missed
>>>> something, haven't I?
>>>
>>> The circular wrapping. On a clock, 55 is in the range of minutes that
>>> starts at 45 and ends at 5.
>>
>> What's wrong with - subtract start from both end and value, add the
>> modulus if either is negative, and compare?
>
> Suppose start is 9223372036854775800 and end is -9223372036854775800
> (or the corresponding values for type 'int', those values are for a
> 64-bit signed integer type). The subtraction gives undefined behavior.
It's all modulo arithmetic - you can do it all as unsigned types.
Or use Python and be happy - this is, after all, comp.programming and
not comp.lang.c !
[toc] | [prev] | [next] | [standalone]
| From | Richard Harnden <richard.nospam@gmail.com> |
|---|---|
| Date | 2022-11-22 16:29 +0000 |
| Subject | FFs [was Re: A little puzzle] |
| Message-ID | <tlitd0$4c5i$1@dont-email.me> |
| In reply to | #15932 |
On 22/11/2022 12:53, Ben Bacarisse wrote: > Richard Heathfield <rjh@cpax.org.uk> writes: > >> On 21/11/2022 8:45 pm, Ben Bacarisse wrote: >>> Do all the news >>> readers used by programmers (or ex programmers) all respect the presence >>> of a form-feed character... >> >> Dunno. Let's find out: >> >> Ctrl-L coming up: >> >> >> > > Didn't see a form feed there. Here's one (I hope): > For me, the FFs work on windows but not on the mac. Both using thunderbird.
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2022-12-14 13:57 +0000 |
| Message-ID | <tncknu$2of9h$4@dont-email.me> |
| In reply to | #15928 |
On 14/12/2022 1:23 pm, Stefan Ram wrote: > Richard Heathfield <rjh@cpax.org.uk> writes: >> Your problem is closely related to the very first question I was >> ever posed (in early 1982), by a friend who needed to be able to >> establish cleanly in a single expression whether a keypress was a >> digit (ASCII 48-57). The relevant dialect of BASIC didn't have >> anything like an isdigit function. >> The friend was on the point of giving up on me when I handed him >> ABS(K-52.5)<4.5 > > "K >= 48 AND K <= 57" also is a single expression in BASIC. The available keywords were LET, PRINT, END, FOR...NEXT, GOTO, GOSUB...RETURN, IF...THEN line number, DEF, READ, DATA, DIM, and REM. AND was not amongst them. Also available were these functions: ABS, ATN (arc tan), COS, EXP, INT, LOG, RND, SIN, SQR (root). -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2022-12-14 13:58 +0000 |
| Message-ID | <tnckph$2of9h$5@dont-email.me> |
| In reply to | #16078 |
On 14/12/2022 1:57 pm, Richard Heathfield wrote: > On 14/12/2022 1:23 pm, Stefan Ram wrote: >> Richard Heathfield <rjh@cpax.org.uk> writes: >>> Your problem is closely related to the very first question I was >>> ever posed (in early 1982), by a friend who needed to be able to >>> establish cleanly in a single expression whether a keypress was a >>> digit (ASCII 48-57). The relevant dialect of BASIC didn't have >>> anything like an isdigit function. >>> The friend was on the point of giving up on me when I handed him >>> ABS(K-52.5)<4.5 >> >> "K >= 48 AND K <= 57" also is a single expression in BASIC. > > The available keywords were LET, PRINT, END, FOR...NEXT, GOTO, > GOSUB...RETURN, IF...THEN line number, DEF, READ, DATA, DIM, and > REM. AND was not amongst them. Also available were these > functions: ABS, ATN (arc tan), COS, EXP, INT, LOG, RND, SIN, SQR > (root). ...and I missed TAN. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2022-12-14 16:22 +0000 |
| Message-ID | <tnct7c$2of9o$4@dont-email.me> |
| In reply to | #16078 |
On 14/12/2022 3:43 pm, Stefan Ram wrote: > Richard Heathfield <rjh@cpax.org.uk> writes: >> On 14/12/2022 1:23 pm, Stefan Ram wrote: >>> Richard Heathfield <rjh@cpax.org.uk> writes: >>>> Your problem is closely related to the very first question I was >>>> ever posed (in early 1982), by a friend who needed to be able to >>>> establish cleanly in a single expression whether a keypress was a >>>> digit (ASCII 48-57). The relevant dialect of BASIC didn't have >>>> anything like an isdigit function. >>>> The friend was on the point of giving up on me when I handed him >>>> ABS(K-52.5)<4.5 >>> "K >= 48 AND K <= 57" also is a single expression in BASIC. >> The available keywords were LET, PRINT, END, FOR...NEXT, GOTO, >> GOSUB...RETURN, IF...THEN line number, DEF, READ, DATA, DIM, and >> REM. AND was not amongst them. Also available were these >> functions: ABS, ATN (arc tan), COS, EXP, INT, LOG, RND, SIN, SQR >> (root). > > Sometimes, multiplication can be used for "AND". > I.e., "( K >= 48 )*( K <= 57 )". Yes, I know. Barely a fortnight after using a mainframe computer for the first time, I didn't know it /then/. With 40 years of programming experience, it is not difficult to devise better solutions to the problems I encountered 40 years ago. But when you're there, you have to use what knowledge you have and what you can dredge up from the photostats that served as a manual. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-11-22 05:24 -0800 |
| Message-ID | <865yf79l66.fsf@linuxsc.com> |
| In reply to | #15916 |
Ben Bacarisse <ben.usenet@bsb.me.uk> 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)...
(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;
}
This function works if T is any integer type, or any real
floating-point type, or is a type pointer to any complete
object type. (Disclaimer: I didn't think carefully about
the case where T is a pointer to an array type.)
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-11-22 15:23 +0000 |
| Message-ID | <87wn7nj9mb.fsf@bsb.me.uk> |
| In reply to | #15936 |
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Ben Bacarisse <ben.usenet@bsb.me.uk> 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.
bool is_circularly_between(T start, T end, T i) {
return start <= end ? start <= i && i < end
: !is_circularly_between(end, start, i);
}
(I put the parameters in a different order because I was using Haskell,
and with Curried functions, is_circularly_between x y is a useful
function in its own right.)
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.
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-11-23 08:04 -0800 |
| Message-ID | <86sfi98xnx.fsf@linuxsc.com> |
| In reply to | #15942 |
Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> 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... :)
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-11-24 00:06 +0000 |
| Message-ID | <87leo1i5bo.fsf@bsb.me.uk> |
| In reply to | #15951 |
Tim Rentsch <tr.17687@z991.linuxsc.com> writes: > 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... :) I didn't make a good job of presenting it. It certainly didn't pique anyone else's interest, but then comp.programming is not well populated. One thing that struck me was that I had not come across this before. I was surprised that this was not one of those idioms that one absorbs along the way. I suppose it is of limited use. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2022-11-24 04:06 +0000 |
| Message-ID | <tlmqja$jbpj$1@dont-email.me> |
| In reply to | #15953 |
On 24/11/2022 12:06 am, Ben Bacarisse wrote: > Tim Rentsch <tr.17687@z991.linuxsc.com> writes: > >> 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... :) > > I didn't make a good job of presenting it. It certainly didn't pique > anyone else's interest, but then comp.programming is not well populated. > > One thing that struck me was that I had not come across this before. I > was surprised that this was not one of those idioms that one absorbs > along the way. I suppose it is of limited use. The trouble is that it comes across as "is y >= x and <= z?", which is about as simple as it gets. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2022-11-24 09:29 +0100 |
| Message-ID | <tlna28$kb88$1@dont-email.me> |
| In reply to | #15954 |
On 24/11/2022 05:06, Richard Heathfield wrote: > On 24/11/2022 12:06 am, Ben Bacarisse wrote: >> Tim Rentsch <tr.17687@z991.linuxsc.com> writes: >> >>> 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... :) >> >> I didn't make a good job of presenting it. It certainly didn't pique >> anyone else's interest, but then comp.programming is not well populated. >> >> One thing that struck me was that I had not come across this before. I >> was surprised that this was not one of those idioms that one absorbs >> along the way. I suppose it is of limited use. > > The trouble is that it comes across as "is y >= x and <= z?", which is > about as simple as it gets. > Some of us managed to misinterpret the post as being about as complex as it gets! I use circular buffers a great deal in my coding. For many of my systems, there are UART communication ports (such as for debugging output - when you don't have a screen or standard output, a UART does the job). There is typically a circular buffer which is piped out to the port via interrupt routines, and when the application code wants to "print" out a message, it gets pushed into the buffer. So the kind of thought needed for Ben's "puzzle" turns up in real code, and I've seen people get it wrong.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-11-24 13:23 +0000 |
| Message-ID | <878rk0iizc.fsf@bsb.me.uk> |
| In reply to | #15955 |
David Brown <david.brown@hesbynett.no> writes: > I use circular buffers a great deal in my coding. For many of my > systems, there are UART communication ports (such as for debugging > output - when you don't have a screen or standard output, a UART does > the job). There is typically a circular buffer which is piped out to > the port via interrupt routines, and when the application code wants > to "print" out a message, it gets pushed into the buffer. Yes, and I've used circular buffers before, but always as queues so there was never a need to know if an index (or pointer) is in the filled or unfilled region. One just had to avoid confusing a full buffer with an empty one. > So the kind of thought needed for Ben's "puzzle" turns up in real > code, and I've seen people get it wrong. What's the modulo solution you had in mind? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-11-24 13:14 +0000 |
| Message-ID | <87edtsijfq.fsf@bsb.me.uk> |
| In reply to | #15954 |
Richard Heathfield <rjh@cpax.org.uk> writes: > On 24/11/2022 12:06 am, Ben Bacarisse wrote: >> Tim Rentsch <tr.17687@z991.linuxsc.com> writes: >> >>> 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... :) >> I didn't make a good job of presenting it. It certainly didn't pique >> anyone else's interest, but then comp.programming is not well populated. >> One thing that struck me was that I had not come across this before. I >> was surprised that this was not one of those idioms that one absorbs >> along the way. I suppose it is of limited use. > > The trouble is that it comes across as "is y >= x and <= z?", which is > about as simple as it gets. I am saddened that you think I would have made a hash of that and amazed that you could think I had never have come across such a thing before. :-( I would have thought that "Consider any ordered measure that "wraps round" -- bearings in degrees, minutes in the hour, indeed hours in either the 12 or 24 hour clock." might have suggested it was not any old start <= x < end problem. How would you have phrased it so as to avoid the confusion? Anyway, the take-away is that the size of the range is not part of the problem and that no modulo operations are involved. I found that mildly interesting. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2022-11-24 14:00 +0000 |
| Message-ID | <tlntda$knou$1@dont-email.me> |
| In reply to | #15956 |
On 24/11/2022 1:14 pm, Ben Bacarisse wrote: > Richard Heathfield <rjh@cpax.org.uk> writes: > >> On 24/11/2022 12:06 am, Ben Bacarisse wrote: >>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes: >>> >>>> 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... :) >>> I didn't make a good job of presenting it. It certainly didn't pique >>> anyone else's interest, but then comp.programming is not well populated. >>> One thing that struck me was that I had not come across this before. I >>> was surprised that this was not one of those idioms that one absorbs >>> along the way. I suppose it is of limited use. >> >> The trouble is that it comes across as "is y >= x and <= z?", which is >> about as simple as it gets. > > I am saddened that you think I would have made a hash of that and amazed > that you could think I had never have come across such a thing > before. :-( Well, of course I don't think that. But that's how it reads, that's all. It couldn't be what you meant, but I'm not a mind reader. > I would have thought that > > "Consider any ordered measure that "wraps round" -- bearings in > degrees, minutes in the hour, indeed hours in either the 12 or 24 hour > clock." > > might have suggested it was not any old start <= x < end problem. It suggested modulo to me. > How > would you have phrased it so as to avoid the confusion? That depends on what you mean, which is evidently now clear to others, but not yet to me. > Anyway, the take-away is that the size of the range is not part of the > problem and that no modulo operations are involved. I found that mildly > interesting. Okay. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-11-24 14:59 +0000 |
| Message-ID | <87v8n4h003.fsf@bsb.me.uk> |
| In reply to | #15958 |
Richard Heathfield <rjh@cpax.org.uk> writes: > On 24/11/2022 1:14 pm, Ben Bacarisse wrote: >> Richard Heathfield <rjh@cpax.org.uk> writes: >> >>> On 24/11/2022 12:06 am, Ben Bacarisse wrote: >>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes: >>>> >>>>> 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... :) >>>> I didn't make a good job of presenting it. It certainly didn't pique >>>> anyone else's interest, but then comp.programming is not well populated. >>>> One thing that struck me was that I had not come across this before. I >>>> was surprised that this was not one of those idioms that one absorbs >>>> along the way. I suppose it is of limited use. >>> >>> The trouble is that it comes across as "is y >= x and <= z?", which is >>> about as simple as it gets. >> I am saddened that you think I would have made a hash of that and amazed >> that you could think I had never have come across such a thing >> before. :-( > > Well, of course I don't think that. But that's how it reads, that's > all. It couldn't be what you meant, but I'm not a mind reader. I hope you can help me express it better. >> I would have thought that >> "Consider any ordered measure that "wraps round" -- bearings in >> degrees, minutes in the hour, indeed hours in either the 12 or 24 hour >> clock." >> might have suggested it was not any old start <= x < end problem. > > It suggested modulo to me. That quote was from the first post -- the one that reads to you as if I meant a plain start <= x < end. >> How >> would you have phrased it so as to avoid the confusion? > > That depends on what you mean, which is evidently now clear to others, > but not yet to me. There's only been one solution, so I'm not 100% anyone else knows what the question was! I'd like to find a way to pin it down in case I ever want to express the problem to someone else. The case in point related to timed events where I only know the start and end minutes. I needed to test if the current time's minutes was in any of the events. So if there were three events running from 10 to 25, 30 to 50 and 55 to 05 minutes past the hour then at 15 past we are in event 1. At 35 past we are not in any event, and at 03 we are in event 3. I really want to find a way of explaining this that avoids too many specifics because any one case is likely to raise a lot of questions. The generic part is that there is some measure, with a direction or order, that wraps round, and we want to test for sub-ranges of that measure. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Harnden <richard.nospam@gmail.com> |
|---|---|
| Date | 2022-11-24 19:00 +0000 |
| Message-ID | <tlof0g$n8kr$1@dont-email.me> |
| In reply to | #15959 |
On 24/11/2022 14:59, Ben Bacarisse wrote: > > I'd like to find a way to pin it down in case I ever want to express the > problem to someone else. The case in point related to timed events > where I only know the start and end minutes. I needed to test if the > current time's minutes was in any of the events. So if there were three > events running from > > 10 to 25, 30 to 50 and 55 to 05 > > minutes past the hour then at 15 past we are in event 1. At 35 past we > are not in any event, and at 03 we are in event 3. Isn't 35 within event 2? Or am I missing something?
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-11-24 20:36 +0000 |
| Message-ID | <87bkowgke4.fsf@bsb.me.uk> |
| In reply to | #15962 |
Richard Harnden <richard.nospam@gmail.com> writes: > On 24/11/2022 14:59, Ben Bacarisse wrote: > >> I'd like to find a way to pin it down in case I ever want to express the >> problem to someone else. The case in point related to timed events >> where I only know the start and end minutes. I needed to test if the >> current time's minutes was in any of the events. So if there were three >> events running from >> 10 to 25, 30 to 50 and 55 to 05 >> minutes past the hour then at 15 past we are in event 1. At 35 past we >> are not in any event, and at 03 we are in event 3. > > Isn't 35 within event 2? Or am I missing something? Yes! I stupidly went and edited the times because I'd chosen very odd ones and then didn't check. You clearly see the question now, so do you have advice on how I could word it so as to avid your initial view of what was asking? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Andreas <nobody@me.com> |
|---|---|
| Date | 2022-11-27 00:38 +0100 |
| Message-ID | <tlu81i$b8l$1@gioia.aioe.org> |
| In reply to | #15956 |
On 24.11.22 14:14, Ben Bacarisse wrote: > Richard Heathfield <rjh@cpax.org.uk> writes: > >> On 24/11/2022 12:06 am, Ben Bacarisse wrote: >>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes: >>> >>>> 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... :) >>> I didn't make a good job of presenting it. It certainly didn't pique >>> anyone else's interest, but then comp.programming is not well populated. >>> One thing that struck me was that I had not come across this before. I >>> was surprised that this was not one of those idioms that one absorbs >>> along the way. I suppose it is of limited use. >> >> The trouble is that it comes across as "is y >= x and <= z?", which is >> about as simple as it gets. > > I am saddened that you think I would have made a hash of that and amazed > that you could think I had never have come across such a thing > before. :-( > > I would have thought that > > "Consider any ordered measure that "wraps round" -- bearings in > degrees, minutes in the hour, indeed hours in either the 12 or 24 hour > clock." > > might have suggested it was not any old start <= x < end problem. How > would you have phrased it so as to avoid the confusion? > > Anyway, the take-away is that the size of the range is not part of the > problem and that no modulo operations are involved. I found that mildly > interesting. > This still bothers me. Take your example of 55 minutes being between 45 minutes and 5 minutes. That's certainly true, but what if the numbers where not minutes? If your numbers wrapped around at 54 instead of at 60, there wouldn't be a 55. How is your program supposed to know it? Is it hard coded? Or do you want something flexible enough to be usable with any "modulo"?
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-11-27 00:11 +0000 |
| Message-ID | <87bkoti7cq.fsf@bsb.me.uk> |
| In reply to | #15972 |
Andreas <nobody@me.com> writes: > On 24.11.22 14:14, Ben Bacarisse wrote: >> Richard Heathfield <rjh@cpax.org.uk> writes: >> >>> On 24/11/2022 12:06 am, Ben Bacarisse wrote: >>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes: >>>> >>>>> 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... :) >>>> I didn't make a good job of presenting it. It certainly didn't pique >>>> anyone else's interest, but then comp.programming is not well populated. >>>> One thing that struck me was that I had not come across this before. I >>>> was surprised that this was not one of those idioms that one absorbs >>>> along the way. I suppose it is of limited use. >>> >>> The trouble is that it comes across as "is y >= x and <= z?", which is >>> about as simple as it gets. >> I am saddened that you think I would have made a hash of that and amazed >> that you could think I had never have come across such a thing >> before. :-( >> I would have thought that >> "Consider any ordered measure that "wraps round" -- bearings in >> degrees, minutes in the hour, indeed hours in either the 12 or 24 hour >> clock." >> might have suggested it was not any old start <= x < end problem. How >> would you have phrased it so as to avoid the confusion? >> Anyway, the take-away is that the size of the range is not part of the >> problem and that no modulo operations are involved. I found that mildly >> interesting. > > This still bothers me. Take your example of 55 minutes being between > 45 minutes and 5 minutes. That's certainly true, but what if the > numbers where not minutes? If your numbers wrapped around at 54 > instead of at 60, there wouldn't be a 55. How is your program supposed > to know it? Is it hard coded? Or do you want something flexible enough > to be usable with any "modulo"? The data are assumed to be valid -- i.e. in the expected range for the kind of data (0 to 59 for minutes for example). And when you need to do this test with potentially invalid data, I'd argue that the correction does not belong here. In some applications it might be appropriate to silently "correct" an invalid datum and in others you might need to hard error. The data validation should be somewhere else. That makes the simple test function re-usable. I agree that the problem specification should have made that as clear as possible. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-11-24 14:51 -0800 |
| Message-ID | <86k03k7yqe.fsf@linuxsc.com> |
| In reply to | #15953 |
Ben Bacarisse <ben.usenet@bsb.me.uk> writes: > Tim Rentsch <tr.17687@z991.linuxsc.com> writes: > >> 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... :) > > I didn't make a good job of presenting it. It certainly didn't > pique anyone else's interest, but then comp.programming is not > well populated. I think part of the problem is that the question looks "easier" than it really is. People have an initial reaction (certainly I know I did) but don't continue to think through what the issues might be. For what it's worth, here is a stab at presenting the problem. It's longer than I would like it to be, but maybe it will be helpful. We are interested in writing a function to answer a more general version of the example problem stated below. Consider a plane flying easterly (and for simplicity, directly above the equator). We measure the plane's progress by its longitude, measured to the nearest second of arc (1/3600 of a degree), so from -180 degrees to 179 degrees 59 minutes 59 seconds (or equivalently from -648000 seconds to 647999 seconds). We would like to know if a given longitude is between the plane's starting longitude and ending longitude. (Note that the longitude measurements below are given in degrees, minutes, and seconds, but we may assume that internally they are represented as an integer number of seconds.) For example, if the plane flies from Los Angeles, US (longitude -118 14' 37") to New York, US (longitude -73 56' 7") does it cross over the longitude lines of Denver, US (longitude -104 59' 30"), or Moscow, Russia (longitude 37 37' 6")? Answer: the plane does cross the longitude line of Denver but not that of Moscow. Similarly, if the plane flies from Beijing, China (longitude 116 23' 0") to Los Angeles, US (longitude -118 14' 37") does it cross over Tokyo, Japan (longitude 139 50' 32"), Waikiki, Hawaii, US (longitude -157 50' 4"), or Moscow, Russia (longitude 37 37' 6")? Answer: the plane does cross the longitude lines of Tokyo and Waikiki but not that of Moscow. For the general case we would like to handle any circular measure (for convenience having coordinates in some integer range). Exercise: write a function to answer this kind of question for circular measures in general. You may assume integer coordinates and intervals that include the starting point but do not include the end point. Give a suitable declaration for the function, and separately give a function definition to implement the given interface.
[toc] | [prev] | [next] | [standalone]
Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
Back to top | Article view | comp.programming
csiph-web