Fairly simple program, Fairly simple programmer (C++)

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Sir_Elderberry
Posts: 4206
Joined: Tue Dec 04, 2007 6:50 pm UTC
Location: Sector ZZ9 Plural Z Alpha
Contact:

Fairly simple program, Fairly simple programmer (C++)

Postby Sir_Elderberry » Sat Jan 22, 2011 2:04 am UTC

I'm trying to build a program that will automatically assign targets in a game of assassins, as explained in the second paragraph of this blog post. This compiles, but at first it was giving me a segfault as soon as it tried to read the file. Honestly, I'm not really much of a programmer--I knew some basic C++ a few years ago and I've googled enough to build this, so I'm not sure how to take that error and turn the diagnosis into a cure. Now when I try to run it it just runs and runs as if it isn't calling buildroster at all, and the IDE doesn't say it's calling buildroster, either. Halp?

Code: Select all

/*
 * File:   main.cpp
 * Author: zach
 * Purpose: Automate target assignment and notification for competitors
 * Created on January 20, 2011, 5:57 PM
 */

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
using namespace std;
// Now that that's out of the way I'm going to define the struct
// This struct allows us to define everything about a person in the game
    struct person {
        string firstlast;
        string email;
        bool hastarget;
        bool haskiller;
        int target;
        int killer;
        int number;
    };
    int population;
    string filename;
    person competitors[50];
/*I really don't know much about scope and the like, admittedly. So this
 * might not be the correct way to get everything declared--defining the
 * size of that array by a variable the program doesn't know about yet
 * feels especially fishy. But there you have it.*/
int buildroster(string file){
    //This takes our files, properly formatted, and builds them into structs
        ifstream roster;
        roster.open(file.c_str());
    int i=0;
    for (i=0;i<population;i++){
    while (roster.good()){
        competitors[i].hastarget = 1;
        competitors[i].haskiller = 1;
        getline(roster, competitors[i].firstlast);
        getline(roster, competitors[i].email);
        //In order: Set that it has no target, no killer, and give it
        // the name and email
        }
    }
    roster.close();
    return 0;
}
int findtarget(int i){
    int target;
    srand((unsigned)time(0));
    while (i=target || competitors[target].haskiller){
        target = rand()%(population+1);
    }
    //While loop continues to execute until random function delivers a
    //target that is neither identical to killer nor has a killer already
    return target;
}
int buildprofile (int n){
        competitors[n].target = findtarget(n);
        competitors[n].hastarget = true;
        competitors[competitors[n].target].haskiller = true;
        competitors[competitors[n].target].killer = n;
        return competitors[n].target;
}
int main() {
    int next;
    // Ideally I'd like to be able to give this program to someone else
    // So I'm avoiding hardcoding things like population or filename
    cout << "Please enter the number of competitors." << endl;
    cin >> population;
    cout << "Please enter the filename of the competitors list." << endl;
    cin >> filename;
    buildroster(filename);
    //buildroster takes human-format data and puts it into person structure
    //After that's done, we just need to set all those values correctly
    //Can't use a simple for loop here because we need to build a circle
    //So I'm going to write a function that sets the values, and the for loop
    //will run that function the correct number of times, but it'll be passed
    //the value of the last target.
    for (int i=0;i<population;i++){
        if(i=0){
            next = buildprofile(0);
        }
        else {
            next = buildprofile(next);
        }
        //So for the first iteration, it builds the profile for the first name
        //For all others, it builds the profile of the previous one's target
        //It builds as many profiles as there are players
    }
    //Not sure this will be in final--for ideal ethics, it won't
    ofstream assignments("killers.txt");
    for (int i=0;i<=population;i++){
        assignments << competitors[i].firstlast << " is killing ";
        assignments << competitors[competitors[i].target].firstlast << endl;
    }
}
http://www.geekyhumanist.blogspot.com -- Science and the Concerned Voter
Belial wrote:You are the coolest guy that ever cooled.

I reiterate. Coolest. Guy.

Well. You heard him.

_Axle_
Posts: 253
Joined: Fri Sep 24, 2010 7:33 pm UTC

