Title: Challenge 4 Report & Outlining Challenge 5

Author: Bob Schmidt

Date: 02 September 2018 18:16:03 +01:00 or Sun, 02 September 2018 18:16:03 +01:00

Summary: Francis Glassborow presents the responses to the challenge from last time and outlines the next one.

Body: 

The challenge from the last C Vu was to write a program that outputs the numbers from 1 to 100 without using if, for, switch, or while. I forgot to exclude the ternary operator. However, considerable ingenuity was exhibited by all. To save space and repetition, I have omitted solutions using the ternary operator unless they have some other ingenuity.

Before I get on with the submissions, here is an idea for a C++ solution which has not been used in any of the (often very ingenious) solutions.

Use a class constructor:

  struct challenge4 {
   static int counter =0;
   static int incr;
   challenge4(){
     cout << counter << \n;
     counter += incr;
  };

Now you can set the counter to the start value and create a vector of (end-start -1) to output the numbers from start to end. The value passed to incr can be calculated with:

  Challenge4::incr =(end-start)/abs(end-start);

Or using signbit():

  int direction[] = {-1, 1}
  challenge4::incr = direction[signbit(start-end)]

Now executing something like

  vector<Challenge4> c4(abs(end-start -1);

I leave it as an exercise for the reader to take those ideas into a working program. You will need to ensure you understand how exactly how C++ initialises containers to get this right as I have deliberately written buggy code snippets. For some of you, the faults will stand out immediately; but some of you may not be quite so familiar with the finer details and have to think or even look up details in your reference sources.

Now to the readers efforts.

From Silas S. Brown

Francis: Sometimes the path from a first cut to the final solution is instructive.

I was sorry to read about the lack of response to Challenge 3.

I knew those things were called ‘quines’ and thought plenty of members would look up how to make them, but it’s easy to forget that not everyone knows such things.

For challenge 4 (outputting numbers first to last without using if, for, switch or while), a very dirty way in C is simply to use goto and the ?: operator:

  #include <stdio.h>
  #include <stdlib.h>
  enum { first=1, last=100 };
  int main() {
    int c = first;
  loop:
    printf("%d\n", c);
    (c==last) ? exit(0) : 0;
    c += (last >= first) ? 1 : -1;
    goto loop;
  }

The fact that exit(), a function with side effects, can be included in a ?: expression means we can terminate without an if. Of course, this won’t do if we additionally say that the function is to be included in a larger program and should therefore return to its caller rather than calling exit(). But there’s another standard function (thankfully little used) which can transfer control back to the caller: longjmp. Here’s the longjmp version (and for variety let’s do it via recursion rather than a goto) :

  #include <stdio.h>
  #include <setjmp.h>
  enum { first=1, last=100 };
  int loop(int c, jmp_buf e) {
    printf("%d\n", c);
    (c==last) ? longjmp(e,1) : 0;
    loop (c + ((last >= first) ? 1 : -1), e);
  }
  int main() {
    jmp_buf e;
    setjmp(e) ? 0 : loop(first, e);
  }

What if we additionally ban the ?: operator? In that case we can rewrite our loop function like this:

  int finished(jmp_buf e) {
    longjmp(e,1);
  }
  int loop(int c, jmp_buf e) {
    printf("%d\n", c);
    c==last && finished(e);
    loop (c + (last >= first) - (last < first), e);
  }

It’s necessary to put the longjmp in a different function because it returns void, so the compiler won’t allow us just to say c==last && longjmp(e,1); and the same goes for exit().

And if we also ban the use of longjmp, we can instead write it like this:

  #include <stdio.h>
  enum { first=1, last=100 };
  int loop(int c) {
    printf("%d\n", c);
    c != last && loop (c + (last > c) - 
      (last < c));
  }
  int main() { loop(first); }

which, come to think of it, is probably what I should have written to begin with.

Francis: But the scenic tour is illuminating.

From James Holland

Francis: This one explores various C++ solutions showing considerable ingenuity but misses the ‘aha’ of populating a container using a type with suitable constructors.

Francis’s challenge deprives us of most flow control constructs. There are, however, one or two left that could still be used. As Francis implies, the challenge is probably easier to solve using C++ rather than C. My first attempt employs the conditional expression (?:) and recursion as shown below.

  #include <iostream>
  void increment(int amount, int value, int last)
  {
    std::cout << value << ' ';
    value - last ? increment(amount, 
      value + amount, last) : static_cast<void>(0);
  }

  int main(int argc, const char * argv[])
  {
    const int first = std::stoi(argv[1]);
    const int last = std::stoi(argv[2]);
    increment(first > last ? -1 : 1, first, last);
    std::cout << '\n';
  }

This solution prints the number in the correct order (beginning with first) and copes with negative values of first and last. It would be better, however, not to use a conditional expression if possible. Another feature of C++ that controls program flow is exceptions. If exceptions are to be used, something needs to be found that generates an exception when supplied with a value that signifies the task of printing the numbers is complete. It would be helpful if such an object was part of the standard library. There are probably several such objects. The one I have chosen is std::bitset as it has a member function that throws an exception when the value of its parameter is not an index of one of its bits. I have used this feature in the code below.

  #include <bitset>
  #include <iostream>
  void increment(int amount, int value, int last)
  {
    std::cout << value << ' ';
    std::bitset<1> bs;
    try
    {
      bs.reset(value - last);
    }
    catch (...)
    {
      increment(amount, value + amount, last);
    }
  }

  int main(int argc, const char * argv[])
  {
    const int first = std::stoi(argv[1]);
    const int last = std::stoi(argv[2]);
    const int amount = 1 - 2 * (first > last);
    increment(amount, first, last);
    std::cout << '\n';
  }

The std::bitset object bs contains just one bit and, therefore, has an index of zero. While the sequence is being written, value - last will not be a valid index and so bs will throw an exception. The exception is immediately caught causing increment() to be called recursively. Just after the last number is printed, value - last will equal 0. This is a valid index of bs. No exception is thrown and increment() recursively returns to main() where, after a final line-feed, the program terminates.

Also in the above program, instead of using the conditional expression to determine the value (1 or -1) by which the sequence should increment, I have constructed a little formula to do the job. Firstly, (first > last) is implicitly converted to 1 if first is greater than last, 0 otherwise. Multiplying this value by -2 gives -2 and 0 for the two conditions. Finally, adding 1 gives 1 or -1 as required.

The std::bitset technique can also be used to iterate instead of recurse as shown below.

  #include <bitset>
  #include <iostream>

  int main(int argc, const char * argv[])
  {
    const int first = std::stoi(argv[1]);
    const int last = std::stoi(argv[2]);
    const int amount = 1 - 2 * (first > last);
    int i = first;
  loop:
    std::cout << i << ' ';
    try
    {
      std::bitset<1> bs;
      bs.reset(i == last);
      i += amount;
      goto loop;
    }
    catch (...)
    {
      std::cout << '\n';
    }
  }

The program uses a goto statement that may be frowned upon. Is there a way of meeting the challenge without using iteration or recursion thus getting rid of explicit flow control altogether? Well, I think there is. The main feature of the program shown below is its use of std::iota().

  #include <algorithm>
  #include <iostream>
  #include <iterator>
  #include <numeric>
  #include <vector>

  int main(int argc, const char * argv[])
  {
    const int first = std::stoi(argv[1]);
    const int last = std::stoi(argv[2]);
    const int length = std::abs(first - last) + 1;
    std::vector<int> numbers(length);
    std::iota(numbers.begin(), numbers.end(), 0);
    const int m = 1 - 2 * (first > last);
    const auto f = [m, first](int x) {
      return m * x + first;};
    const std::ostream_iterator<int>
      output(std::cout, " ");
    std::transform(numbers.cbegin(),
      numbers.cend(), output, f);
    std::cout << '\n';
  }

An std::vector is created that contains a sequence of values from zero to one less that the number of values to be printed. The coefficients of the formula designed to map the values in the vector to the required output sequence is then calculated. This is based on the equation y = mx + c, where y is the desired printed value and m is the value of the corresponding element in the vector. Within the program, c has the value of last. The function std::transform() is used to successively convert to the required value each element of the vector and then print it.

As can be seen from the above discussion, C++ provides sufficient flexibility to provide various solutions to the challenge. The C language is not quite so accommodating.

Using the conditional operator, a C language solution is not too difficult. A recursive version is shown below.

  #include <stdio.h>
  #include <stdlib.h>
  void increment(int amount, int value, int last)
  {
    printf("%d ", value);
    value != last ? increment(amount, 
      value + amount, last) : (void)0;
  }
  int main(int argc, const char * argv[])
  {
    const int first = atol(argv[1]);
    const int last = atol(argv[2]);
    increment(first > last ? -1 : 1, first, last);
    putchar('\n');
  }

Alternatively, an iterative version can be provided.

  #include <stdio.h>
  #include <stdlib.h>

  int main(int argc, const char * argv[])
  {
    const int first = atol(argv[1]);
    const int last = atol(argv[2]);
    const int amount = 1 - 2 * (first > last);
    int i = first;
  loop:
    printf("%d ", i);
    (i == last) ? exit(0) : (void)0;
    i += amount;
    goto loop;
  }

Providing a C language solution that does not use a conditional expression is a little more difficult. The best I can manage is shown below.

  #include <assert.h>
  #include <stdio.h>
  #include <stdlib.h>

  int main(int argc, const char * argv[])
  {
    const int first = atol(argv[1]);
    const int last = atol(argv[2]);
    const int amount = 1 - 2 * (first > last);
    int i = first;
  loop:
    printf("%d ", i);
    assert(i != last);
    i += amount;
    goto loop;
  }

The program certainly prints the numbers from first to last but other unwanted text is also printed due to the assert statement. I am not familiar with the later C standards and better solutions may be possible.

From Paul Davies

I have these entries for Francis. He didn’t give an email so no wonder he didn’t get many responses

Francis: Excellent point, please send submissions to francis.glassborow@gmail.com

The following is a c-quine which is ‘portable’. I based it on a C++ one I wrote in 2006 and just changed the couts into printf.

  #include<stdio.h>
  char p[]="\";int main(){
    printf(\"#include<stdio.h>\\nchar p[]=\\\"\");
    for (char* q=p;*q;++q){
      if(*q=='\\\\'||*q=='\"')printf(\"\\\\\");
      printf(\"%c\",*q);}
    printf(\"%s\\n\",p);
    return 0;}";
    int main(){
      printf("#include<stdio.h>\nchar p[]=\"");
      for (char* q=p;*q;++q){
        if(*q=='\\'||*q=='"')printf("\\");
        printf("%c",*q);}
      printf("%s\n",p);return 0;}

At least, it’s ‘portable’ if you save it in the same encoding you will go on to run it in!

Francis: Thanks, I think that is as much as we could expect. A quine that could be compiled for one character encoding and then work with a different one seems to me to be a step too far (unless you, the reader, knows better).

The key is to put most of the program in the data string, and then print it twice, once quoted and once not quoted. Francis’s example did this easily; mine uses a for loop to go through and deliberately quote the awkward characters.

accu.cpp generates the numbers first to last without if, for, switch or while. Ok, I cheated: I used the ternary operator.

Francis: Not really, but I have omitted it because this column is already about to take over this issue of CVu.

This does it without the ternary operator.

(This code was done in my own time and is not connected with my employer.)

  #include <stdio.h>
  #include <stdlib.h>
  int f(int, int);
  int g(int, int) { return 0; }
  int (*which[2])(int,int) = { f, g };
  
  int f(int first, int last) {
    printf("%d\n",first);
    int next = first - 1 + 2*(last > first);
    return (*(which[first == last]))(next,last);
  }

  int main(int argc, char** argv){
    f(atoi(argv[1]), atoi(argv[2]));
  }

Francis: Great idea and results in a really simple program.

And a Java solution from Pete Disdale

Please find attached my solution – it is written in Java on the grounds that “anything not expressly forbidden is allowed”. I could probably write something similar in C using linked lists but that is an exercise for a rainy day and printing the output would be a challenge.

You will need Java 7 or above to compile and run this code, although with some tweaking it should be OK with Java 5 or 6. As you can see, it uses recursion to build up the numbers to print (incrementing or decrementing) controlled by a ternary operator. The System.out in main() and the two ret methods are just fluff in order to use it.

No doubt it could be factored into something simpler but it appears to work as is on all the number ranges I tried.

  import java.util.ArrayList;
  import java.util.List;
  
  public class AccuChallenge {

    public static void main(String[] args) {
      try {
        new AccuChallenge(args[0], args[1]);}
      catch (IndexOutOfBoundsException ex) {
        System.err.println("Insufficient arguments: 2 integers required.");}
    }
    private AccuChallenge(String arg1, String arg2)
    {
      int a, b;
      try {
        a = Integer.parseInt(arg1);
        b = Integer.parseInt(arg2);
        System.out.print((a <= b) 
          ? new Incrementing(a, b).ret() 
          : new Decrementing(a, b).ret());
      } catch (NumberFormatException nfe) {
        System.err.println("One or both arguments are not parsable as integers.");
      }
    }
    private class Incrementing {
      private final List<Integer> result 
        = new ArrayList<>();
      private final int b;
      private int a;
      public Incrementing(int a, int b) {
        this.a = a;
        this.b = b;
        addInt();
      }
      private boolean addInt() {
        return a <= b ? keepGoing() 
          : printResult();
      }
      private boolean keepGoing() {
        result.add(a++);
        addInt();
        return true;
      }
      private boolean printResult() {
        System.out.println(result);
        return true;
      }
      public String ret() {
        return "";
      }
    }
    private class Decrementing {
      private final List<Integer> result 
        = new ArrayList<>();
      private final int b;
      private int a;
      public Decrementing(int a, int b) {
        this.a = a;
        this.b = b;
        addInt();
      }
      private boolean addInt() {
        return a >= b ? keepGoing() 
          : printResult();
      }
      private boolean keepGoing() {
        result.add(a--);
        addInt();
        return true;
      }
      private boolean printResult() {
        System.out.println(result);
        return true;
      }
      public String ret() {
        return "";
      }
    }
  }

Francis: I note that this is about the longest solution submitted. I wonder if that is inherent in the choice of language.

From Richard Brookfield

I managed it in C, originally by using the ternary operator, but that felt like a bit of a cheat (though you didn’t prohibit it), so I refactored it out – hence the two attached versions.

Francis: I have omitted the first because of space constraints.

#include <stdio.h>
typedef enum tagBOOL
{
  FALSE  = 0,
  TRUE  = 1
} BOOL;
static BOOL ShowNumber(int n)
{
  printf("%d ",n);
  return TRUE;
}
static BOOL ShowRangeBase(int start, int end,
  BOOL ascending)
{
  int halfwayish  = (start+end)/2;
  return
    // Gone too far
    ascending && start>end || 
    !ascending && start<end ||
    // Something to do
    ShowNumber(start) &&
    // Maximum recursion O(log2(n))
    ascending &&
    ShowRangeBase(start+1,halfwayish,ascending) &&
    ShowRangeBase(halfwayish+1,end,ascending)||
    !ascending &&
    ShowRangeBase(start-1,halfwayish,ascending) &&
    ShowRangeBase(halfwayish-1,end,ascending);
}
static void ShowRange(int start, int end)
{
  printf("Showing range from %d to %d\n",
    start,end);
  ShowRangeBase(start,end,start<end);
  printf("\n");
}
int main(int argc, char *argv[])
{
  // Various examples and edge cases
  int i;
  for (i=-2; i<12; ++i)
  {
    ShowRange(1, i);
  }
  ShowRange(2, 1);
  ShowRange(3, 1);
  ShowRange(5, 1);

  ShowRange(-1, 2);
  ShowRange(2, -1);

  ShowRange(0, 2);
  ShowRange(2, 0);

  // Enough to show the recursion isn't deep
  ShowRange(1, 200);
  return 0;
}

Francis: Whilst this is a fairly long solution, it does a good deal of checking as well as testing edge cases and being adequately commented.

From Robin Williams

Francis: Though Robin has used the ternary operator, his solution is novel.

I thought of two ways to avoid control statements in C: operator ?: and short-circuit logic. Both rely on expression evaluation, which means you need functions to return something, even if the result will be ignored (apart from generating compiler warnings).

The attached uses operator ?: for the core logic: the short-circuit version would be more verbose. I use short-circuit logic for error-checking, in a common scripting language idiom.

It’s possible to do the iteration by simple stepping rather than bisection. However, without tail-call optimization, stepping can cause the program to fail for large ranges.

  #include <stdio.h>
  #include <stdlib.h>
  int rangeprint(int i1, int i2)
  {
    int im = (i1+i2)/2;
    // If range has one element
    return im == i1 || im == i2 ? 
    printf("%d\n",i1) :  // Print that

    // Else split
    rangeprint(i1,im) && rangeprint(im,i2);
  }
  int usage(char* s, int i)
  {
    printf("Usage: %s <n1> <n2>\n",s);
    exit(i);
    return 1;
  }
  int main(int argc, char*argv[])
  {
    int i1, i2;
    argc == 3 || usage(argv[0],1);
    sscanf(argv[1],"%d\n",&i1) == 1 
      || usage(argv[0],1);
    sscanf(argv[2],"%d\n",&i2) == 1 
      || usage(argv[0],1);
    i1 == i2 || rangeprint(i1,i2);
    printf("%d\n",i2);
  }

Francis: Robin also sent in a system-independent quine.

#include <stdio.h>
int main()
{
 char s[]="#include <stdio.h>\n"
"int main()\n"
"{\n"
" char s[]=$;\n"
" for(char*t=s;*t;++t){\n"
"  if(*t=='$' && *(t+1)==';'){\n"
"   putchar('\"');\n"
"   for(char*u=s;*u;++u){\n"
"    if(*u=='\\n')printf(\"\\\\n\\\"\\n\\\"\");\n"
"    else if(*u=='\"')printf(\"\\\\\\\"\");\n"
"    else if(*u=='\\\\')printf(\"\\\\\\\\\");\n"
"    else putchar(*u);}\n"
"   putchar('\"');}\n"
"  else putchar(*t);\n"
" }\n"
"}\n"
"";
 for(char*t=s;*t;++t){
  if(*t=='$' && *(t+1)==';'){
   putchar('"');
   for(char*u=s;*u;++u){
    if(*u=='\n')printf("\\n\"\n\"");
    else if(*u=='"')printf("\\\"");
    else if(*u=='\\')printf("\\\\");
    else putchar(*u);}
   putchar('"');}
  else putchar(*t);
 }
}

A conversation piece from Steven Singer

Francis: I really enjoy this way of presenting a solution. I find them so much more fun than just cold code.

S: Let’s see, you want me to write a program that takes two integer inputs (first and last), to output the integers from the first to the last and you don’t want me to use if, for, switch or while.

F: Yes, and first may be higher than last.

S: There are a couple of ways of interpreting that last condition, I’ll assume you mean that if first is higher than last you want me to count down. The alternative would be to count from the lower of first and last up to the higher.

F: That’s a reasonable interpretation of the problem.

S: OK, let’s recurse and use the ternary operator. Although the ternary operator doesn’t allow us to embed statements, like return, we can embed function calls and that’s all we need for recursion:

  #include <stdlib.h>
  #include <stdio.h>

  void count(int first, int last, int step)
  {
    printf("%d\n", first);
    first != last ? count(first + step, last, step)
    : (void) 0;
  }
  int main(int argc, char *argv[])
  {
    int first = argc >= 2 ? atoi(argv[1]) : 1;
    int last = argc >= 3 ? atoi(argv[2]) : 100;
    int step = first < last ? 1 : -1;
    count(first, last, step);
    return 0;
  }

F: What’s the (void) 0 for?

S: A ternary operator always has two value expressions but I only need one. I need to specify something in the unwanted path. The two value expressions for the ternary operator must have compatible types. Since count() naturally has no return value, I need the third expression also to have no return value but I can’t leave it blank. Personally, I like using (void) 0 as it makes it clear to the reader and the compiler that I really, really want to do nothing. It’s very Zen.

F: Well, I suppose that works but aren’t you worried about the stack usage of the recursion?

S: A little, but modern compilers are pretty good at tail call optimisations. For example, gcc 5.4.0 at optimisation level 2 produces the following on my Linux box (I’ll remove some non-essential lines, like call frame information directives, alignment directives, unused labels and so on for clarity):

  count:
    pushq %r12
    movl  %edx, %r12d
    pushq %rbp
    movl  %esi, %ebp
    pushq %rbx
    movl  %edi, %ebx
    jmp   .L3
  .L6:
    addl  %r12d, %ebx
  .L3:
    xorl  %eax, %eax
    movl  %ebx, %edx
    movl  $.LC0, %esi
    movl  $1, %edi
    call  __printf_chk
    cmpl  %ebp, %ebx
    jne   .L6
    popq  %rbx
    popq  %rbp
    popq  %r12
    ret

S: You can see the call to printf() but the recursive call to count has become the conditional jump to label .L6.

F: That looks good but what if someone feels that using a ternary operator is perhaps a little too much like an if-else, particularly as there are redundant expressions.

S: No problem, I can remove the ternary operators:

  #include <stdlib.h>
  #include <stdio.h>
  void count(int first, int last, int step)
  {
    printf("%d\n", first);
    (void) (first != last && (count(first + step,
      last, step), 0));
  }
  int main(int argc, char *argv[])
  {
    int first = 1, last = 100, step = 1;
    (void) (argc >= 2 && (first = atoi(argv[1])));
    (void) (argc >= 3 && (last = atoi(argv[2])));
    (void) (first > last && (step = -1));
    count(first, last, step);
    return 0;
  }

S: There you go, not a ternary operator in sight. The logical operators short-circuit paths that aren’t taken so the recursion terminates properly.

F: I notice you’re using a comma operator.

S: Yes, when using short circuit operators, the terms on either side can’t be void expressions. Since I’ve declared count() as not having a return value, I need something to keep the compiler happy. I could have avoided the comma operator by declaring count() as returning int but that’s a little unnatural as there’s nothing meaningful for count to return.

F: OK, I see what you did there but if we’re avoiding ternary operators then the short-circuit logical operators are still a bit too much like an if.

S: OK, fine, no short-circuiting logical or ternary operators:

  #include <stdlib.h>
  #include <stdio.h>
  int opt_default(int dflt, char *argv[], int arg)
  {
    return dflt;
  }
  int opt_parse(int dflt, char *argv[], int arg)
  {
    return atoi(argv[arg]);
  }
  int (*opt_select[])(int, char *[], int) = {
    opt_default, opt_parse };
  void nop(int first, int last, int step)
  {
  }
  void count(int, int, int);/* Forward reference */

  void (*funcs[])(int, int, int) = { nop, count };
  void count(int first, int last, int step)
  {
    printf("%d\n", first);
    funcs[first != last](first + step, last, step);
  }
  int main(int argc, char *argv[])
  {
    int first = opt_select[argc >= 2](1, argv, 1);
    int last = opt_select[argc >= 3](100, argv, 2);
    int step = (first < last) * 2 - 1;
    count(first, last, step);
    return 0;
  }

S: This time, there are no if-like operators at all. I’ve used two-element arrays of function pointers and then indexed them with boolean expressions. Element zero gets called when the expression is false and element one gets called when the expression is true.

F: Isn’t that a bit obscure?

S: Actually, no. Many real systems defer complex decisions to state machines and the core of a state machine is logically a two-dimensional array of function pointers indexed by the current state and the event received. Usually there’s some compression of the data structures as not all events can be received in all states. Think of the code I just gave as a state machine compressed to deal with having just one state in which it can receive events (printing a number) and two events (continue and stop).

F: I suppose that’s fair.

S: Did you know that even though we’re using function pointers, GCC has still performed the tail call optimisation so we won’t overflow the stack:

  count:
    pushq %r12
    pushq %rbp
    movl  %edx, %r12d
    pushq %rbx
    movl  %esi, %ebp
    movl  %edi, %ebx
    movl  %edi, %edx
    movl  $.LC3, %esi
    movl  $1, %edi
    xorl  %eax, %eax
    call  __printf_chk
    xorl  %eax, %eax
    cmpl  %ebp, %ebx
    leal  (%rbx,%r12), %edi
    setne %al
    movl  %r12d, %edx
    movl  %ebp, %esi
    popq  %rbx
    popq  %rbp
    popq  %r12
    movq  funcs(,%rax,8), %rax
    jmp   *%rax

S: The jmp *%rax is a tail call to the function pointer. You can see the three popqs a few lines earlier that unwind this stack frame.

F: Hmm, not all compilers are that good at tail call optimisation and it may depend on which processor is being targeted. Can you avoid recursion completely?

S: Sure, but do you mind if I go back to using ternary operators for the simple if conditions? I’ve got a choice of several options but ternary operators will make it easier to see the new code.

F: It’s the least I can do.

S: OK, here goes, but be warned that since you’ve taken away for, while and recursion, I can think of only one way to make the loop I need:

  #include <stdlib.h>
  #include <stdio.h>
  int main(int argc, char *argv[])
  {
    int first = argc >= 2 ? atoi(argv[1]) : 1;
    int last = argc >= 3 ? atoi(argv[2]) : 100;
    int step = first < last ? 1 : -1;
  loop:
    printf("%d\n", first);
    first == last ? exit(0) : (void) 0;
    first += step;
    goto loop;
  }

S: We couldn’t use this trick for return as it’s a statement but exit() is a function. C is a small language, a lot of functionality is provided by functions in libraries.

F: Exiting the entire program is a bit brute force; you can’t use this trick in a function embedded in a program.

S: The rules don’t say this has to be a function.

F: I suppose they don’t but it’d be a better example if it were.

S: OK, how about this:

  #include <stdlib.h>
  #include <stdio.h>
  #include <setjmp.h>
  void count_internal(int first, int last, 
    int step, jmp_buf env)
  {
  loop:
    printf("%d\n", first);
    first == last ? longjmp(env, 1) : (void) 0;
    first += step;
    goto loop;
  }
  void count(int first, int last, int step)
  {
    jmp_buf env;
    
    setjmp(env) ? (void) 0 
      : count_internal(first, last, step, env);
  }
  int main(int argc, char *argv[])
  {
    int first = argc >= 2 ? atoi(argv[1]) : 1;
    int last = argc >= 3 ? atoi(argv[2]) : 100;
    int step = first < last ? 1 : -1;
    count(first, last, step);
    return 0;
  }

S: There you go, no premature exit.

F: Oh good grief. That is not a better example.

S: That’s the first time I’ve used setjmp/longjmp.

F: I’m glad to hear it.

S: It kept me entertained.

F: That’s what concerns me.

S: I can do worse.

F: Oh dear.

S: How about this:

  #include <stdlib.h>
  #include <stdio.h>
  int main(int argc, char *argv[])
  {
    int first = argc >= 2 ? atoi(argv[1]) : 1;
    int last = argc >= 3 ? atoi(argv[2]) : 100;
    int reverse = first > last;
    char buffer[256];
    sprintf(buffer, "perl -e 'print map { \"$_\\n\"
      } %s (%d..%d)'", reverse ? "reverse" : "",
      reverse ? last : first,
      reverse ? first : last);
    (void) system(buffer);
    return 0;
  }

F: How can you justify that?

S: Like the function pointers code being an example of a more sophisticated technique (state machines) which is valid for more complex problems, sometimes it’s important to realise you’re using the wrong language to solve a problem. Why write a thousand lines of hard-to-debug C when it might only take a couple of lines in Perl.

F: A couple of lines of hard-to-debug Perl. You could use Python.

S: OK, a dozen lines of hard-to-debug Python. It’s the programmer that makes code hard-to-debug, not the language.

F: Let’s not start a flame war.

S: Spoilsport. But even if you don’t go to another language, you should look at the libraries for the language you’re using. In the Perl example, the loops and the iteration are implicit. Many languages have similar higher-level constructs. C has a smaller set, but there are some useful routines there (not to mention a wide variety of third party libraries). For example, if you wanted to sort an array in C you wouldn’t write your own sort routine without having a story as to why the library qsort() routine wasn’t suitable. Writing sort routines from scratch is error prone; it’s better to avoid it if possible. Less well-known are functions for searching flat arrays either linearly or using binary search. There are even functions for managing binary trees and hash tables. For example, we can solve the problem with this program, which you could imagine as a learning exercise to investigate the order in which lfind() visits a linear array just with the output slightly manipulated to give the numbers we want:

  #include <stdlib.h>
  #include <stdio.h>
  #include <search.h>
  struct params {
    int first;
    int step;
    char *base;
  };
  int compar(const void *key, const void *velem)
  {
    const struct params *pp = key;
    const char *elem = velem;
    int index = (int) (elem - pp->base);
    printf("%d\n", index * pp->step + pp->first);
    return 1; /* Keep going */

  }
  int main(int argc, char *argv[])
  {
    struct params p;
    int last;
    size_t num;
    p.first = argc >= 2 ? atoi(argv[1]) : 1;
    last = argc >= 3 ? atoi(argv[2]) : 100;
    p.step = p.first < last ? 1 : -1;
    num = (last - p.first) * p.step + 1;
    p.base = malloc(num);
    (void) lfind(&p, p.base, &num, 1, compar);
    return 0;
  }

F: I notice you didn’t initialise the array you allocate.

S: There’s no need as I never actually dereference the values. I just print out the order in which the array indexes are visited.

F: I guess that’s technically correct, even if it’s a little ugly. You are using a lot of memory for no benefit.

S: I wanted to keep it legal so I needed to ensure the pointers p.base and elem pointed to the same object otherwise the subtraction wouldn’t be defined in the C specification. Some equivalent techniques in other languages might suffer the same problem; for example, building the entire output in memory before writing it out consumes memory. Sometimes this is a problem and using iterator functions or objects can help. Other times, the problem you’re solving requires having all the data in memory so you have to pay that cost anyway. However, overall, I agree for this problem it’s ugly and overkill. I don’t even test whether the allocation succeeded.

F: It could be worse, at least you didn’t abuse the C pre-processor.

S: Did someone say “abuse the C pre-processor”:

  #include <stdlib.h>
  #include <stdio.h>
  #define PASTE(a, b) b ## a
  #define until(x) PASTE(ile, wh) (!(x))
  int main(int argc, char *argv[])
  {
    int first = argc >= 2 ? atoi(argv[1]) : 1;
    int last = argc >= 3 ? atoi(argv[2]) : 100;
    int step = first < last ? 1 : -1;
    do {
      printf("%d\n", first);
      first += step;
    } until(first == last + step);
    return 0;
  }

F: I should have kept my mouth shut.

S: Hey, it obeys the rules, it doesn’t contain the word ‘while’, it doesn’t even include the letters w, h, i, l and e in that order.

F: Can we stop now?

S: Nope. A coding competition isn’t over until someone abuses the rules.

F: And that last example didn’t already abuse the rules?

S: Let’s pretend it’s an important real-world lesson about requirements. What did the rules say the program had to output?

F: “the integers from the first to the last”.

S: Thanks for the quotation marks:

  #include <stdio.h>
  int main(void)
  {
    printf("the integers from the first to the last\n");
    return 0;
  }

S: Does it help if I pretend it’s an important lesson about escaping strings to avoid SQL injection attacks and similar.

F: Not really. Please can we stop now?

S: Alright. I’ve had my fun.

F: Yes, you seemed to be enjoying this all too much.

From Stephen Baynes

Francis: Here is an interesting collection of (short) solutions.

The problem is not how to do it at all, C provides short circuit operators that combined with recursion easily do the job (1, 2, 3) but how many other ways it can be done. One can terminate a goto loop by terminating the program with assert (4), division by zero [undefined behaviour so will depend on implementation] (5) or by the process killing itself using some clever arithmetic using booleans as integers to calculate signal number that does or does not stop execution [requires POSIX] (6). Using booleans as integers can be used to select a function to call from a table that recurses or not to end the loop (7). It should be possible to recursively use the error callback of memset_s to provide a controlled recursive loop (8) but I was unable to find a compiler that implements this optional feature so this code is untested.

One could do all sorts of non-portable implementations using system but that is outside the spirit of doing it in C.

I wondered about printing consecutive numbers from the comparison function passed to qsort. qsort on an array of size n would give you at least n-1 comparisons but could give more though a finite amount. The printing would terminate, but it would be very difficult to ensure it terminated at the right time and when it terminated would not be portable.

Having to read in the first and last values means one cannot use recursive pre-processor macros to solve the challenge.

Francis: Which is just as well because this column is already heading for record-breaking size.

1)

  #include <stdio.h>
  static int from, to;
  int pri( int n ){
    printf( "%d\n", n );
    n < to && pri( n + 1 );
    return n;
  }
  int main(){
    scanf( "%d %d", &from, &to );
    pri( from );
    return 0;
  }

2)

  #include <stdio.h>
  static int from, to;
  int pri( int n ){
    printf( "%d\n", n );
    n >= to || pri( n + 1 );
    return n;
  }
  int main(){
    scanf( "%d %d", &from, &to );
    pri( from );
    return 0;
  }

3)

  #include <stdio.h>
  static int from, to;
  int pri( int n ){
    printf( "%d\n", n );
    n < to ? pri( n + 1 ) : 0;
    return n;
  }
  int main(){
    scanf( "%d %d", &from, &to );
    pri( from );
    return 0;
  }

4)

  #include <stdio.h>
  #include <assert.h>
  static int from, to;
  int main(){
    scanf( "%d %d", &from, &to );
    int n = from;
  LOOP:
    printf( "%d\n", n );
    assert( n < to );
    ++n;
    goto LOOP;
    return 0;
  }

5)

  #include <stdio.h>
  static int from, to;
  static int j = 0;
  int main(){
    scanf( "%d %d", &from, &to );
    int n = from;
  LOOP:
    printf( "%d\n", n );
    j =  1 / ( to -n );
  // This might depend on your compiler
    ++n;
    goto LOOP;
    return 0;
  }

