Hangman Search and Sort Algorithms

[stianon]

I cannot figure out the search and sort algorithms for a hangman game I am designing. I am supposed to pass a user guess(char guess), the number of valid guesses(int used) and the array I am supposed to search(usedLetters[]). I can get the letters sorted but after a certain number of guesses it allows the user to guess the same letter again. It appears that the search works for a certain number of guesses but stops after a certain point. To be clear, the array should not save a duplicate value and thus print it out on the screen. It should be prevented from doing this by the search algorithm. I am using a binary search algorithm and a selection sort, sort algorithm. I can post more code if need be, it is a rather large file so I only posted the functions.

Here is the code:

int binarySearch(char usedLetters[], int used, char guess) //Binary sort function
{
	int first = 0;
	int last = used;
	int mid = 0;
	while (first < last)
	{
		mid = first +(last - first) / 2;
		if (guess == usedLetters[mid])
			return mid;
		else if (guess < usedLetters[mid])//descending
			first = mid + 1; // decided it is in the last half
		else
			last = mid - 1; // deicded it is in the first half
	}
	return -1;
}
void selectionSort(char usedLetters[], int used)
{
	int top = 0; // index of top array
	int small = 0; // index of largest item in array
	char tmpChar; // temp variables for swapping

	for (top = 0; top < used; top++)
	{
		small = top;
		for (int i = top;i < used; i++)
		{
			if (usedLetters[small] > usedLetters[i])
				small = i;
		}
		//swap
		tmpChar = usedLetters[top];
		usedLetters[top] = usedLetters[small];
		usedLetters[small] = tmpChar;
	}

}


Here is the output of the game. The search function that prevents duplicate guesses stops working after two correct guesses or a random number of incorrect guesses. 

/*
<<<<<<<<<< MAKE A GUESS >>>>>>>>>>
Guessed letters: A D F G G S

Enter a letter to guess: g
That letter has already been guessed!

  -------------|
  |            |
  |            |
  0            |
--|--          |
  |            |
               |
               |
               |
---------------------
_ _ A _ _ S

<<<<<<<<<< MAKE A GUESS >>>>>>>>>>
Guessed letters: A D F G G S

Enter a letter to guess: j

You entered: J

J is NOT FOUND in the word

  -------------|
  |            |
  |            |
  0            |
--|--          |
  |            |
 /             |
               |
               |
---------------------
_ _ A _ _ S

<<<<<<<<<< MAKE A GUESS >>>>>>>>>>
Guessed letters: A D F G G J S

Enter a letter to guess: j

You entered: J

J is NOT FOUND in the word

  -------------|
  |            |
  |            |
  0            |
--|--          |
  |            |
 / \           |
               |
               |
---------------------

You have lost try again! The Word was: LEAVES
*/

[Thomas1965]

Why so complicated?
Why don't you just use a string and its find method ?
Even if you have to use an array you could just use a linear search.

[stianon]

I have to use a char array and a binary search method. Otherwise I would totally use the .find. I don't understand what the search is doing wrong? It works for some chars and not for others.

[Thomas1965]

Shame that you have to use char array and write sort and search functions, but I guess you are taking a course so you have to grid your teeth.
There are some flaws in your search function.
Have a look at this demo and the tutorials.
Also it might be a good idea to write a little function to check if the array is actually sorted.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

// expects the array to be sorted in ascending order
int binarySearch(char usedLetters[], int used, char guess) //Binary sort function
{
  int first = 0;
  int last = used;
  int mid = 0;
  while (first <= last)
  {
    mid = (first + last) / 2;
    char current = usedLetters[mid]; 
    if (guess == current)
      return mid;
    else if (guess < current)
      last = mid - 1;// decided it is in the first half
    else
      first = mid + 1; // deicded it is in the last half
  }
  return -1;
}

void Check(char search, int expected, int actual)
{
  if (expected == actual)
    cout << "** Passed ** ";
  else
    cout << "** Failed ** ";
  cout << "searched = " << search << "\texpected = " << expected << "\tactual = " << actual << "\n";
}

void TestLowerCase()
{
  char letters[] = "abcdefghijklmnopqrstuvwxyz";
  int numLetters = strlen(letters);

  // test all lower case letters
  cout << "Test all lower case letters\n";
  cout << "===========================\n\n";
  for (int i = 0; i < numLetters; i++)
  {
    int result = binarySearch(letters, numLetters, letters[i]);
    int idx = letters[i] - 97;
    Check(letters[i], idx, result);
  }
}

void TestOther()
{
  // check some not to be found
  cout << "\n\nTest some characters not to be found\n";
  cout << "====================================\n\n";
  char letters[] = "abcdefghijklmnopqrstuvwxyz";
  char characters[] = "@!£$%^&*(){}:;'~#|\\";
  int numLetters = strlen(characters); 
  for (int i = 0; i < numLetters; i++)
  {
    int result = binarySearch(letters, numLetters, characters[i]);
    Check(characters[i], -1, result);
  }
}

int main() 
{
  TestLowerCase();
  TestOther();
  system("pause");
  return 0;
}

https://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm
https://en.wikipedia.org/wiki/Binary_search_algorithm

[stianon]

Thank you for the links. I am wondering if my sort algorithm is in the wrong place? I call the search search function before the sort function. This way if the char is in the array it will not sort it and then add it to the array. I will try playing with the search algorithm and write a function to see if things are being sorted properly. Thanks!

[stianon]

Thank you Thomas1965, for a hobby programmer you are killin it. I took a look at my code and figured out where the error was. Thanks again!

[Thomas1965]

You are very welcome.