Re: Fairly simple program, Fairly simple programmer (C++)

Postby _Axle_ » Sat Jan 22, 2011 2:57 am UTC

Up front, it looks fine and I copy/pasted into a Visual Studios solution and it ran fine. Something you should do is when you open the file, do a check after to see if it loaded correctly. Since, if would be flagged as bad and then just fall through the while loop and return 0. You don't handle if the file doesn't exist, either from wrong location or typed the name in wrong.


Not to be picky, You probably shouldn't have a static array of 50 people, when you allow a dynamic number as entry. What if a person enters 51 or more? Might not be a major issue, but something to think about.
Yakk wrote:Computer Science is to Programming as Materials Physics is to Structural Engineering.

User avatar
Area Man
Posts: 256
Joined: Thu Dec 25, 2008 8:08 pm UTC
Location: Local

Re: Fairly simple program, Fairly simple programmer (C++)

Postby Area Man » Sat Jan 22, 2011 3:08 am UTC

Took just a quick look, didn't try building, but...
1. Use a vector instead of an array, that way you use vector.size() instead of asking for and using population.
and 2. check out the second while loop and that last if. I recommend using a -Wall switch (or equivalent for your compiler).
Bisquick boxes are a dead medium.

User avatar
Sir_Elderberry
Posts: 4206
Joined: Tue Dec 04, 2007 6:50 pm UTC
Location: Sector ZZ9 Plural Z Alpha
Contact:

Re: Fairly simple program, Fairly simple programmer (C++)

Postby Sir_Elderberry » Sat Jan 22, 2011 3:08 am UTC

I tried to do competitors[population] but I got an error. Maybe I was doing something else wrong with the declaration.

Anyway! You say it ran for you? That's odd. I'll look at this more tomorrow and see what's going on.

@Area Man: Thanks. I'll look into that.
http://www.geekyhumanist.blogspot.com -- Science and the Concerned Voter
Belial wrote:You are the coolest guy that ever cooled.

I reiterate. Coolest. Guy.

Well. You heard him.

_Axle_
Posts: 253
Joined: Fri Sep 24, 2010 7:33 pm UTC

Re: Fairly simple program, Fairly simple programmer (C++)

Postby _Axle_ » Sat Jan 22, 2011 3:14 am UTC

Sir_Elderberry wrote:I tried to do competitors[population] but I got an error. Maybe I was doing something else wrong with the declaration.

Anyway! You say it ran for you? That's odd. I'll look at this more tomorrow and see what's going on.

@Area Man: Thanks. I'll look into that.


Yeah, you can't use a static array with a variable like that. You can do something like

Code: Select all

person* competitor;

// many lines later after population is filled out

competitor = new person[population];


Or use the stl vector.

Yeah, Visual Studios 2008, in debug mode. I stepped through with a dummy .txt file. If it finds it, it does the loop fine. If it doesn't exist, it just breaks the while loop on the check and returns 0.
Yakk wrote:Computer Science is to Programming as Materials Physics is to Structural Engineering.

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: Fairly simple program, Fairly simple programmer (C++)

Postby kmatzen » Sat Jan 22, 2011 4:12 am UTC

