Title: Challenges

Author: Bob Schmidt

Date: 02 May 2019 23:21:01 +01:00 or Thu, 02 May 2019 23:21:01 +01:00

Summary: Francis Glassborow revisits old challenges and sets a new one.

Body: 

I am under a good deal of time pressure as I write this column. I got back from the ACCU Conference 2019. That was a great event and I was delighted by the number of first time attendees. It was also great to see that we are beginning to achieve more diversity in attendance and participation.

If you are not already familiar with #include<C++> please take a few minutes to read about it at www.includecpp.org. I think that it is important.

Do you know what the Pac-Man Rule is? If not, look it up on the internet using your search engine of choice. (Note that we should not call that ‘googling’ just as we no longer call using a vacuum cleaner ‘hoovering’. We should avoid referring to a generic activity by deriving a verb from a proprietary name.) When you have found out what the Pac-Man Rule is, consider using it, not just at conferences but at all gatherings (weddings, funerals, etc.).

OK, so returning from the conference left me with work to do on the allotment (surprising how quickly the grass grows) and the house, where I’m in the middle of laying new wooden floors upstairs, requiring tedious moving of furniture, piles of books, etc. (The actual process of laying engineered wooden floors is pretty straightforward – well, it is if you have all the right tools, such as a saw table, spacers, etc.) But now, just five days later, I am off to Eastercon for the whole of the Bank Holiday weekend, Friday to Monday inclusive.

Then your editor emailed me that he was using this weekend to put together the issue of C Vu you are reading. Well, I know what it is like to be an editor and how precious contributions are. So here I am throwing together a column without the time to polish it.

Time to get started.

Challenge 5 revisited

Don’t you just love it when a spam filter blocks an email that has valuable content? (As I wrote that I reflected on English abbreviations, concatenations etc. Try replacing ‘don’t’ with ‘do not’ and you will see what I mean.)

Sadly, a spam filter somewhere prevented me from seeing an excellent entry from Silas Brown. Every time I get something from Silas, I am reminded that he was the youngest ever contributor to C Vu. Somewhere over the years ACCU has lost touch with the youthful enthusiasts among whom are the future contributors to the developer community. I think it is time for members to try to involve themselves in ‘Code Club’ not just by helping in a local school but by actively encouraging the young to tell us about what they are coding. (Steve, do you think we could set aside a regular column about Code Club with space for contributions from young coders?) [Ed. Yes, I think it’s a great idea. If anyone has any suggestions for starting this, please get in touch!]

Well here is Silas’ excellent response to Challenge 5.

From Silas Brown

Dear Francis,

I’m sorry to read in C Vu 30.6 that you received only one partial submission for Challenge 5 and the submitter was silent after you gave a further hint. I’m now suspecting that spam filters are working against us. I sent a submission (copy below) on 17th September, and I did not hear back from you. So if you received one submission and sent one hint, then either my submission was lost on its way to you, or, if mine was the one you received and responded to with a hint, then your hint was lost on its way back to me.

Neither possibility is very comfortable to consider, as I begin to wonder if the filters responsible for this are also blocking other submissions. I am therefore CC’ing this message to cvu@accu.org as if the worst comes to the worst, printing it may be the only way to reach you! Please check your filter settings to make sure you can receive submissions. It might also help if every episode of your Challenge series were to clearly mention where submissions should be sent. Many thanks.

[Francis: I think it is probably wise to copy all submissions to cvu@accu.org as well as to the columnist, in my case francis.glassborow@btinternet.com, so that there are at least two chances of beating the filters.]

Here is what I sent:

I am not sure we need 7 operators. If we choose 6: = - / < ^ & we can get what is (I think) all of the C++ operators that are capable of being overloaded in static functions, although I had to cheat a bit for 3 of them (I commented where I cheated in the code below), so if you want you can replace one of the three ‘cheats’ with its real operator to choose a 7th.

template<typename T> T operator+(T t1, T t2)
{ return t1 - (0 - t2); }
/* This was given in the challenge, so I assume 
   T is numeric, not a string etc. */
