Title: Student Code Critique Competition 28

The simple answer to the student's problem is arrays in C++ being indexed from 0 he does not need the + 1 in his loop which would then read:

for (int i = 0; i <= len; i++)
cout << str[i];

However this leaves a few problems. Addressing the most obvious first main should return an int rather than a void (most obvious because my version of GCC will not compile the code until this is fixed). [gcc 3.3.3 will allow void main() to be compiled. A warning is given rather than an error - Ed]

A lot of the remaining problems stem from the use of C-style strings and changing these for STL strings will address a number of issues. In terms of the current issues related to the C strings the arraySize constant is unnecessary and dangerous, if "Need help with C++." becomes "Need no help with C++." in a moment of hubris and the arraySize value is not increased then there are potential problems, char str[] = "Need ..." will suffice instead. The loop given is printing the final null character which whilst not harmful is not necessary.

Initially changing to use C++ strings tidies these up a bit.

#include <iostream>
#include <string>
using namespace std;
int main() {
  string str = "Need help with C++.";
  int len = str.size();
  cout << "The sentence \"Need help with
       C++.\" has " << len << " characters."
       << endl << endl;
  for (int i = 0; i < len; i++)
    cout << str[i];
}

Even this is correct but could still be improved in a few ways. The "Need help with C++." string is hard coded in two places and the len variable is could be replaced with the str.size() call where it is used. In a program of this size it also not necessary (though not harmful) to flush the output buffers with endl repeatedly, "\n" will suffice. (Incidentally the original loop version dropped the carriage return after each character, which behaviour is required is unclear.)

#include <iostream>
#include <string>
using namespace std;
int main() {
  string str = "Need help with C++.";
  cout << "The sentence \"" << str << "\" has "
       << str.size() << " characters.\n\n";
  for (int i = 0; i < str.size(); i++)
    cout << str[i];
}

Finally the loop could be made more idiomatic by using string iterators rather than indexing (which would also handle the case if the string size happened to overflow the int).

for (string::const_iterator i = str.begin();
     i != str.end(); ++i)
  cout << *i;

But even more so by using an STL algorithm rather than an explicit loop to perform the job, the final version becoming

#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;
int main() {
  string str = "Need help with C++.";
  cout << "The sentence \"" << str << "\" has "
       << str.size() << " characters.\n\n";
  std::copy(str.begin(), str.end(),
            ostream_iterator<char>(cout, ""));
}

The initial problem which the student reports is the false positives for some primes. For example:

C:>ugly 30 32
30
31
32

where '31' should be missing - but:

C:>ugly 70 72
72

correctly doesn't display '71'. How can we find the bug?

I can think of four main ways to resolve down the problem.

These options are not exclusive - and for more complicated problems several of these might be used together.

Let's look at how the problem might be resolved in each case:

The first thing that strikes me about this code is that the structure does not obviously relate to the question. The question asks for a list of 'ugly numbers', so I would expect to see at least one function with the word 'ugly' somewhere in its name. Instead there is a function which sort of produces a list of prime factors, and the rest of the code is all bundled into main.

The student wonders why some additional numbers are output. This is because for any prime number the while loop never executes, so the variable ugly is never reset. This is a direct result of putting too much logic into the main function - extracting the test for ugliness to a separate function would have prevented this particular error ever happening.

The function to extract prime factors has several problems of its own: it uses a fixed length array for the factors with no check for overflow and the length chosen is too short even for 32 bit integers; if it is given a large prime number to factorise it will test every possible divisor up to the number (which could take a while) when it only needs to test divisors up to the square root of the number to determine the prime factors, or up to five to determine whether the number is ugly. The function also doesn't do what the comment at the top says: if it is given a prime number to factorise then instead of returning the number itself it returns an empty list as a special case. This is likely to surprise anyone trying to use the function, so it would be good if the behaviour were documented, but better still if the special behaviour for primes was removed altogether.

Rather than just showing a working program, I will show the steps I use to get to a solution to the problem. I am going to use Python rather than C since that lets me ignore issues like memory management and overflows and also lets me try a variety of algorithms more quickly than I could in C.

When I have a working solution, then if it needs speeding up, or if there is another reason for requiring a C solution the code can be translated to C fairly easily.

Here is my first effort in Python. It follows the student's logic fairly closely in so far as it counts through all the numbers in the range and tests each one for ugliness. The test is a bit different though, instead of extracting all the prime factors, we just look for the factors 2, 3 and 5 and then see if there is any unfactorised residue.

The main code converts its arguments to integers using the eval functions. This makes it easy for me to test comparatively large numbers as I can type an expression as the argument (say 2**29 instead of having to enter 536870912).

# File ugly.py

import sys

BADFACTORS = 2, 3, 5

