passing the point just once.

[jimmy5023]

i want to write a program that only pass through a city ONCE, and here's my approach.

let's say there are 5 city, A B C D and E. and the size = 5

so my approach is first declare num and each time i pass a city i add 1 and lastly write an if statement

if (num != size) 
    cout<<"this route is not valid";
    break;
else 
cout<<"congrats";
break;

[quirkyusername]

and the question is...?

[jimmy5023]

the question is, how to code it? how to code "if each time i pass one city i add one" <-- into c++ code.

[Mathhead200]

Something like this?

struct City {
  int passes = 0;
  ...
} A, B, ...;

int main() {
  ...
  A.passes++;
  if( B.passes > 1 ) ...
  ...
}

[jimmy5023]

ehh... maybe... i don't really understand what your code means. But from teh look of it seems you know what i meant.
and the if statemnet is not b.passes>1 is b.passes!="number of cities".

[Mathhead200]

B.passes refers to the number of times city B was passed. You should do that for all the cities, B was just an example...

Look at http://cplusplus.com/doc/tutorial/structures and http://cplusplus.com/doc/tutorial/classes for more about OOP, i.e. "struct" or "class"

[jimmy5023]

i do have knowledge on structs and class. However, i don't think using it will work, that is because the number of city is SET, and if i do a general struct city and create my own city, how am i suppose to know how many cities are there in the first place?
so you are suggesting

struct city
{
int pass = 0; //i just copy yours i don't really know what is this for

};

int main(void)
{
city A;//declare city A
A.passes++;//yea, so it makes sense you incrementing it
  if( A.passes > 1 )//why ">1"? isn't is suppose to compare to the number of city? which in this example it should be 5. 
}

[userulluipeste]

Congratulations, jimmy5023! You just made it to the top! And if you may wander how, check out this:
http://en.wikipedia.org/wiki/Travelling_salesman_problem

[jimmy5023]

I know the TSP, i am trying to solve it =.=. And my rules are different from the TSP too. Erm anyways can you answer my previous post?


i do have knowledge on structs and class. However, i don't think using it will work, that is because the number of city is SET, and if i do a general struct city and create my own city, how am i suppose to know how many cities are there in the first place?
so you are suggesting

struct city
{
int pass = 0; //i just copy yours i don't really know what is this for

};

int main(void)
{
city A;//declare city A
A.passes++;//yea, so it makes sense you incrementing it
  if( A.passes > 1 )//why ">1"? isn't is suppose to compare to the number of city? which in this example it should be 5. 
}

[Zeillinger]

If you know the number of cities in advance just create the same number of city instances. Although, you don't necessary need structures if you create an array of booleans/integers where each element is a city - onces you pass that city the value for the city becomes true/1 etc.

[userulluipeste]

