3

I was inspired to write a small C++11 program that would generate so-called Conway numbers, or 'look and say' numbers. Essentially, given the nth term, e.g. 11112, the next is simply the pronunciation of the former term; in our case 4112, because there were 4 1's and only one 2. Another example: '13' to '1113'.

The following is the source code of the program in its entirety for completeness (omit stdafx.h include if not compiling with MS Visual Studio):

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

void print_usage(){

    cout << endl << "Conway Number Generator";
    cout << endl << "Arguments: initializer followed by nth term to be printed" << endl;
}

string say(string s){

    // Returns string said phonetically
    // e.g. '111' becomes '31'

    unsigned int sz = s.size();

    if (sz == 1){
        s.insert(0, "1");
    }
    else{
        s.insert(0, to_string(sz));
        s.erase(2, sz-1);
    }
    return s;
}

string get_next(string x){

    // Returns next term in Conway sequence

    unsigned prev_point = 0;
    vector<string> grp;
    string tmp;
    tmp.resize(x.size());

    // Organize sequence in group of identical consecutive characters

    for (unsigned int i = 0; i < x.size(); ++i){

        if (i != x.size() - 1){

            if (x.at(i) != x.at(i + 1)){
                tmp.assign(x, prev_point, i - prev_point);
                grp.push_back(tmp);
                prev_point = i + 1;
                tmp.clear();
            }
        }
        else if (i != 0){

            if (x.at(i) != x.at(i - 1)){
                tmp = x.at(i);
                grp.push_back(tmp);
                tmp.clear();
            }
        }
    }

    // Phonetically say each group

    // Could use a lambda: transform(begin(grp), end(grp), begin(said_grp)[=](string s){return say(s);});
    // if I create a new vector<string> said_grp to copy in
    // That didn't help the runtime error

    for (auto& i : grp)
        i = say(i);

    // Join each vector<string> entry into a single string

    string next_seq;
    next_seq = accumulate(begin(grp), end(grp), string(""));
    return next_seq;
}

string conway(string init, int n){

    // Print out nth Conway term
    // starting sequence at init

    for (int i = 1; i <= n; ++i)
        init = get_next(init);
    return init;
}

int main(int argc, const char* argv[]){

    if (argc < 3){
        print_usage();
        return 0;
    }
    cout << endl << "Conway number: " << conway(argv[1], stoi(argv[2])) << endl;
    return 0;
}

The general approach:

  1. Accept two arguments: the first term of the Conway sequence, and an integer n choose to compute the nth term of that sequence.
  2. The function conway(...) loops through applying get_next() to the initial string n times.
  3. The function say() 'pronounces' the numbers.
  4. get_next() functions by splitting the entire number into consecutive identical numbers; each is then transformed by say().

The issue I'm having is an error, std::out_of_range, from the return statement of my say() function. However, I can recall testing say() alone with various inputs, and it never caused an exception. I must be using it incorrectly somehow. As I note in the code comments, I tried using the STL transform instead of a for loop with a lambda before, same error.

Note: to those interested in the Conway sequence, see the original paper by Conway. They admit some interesting properties, and it appears they give rise to a constant known as Conway's constant which was shown to be algebraic.

