3
\$\begingroup\$

For anyone familiar with the UVa Programming Challenges website, I have started experimenting with some of the basic challenges. I was hoping to get critique for the code I wrote for "The 3n+1 Problem" (Problem ID 100).

The run-time for this submission was 0.040 and my best submission was only 0.036. Looking at the scoreboard I have seen that many people have attained 0.000 runtime scores. I would really like some feedback for any/all of the following:

  • My choice of "algorithm"
  • C++ Implementation [code (re-)structure]
  • How did others attain the amazing runtime scores? Math trick(s) ?

To help with code readability: My code calculates the length of a sequence with compute() and stores the result in a table (vector of sequence lengths which is indexed by the value).

Along the way, any intermediate values encountered are saved on a temporary 'stack', and when the final result is computed, all the values in the list are also entered into the table. For example, for compute(8) the sequence becomes 8 4 2 1.

So, table[8] = 4; table[4] = 3; table[2] = 2; At the beginning of compute(), any nonzero value in the table causes it to return the length immediately.

Besides reducing table size, and using a loop/goto instead of recursion, I can't think of a way to improve my current approach. For curious readers, before I implemented the intermediate value stack, my best run-time of 0.036 was from using this table approach but 'seeding' the table with values 1 to 200 before accepting user input, a la start(1,200).

Thanks!

/// The 3n+1 Problem
// Consider the following algorithm to generate a sequence of
// numbers. Start with an integer n. If n is even, divide by 2. If n
// is odd, multiply by 3 and add 1. Repeat this process with the new
// value of n, terminating when n = 1. For example, the following
// sequence of numbers will be generated for n = 22:
//
// 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
//
// It is conjectured (but not yet proven) that this algorithm will
// terminate at n = 1 for every integer n. Still, the conjecture holds
// for all integers up to at least 1, 000, 000.  For an input n, the
// cycle-length of n is the number of numbers generated up to and
// including the 1. In the example above, the cycle length of 22 is
// 16. Given any two numbers i and j, you are to determine the maximum
// cycle length over all numbers between i and j, including both
// endpoints.
//
// Input
//
// The input will consist of a series of pairs of integers i and j,
// one pair of integers per line. All integers will be less than
// 1,000,000 and greater than 0.
//
// Output
//
// For each pair of input integers i and j, output i, j in the same
// order in which they appeared in the input and then the maximum
// cycle length for integers between and including i and j. These
// three numbers should be separated by one space, with all three
// numbers on one line and with one line of output for each line of
// input.

#include <iostream>
#include <vector>

template<typename T = int>
class BlackBox 
{     
public:
  BlackBox(T maxsize) : tablesize_(maxsize)
  {
    table_ = std::vector<T>(maxsize, 0);
    // Seed the table for values 0 and 1
    // Note: 0 treated as odd=> 0: 3*(0) + 1 => 1
    // Sequence 0 1 => length = 2
    table_[0] = 2;
    table_[1] = 1;
  }
  ~BlackBox()
  {  }

  void print()
  {
    std::cout << current_ << " ";
  }

  void printn()
  {
    std::cout << "\n";
  }

  // compute the length of the sequence started from 'current' if not
  // found in the table, we will compute the sequence storing each
  // value on a 'stack' so we can update it along with the final value
  // sequence S=>
  // compute(S[0]) => length(S)
  // compute(S[1]) => length(S) - 1
  // ...
  // compute(S[n-1]) => 1

  std::size_t compute(T current)
  {
    std::size_t count = 0;

    if (current < tablesize_ && table_[current]) {
      //std::cout << "=> " << current << " ";
      return table_[current];
    }

    // Not in table, increment operation count and
    // perform at least one operation
    stack_.push_back(current);
    count++;

    //std::cout << current << " ";
    // Detect odd (1s bit)
    if ((current & 0x01)) {
      // odd
      // 3n+1
      current = 3 * current + 1;

      //std::cout << current << " ";
      // After performing an expensive 3n+1 operation
      // the number will always be even, so increase
      // count and perform divide by two operation
      stack_.push_back(current);
      count++;
    }

    // even
    // divide by two
    current = current >> 1;

    return ( count + compute(current) );
  }

  // if compute() put anything on the stack, we will update the table
  // containing the sequence lengths
  // compute(index]) = table[index]
  void update_table()
  {
    T thecount = count_;
    typename std::vector<T>::iterator it = stack_.begin();
    typename std::vector<T>::iterator it_end = stack_.end();

    for ( ; it != it_end; it++) {
      T index = *it;

      if (index < tablesize_)
        table_[index] = thecount;

      thecount--;
    }
  }