6)

  #include <sys/types.h>
  #include <signal.h>
  #include <unistd.h>
  #include <stdio.h>
  static int from, to;
  int main(){
    scanf( "%d %d", &from, &to );
    int n = from;
    pid_t pid = getpid();
  LOOP:
    printf( "%d\n", n );
    int j = (int)( n >= to );
    kill( pid, j * SIGTERM ) ; 
      // Signal 0 does not signal.
    ++n;
    goto LOOP;
    return 0;
  }

7)

  #include <sys/types.h>
  #include <signal.h>
  #include <unistd.h>
  #include <stdio.h>
  static int from, to;
  typedef void action( int );
  action *jump_table[2];
  static void action_end( int n ) { }
  static void action_next( int n ) {
    printf( "%d\n", n );
    int j = (int)( n >= to );
    jump_table[ j ]( n + 1 );
  }
  int main(){
    scanf( "%d %d", &from, &to );
  
    jump_table[ 0 ] = action_next;
    jump_table[ 1 ] = action_end;
    action_next( from );
    return 0;
  }

8)

  // This code is not tested as my compiler 
  // does not support memset_s
  #define __STDC_WANT_LIB_EXT1__ 1
  #include <stdio.h>
  #include <string.h>
  #include <stdlib.h>
  static int from, to;
  static int n;
  void pri( void ){
    printf( "%d\n", 1 + from - n );
    --n;
    char c;
    memset_s( &c, 1, 0, n );
  }
  void ch(
    const char *restrict msg,
    void *restrict ptr,
    errno_t error
  ){
    pri()
  }
  int main(){
    scanf( "%d %d", &from, &to );
    n = 1 +  from - to;
    set_constraint_handler_s( ch )
    pri( );
    return 0;
  }