user45389
  • 81
  • 8
  • 2
    Assigning to `i` in that loop does nothing because the type is `auto` (no reference) rather than `auto&` (reference) – hlt Aug 15 '14 at 20:58
  • `std::out_of_range` is probably thrown in `s.erase(2, sz-1);` when `sz < 2` (cf. [here](http://en.cppreference.com/w/cpp/string/basic_string/erase)). Because you check for `sz == 1` the problem might be that you pass an empty argument to `say` at some point. – hlt Aug 15 '14 at 21:02
  • `tmp = x.at(i);` are you assigning `char` to a `string` here? – Ashalynd Aug 15 '14 at 21:49
  • @Ashalynd: The other way around. Should be alright. – AndyG Aug 15 '14 at 21:56
  • @Ashalynd: Just to be safe I'll write `to_string(x.at(i))`. – user45389 Aug 15 '14 at 21:59
  • @hlt: I've added a case for `sz == 0` now, which will cause `say()` to return an empty string given an empty input, but now my program isn't outputting the right numbers. I suspect something is wrong in `get_next()`. – user45389 Aug 15 '14 at 22:04
  • This is the type of problem that really benefits from a debugger. If I may offer one suggestion: Don't you mean to say `tmp.assign(x, prev_point, i + 1 - prev_point);`? That is if your input is `13`, on your initial go around `i = 0` and `prev_point=0` so the way you currently have it, you are assigning a zero length string to tmp, whereas you mean to assign a single character string – user3288829 Aug 16 '14 at 03:58
  • @user3288829: I've used a debugger, but couldn't quite resolve the issue. I'll try your suggestion. – user45389 Aug 16 '14 at 08:04
  • You don't need `#include "stdafx.h"` in MS Visual Studio builds either, which is why there was no point in including it at all. – AnT stands with Russia Mar 31 '17 at 06:59

2 Answers2

2

As I mentioned in the comments, this is the perfect sort of question to solve with a debugger. 80+ (very smart) people have looked at your code and no one was able to solve it completely just by looking (though @hlt got much of it). After a lit bit of debugging, I think I've caught the rest. Let's look at the pieces.

Like hlt said, you need auto& in your range-based for loop in get_next(), otherwise you're never actually changing grp and you keep getting your original number back. See this question for more info.

Also, thanks to hlt, you had a piece of missing logic regarding zero length string inputs. However, there's another missing piece in your get_next() function. Take for example the input ./conway 111 2. The number 111 would never actually get put into grp because all the characters are the same, so neither if (x.at(i) != x.at(i + 1)) nor if (x.at(i) != x.at(i - 1)) would ever evaluate to true; as such, you would get an empty string as the result. The missing piece is included below.

for (unsigned int i = 0; i < x.size(); ++i){

    if (i != x.size() - 1){

        if (x.at(i) != x.at(i + 1)){
            tmp.assign(x, prev_point, i+1 - prev_point);
            grp.push_back(tmp);
            prev_point = i + 1;
            tmp.clear();
        }
    }
    else if (i != 0){

        if (x.at(i) != x.at(i - 1)){
            tmp = x.at(i);
            grp.push_back(tmp);
            tmp.clear();
        }
        else
        {
            tmp.assign(x, prev_point, i+1 - prev_point);
            grp.push_back(tmp);
            tmp.clear();
        }
    }

The last issue I mentioned in my comment above, and included in the code here. To assign a substring of the correct length to tmp, you need i+1-prev_point rather than i-prev_point.

I said to start that I think I've caught the rest of the bugs, but that may not be true. I'd recommend writing some tests with a large number of numbers with different characteristics (eg 1, 12121212, 0000, 1222, 2221, etc) and their expected results. If any of them give unexpected results, then its time to go back to the debugger.

Community
  • 1
  • 1
user3288829
  • 1,266
  • 15
  • 26
  • I'll add, though, that I actually rather enjoyed debugging this. After a week of dealing with bloated data structures and convoluted logic in some of our alpha code at work, this was quite therapeutic – user3288829 Aug 16 '14 at 21:40
  • Thank you for your help, program now works as intended. Will write a fuzzer to test it now. – user45389 Aug 17 '14 at 14:35
0

I have looked at your source code, and noticed that your function get_next() can be simplified. I have replaced it with the following version:

string get_next(const string & inStr) {
    string result;
    int len = inStr.size();
    int count = 0;
    // Loop over non-duplicates
    for (int i = 0; i < len; i += count) {
        // Calculate total number of duplicates for inStr[i]:
        for (count = 0; i+count < len; count++) {
            if (inStr[i+count] != inStr[i]) {
                break;
            }
        }
        // Append count + non-duplicate (count and say)
        result += to_string(count) + inStr[i];
    }
    return result;
}

When I run the new code with “1” as the initial string and 5 as n, I get the following output result:

Conway number: 312211

which is correct: 1 -> 11 -> 21 -> 1211 -> 111221 -> 312211

No debugging is needed. Hope this helps.

jonathanzh
  • 1,346
  • 15
  • 21