Thread: simple singleton pattern

I've been struggling with this. Let's define a SINGLETON to be a data element that is not repeated immediately before or after itself in the sequence.
I pass most tests. But I'm failing in this one:
a b c c b b b d a
It should return 4 but its returning 3.
I think I'm not granting a point for the first a
I think that my code is a bit of a cheat too ie: going below 0 sometimes.
Wondering if someone can offer advice to steer me in the right algorithm.?

Code:

#include<iostream>
using namespace std;


int main(){


string previous_word = ""; 
string word;
int n = 0;


cout << "Please enter a sequence of words terminated by xxxxx" << endl;
//a b c c b b b d a


cin >> word;


while (word != "xxxxx"){
    previous_word = word;
    cin >> word;
    if (word != previous_word)
        n++;
    else
        n--;
};


if (n < 0)
    n=0;


cout << "There were " << n << " singletons found." << endl;
}

Just to add, this method is for longer sequences. If the sequence is actually short, it's not a big deal, but it is handled different.

Basically you have the following word (result) pairs: a (1); a, b (2); a, a (0). That's the only headache I've really found, and you can just treat it as a special case again.

yeah

I wrote a stack implementation yes, but it still comes down to an algorithm.
My stack main alg. has too much conditional logic. Instead I have crafted this simple loop.
It is close I think. It fails on the last test. It is counting 9-7-2 twice for some reason.
I will continue the stack solution after if this current try is not possible.

Code:

#include <iostream>
using namespace std;


int main(){


int start = 0;
int array_size = 9;
int end = array_size - 1;


//int array[array_size] = {7,7,2}; //pass 1
//int array[array_size] = {2,7,7}; //pass 1
//int array[array_size] = {2}; //pass 1
//int array[array_size] = {2,7}; //pass 2 
//int array[array_size] = {2,7,4}; //pass 3
//int array[array_size] = {2,1,2,1}; //pass 4
//int array[array_size] = {2,1,2,1,2}; //pass 5
//int array[array_size] = {2,1,2,1,2,1}; //pass 6
//int array[array_size] = {2,2,2}; //pass 0
//int array[array_size] = {5,1,5}; //pass 3
int array[array_size] = {2,7,5,5,7,7,7,9,2}; //fail 5


int singleton_count = 0;


for (int i=0; i<=end; i++){


	for (int j=i; j>=start && array[j-1] !=array[j] && array[j+1] !=array[j]; j--){
		
		cout << array[j] << " " << array[j-1] << " " << array[j+1] << endl;
		
		singleton_count += 1;
		start += 1;
				
	}
}
cout << "there are "<< singleton_count << " singletons" << endl;
return 0;
}

Thanks, I will study this that you sent me. My stack is below for posterity. It is missing on aab, counting 2 instead of 1.
I've tried and am close to re-writing it. Would you suggest a total re-write even though the stack is working?
Or am I missing something simple that I can still do this with the stack idea.

Code:

#include<iostream>
#include<stdlib.h>
using namespace std;


struct wordNode{
   string word;
   struct wordNode *next;
};


struct wordNode *wordCollection = NULL;
struct wordNode *prev, *cur;
struct wordNode * insert(struct wordNode *p);
void print(wordNode*p);
void delete_list(struct wordNode *list);
int count_nodes(struct wordNode *p);
int count_singletons(struct wordNode *p, int count_of_nodes);


int main(){


char code;
int count_of_nodes;
int singletons;


for (;;) {


    cout << "Enter list command(+-flx): ";
    cin >> code;


    switch (code) {
      case '+':
          wordCollection = insert(wordCollection);
          break;
      case 'f':
          count_of_nodes = count_nodes(wordCollection);
          cout << count_of_nodes << " nodes in list." << endl;
          singletons = count_singletons(wordCollection,count_of_nodes);
          cout << "There are " << singletons << " singletons in the list." << endl;
          break;
      case '-':
          delete_list(wordCollection);
          break;
      case 'l':
          print(wordCollection);
          break;
      case 'x':
          cout << "Goodbye." << endl;
          return 0;
      default:
          cout << "Illegal code" << endl;
    }
    cout << endl;
  }
}


struct wordNode * insert(struct wordNode *p){


    struct wordNode *newNode;


    string string_to_store;
    cout << endl;
    cout << "What string to store?" << endl;
    cin >> string_to_store;
    newNode = new wordNode;
    newNode->word = string_to_store;
    newNode->next = p;
    return newNode;
}




void print(struct wordNode *p){
while (p != NULL)
  {
    cout << p->word;
    p=p->next;
  }
}




int count_nodes(struct wordNode *p){
int count=0;
while (p != NULL)
  {
    count++;
    p=p->next;
  }
return count;
}




void delete_list(wordNode *head){


if (head != NULL)
   {
   struct wordNode *cur;
   cur = head->next;
   while(cur!=NULL)
      {
         head->next = cur->next;
         cur->next = NULL;
         free(cur);
         cur = head->next;
      }
   }
}




int count_singletons(struct wordNode *p, int count_of_nodes){


struct wordNode *cur, *prev;
//int counter=0;
string prev_cur = "";
string prev_prev = "";
int singletons=0;
bool real_point;


   if (count_of_nodes == 0)
      return 0;


   if (count_of_nodes == 1)
      return 1;


   if (count_of_nodes == 2){
      cur=p;
      prev=cur;
      cur=cur->next;
      if (prev->word != cur->word)
        return 2;
      else
        return 0;}




   for (cur=p; cur!=NULL; ){


     prev=cur;
     cur=cur->next;


     //if we are at the end and the last two match then don't count else count
     if ((cur==NULL) && (prev_prev.length()> 0 ) && (prev->word!=prev_prev)&& (real_point == true))
       singletons += 1;
     else
     real_point = false;
     if ((cur!=NULL)&&(prev->word != cur->word)){
       singletons += 1;
       real_point = true;
       prev_prev = prev->word;
       }


   }
   return singletons;
}