Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #15916 > unrolled thread

A little puzzle.

Back to article view | Back to comp.programming

Contents

  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 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

#15965

On 2022-11-24 23:51, Tim Rentsch wrote:

> For the general case we would like to handle any circular measure
> (for convenience having coordinates in some integer range).

Not necessarily circular. The same issue arise with overflowing 
counters. E.g. the typical case when you have some real-time clock 
counter which periodically runs over and you have to detect overflows.

> 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.

Usual technique is expanding the range this or that way. E.g.

- Computing differences in the specified direction and complementing by 
the modulo when the difference turns negative.
- Using large non-modular numbers that never overflow, e.g. with indices 
of a ring buffer. A 64-bit sequence number I is the new "index." To 
access elements I mod N is used.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#15966

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2022-11-24 23:51, Tim Rentsch wrote:
>
>> 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.
>
> Usual technique is expanding the range this or that way.  E.g.
>
> - Computing differences in the specified direction and complementing
> by the modulo when the difference turns negative.
> - Using large non-modular numbers that never overflow, e.g. with
> indices of a ring buffer.  A 64-bit sequence number I is the new
> "index."  To access elements I mod N is used.

Even Edsgar Dijkstra wrote code to show solutions to
programming exercises.  Where is your code?

[toc] | [prev] | [next] | [standalone]

#15967

On 2022-11-25 10:16, Tim Rentsch wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On 2022-11-24 23:51, Tim Rentsch wrote:
>>
>>> 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.
>>
>> Usual technique is expanding the range this or that way.  E.g.
>>
>> - Computing differences in the specified direction and complementing
>> by the modulo when the difference turns negative.
>> - Using large non-modular numbers that never overflow, e.g. with
>> indices of a ring buffer.  A 64-bit sequence number I is the new
>> "index."  To access elements I mod N is used.
> 
> Even Edsgar Dijkstra wrote code to show solutions to
> programming exercises.  Where is your code?

If you ask for code rather than for an algorithm, you must formalize you 
question, by providing written specifications in the programming 
language of choice. E.g. specify the ADT longtitude and the operations 
you want to implement on it, e.g. range comparisons.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#15968

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2022-11-25 10:16, Tim Rentsch wrote:
>
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>
>>> On 2022-11-24 23:51, Tim Rentsch wrote:
>>>
>>>> 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.
>>>
>>> Usual technique is expanding the range this or that way.  E.g.
>>>
>>> - Computing differences in the specified direction and complementing
>>> by the modulo when the difference turns negative.
>>> - Using large non-modular numbers that never overflow, e.g. with
>>> indices of a ring buffer.  A 64-bit sequence number I is the new
>>> "index."  To access elements I mod N is used.
>>
>> Even Edsgar Dijkstra wrote code to show solutions to
>> programming exercises.  Where is your code?
>
> If you ask for code rather than for an algorithm, you must formalize
> you question, by providing written specifications in the programming
> language of choice.  E.g. specify the ADT longtitude and the operations
> you want to implement on it, e.g. range comparisons.

Apparently you don't realize that part of the problem is to
define the interface, not just implement it.  For the programming
language, pick any common, widely used language, as for example
Ada or C.  For the type of the values involved, pick any standard
integer data type that covers a large range of possible values,
such as 'intmax_t' in C.  "Give a suitable declaration for the
function" means both (a) supplying an appropriate prototype
(using C terminology), and (b) either writing a comment or
choosing adequately descriptive parameters names for whatever
argument values are needed.  "Give a function definition to
implement the given interface" means supplying a complete
function definition that is compatible with the previously
supplied declaration, and that computes the desired result.

Now once again, where is your code?

[toc] | [prev] | [next] | [standalone]

#15969

On 2022-11-25 15:26, Tim Rentsch wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On 2022-11-25 10:16, Tim Rentsch wrote:
>>
>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>
>>>> On 2022-11-24 23:51, Tim Rentsch wrote:
>>>>
>>>>> 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.
>>>>
>>>> Usual technique is expanding the range this or that way.  E.g.
>>>>
>>>> - Computing differences in the specified direction and complementing
>>>> by the modulo when the difference turns negative.
>>>> - Using large non-modular numbers that never overflow, e.g. with
>>>> indices of a ring buffer.  A 64-bit sequence number I is the new
>>>> "index."  To access elements I mod N is used.
>>>
>>> Even Edsgar Dijkstra wrote code to show solutions to
>>> programming exercises.  Where is your code?
>>
>> If you ask for code rather than for an algorithm, you must formalize
>> you question, by providing written specifications in the programming
>> language of choice.  E.g. specify the ADT longtitude and the operations
>> you want to implement on it, e.g. range comparisons.
> 
> Apparently you don't realize that part of the problem is to
> define the interface, not just implement it.