From Tim Kent

My first thought was how to control program flow without loops and if statements and it didn’t take a moment to recall a code base that I inherited which uses exceptions for normal code flow. I ignored the use of the ternary (?:) operator thinking that this was not in the spirit of the challenge. So how could I use exceptions to control a loop? The first thing that came to mind was divide by zero. This led me to the following solution:

  #include <iostream>
  int main()
  {
    /*Here is an initial idea using divide by zero,
      to solve Challenge 4 in CVU Vol 30 Issue 3,
      July 2018 */
    int first = 1;
    int last = 100;
    /*check that first is less than last otherwise
      fault on divide by zero to terminate program.
      TRUE - TRUE = 0*/
    volatile int terminating_calc1 = 
      1/ ((first > last) - true);
  loop:
    std::cout << first++ << '\n';
    volatile int terminating_calc2 =
      1/(last-first+1);
      /* fault terminate with divide by zero after
         we reached the last number */
    goto loop;
    return 0;
  }

The only problem is that this signals and terminates [well, you hope it does that rather than rewrite your hard-drive ☺] the program meaning this could not be used in a larger program. Sure, it would be possible to handle the signal and not terminate but that would be platform dependent code. How to conditionally throw an exception? I almost have this condition in the program above. True - True == 0, True - False == ?. If I could force True - False == 1 then I could use a two-element array of functions to throw or not throw based on the index. I ended up just dividing by true to achieve this. The only other question in my mind was what to throw. I arbitrarily chose a void pointer so as not to interfere with any other code that might be used with this solution (not that I am recommending using this solution anywhere!), which leads to the following solution:

  void throw_if_true(bool condition)
  {
    typedef void fntype();
    static fntype* fn_lut[2] = { []{
      throw static_cast<void*>(0);}, []{}};
    int index = (true - condition)/true;
    fn_lut[index]();
  }

  int main()
  {
  /*Using an exception for flow control, to solve
    Challenge 4 in CVU Vol 30 Issue 3, July 2018 */
    int first = 1;
    int last = 100;
    try{
      throw_if_true(first > last);
      loop:
      std::cout << first++ << '\n';
      throw_if_true(first > last);
      goto loop;
    }catch(...) {}
    return 0;
  }