def isUgly(n):
  if n in BADFACTORS or n in (0, 1):
    return False
  for factor in BADFACTORS:
    while n%factor == 0:
      n = n/factor
  return n == 1

def printUglyRange(start, end):
  print "Ugly numbers from",start,"to",end
  for i in xrange(start, end):
    if isUgly(i):
      print i
  if name__=='__main__':
    if len(sys.argv) != 3:
      sys.exit("Usage: %s start end" % sys.argv[0])
    start, end = eval(sys.argv[1]), eval(sys.argv[2])
    printUglyRange(start, end+1)

I don't feel this code quite expresses my intent yet, so the next step is to refactor printUglyRange:

def uglyRange(start, end):
  for i in xrange(start, end):
    if isUgly(i):
      yield i

def printUglyRange(start, end):
  print "Ugly numbers from",start,"to",end
  for i in uglyRange(start, end):
    print I

For consistency with how Python works generally, the uglyRange function includes its start value but excludes the end value, so 1 is added to the end value to get the same output as the student expected. The yield statement may be unfamiliar to C programmers: when executed it suspends execution of the generator function it is in and returns its argument to the for loop that invoked it; each time the for loop needs another value the generator is resumed exactly where it was suspended and another value calculated.

This separates the printing of the ugly numbers from the logic, and the program seems to run, but when we get up to large numbers (like 2**29) it takes a long time to output each number. The problem is that we are searching an increasingly sparse space for each ugly number instead of going directly to the next value. A better solution would be to generate only the ugly numbers and completely ignore other numbers. First though, I suggest writing some tests in another file testugly.py:

import unittest
class TestUgly(unittest.TestCase):
UGLYTO11 = [ 4, 6, 8, 9, 10, ]
UGLY100TO130 = [ 100, 108, 120, 125, 128, ]

  def setUp(self):
    import ugly
    self.uglyRange = ugly.uglyRange

  def test0to11(self):
    expected = self.UGLYTO11
    actual = list(self.uglyRange(0, 11))
    self.assertEquals(expected, actual)

  def test100to130(self):
    expected = self.UGLY100TO130
    actual = list(self.uglyRange(100, 130))
    self.assertEquals(expected, actual)

if name__=='__main__':
  unittest.main()

The tests allow us to modify the code with confidence that it will continue working, so we can move from an implementation which is easy to understand to one that is much more complex. I tried a few different algorithms, but the version below is my favourite. It generates ugly numbers in ascending order with the numbers partitioned into three lists according to the smallest factor present in that number:

import sys

BADFACTORS = 2, 3, 5

class UglyFifo:
  '''Stores a list of ugly numbers,
     first in first out. Fifos are
     chained so that pushes ripple
     down the chain.'''

  def __init__(self, factor, nextFifo):
    self.head, self.tail = [], []
    self.factor = factor
    if nextFifo:
      self.callNext = nextFifo.push
    else:
      self.callNext = None
    self.push(factor)

  def push(self, n):
    '''Append n multiplied by the
       factor for this fifo, then
       propagate n to the next
       queue.'''
    self.tail.append(n * self.factor)
    if self.callNext:
      self.callNext(n)

  def pop(self):
    '''Returns the oldest (i.e.
       smallest) ugly number from
       the fifo'''
    if not self.head:
      self.head, self.tail = self.tail,self.head
      self.head.reverse()
    return self.head.pop()

  def pushThenPop(self, n):
    self.push(n)
    return self.pop()

def generateUgly():
  '''Generate a potentially infinite
     sequence of ugly numbers, in
     increasing order.'''
  values = []
  fifo = None

def processLowest(lowest):
  '''Push a new value into a fifo,
     update the working values and
     return an ugly number'''
  ugly, fifo = lowest
  lowest[0] = fifo.pushThenPop(ugly)
  return ugly
  for factor in BADFACTORS:
    while values:
      lowest = min(values)
      if lowest[0] > factor:
        break
      yield processLowest(lowest)
    fifo = UglyFifo(factor, fifo)
    values.append([fifo.pop(), fifo])
  while 1:
    yield processLowest(min(values))

def uglyRange(lo, hi):
  '''Generate all ugly numbers from lo
     (inclusive) to hi exclusive.'''
  for i in generateUgly():
    if i >= hi:
      break
    if i >= lo:
      yield i

def main(start, end):
  print "Ugly numbers from",start,"to",end
  for i in uglyRange(start, end+1):
    print i
  if __name__=='__main__':
    if len(sys.argv) != 3:
      sys.exit("Usage: %s start end" % sys.argv[0])
    main(eval(sys.argv[1]), eval(sys.argv[2]))