Why do you expect code if you cannot formulate the problem?

> For the programming
> language, pick any common, widely used language, as for example
> Ada or C.  For the type of the values involved, pick any standard
> integer data type that covers a large range of possible values,
> such as 'intmax_t' in C.  "Give a suitable declaration for the
> function" means both (a) supplying an appropriate prototype
> (using C terminology), and (b) either writing a comment or
> choosing adequately descriptive parameters names for whatever
> argument values are needed.  "Give a function definition to
> implement the given interface" means supplying a complete
> function definition that is compatible with the previously
> supplied declaration, and that computes the desired result.
> 
> Now once again, where is your code?

Since you didn't said what you want, here is an implementation of an 
advanced ring buffer with a defined order on its elements that survives 
overriding them in the buffer:

http://www.dmitry-kazakov.de/ada/components.htm#10.2

The source is freely available.

(Ordering elements in a ring of module is the general problem of which 
what you wanted is a special case, I guess)

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#15970

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> 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.

I think so.  I am, to be honest, rather disappointed by the reception
this problem has had.  Even after various examples and two explanations,
some posters still don't know what's being asked, but at the time it is
claimed that it's trivial and not worth coding up.  Sometimes both
claims are made by the same poster.

> 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.

I think this is good, though the example with seconds of arc may appear
fiddly to some people.  Degrees would do, but then the examples would
become a bit fuzzy.

I would probably use times of day.  For example, my cheap "off-peak"
electricity is from 22:00 to 00:30 and from 02:30 to 7:30 but there are
all sorts possible examples: times of day when I do not want to be
disturbed, times when particular parking rules apply and so on.

The problem would then be to determine, given a time of day (in minutes
past midnight), if that time is within a particular period.

I don't think it's a spoiler to give, first, a very concrete example,
even including the function interface.  A second part of the question
would be by ask about generalising this interface to any "circular"
measure.