Now that this works, can I go a step further and avoid signals and exceptions altogether? Building on what I have so far, I thought about replacing the lambda that throws with a lambda that recurses, and this led eventually to the following solution.

  #include <iostream>
  typedef void fntype(int,int);
  void count_inner(const int first,
    const int last);
  static fntype* fn_lut[2] = {
    [](const int first, const int last){},
    [](const int first, const int last)
    {count_inner(first+1, last);} };
  void count_inner(const int first, const int last)
  {
    int index = (true - (first > last))/true;
    std::cout << first << '\n';
    fn_lut[index](first, last);
  }
  void count(const int first, const int last)
  {
    int index = (true - (first > last))/true;
    fn_lut[index](first-1, last-1);
  }
  int main()
  {
  // Using recursion  for flow control, to solve
  // Challenge 4 in CVU Vol 30 Issue 3, July 2018
    int first = 1;
    int last = 100;
    count(first, last);
    return 0;
  }

From Colin Hersom

In CVu 30.3, you challenged us to devise a program to output a sequence of numbers without using for, if, switch and while. You also made an implicit challenge to do it in C (by stating that you could not) as well as C++. Now, I know that you are a very clever man and know the intricacies of C in far more detail than most, so I was surprised at the statement that you could not do it in C. If this was meant as a provocation, it worked!