Perhaps this seems like overkill for a simple problem, but this version of the program works up to quite large ugly numbers, albeit with a delay if the starting value is large. On my system it takes just over 10 seconds to calculate the 1.7 million values up to 10**100 which is probably fast enough for most purposes and therefore doesn't really need converting back to C.

If the student wants to convert this to C (or is compelled to do so by the teacher), there are several ways to do it, but the one I would recommend would be to use the Python program to write all ugly numbers up to some arbitrary limit into a file (there are 1844 up to 2**32, or 13278 up to 2**64) then write a program to print ugly numbers by reading them from the file and printing those in the required range. The code could handle the numbers as strings which would allow even a simple C program to work with arbitrarily large values, but I'll leave this as an exercise for the student.

The student is quite correct in stating that any prime number should fail the while() test. The problem is that the value of ugly is only set within the while loop. When n is a prime number, the value of ugly remains at what it was set to on the previous trip through the while loop. Thus any prime number which immediately follows an ugly number will also be printed. To fix the problem it is just necessary to set ugly to 0 at the start of each iteration through the for loop.

Now to look at improvements to the code in general. I'll start with the function to calculate prime factors. This could be a useful general purpose function if it did what the comment claims it does, namely to find the prime factors of a number. As it stands, however, it only finds the prime factors of compound numbers, returning 0 for prime numbers. The student has introduced a special behaviour for primes. I would prefer to modify the function to:

/* find the prime factors of number */
int *pf(int number) {
  int *flist, quotient=0, divisor=2, idx=0;
  flist = calloc(SIZE, sizeof(int));
  while(divisor < number + 1) {
    if(divisor == number) {
      flist[idx] = divisor;
      /* add last factor to list */
      break;
    }
    if(number % divisor == 0) {
      flist[idx++] = divisor;
      quotient = number/divisor;
      number = quotient;
    }
    else ++divisor;
  }
  return flist;
}

then add the special treatment in the main function

if(flist[1] == 0) {
  ugly = 0;
else {
  while flist[idx]) {
    ...
  }
}

Ideally the pf() function should also ensure that the factorisation does not go beyond the end of the array, either by checking that idx remains less than SIZE, or by choosing SIZE so that the array is large enough to hold the maximum possible number of factors of any number that will fit in an int. (Since MAXINT is always 2n-1, where n will depend on how many bytes make up an int, any number that can be stored in an int can have at most (n-1) prime factors).

However, we don't actually need to know all the prime factors of a compound number to determine whether it is ugly or not. We just need to know whether it has at least one prime factor that is different from 2, 3 and 5. For all numbers > 5 we can determine this without storing the factors as follows.

while(n % 2 == 0) {
  n /= 2;
}

while(n % 3 == 0) {
  n /= 3;
}

while(n % 5 == 0) {
  n /= 5;
}

if(n == 1) {
  ugly = 1;
}

The numbers < 6 can be treated as special cases, 4 is the only ugly one:

if(n == 4) {
  ugly = 1;
}

(Remember that ugly is initialised to 0 at the start of the for loop, so 1, 2, 3, 5 will not become ugly)

Thus all that is required (apart from checking that start and stop are valid numbers, with stop >= start, and printing some helpful message if the user has not supplied 2 correct arguments) is:

/* find "ugly numbers": their prime factors
   are all 2, 3, or 5 */
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
  int n, ugly, number;
  int start, stop;
  if(argc != 3) {
    /* print helpful message */
    exit(EXIT_FAILURE);
  }
  start = atoi(argv[1]); /*enter a range */
  stop = atoi(argv[2]);
  if(start > stop) {
    n = stop;
    stop = start;
    start = n;
  }
  for(number = start; number < stop +1; ++number) {
    n = number;
    ugly = 0;
    if(n == 4) {
      ugly = 1;
    }
    else if(n > 5) {
      while(n % 2 == 0) {
        n /= 2;
      }
      while(n % 3 == 0) {
        n /= 3;
      }
      while(n % 5 == 0) {
        n /= 5;
      }
      if(n == 1) {
        ugly = 1;
      }
    }
    if(ugly == 1) {
      printf("%d\n", number);
    }
  }
  exit(0);
}

The editor's choice is: Nevin Liber

Please email <francis@robinton.demon.co.uk> to arrange for your prize.

I chose the student code for this critique because there was a point that I wanted to make. The student is more competent than most in so far as coding in C is concerned. Magic numbers are avoided, all uppercase is used for pre-processor constants and uses lower case for other variables. EXIT_FAILURE is used after checking for the correct number of command line arguments fails. However there are a couple of points about the code:

Once the logic error has been dealt with the program illustrates reasonable competence with C and from that respect I would give a good grade. However it still, in my opinion, is poor programming because it is a very heavy handed solution to the problem. That is the main point I wanted to make, there is a great deal more to programming than writing syntactically correct source code that produces the correct answer. So let me tackle the problem from the start.