  // find the longest sequence over the range [start, end]
  void start(T start, T end)
  {
    T index;

    maxcount_ = 0;

    if (end < start) {
      std::swap(start, end);
    }

    for (index = start; index <= end; index++) {
      current_ = index;
      count_ = 1;

      stack_.clear();

      count_ = compute(index);

      if (!stack_.empty())
        update_table();

      if (count_ > maxcount_)
        maxcount_ = count_;
    }

  }

  std::size_t max() { return maxcount_; }

protected:

private:
  std::vector<T> table_;
  std::vector<T> stack_;
  std::size_t tablesize_;
  T input_;
  T current_;
  std::size_t count_;
  std::size_t maxcount_;
};

// usage: ./100
//
// on each line enter a range, n m
// where 0 <= n,m <= tablesize
// the output will be
// n m MAXSEQLENGTH
int main(int argc, char *argv[])
{
// Table size for tracking (FULL SIZE)
  long long const tablesize = 1000000;

// TODO:
// Could consider splitting the table in half since
// for even_num/2 => odd num
// the sequence length is given by:
// table[even_num] = table[even_num/2] + 1
// Potentially good idea?

  BlackBox<long long> box(tablesize);
  long long start;
  long long end;

  while (std::cin >> start >> end) {

    box.start(start, end);

    std::cout << start << " " << end << " " << box.max() << "\n";
  }
  return 0;
}
\$\endgroup\$
1
\$\begingroup\$

This is overly confusing, and things are obscurely named. This is a one-off for a programming contest thingy, so it doesn't seem like it's that important. But I find that organizing my code well helps me think. You might find that's true of you.

Also, you have several fixed sized tables that are very huge. Quite likely unnecessarily so as the short cycle lengths for large numbers indicate that most sequences converge rather rapidly on a common chain. Lastly, you keep a stack of values when no such stack is necessary because the problem description doesn't require you to print out what the chains are. And even if it did, a very slight tweak to the table contents would allow you to easily print out the chains by just following pointers with no stack necessary.

There are other details that seem minor but are actually a big deal. For example, you create an empty vector, then assign it a very large table. This will create two copies of the very large table, and throw away the (rather minimal admittedly) work done to create the empty vector. Since this last is a very specific coding flaw, here's how it would be fixed:

  BlackBox(T maxsize) : table_(maxsize, 0), tablsize_(maxsize)
  {
     // Seed the table for values 0 and 1
     // Note: 0 treated as odd=> 0: 3*(0) + 1 => 1
     // Sequence 0 1 => length = 2
     table_[0] = 2;
     table_[1] = 1;
  }

Lastly, your organization is very confused. You make one class responsible for too many things. There is no need for one class to both handle finding the max value in a range and to compute the cycle lengths.

But, while these issues are important, I can't see that fixing them is going to shave more than about 20% off your time. :-/

\$\endgroup\$
  • \$\begingroup\$ Thanks for your comments; I've reorganized my class to perform only cycle length computation and eliminated the erroneous copy of a large vector. This alone shaved a small amount of time off - to 0.024 \$\endgroup\$ – assem Mar 20 '12 at 6:41
  • \$\begingroup\$ You understand why I use the stack though, right? When length computation finishes, every intermediate 'element' in the chain will be added to the table - not just the value we were hunting for. If I don't maintain that stack of intermediate elements of the 'chain' then i run the risk of performing the same subchain computation twice. Could you explain your comment in more detail about tweaking table contents? \$\endgroup\$ – assem Mar 20 '12 at 6:49
  • \$\begingroup\$ @assem: Now I see. You use it to do something you could do with recursion. Are you sure that's more efficient than recursion? Recursion has a bad rap with regards to efficiency. \$\endgroup\$ – Omnifarious Mar 20 '12 at 15:44
  • \$\begingroup\$ @assem - There is a cheater way to do part of it. __builtin_ctz can count the number of trailing 0 bits in one instruction. This enables you to shift them all out (dividing by a power of 2) in another. And if you analyze the graph carefully, there are a small number of choke points that a significant number of paths pass through. \$\endgroup\$ – Omnifarious Mar 21 '12 at 6:48
  • \$\begingroup\$ Thanks for the tips; I can't seem to get it below 0.020, but I am happy with the current solution. I'll edit my original post to show before and after code! :) \$\endgroup\$ – assem Mar 28 '12 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.