Francis: Hmm… I am getting old and forgetful. For example I forgot to exclude the ternary operator. ☺

I agree that recursion (or indeed anything) cannot know when to stop without a condition (unless you cause the program to crash!), but you have not excluded conditions, only those keywords. There is still the conditional operator, and I have used this in my solution [omitted to save space]. The problem with this is that the recursion will take up a lot of stack space and if you ask for a very large range, the system may run out of space and cause an error. With my system, it crashes when asked to produce a sequence of around 261,850 numbers, but varies from run to run. [You need a better compiler that spots tail recursion. ☺]

So to C++. My first solution was to create a vector with all the numbers in and then output the vector. This is OK, but also uses stack space, although not so much. However, the vector is being created and then written, without any other use, so it seemed sensible to remove the vector completely and replace it with an iterator that produced the correct sequence, outputting that directly.

Francis: Both of Colin’s C++ solutions use the ternary operator in the set-up in main but the actual method for creating the desired output do not. I have provided them because they have interesting mechanisms.

  class sequence_interator :
    public   iterator<forward_iterator_tag, int>
  {
  public:
    sequence_interator(int start, int end)
      : current(start)
      , last(end)
      , inc(start < end ? 1 : -1)
    {  }
    sequence_interator &begin()
    {
      return *this;
    }
    sequence_interator &end()
    {
      return *this;
    }
    // The compared interator is always 'this' so
    // no need to examine it
    // Just using to test for the last one
    bool operator !=(const sequence_interator&)
    {
      return last != current - inc;
    }
    sequence_interator &operator++()
    {
      current += inc;
      return *this;
    }
    int operator *() const
    {
      return current;
    }
  private:
    int current;
    int last;
    int inc;
  };
  int main(int av, char **ac)
  {
    int start = av >1 ? atoi(ac[1]) : 0;
    int end = av >2 ? atoi(ac[2]) : 100;
    int inc = start < end ? 1 : -1;
    sequence_interator seq(start, end);
    copy(seq.begin(), seq.end(),
      ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
  }

From Burkhard Kloss

Spurred on by Francis’s challenge, I dusted off the C compiler and wrote my first C program in ... over a decade at least? Turns out I can still do it, although I wouldn’t say I’m particularly proud of this one. It does work, though, and matches the spec as far as I can tell. For the simple case, this should do the trick.

  #include <stdio.h>
  #include <stdlib.h>
  int quitter()
  {
    exit(0);
    return -1;
  }
  int main()
  {
    int i = 1;
  start:
    printf("%d\n", i);
    i = i < 100 ? i + 1 : quitter();
    goto start;
  }

Francis: Yes, but I forgot to exclude the ternary operator. Your solution can be amended to avoid use of the ternary operator by replacing that statement with:

  i < 100 || quitter(); ++i;

I notice that the ternary operator can almost invariably be replaced by lazy evaluation. For example, usually this:

  expr1 ? expr2 : expr3

can be transformed into:

  (expr1 && expr2) ||| expr3;

Using the same approach for the extended problem with inputs of first and last on the command line – even including rudimentary input checking:

  #include <stdio.h>
  #include <stdlib.h>
  int quitter()
  {
    exit(0);
    return -1;
  }
  int sign(int x)
  {
    return x > 0 ? 1 : -1;
  }
  int noisy_quit(char const * msg)
  {
    puts(msg);
    exit(1);
    return -1;
  }
  void check_args(int argc)
  {
    argc == 3 ? 0 : noisy_quit
      ("first_to_last start stop");
  }
  int main(int argc, char * argv[])
  {
    check_args(argc);
    int start = atoi(argv[1]);
    int stop = atoi(argv[2]);
    int step = sign(stop - start);
    int i = start;
  loop:
    printf("%d\n", i);
    i = i != stop ? i + step : quitter();
    goto loop; 
  }

Not the world’s most elegant code, but it seems to handle all possible conditions, and has no sign of if, for, while, or switch.

And the winner is…

Well, none of the above. I have asked Steve to turn the winning submission (from Andreas Gieriet) into a free-standing article, which you will find on page 6.

Thanks to all of you who have put in so much thought and ingenuity. It is eye-opening to see how many completely different solutions you collectively managed to find.

Challenge 5

Many years ago someone – I have forgotten who – ran a competition for writing a (natural) language that only had seven words. The trap was to assume that each word had to have a single meaning. To deal with such a paucity of words requires making good use of combinations. Start with two words meaning one and zero then using binary you have an unlimited supply of numbers. Now make a third word mean ‘select meaning n from the next word’ and you have an unlimited supply of meanings available to you (and only using four words … and yes, I know that I could do the same with only three words).

However, I am going to test your ingenuity by asking you to select seven operators with their normal meanings. No grotesque multi-purpose operators. So if + is one of your operators, a+b will mean add ‘a to b’)

Having chosen your seven operators, show how you would obtain as many other operators from C++ as you can. To get you started: Suppose that one of your seven operators is - then you could write:

  template<typename T> T operator+(T t1, T t2)
    { return t1 - (0 - t2)};

I am pretty sure you cannot find a subset of seven operators that spans the set of C++ operators but I wonder how far you can get.

Submissions to francis.glassborow@gmail.com

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