The definition of an ugly number is one that has no prime factors other than 2, 3 and 5 [that is not how I would have defined an ugly number but that is irrelevant]. What the student has done is to reduce each number to its prime factors (not very efficiently as it happens, but that is another artefact of lack of clarity of thought). Then the code checks to see if any of the factors are other than the specified 2, 3 and 5.

Let us step back and think a little. What the problem requires is that we ignore all factors that are 2, 3 or 5 and see if there are any others. We can simply discard the factors in which we are not interested. That idea leads me to write the following little function:

int remove_factor(int number, int factor) {
  while((number % factor) == 0)
    number /= factor;
  return number;
}

In other words as long as the number is exactly divisible by factor (not a perfect name, can you suggest a better one?) reduce number by dividing by factor.

Now look at that little bit of code and decide if there are any ways in which it could fail. OK, it assumes that neither number nor factor is zero. The reason for failure will be different in the two cases. If number is zero the function is well defined, it simply goes into an infinite loop. If factor is zero we have a divide by zero error. Should remove_factor() handle either of those problems? Doing so is not cost free. It is a design decision, but one that can now be clearly identified and handled as the programmer chooses.

We can use this little function to determine if a given number is an ugly one:

bool is_ugly(int number) {
  number = remove_factor(number, 2);
  number = remove_factor(number, 3);
  number = remove_factor(number, 5);
  return (number == 1);
}

You might not want to use bool as the return type but that is your choice. Again there is the issue of whether number is a suitable candidate. We have two issues here: it must not be negative and it must be a compound number (i.e. it must have more than one prime factor). As the second is a defining property of being 'ugly' I think it should be dealt with here. So our function gets modified to:

bool is_ugly(int number) {
  if(number == 4) return TRUE;
  // direct test for smallest composite
  if(number < 6) return FALSE;
  number = remove_factor(number, 2);
  number = remove_factor(number, 3);
  number = remove_factor(number, 5);
  return (number == 1);
  // only 2, 3 and 5 were factors
}

Note that the second test deals with all the other cases (number being zero or negative) and also deals with one of the possible problems with remove_factor(). The other problem with remove_factor() is eliminated because we haven't actually tried to remove zero as a factor. Deal with problems at an appropriate level and assume that the caller of a function knows the pre-conditions (because they have been documented in the manual.)

Now I am ready to write my program:

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

int main(int argc, char *argv[]){
  if(argc != 3) {
    bad_command_line_args("Wrong number");
    return EXIT_FAILURE;
  }
  int first = atoi(argv[1]);
  int last = atoi(argv[2]);
  if((first < 1) || (first > last)) {
    bad_command_line_args("Bad range");
    return EXIT_FAILURE;
  }
  for(int i = first; i <= last; ++i) {
    if(is_ugly(i)) printf("%d\n", i);
  }
  return EXIT_SUCCESS
}

I haven't supplied the code for bad_command_line_args() but writing it should be trivial, certainly for a student who wrote the code we are critiquing. Note that this program is considerably shorter than the original even though it does a great deal to trap errors. All the code conforms to the C99 Standard though some, such as late declarations does not conform to the older standard.

The interesting feature of the above code is that it uses less C technology than the original yet, I hope you will agree, it is a much better program. One of the arts of programming is to use simple things well.

I'm newbie to C++ and I would like to know which would be the best (elegant and correct) solution for the following small (string) read problem with gets.

#include <iostream>
using namespace std;
#include <cstdio>
main() {
  int n;
  int waste; // needs this to work
             // (read) properly!!
  char name[51];
  cout << "Enter any integer number...\n";
  cin >> n;
  cout << "Enter your name...\n";
  cin >> waste; // 'gets' does not read the
                // name without this line!!
  gets(name);
}

Mixing C and C++ functions doesn't seem the best way to write this program. Please provide alternatives, taking also into account its security implications.

If I enter 23 and 5 the answer should be 23 * 5 = 115 my answer is off by five or whatever number 2 is. I was told I am not including the first two numbers in the loop. I thought when I cin the numbers it is including them. Does anyone have any suggestions on how I can fix this?

#include<iostream>
#include<iomanip>
#include<string>

using namespace std;

int main()
{
  while (1) {
int num1, num2, total = 0;
cout<<"Enter two numbers: ";
cin>>num1>>num2;
while (num1 != 1)
cout<<setw(5)<<num1<<setw(5)<<num2<<endl;
  num1 /= 2;
  num2 *= 2;
  if (num1 % 2 != 0)
    total += num2;
}
  cout<<"the total is "<<total <<endl;
} //End While 1
return 0;
}

There are numerous errors in both the code and the student's understanding. Please address these comprehensively.