int target;
srand((unsigned)time(0));
while (i=target

You want i == target, right? I think that makes sense based on your comment. You don't want the target equal to the current individual. Also, on the first iteration, target is uninitialized, so there is no guarantee what is going to happen. Finally, when target is non-zero, the condition in the while loop evaluates to true since this test is incorrect.

What do you plan on doing differently with haskiller and hastarget? They are both set true at the same time, so they seem to be equivalent even though, haskiller doesn't really mean they have a killer yet if you think of what happens to person 0.

I actually don't understand why you set some bools to 1 in one place and true in another. Why the inconsistency?

for (i=0;i<population;i++){
while (roster.good()){
competitors[i].hastarget = 1;
competitors[i].haskiller = 1;
getline(roster, competitors[i].firstlast);
getline(roster, competitors[i].email);
//In order: Set that it has no target, no killer, and give it
// the name and email
}
}

I don't quite understand this. Is it one person per file or are all people in the same file? while(roster.good()) will just keep going until the stream is no longer good. Every person will get the same value of i. Finally, I don't understand why the bools are set to 1. Shouldn't they be false? I mean, they don't have targets and killers yet.

User avatar
Sir_Elderberry
Posts: 4206
Joined: Tue Dec 04, 2007 6:50 pm UTC
Location: Sector ZZ9 Plural Z Alpha
Contact:

Re: Fairly simple program, Fairly simple programmer (C++)

Postby Sir_Elderberry » Mon Jan 24, 2011 6:01 pm UTC

I've fixed some stuff--that previous while loop was bad. Anyway, I tried to implement this all with vectors, but I'm still getting segfaults. Dummying out particular lines and using couts to check which line is causing it tells me it seems to happen as soon as I try to modify any of the variables in my vector. It's crashing in buildroster, right after "a." I think I'm just mishandling vectors here--advice?

Spoiler:

Code: Select all

/*
 * File:   main.cpp
 * Author: zach
 * Purpose: Automate target assignment and notification for competitors
 * Created on January 20, 2011, 5:57 PM
 */

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include <vector>
using namespace std;
// Now that that's out of the way I'm going to define the struct
// This struct allows us to define everything about a person in the game
    struct person {
        string firstlast;
        string email;
        bool haskiller;
        int target;
        int killer;
        int number;
    };
    string filename;
vector<person> competitors;
/*I really don't know much about scope and the like, admittedly. So this
 * might not be the correct way/place to get everything declared.
 * But there you have it.*/
int buildroster(string file){
    //This takes our files, properly formatted, and builds them into struct
    fstream roster(file.c_str(),ios::in);
    int i=0;
    while (roster.good()){
        cout << "a" << endl;
        competitors[i].haskiller = false;
        cout << "b" << endl;
        getline(roster, competitors[i].firstlast);
        cout << "c" << endl;
        getline(roster, competitors[i].email);
        cout << "d" << endl;
        cout << competitors[i].firstlast << endl;
        cout << competitors[i].email << endl;
        cout << i << endl;
        i++;
        //In order: Set that it has no killer, and give it
        // the name and email. Then iterate the loop.
    }
    roster.close();
    return 0;
}
int findtarget(int i){
    int target = i;
    srand((unsigned)time(0));
    while (i==target || competitors[target].haskiller){
        target = rand()%(competitors.size()+1);
    }
    //While loop continues to execute until random function delivers a
    //target that is neither identical to killer nor has a killer already
    return target;
}
int buildprofile (int n){
        competitors[n].target = findtarget(n);
        competitors[competitors[n].target].haskiller = true;
        competitors[competitors[n].target].killer = n;
        return competitors[n].target;
}
int main() {
    int next;
    int retry = 1;
    int i;
    // Ideally I'd like to be able to give this program to someone else
    // So I'm avoiding hardcoding things like population or filename
    while (retry == 1){
        cout << "Please enter the filename of the competitors list." << endl;
        cin >> filename;
        buildroster(filename);
        if (competitors.size() == 0){
            cout << "No players found. ";
            cout << "Press 1 to specify different file." << endl;
            cout << "Press any other key to exit." << endl;
            cin >> retry;
        }
        else{
            cout << competitors.size() << " players found." << endl;
            cout << "Building assignments..." << endl;
            //buildroster takes human-format data and puts it into person structure
            //After that's done, we just need to set all those values correctly
            //Can't use a simple for loop here because we need to build a circle
            //So I'm going to write a function that sets the values, and the for loop
            //will run that function the correct number of times, but it'll be passed
            //the value of the last target.
            for (int i=0;i<competitors.size();i++){
                if(i=0){
                    next = buildprofile(0);
                }
                else {
                    next = buildprofile(next);
                }
                //So for the first iteration, it builds the profile for the first name
                //For all others, it builds the profile of the previous one's target
                //It builds as many profiles as there are players
            }
            //Not sure this will be in final--for ideal ethics, it won't
            ofstream assignments("killers.txt");
            for (int i=0;i<=competitors.size();i++){
                assignments << competitors[i].firstlast << " is killing ";
                assignments << competitors[competitors[i].target].firstlast << endl;
            }
            cout << "Assignments printed to killers.txt." << endl;
        }}
}
http://www.geekyhumanist.blogspot.com -- Science and the Concerned Voter
Belial wrote:You are the coolest guy that ever cooled.

I reiterate. Coolest. Guy.

Well. You heard him.

User avatar
Area Man
Posts: 256
Joined: Thu Dec 25, 2008 8:08 pm UTC
Location: Local

Re: Fairly simple program, Fairly simple programmer (C++)

Postby Area Man » Mon Jan 24, 2011 6:33 pm UTC

You must add a person to the vector using push_back() before you can access it using [].
Bisquick boxes are a dead medium.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Fairly simple program, Fairly simple programmer (C++)

Postby Yakk » Mon Jan 24, 2011 6:58 pm UTC

Arrays of size n do not have a valid element at [n].

They start at [0] and end at [n-1].

Second, learn to check fenceposts. This means that each and every time you access an array, make sure that your array index is valid. No, each and every time. You aren't doing anything where the performance hit is important enough to not do this, unless your code takes days to run or you are having thousands of people use your product (or its output).

Note that your program takes time quadratic in your player count. The last player keeps on randomly trying players until it finds the one and only valid one. This ... is less than optimal.

For a more sane approach:
1> Build the list of players.
2> Shuffle the list of players.
3> Each player is killing the one after them in the shuffle.

This is a bit annoying, in that shuffling is hard to do. So an easier method:
1> Build an input list of players.
2> Build an empty output list of players.
3> While list 1 isn't empty, take a random player from list one and put it into list 2.
4> Profit.
This finishes in O(n) time and is easier to code than either of the above options.

Here is a framework for the final design:

Code: Select all

// Idenification information:
struct Identity {
   string name;
   string email;
};

// a player is an identity
// plus a prey and preditor
struct Player:Identity {
   identity preditor;
   identity prey;
};

typedef std::vector<identity> Players;
typedef std::vector<identity> Game;

bool get_players( Players& result, std::string filename );
Players shuffle_players( Players players );
void make_game( Game& result, Players const& players );
bool prompt_filename( string& result, bool previous_error );
void output_game( Game const& game );

int main( int argc, char** argv )
{
   string filename;
   bool abort = false;
   if (argc > 1)
   {
      filename = argv[1];
   } else {
      abort = prompt_filename( filename, false );
   }

   Players players;

   while(!abort) {
      bool read_result = get_players( players, filename );
      if (!read_result)
      {
         abort = prompt_filename( filename, true );
      }
   }

   if (!abort) {
      Players shuffled = shuffle_players( players );
      Game game;
      make_game( game, shuffled );
      output_game( game );
   }
}

Left unwritten are these functions:

Code: Select all

bool get_players( Players& result, std::string filename );
Players shuffle_players( Players players );
void make_game( Game& result, Players const& players );
bool prompt_filename( string& result, bool previous_error );
void output_game( Game const& game );

There are a couple of things I did differently than you.

First no global variables.

Second, I allowed command-line filename entry.

Third, the type of my variables describes their state. Unless an abort bool is set, a variable of type Players is always a valid variable of type Players. I don't leave uninitialized data around.

The data flow is mostly:
file -> players -> shuffled -> game -> output
Each step is simple. We read the data from the file into the players vector (using push_back).
We then write the really simple shuffle function. To do fast shuffling, you'll want to pick a random element from the input vector, push_back on the output vector with it, then swap it for the end element on the input vector and pop the last element off the input vector. (deleting from the middle of a vector is slow).

Ie:

Code: Select all

Players shuffle( Players input )
{
  Players retval;
  while(!input.empty())
  {
    int index = Rand()%input.size();
    Assert(index >= 0);
    Assert(index < players.size());
    Player player = input[index];
    retval.push_back(player);
    std::swap( input[index], input.back() );
    input.pop_back(); // or resize(input.size()-1) if that isn't valid, I forget
  }
  return retval;
}

Also remember to make sure your random number generator is actually random. :)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 8 guests