template<typename T> T operator+(T t)
{ return t; }
template<typename T> T operator-(T t)
{ return 0 - t; }
template<typename T> T operator*(T t1, T t2)
{ return t1 / (1 / t2); }
template<typename T> T operator%(T t1, T t2)
/* cheat: this works only if T is an integer type */
{ return t1 - (t1 / t2) * t2;
template<typename T> T operator+=(T &t1, T t2)
{ t1 = t1 + t2; return t1; }
template<typename T> T operator-=(T &t1, T t2)
{ t1 = t1 - t2; return t1; }
template<typename T> T operator*=(T &t1, T t2)
{ t1 = t1 * t2; return t1; }
template<typename T> T operator/=(T &t1, T t2)
{ t1 = t1 / t2; return t1; }
template<typename T> T operator%=(T &t1, T t2)
{ t1 = t1 % t2; return t1; }
template<typename T> T operator++(T & t1) 
/* prefix */
{ return (t1 = t1 + 1); }
template<typename T> T operator++(T & t1, int)
/* postfix */
{ T t0 = t1; t1 = t1 + 1; return t0; }
template<typename T> T operator--(T & t1)
{ return (t1 = t1 - 1); }
template<typename T> T operator--(T & t1, int)
{ T t0 = t1; t1 = t1 - 1; return t0; }
template<typename T> bool operator!(T t)
{ if(t) return false; else return true; }
template<typename T,typename U> bool 
  operator&&(T t,U u)
/* cheat: this won't lazily-evaluate u */
 { if(t) { if(u) return true; } return false; }
template<typename T,typename U> bool 
  operator||(T t,U u)
/* cheat: this won't lazily-evaluate u */
{ if(t) return true; if(u) return true; 
  return false; }
template<typename T> bool operator>(T t1, T t2)
{ return t2 < t1; }
template<typename T> bool operator!=(T t1, T t2)
{ return t1 < t2 || t1 > t2; }
template<typename T> bool operator==(T t1, T t2)
{ return !(t1 == t2); }
template<typename T> bool operator<=(T t1, T t2)
{ return t1 < t2 || t1 == t2; }
template<typename T> bool operator>=(T t1, T t2)
{ return t1 > t2 || t1 == t2; }
template<typename T> bool operator~(T t)
{ return t ^ (T)-1; }
template<typename T> bool operator|(T t1, T t2)
{ return t1 ^ t2 ^ (t1 & t2); }
template<typename T> T operator&=(T &t1, T t2)
{ t1 = t1 & t2; return t1; }
template<typename T> T operator|=(T &t1, T t2)
{ t1 = t1 | t2; return t1; }
template<typename T> T operator^=(T &t1, T t2)
{ t1 = t1 ^ t2; return t1; }
template<typename T,typename U> T 
  operator<<(T t, U u)
{ while(u--) t*=2; return t; }
template<typename T,typename U> T 
  operator>>(T t, U u)
{ while(u--) t/=2; return t; }
template<typename T,typename U> T 
  operator<<=(T & t, U u)
{ t = t << u; return t; }
template<typename T,typename U> T 
  operator>>=(T & t, U u)
{ t = t >> u; return t; }
template<typename T,typename U> U 
  operator,(T t, U u)
{ return u; }

I would have liked to add something like:

  template<typename T> T operator=(T &t1, T t2)
  { t1(t2); return t1; }

but this won’t compile: an overloaded = must be a nonstatic member function of T, which means you can’t just template it across all types like that. If the above were legal, it would work only for types where construction is equivalent to assignment, but I’m assuming that’s the case for numeric types and it would buy us one more operator.

new and delete are operators too, but overriding them will require some serious low-level work. And overriding the [] operator must also be done as a nonstatic member function (for good reason: we cannot assume t[u] is always equivalent to *(t+u) when we’re dealing with non-array containers.) And the ?: operator cannot be overloaded so it shouldn’t count.

Francis responds...

Thanks. You have surfaced a number of issues that I had not considered. The case of lazy evaluation is interesting because there is currently no way that a programmer can write functions that involve lazy evaluation. Indeed, it is worse than that because we do not (or has the language changed somewhere in the last few years?) even control the order of evaluation of arguments in a call to a function with more than one parameter.

C++ is relatively free of the core language doing things that cannot be done by libraries. The lazy evaluation case is notable because those operators can be overloaded but cannot emulate the built-in version.

Anyone like to highlight other places that the core language does things that cannot be emulated by libraries?

Challenge 6

From James Holland

For this challenge, I can do no better than to reproduce the work of the rector and mathematician Christian Zeller (1822–99) to calculate the day of the week from a given year, month and day of the month. By the time some output formatting has been added, the program is not all that short but it may be of some interest. The code for the Gregorian calendar follows.

#include <iostream>
#include <string>
std::string dow(int y, unsigned int m, 
  unsigned int d)
{
  if (m == 1)
  {
    m = 13;
    --y;
  }
  else
  if (m == 2)
  {
    m = 14;
    --y;
  }
  const auto h = (d + (13 * (m + 1)) / 5 + y + y /
    4 - y / 100 + y / 400) % 7;
  std::string day;
  switch (h)
  {
  case 0:
    day = "Saturday";
    break;
  case 1:
    day = "Sunday";
    break;
  case 2:
    day = "Monday";
    break;
  case 3:
    day = "Tuesday";
    break;
  case 4:
    day = "Wednesday";
    break;
  case 5:
    day = "Thursday";
    break;
  case 6:
    day = "Friday";
    break;
  }
  return day;
}
int main()
{
  std::cout << dow(2019, 3, 27) << '\n';
}

Francis responds...

Thanks, James. We can quickly reduce the size of that function with a look-up table of days of the week (which, has the potential for being populated from an external source and so make it transportable to other languages.

The second problem is that it only works for the Gregorian calendar and needs substantial reworking for other calendars, in particular the Julian calendar.

Let me outline the solution of my pupil.

The first thing he did was to substitute much calculation with look-up tables. In C++ terms:

1. A 2-dimensional 2 × 12 array of month names, the first row consisted of the first 3 letters of each month in lower case. The second row were the numbers 1 through 12 as strings.
2. An array of weekday names, fully spelt with leading letter in uppercase, starting with Sunday. You will see that this works well for zero-based array indices as 01/01/01was a Monday.
3. A 2-dimensional 2 × 13 array of offsets from the first day of the year for first of each month (so the entries for January were 0, for February were 31, for March were 59 and 60. And from then onwards the second row were one more than for the first row. The 13th entry was either 365 or 366.

The next process was to acquire input and validate it. To avoid problems with different date formats, he explicitly asked for

1. The year
2. The month
3. The day of the month

The first of these simply had to be a positive integer (i.e. greater than 0).

The second was read as a string that was converted to lower case and if there were more than 2 char it was truncated to 3 char. Then the first row of the month array was searched for a match. The value of the index for a match was stored in an int. If there were less than 3 char the second row was searched and a match was similarly stored as an int.

If no match was found, the user would be informed that the month was invalid and prompted again. Up to three attempts were allowed before the program politely informed the user that it was unable to help.

The day of the month was checked to be in range for the relevant month (note that the third look-up table above can be used as month+1 - month gives the number of days in the current month). February 29 was provisionally accepted for any year that was a multiple of 4.

The Julian leap day calculation was next performed as (year- year%100)

At this point, the user was prompted as to whether they wished to use the Gregorian calendar. If the answer was yes, the leap day calculation was adjusted by adding year%400.

Final preparation was to revisit the case of February 29 and reject it if the year was a multiple of 100 (Julian) or a multiple of 100 but not 400 (Gregorian).

Now the weekday array was used with an index computed as:

  (day+days_offset[month, leap] +
     number of leap days)%7

As I mentioned earlier, the use of look-up tables that could be populated from a configuration file made the final program independent of English names for months and weekdays. That was a particular telling point with examiners who appreciated this attempt at internationalisation (which the moderators had not).

My apologies that this is only an outline, but I am out of time and you all know how much time it takes to write good, correct code.

Challenge 7

How many actual characters from the source code character set are actually necessary to write C programs? C++ programs? As a little hint, I once came across a Cobol programmer who feared for his continued employment and started using only ‘O’, ‘0’, ‘I’ and ‘1’ for identifiers in his code. The theory being that they would need to keep employing him as he would be the only person who could maintain his code. As you might guess, it was a self-fulfilling strategy as his employers quickly removed him before he had actually written much.

Appeal

Do you have a problem that could serve as a challenge? Good challenges should require a degree of lateral thinking, not too much coding and reveal some aspect of programming that we easily miss (for example, the problem of lazy evaluation mentioned above). They do not have to be C or C++ based but unless it is Forth, Basic, Old Fortran or Snobol, my commentary on responses will be minimal. I once spent a lot of time trying to master Lisp but never succeeded to the extent that made me a Lisp programmer, just a procedural programmer expressing procedural code in Lisp (horrible ☺).

Francis Glassborow Since retiring from teaching, Francis has edited C Vu, founded the ACCU conference and represented BSI at the C and C++ ISO committees. He is the author of two books: You Can Do It! and You Can Program in C++.

Notes: 

More fields may be available via dynamicdata ..