A way of solving this using the so-called back-tracking would mean
- Having an unique identifier for the cities (you don't need a "pass" counter if pass only once is required, and not the minimum of passes). An enumeration of cities should suffice.
- Having the relations among cities (distances). If you have a global access for each of distance and not restricted to identify ("discover") new distances only reaching a city, then a simple array NxN where N is the total number of cities would do the job perfectly.
- A stack with cities that you already went trough. Actually you'll use it as a LIFO object, but you'll need access to all of the object's collection. So don't want to consider stl stack. You may use (a) stl list instead. It would be an list of city enumerations.
- If you want to remember the longest way (the one with the most of the cities visited), you consider having another copy of the visited-cities list, for storing the result.
- Finaly, you need a recursive function that receives as a parameter a city. This function should have access (obviously) to the distances among the cities and to that "have been in the X city" stack. That access should be granted through additional parameters or should be made globally available.

Let's say you have have 3 cities:

enum Cities { CITY_A, CITY_B, CITY_C, NR_OF_CITIES }; //3 cities defined
int vDistances[NR_OF_CITIES][NR_OF_CITIES] = { 0, 1, 2,
                                               1, 0, 3,
                                               2, 3, 0};
list<Cities> beenThere;
list<Cities> finalRouteResult;

In some "TrackCity" recursive function, you'll have to:
- Identify the available options (that mean in our case tracking the City's row, like for CITY_B having each vDistances[CITY_B][n] in a loop with 'n' from CITY_A to CITY_C. If a distance is 0, like you said, would mean the same city, an option that you'll have to ignore.
- For each considered city, inside the tracking distances loop you'll have a second loop traking this time the stack of visited cities. If the current considered distance would be one between the current city and one already visited, ignore it. Overwise - go recursively to the new city.
- If reached a point when from the current city you can't go anywhere else, consider remembering the way in that copy of visited-cities list. That would mean taking care and do that only when the current number of visited cities is no less than the one previously remembered.

A model for the recursive function:

void TrackCity (Cities currentCity)
{
  int nCounter;
  list <Cities>::iterator it;
  bool bContinueRecursively;

  //register the current city in the stack
  beenThere.push_front(currentCity);

  for (nCounter = CITY_A; nCounter < NR_OF_CITIES; nCounter++)
  {
    if (vDistances[currentCity][nCouter] > 0)  //check valid distance
    {
      bContinueRecursively = true;  //the default is to go further...

      for (it = beenThere.begin(); it != beenThere.end(); it++)
        if (currentCity == *it)
          bContinueRecursively = false;  //...until proven wrong to do so

      if (bContinueRecursively == true)
      {
        TrackCity(nCouter);  //follow the white rabbit into a rabbit hole
                             //...which means going recursively to another city
      }
      else  //nowhere to go, so consider remembering the path
      {
        if (beenThere.size() > finalRouteResult.size())
          finalRouteResult = beenThere;
      }
    }
  }

  beenThere.pop_front();
}

These being said, I hope I've been helpful in some degree and you may have now some reference for either further study or implementation.

[jimmy5023]

Thank you. I really appreciate your help userulluipeste, but there are few syntax i am not fimliar with

1) line 4 list <Cities>::iterator it; does?
2) line 5 push_front() is not part of beenThere.
3)what does the "b" stands for for bContinueRecursively?
4) what does list<cities> means?

[userulluipeste]

1) Iterators are (third party) objects in between the stl list container and your objects. Iterators are kind of smart pointers (or I'd rather say smart references) that you'll probably hear of somewhere later in your experience. All you have to know now is that you need them in order to iterate through containers. You might actually escape them thanks to recent changes in the C++ standard (C++0x), that allow you to do a enhanced "for" to get each of the elements you put in the container list.
2) That's funny! Although I've written blind that piece of code (and made minor mistakes with 'nCounter' identifier), now that I'm checking it out I can't reproduce your problem with 'push_front'. That function is definitely a member of list template:
http://www.cplusplus.com/reference/stl/list/push_front
and 'beenThere' object is a such list object!
3) It's just part of Microsoft's notation or guide style. The prefix 'b' in the 'bContinueRecursively' identifier comes from 'boolean' - a way of making things easier to read. The same is with 'n' ('nCounter') coming from 'number', later you might get the chance to find 'p' as prefix for pointers, 's' - for strings, etc.
4) I might mis-estimated your level and made you confused. I suggest to follow the site's tutorial: http://www.cplusplus.com/doc/tutorial
There you'll find "Templates" at the "Advanced Concepts" group. After familiarizing with templates, check out the "standard" templates of C++: http://www.cplusplus.com/reference/stl - list is just one of them.

[jimmy5023]

oh.,. it's a template i learn template in a form of

tempate <T class>
instead of list <xxxx> BUt thanks i will try to follow things up now.

[Mathhead200]

//I was saying you create 5 Cities
City A, B, C, D, E;
//Now (A.passes == 0 && B.passes == 0 && ... && E.passes == 0) is true.
// Then as you pass a city, you increment it's passes value.
// Finally you check each city to see if it has been passed no more then once.
// Also try storing them in an array so you can utilize for loops
City cities[5];

[jimmy5023]

yes.... mathead200 "Also try storing them in an array so you can utilize for loops" in my previous post i did insist to store in an array and it seems u figure out what i was planning to code too lol