So I don't think it would matter to help DAK by giving

  with Ada.Text_IO;
  use Ada.Text_IO;

  procedure Longitude is

     function Flight_East_Crosses_Longitude
       (Start_Seconds, End_Seconds, Longitude : Integer) return Boolean is
     begin
        -- Your code here
     end Flight_East_Crosses_Longitude;

     Beijing     : constant Integer := ((+116 * 60) + 23) * 60 +  0;
     Los_Angeles : constant Integer := ((-118 * 60) + 14) * 60 + 37;
     Tokyo       : constant Integer := ((+139 * 60) + 50) * 60 + 32;
     Waikiki     : constant Integer := ((-157 * 60) + 50) * 60 +  4;
     Moscow      : constant Integer := ((+037 * 60) + 37) * 60 +  6;

  begin
     Put_Line(Flight_East_Crosses_Longitude(Beijing, Los_Angeles,   Tokyo)'img);
     Put_Line(Flight_East_Crosses_Longitude(Beijing, Los_Angeles, Waikiki)'img);
     Put_Line(Flight_East_Crosses_Longitude(Beijing, Los_Angeles,  Moscow)'img);
  end Longitude;

Of course, Ada is one of the few languages where one can actually
implement largely type-generic functions, so it's a shame to be this
specific, but as I say, that could come later.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#15971

On 2022-11-26 17:25, Ben Bacarisse wrote:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> 
>> 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.
>>
> So I don't think it would matter to help DAK by giving
> 
>    with Ada.Text_IO;
>    use Ada.Text_IO;
> 
>    procedure Longitude is
> 
>       function Flight_East_Crosses_Longitude
>         (Start_Seconds, End_Seconds, Longitude : Integer) return Boolean is
>       begin
>          -- Your code here
>       end Flight_East_Crosses_Longitude;
> 
>       Beijing     : constant Integer := ((+116 * 60) + 23) * 60 +  0;
>       Los_Angeles : constant Integer := ((-118 * 60) + 14) * 60 + 37;
>       Tokyo       : constant Integer := ((+139 * 60) + 50) * 60 + 32;
>       Waikiki     : constant Integer := ((-157 * 60) + 50) * 60 +  4;
>       Moscow      : constant Integer := ((+037 * 60) + 37) * 60 +  6;
> 
>    begin
>       Put_Line(Flight_East_Crosses_Longitude(Beijing, Los_Angeles,   Tokyo)'img);
>       Put_Line(Flight_East_Crosses_Longitude(Beijing, Los_Angeles, Waikiki)'img);
>       Put_Line(Flight_East_Crosses_Longitude(Beijing, Los_Angeles,  Moscow)'img);
>    end Longitude;
> 
> Of course, Ada is one of the few languages where one can actually
> implement largely type-generic functions, so it's a shame to be this
> specific, but as I say, that could come later.

Here is an implementation based on an integer type. Usually one would 
deploy a fixed-point type instead, but I don't want to mud the details. 
Also a ring buffer would use a modular type, but then it must start at 
0, and here we start at -180 * 3600 seconds.
--------------------------------------------------
with Ada.Text_IO;  use Ada.Text_IO;

procedure Test_Longtitude is
--
-- Longtitude in seconds
--
    type Longtitude is range -180 * 3600 .. 180 * 3600 - 1;

    type Degree is range -180..180;
    type Minute is range 0..59;
    type Second is range 0..59;

    function Compose (D : Degree; M : Minute; S : Second)
       return Longtitude is
       Result : constant Integer :=
                   (Integer (D) * 60 + Integer (M)) * 60 + Integer (S);
    begin
       if Result <= Integer (Longtitude'Last) then
          return Longtitude (Result);
       else
          return Longtitude (Result - 360 * 3600);
       end if;
    end Compose;

    Beijing     : constant Longtitude := Compose (+116, 23,  0);
    Los_Angeles : constant Longtitude := Compose (-118, 14, 37);
    Denver      : constant Longtitude := Compose (-104, 59, 30);
    New_York    : constant Longtitude := Compose ( -73, 56,  7);
    Tokyo       : constant Longtitude := Compose (+139, 50, 32);
    Waikiki     : constant Longtitude := Compose (-157, 50,  4);
    Moscow      : constant Longtitude := Compose (+037, 37,  6);

    function Flight_East_Crosses_Longitude
             (  Start, Stop, X : Longtitude
             )  return Boolean is
    begin
       if Start <= Stop then
          return X in Start..Stop;
       else
          return X <= Stop or else X >= Start;
       end if;
    end Flight_East_Crosses_Longitude;
begin
    Put_Line
    (  "Los_Angeles to New_York    over Denver  "
    &  Flight_East_Crosses_Longitude (Los_Angeles, New_York, Denver)'Image
    );
    Put_Line
    (  "Los_Angeles to New_York    over Moscow  "
    &  Flight_East_Crosses_Longitude (Los_Angeles, New_York, Moscow)'Image
    );
    Put_Line
    (  "Beijing     to Los_Angeles over Tokyo   "
    &  Flight_East_Crosses_Longitude (Beijing, Los_Angeles, Tokyo)'Image
    );
    Put_Line
    (  "Beijing     to Los_Angeles over Waikiki "
    &  Flight_East_Crosses_Longitude (Beijing, Los_Angeles, Waikiki)'Image
    );
    Put_Line
    (  "Beijing     to Los_Angeles over Moscow  "
    &  Flight_East_Crosses_Longitude (Beijing, Los_Angeles, Moscow)'Image
    );
end Test_Longtitude;
------------------------------

It should print:

Los_Angeles to New_York    over Denver  TRUE
Los_Angeles to New_York    over Moscow  FALSE
Beijing     to Los_Angeles over Tokyo   TRUE
Beijing     to Los_Angeles over Waikiki TRUE
Beijing     to Los_Angeles over Moscow  FALSE


-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#15974

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 2022-11-26 17:25, Ben Bacarisse wrote:
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>> 
>>> 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.
<cut my outline>

> Here is an implementation based on an integer type. Usually one would
> deploy a fixed-point type instead, but I don't want to mud the
> details.

The original question was posed in terms of an arbitrary ordered type so
I don't think that would have muddied the waters at all.

> Also a ring buffer would use a modular type, but then it must start at
> 0, and here we start at -180 * 3600 seconds.

I don't know enough Ada to know how generic it can be made in that
language, but the Haskell version requires only that the type has an
ordering.  I think that can also be expressed (messily) in recent C++
with template type constraints.

> --------------------------------------------------
> with Ada.Text_IO;  use Ada.Text_IO;
>
> procedure Test_Longtitude is
> --
> -- Longtitude in seconds
> --
>    type Longtitude is range -180 * 3600 .. 180 * 3600 - 1;
>
>    type Degree is range -180..180;
>    type Minute is range 0..59;
>    type Second is range 0..59;
>
>    function Compose (D : Degree; M : Minute; S : Second)
>       return Longtitude is
>       Result : constant Integer :=
>                   (Integer (D) * 60 + Integer (M)) * 60 + Integer (S);
>    begin
>       if Result <= Integer (Longtitude'Last) then
>          return Longtitude (Result);
>       else
>          return Longtitude (Result - 360 * 3600);
>       end if;
>    end Compose;
>
>    Beijing     : constant Longtitude := Compose (+116, 23,  0);
>    Los_Angeles : constant Longtitude := Compose (-118, 14, 37);
>    Denver      : constant Longtitude := Compose (-104, 59, 30);
>    New_York    : constant Longtitude := Compose ( -73, 56,  7);
>    Tokyo       : constant Longtitude := Compose (+139, 50, 32);
>    Waikiki     : constant Longtitude := Compose (-157, 50,  4);
>    Moscow      : constant Longtitude := Compose (+037, 37,  6);
>
>    function Flight_East_Crosses_Longitude
>             (  Start, Stop, X : Longtitude
>             )  return Boolean is
>    begin
>       if Start <= Stop then
>          return X in Start..Stop;
>       else
>          return X <= Stop or else X >= Start;
>       end if;
>    end Flight_East_Crosses_Longitude;

Except for some boundary cases that have got lost in the telling, this
is similar to Tim's solution.  I chose to use a recursive call, because
I though it explained the non-trivial case more clearly (but I bet I am
pretty much the only one who thinks that).

[The boundary cases of the original problem were that the region was half
open: [start, end) so (in the specific case here)

  Flight_East_Crosses_Longitude(X, X, X)

would be FALSE, and for any Y /= X

  Flight_East_Crosses_Longitude(X, Y, X)
  Flight_East_Crosses_Longitude(X, Y, Y)

would be TRUE and FALSE respectively.]


Tim's description was intended to clarify the problem, but it did not do
so for you.  How, in your opinion, could the question be posed (ideally
in the general form) so that it can be readily understood?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#15975

On 2022-11-27 03:03, Ben Bacarisse wrote:
> Except for some boundary cases that have got lost in the telling, this
> is similar to Tim's solution.  I chose to use a recursive call, because
> I though it explained the non-trivial case more clearly (but I bet I am
> pretty much the only one who thinks that).
> 
> [The boundary cases of the original problem were that the region was half
> open: [start, end) so (in the specific case here)
> 
>    Flight_East_Crosses_Longitude(X, X, X)
> 
> would be FALSE, and for any Y /= X
> 
>    Flight_East_Crosses_Longitude(X, Y, X)
>    Flight_East_Crosses_Longitude(X, Y, Y)
> 
> would be TRUE and FALSE respectively.]
> 
> 
> Tim's description was intended to clarify the problem, but it did not do
> so for you.  How, in your opinion, could the question be posed (ideally
> in the general form) so that it can be readily understood?

It depends on the background. E.g.

    implement tests on directed intervals in a ring of modulo K

Is that readily understood? I don't know. Intervals in a ring are 
ambiguous. One needs to disambiguate, e.g. by introducing a direction.

In practical cases rings represent some measurement process gone skewed 
due to wrapping, like longitude or an RT counter etc. You somehow need 
to restore the original contiguous value, e.g. when comparing them. It 
is sometimes impossible to do. I remember a nasty controller designed in 
a way that the order of messages in its buffer was impossible to restore.

For example, by using unrolling. Consider interval [I1, I2] in a ring of K.

    if I1 > I2 then
       I2 := I2 + K; -- Unroll, now I1 <= I2
    end if;

here we assume I1 > I2 indicates one single wrap happened. If multiple 
did, we are lost. (This is how you lose data/get garbage in I/O on data 
overrun)

Now the inclusion test must take into account unrolled x:

    x in [I1, I2] or else x + K in [I1, I2]

Graphically:
                K
    |###    ####| -->      2K
    |###    #######    ####|
      |          |
      x         x+K

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#16018

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

[...]

>>    function Flight_East_Crosses_Longitude
>>             (  Start, Stop, X : Longtitude
>>             )  return Boolean is
>>    begin
>>       if Start <= Stop then
>>          return X in Start..Stop;
>>       else
>>          return X <= Stop or else X >= Start;
>>       end if;
>>    end Flight_East_Crosses_Longitude;
>
> Except for some boundary cases [ie, the region being half open] that
> have got lost in the telling, this is similar to Tim's solution.  I
> chose to use a recursive call, because I though it explained the
> non-trivial case more clearly (but I bet I am pretty much the only
> one who thinks that).

I want to add something here to my earlier comment.  The idea of
using a recursive call reflects a deeper understanding of what
"circular regions" are.  If one has already assimilated that
understanding then I think the recursive call is "more obvious",
in the sense that it takes less thought, or I might say less
additional thought.  I didn't have that background (and didn't
develop it while solving the problem) so for me the cruder but
more direct approach was easier to see.  Bottom line, I don't
think either formulation is uniformly "easier to understand" than
the other;  it depends on one's background (or ability to develop
a suitable understanding on the fly, which in this case I did not
possess).

This problem provides an example where it helps to see both
approaches to solving the problem, to see how they relate to each
other, but also to give an appreciation for the power of having
more advanced tools available in the mental toolbox.

[toc] | [prev] | [next] | [standalone]

#16022

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
> [...]
>
>>>    function Flight_East_Crosses_Longitude
>>>             (  Start, Stop, X : Longtitude
>>>             )  return Boolean is
>>>    begin
>>>       if Start <= Stop then
>>>          return X in Start..Stop;
>>>       else
>>>          return X <= Stop or else X >= Start;
>>>       end if;
>>>    end Flight_East_Crosses_Longitude;
>>
>> Except for some boundary cases [ie, the region being half open] that
>> have got lost in the telling, this is similar to Tim's solution.  I
>> chose to use a recursive call, because I though it explained the
>> non-trivial case more clearly (but I bet I am pretty much the only
>> one who thinks that).
>
> I want to add something here to my earlier comment.  The idea of
> using a recursive call reflects a deeper understanding of what
> "circular regions" are.  If one has already assimilated that
> understanding then I think the recursive call is "more obvious",
> in the sense that it takes less thought, or I might say less
> additional thought.  I didn't have that background (and didn't
> develop it while solving the problem) so for me the cruder but
> more direct approach was easier to see.  Bottom line, I don't
> think either formulation is uniformly "easier to understand" than
> the other;  it depends on one's background (or ability to develop
> a suitable understanding on the fly, which in this case I did not
> possess).

For me, the negated recursive call was a sort of "ah ha!" moment.  I was
ploughing forwards trying to work out this and that case when a
light-bulb went off.

Above I say "it explained the non-trivial case more clearly" but that's
lazy wording and does not capture what I meant.  Rather than explaining
anything, I want code that is easy to verify.  I want, with just a
little thought, to know it's right.

> This problem provides an example where it helps to see both
> approaches to solving the problem, to see how they relate to each
> other, but also to give an appreciation for the power of having
> more advanced tools available in the mental toolbox.

I've got rather fond of it as a question.  I don't conduct any
interviews anymore or I would be tempted to use it.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#16026

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

For reference here is my earlier answer [with return type changed
to 'bool']:

    bool
    is_circularly_between( T a, T b, T c ){
        return  a <= c    ?  a <= b  &&  b < c    :  a <= b  ||  b < c;
    }

>>> [In contrast to the definition above]  I
>>> chose to use a recursive call, because I though it explained the
>>> non-trivial case more clearly (but I bet I am pretty much the only
>>> one who thinks that).
>>
>> I want to add something here to my earlier comment.  The idea of
>> using a recursive call reflects a deeper understanding of what
>> "circular regions" are.  If one has already assimilated that
>> understanding then I think the recursive call is "more obvious",
>> in the sense that it takes less thought, or I might say less
>> additional thought.  I didn't have that background (and didn't
>> develop it while solving the problem) so for me the cruder but
>> more direct approach was easier to see.  Bottom line, I don't
>> think either formulation is uniformly "easier to understand" than
>> the other;  it depends on one's background (or ability to develop
>> a suitable understanding on the fly, which in this case I did not
>> possess).
>
> For me, the negated recursive call was a sort of "ah ha!" moment.  I
> was ploughing forwards trying to work out this and that case when a
> light-bulb went off.

For reference here is your recursive version:

  bool is_circularly_between(T start, T end, T i) {
      return start <= end ? start <= i && i < end
                          : !is_circularly_between(end, start, i);
  }

> Above I say "it explained the non-trivial case more clearly" but
> that's lazy wording and does not capture what I meant.  Rather than
> explaining anything, I want code that is easy to verify.  I want,
> with just a little thought, to know it's right.

Even after understanding the "ah ha!", I am still not entirely happy
with this version.  Even though I know the trick, there is still a
mental slowdown around the negated recursive call.  I can see that
it works, but it takes a little bit of mental effort each time.

Thinking a little more about how to write an answer, I came up with
this:

    extern  bool is_circularly_between( T, T, T );
    extern  bool is_circularly_outside( T, T, T );

    bool
    is_circularly_between( T start, T limit, T x ){
        if(  start <= limit  )  return  start <= x  &&  x < limit;

        return  is_circularly_outside( limit, start, x );
    }

    bool
    is_circularly_outside( T start, T limit, T x ){
        if(  start <= limit  )  return  x < start  ||  limit <= x;

        return  is_circularly_between( limit, start, x );
    }

For me this version is mentally smoother than the negated directly
recursive call.  Part of the reason for that is having the two
complementary functions shows the duality more explicitly.  Of
course I never would have gotten here if not for your insight;  even
so, I'm inclined to prefer this version on the metric of which is
easier to convince myself that it's right.


>> This problem provides an example where it helps to see both
>> approaches to solving the problem, to see how they relate to each
>> other, but also to give an appreciation for the power of having
>> more advanced tools available in the mental toolbox.
>
> I've got rather fond of it as a question.  I don't conduct any
> interviews anymore or I would be tempted to use it.

It's a great question.  I'm glad you posted it.

[toc] | [prev] | [next] | [standalone]

#16027

On Saturday, 3 December 2022 at 07:30:46 UTC+1, Tim Rentsch wrote:
> Ben Bacarisse <ben.u...@bsb.me.uk> writes: 
<snip>
> For reference here is my earlier answer [with return type changed 
> to 'bool']: 
> 
> bool
> is_circularly_between( T a, T b, T c ){
> return a <= c ? a <= b && b < c : a <= b || b < c;
> }

What mental gymnastics?  To begin with, that is just
a pain to read with those variables names plus their
unconventional order.  Written slightly better, that is:

bool is_circularly_between(T x, T lo, T hi){
  return lo <= hi ? lo <= x && x < hi : lo <= x || x < hi;
}

That said, circular over what exactly?  Namely, define
constructors for T: how is someone, starting from the
usual machine types, supposed to get to calling your
function?  (Try and see what you cannot but end up
with: there are only two options...)

Julio

[toc] | [prev] | [next] | [standalone]

#15977

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> 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.
>
> I think so.  I am, to be honest, rather disappointed by the
> reception this problem has had.  Even after various examples and
> two explanations, some posters still don't know what's being
> asked, but at the time it is claimed that it's trivial and not
> worth coding up.  Sometimes both claims are made by the same
> poster.

I am somewhat baffled by the replies.  I thought what was being
sought was evident in your initial posting.  Perhaps not obvious,
but still clear enough after a bit of thought.

>> 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.
>
> I think this is good, though the example with seconds of arc may
> appear fiddly to some people.  Degrees would do, but then the
> examples would become a bit fuzzy.

I agree on both points.  I didn't like the fiddly-ness, but no
better example came to mind.

> I would probably use times of day.  For example, my cheap
> "off-peak" electricity is from 22:00 to 00:30 and from 02:30 to
> 7:30 but there are all sorts possible examples:  times of day when
> I do not want to be disturbed, times when particular parking rules
> apply and so on.

I was looking for a circular measure that is widely known and also
has some negative values.  Longitude was the best I could think of.

> The problem would then be to determine, given a time of day (in
> minutes past midnight), if that time is within a particular
> period.

Hours of the day, especially on a 24-hour clock, is probably better
than longitude for the initial example. 

> I don't think it's a spoiler to give, first, a very concrete
> example, even including the function interface.  A second part of
> the question would be by ask about generalising this interface to
> any "circular" measure.

I was trying to be faithful (what I thought was) your not wanting
to give away the simplicity of a general solution.  I can't
decide if your example below gives away too much or might be
slightly misleading (because the modulus is inherent in the
measure).  It's hard to find a phrasing that is both specific
enough to clearly state what is being sought and also not so
specific that it gives away the nature of the problem.  I was
trying to strike a balance point, apparently not quite balanced
enough.  :)

> So I don't think it would matter to help DAK by giving
>
>   with Ada.Text_IO;
>   use Ada.Text_IO;
>
>   procedure Longitude is
>
>      function Flight_East_Crosses_Longitude
>        (Start_Seconds, End_Seconds, Longitude : Integer) return Boolean is
>      begin
>         -- Your code here
>      end Flight_East_Crosses_Longitude;
>
>      Beijing     : constant Integer := ((+116 * 60) + 23) * 60 +  0;
>      Los_Angeles : constant Integer := ((-118 * 60) + 14) * 60 + 37;
>      Tokyo       : constant Integer := ((+139 * 60) + 50) * 60 + 32;
>      Waikiki     : constant Integer := ((-157 * 60) + 50) * 60 +  4;
>      Moscow      : constant Integer := ((+037 * 60) + 37) * 60 +  6;
>
>   begin
>      Put_Line(
>         Flight_East_Crosses_Longitude(Beijing, Los_Angeles,   Tokyo)'img
>      );
>      Put_Line(
>         Flight_East_Crosses_Longitude(Beijing, Los_Angeles, Waikiki)'img
>      );
>      Put_Line(
>         Flight_East_Crosses_Longitude(Beijing, Los_Angeles,  Moscow)'img
>       );
>   end Longitude;

(I reformatted the calls to Put_Line() so they wouldn't violate
my newsreader's idea of how long lines should be.)

> Of course, Ada is one of the few languages where one can actually
> implement largely type-generic functions, so it's a shame to be
> this specific, but as I say, that could come later.

I can't help feeling that your suggestion of using times of
day -- especially if expressed in 4-digit military time format --
would be a better choice for the example.

[toc] | [prev] | [next] | [standalone]

#15976

On Monday, 21 November 2022 at 21:45:34 UTC+1, 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 don't think much better can be done of the obvious implementation:

```js
function inOpenModRange(x: number, lo: number, hi: number, m: number): boolean {
    let x_ = MOD(x, m);
    let lo_ = MOD(lo, m);
    let hi_ = MOD(hi, m);
    return lo_ <= x_ && x_ < hi_;
}
```

where MOD is modulo, not remainder.

In terms of remainder (as in JS), MOD looks like this:

```js
function MOD(x: number, m: number): number {
    if (x * m === 0) { return 0; }  // allow for MOD(x, 0)
    if (x > 0) { x = x % m; }
    else { x = (m + x % m) % m; }
    return x;
}
```

Beware of bugs.

HTH,

Julio

[toc] | [prev] | [next] | [standalone]

#15978

Julio Di Egidio <julio@diegidio.name> writes:

> On Monday, 21 November 2022 at 21:45:34 UTC+1, 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 don't think much better can be done of the obvious implementation:
>
> ```js
> function inOpenModRange(
>    x: number, lo:  number, hi:  number, m:  number
> ):  boolean {
>     let x_ = MOD(x, m);
>     let lo_ = MOD(lo, m);
>     let hi_ = MOD(hi, m);
>     return lo_ <= x_ && x_ < hi_;
> }
> ```
>
> where MOD is modulo, not remainder.
>
> In terms of remainder (as in JS), MOD looks like this:
>
> ```js
> function MOD(x:  number, m:  number):  number {
>     if (x * m === 0) { return 0; }  // allow for MOD(x, 0)
>     if (x > 0) { x = x % m; }
>     else { x = (m + x % m) % m; }
>     return x;
> }
> ```

This proposed function doesn't work.  Consider a curfew that
starts at 10 pm (2200) and goes until 5 am (0500).  Is 3 am
(0300) a curfew violation?  The call to your function would be

    inOpenModRange( 0300, 2200, 0500, 2400 );

which yields false.  But it should yield true.

[toc] | [prev] | [next] | [standalone]

#15979

On Monday, 28 November 2022 at 04:23:28 UTC+1, Tim Rentsch wrote:
> Julio Di Egidio <ju...@diegidio.name> writes: 
> > On Monday, 21 November 2022 at 21:45:34 UTC+1, 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. 
<snip>

> > In terms of remainder (as in JS), MOD looks like this: 
> > 
> > ```js 

Should have been "ts", i.e. TypeScript (for the few type annotations:
get rid of those to get the plain JS).

> > ```js 
> > function MOD(x: number, m: number): number { 
> > if (x * m === 0) { return 0; } // allow for MOD(x, 0) 

BTW, better not do that multiplication:

```js
    if (m === 0) { return 0; } // allow for m = 0
    if (x === 0) { return 0; }  // a short-cut
```

Moreover, notice that this MOD fails (in particular, does not
return positive) for m <= 0. (!!)  But I won't bother with that now.

> > if (x > 0) { x = x % m; } 
> > else { x = (m + x % m) % m; } 
> > return x; 
> > } 
> > ```
> This proposed function doesn't work. Consider a curfew that 
> starts at 10 pm (2200) and goes until 5 am (0500). Is 3 am 
> (0300) a curfew violation? The call to your function would be 
> 
> inOpenModRange( 0300, 2200, 0500, 2400 ); 
> 
> which yields false. But it should yield true.

Argh!  But you should not have snipped that "beware
of bugs", that was the most important part!!   ;)

This one should do the trick:

```ts
/** Returns whether x in [lo, hi[ (mod m). */
function inOpenModRange(
    x: number, lo: number, hi: number, m: number
): boolean {
    let x_ = MOD(x - lo, m);
    let hi_ = MOD(hi - lo, m);
    return x_ < hi_;
}
```

Still untested, I hope I have not botched it again...

Julio

[toc] | [prev] | [next] | [standalone]

#15980

On Monday, 28 November 2022 at 07:59:31 UTC+1, Julio Di Egidio wrote:

> Moreover, notice that this MOD fails (in particular, does not 
> return positive) for m <= 0. (!!) But I won't bother with that now.

I meant, for m < 0.  You get the point: that I won't get it totally
right here ever...

Julio

[toc] | [prev] | [next] | [standalone]

#15982

Julio Di Egidio <julio@diegidio.name> writes:

> On Monday, 28 November 2022 at 04:23:28 UTC+1, Tim Rentsch wrote:
>
>> Julio Di Egidio <ju...@diegidio.name> writes:

I recommend switching away from google groups, to a posting service
that is more well-behaved.  Try eternal-september.org, which offers
free accounts after registering, if you can't find anything else
more to your liking.

>>> On Monday, 21 November 2022 at 21:45:34 UTC+1, 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.
>
> <snip>
>
>>> In terms of remainder (as in JS), MOD looks like this:
>>>
>>> ```js
>
> Should have been "ts", i.e. TypeScript (for the few type
> annotations:  get rid of those to get the plain JS).
>
>>> ```js
>>> function MOD(x:  number, m:  number):  number {
>>> if (x * m === 0) { return 0; } // allow for MOD(x, 0)
>
> BTW, better not do that multiplication:
>
> ```js
>     if (m === 0) { return 0; } // allow for m = 0
>     if (x === 0) { return 0; }  // a short-cut
> ```
>
> Moreover, notice that this MOD fails (in particular, does not
> return positive) for m <= 0.  (!!)  But I won't bother with that
> now.
>
>>> if (x > 0) { x = x % m; }
>>> else { x = (m + x % m) % m; }
>>> return x;
>>> }
>>> ```
>>
>> This proposed function doesn't work.  Consider a curfew that
>> starts at 10 pm (2200) and goes until 5 am (0500).  Is 3 am
>> (0300) a curfew violation?  The call to your function would be
>>
>> inOpenModRange( 0300, 2200, 0500, 2400 );
>>
>> which yields false.  But it should yield true.
>
> Argh!  But you should not have snipped that "beware
> of bugs", that was the most important part!!   ;)

It's your job to beware of bugs, not mine.

> This one should do the trick:
>
> ```ts
> /** Returns whether x in [lo, hi[ (mod m). */
> function inOpenModRange(
>     x:  number, lo:  number, hi:  number, m:  number
> ): boolean {
>     let x_ = MOD(x - lo, m);
>     let hi_ = MOD(hi - lo, m);
>     return x_ < hi_;
> }
> ```

This scheme looks like it will work, as long as the values given
don't get too near the edges of representation.  JavaScript
represents numeric values using floating point, and that choice
leads to some unexpected results when working with large numbers.

However, this approach is more complicated than it needs to be.
Have you tried looking at the other answers?

[toc] | [prev] | [next] | [standalone]

#15985

On Monday, 28 November 2022 at 16:22:38 UTC+1, Tim Rentsch wrote:
> Julio Di Egidio <ju...@diegidio.name> writes: 
> >>> On Monday, 21 November 2022 at 21:45:34 UTC+1, Ben Bacarisse wrote: 
> 
> > On Monday, 28 November 2022 at 04:23:28 UTC+1, Tim Rentsch wrote: 
> > 
> >> Julio Di Egidio <ju...@diegidio.name> writes:
> 
> I recommend switching away from google groups,

That is your prerogative, I suppose.

> >>>> 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. 

> > Argh! But you should not have snipped that "beware 
> > of bugs", that was the most important part!! ;)
> 
> It's your job to beware of bugs, not mine.

I didn't know you were paying me for production level code:
in that case, I'd have asked for the technical requirements,
not just the functional ones...

IOW, I have have given a mathematical spec written in some
simply-typed functional language, can be functions on the real
numbers.  Which is often step one in functional/algorithmic
design.  Beside that point, one needs technical requirements,
i.e. info on the concrete numeric types available as a minimum.

> > This one should do the trick: 
> > 
> > ```ts 
> > /** Returns whether x in [lo, hi[ (mod m). */ 
> > function inOpenModRange( 
> > x: number, lo: number, hi: number, m: number 
> > ): boolean { 
> > let x_ = MOD(x - lo, m); 
> > let hi_ = MOD(hi - lo, m); 
> > return x_ < hi_; 
> > } 
> > ```
> This scheme looks like it will work, as long as the values given 
> don't get too near the edges of representation. JavaScript 
> represents numeric values using floating point, and that choice 
> leads to some unexpected results when working with large numbers. 
> 
> However, this approach is more complicated than it needs to be. 
> Have you tried looking at the other answers?

That is complicated??  Maybe I haven't looked well enough
but, honestly, I have not seen anything that is even vaguely as
clear, and efficient, and to the point.  Have I missed it?

Julio

[toc] | [prev] | [next] | [standalone]

Page 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

Back to top | Article view | comp.programming

csiph-web