For a couple of days I was trying to find a linear algorithm with constant storage that is able to find which element in a string has majority if one exists. This was in response to a programmingpraxis exercise where I stopped reading the answer after seeing a reference to the algorithm with this perplexing complexity – the naive solution used O(N) storage. Unfortunately I failed even though it turned out you can formulate that algorithm in a straightforward way. For more information see ProgrammingPraxis site.

After so much thinking, today a task that was more practical engineering than theoretical science. Write a game of Hangman. The language is C++ although, for the sake of simplicity, I avoided classes and algorithms. There’s a rudimentary test though.

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

const int LEVELS = 6;

//#define TEST

#ifdef TEST
char getCh()
{
  static int k = 0;
  char inputs[]= "EAEHMSTROGB_HNGMNA.";
  return inputs[k++]; 
}

std::string getNextWord()
{
  return "HANGMAN";
}

#else
char getCh()
{
  std::string s;
  std::cin >> s;
  if (s.length() > 0)
  {
    return s[0];
  }
  return ' ';
}

std::string getNextWord()
{
  char words[][20] = { "THE", "QUICK", "BROWN", "FOX", "JUMPS", "OVER", "LAZY", "DOG", "RED", "GREEN", "GROSS", "GRAAL" };
  unsigned int sz = sizeof(words) / sizeof(words[0]);
  return words[rand() % sz];
}

#endif

void display(const std::string& word_with_blanks, int level)
{
  //                    012345678901
  char pict[6][13] = { "+--------  \n",
                       "|/      |  \n",
                       "|       o  \n",
                       "|      /#\\ \n",
                       "|      / \\ \n",
                       "|          \n" };
  int blank_line_pos[LEVELS * 2] = { 2, 8,  3, 8,  3, 7,  3, 9,  4, 7,  4, 9};
  for (int i = level; i < LEVELS; ++i)
  {
    pict[blank_line_pos[2 * i]][blank_line_pos[2 * i + 1]] = ' ';
  }
  for (unsigned int i = 0; i < sizeof(pict) / sizeof(pict[0]); ++i)
  {
    std::cout << pict[i];
  }
  for (unsigned int i = 0; i < word_with_blanks.length(); ++i)
  {
    std::cout << word_with_blanks[i] << ' ';
  }
  std::cout << std::endl;
}

int blankWord(std::string& word, const char blank_char, const std::string& uncover)
{
  std::string::size_type i = 0;
  int changes = 0;
  while (i != std::string::npos)
  {
    i = word.find_first_not_of(uncover, i);
    if (i == std::string::npos)
    {
      break;
    }
    word[i++] = blank_char;
    ++changes;
  }
  return changes;
}

bool endGame(const std::string& word, const std::string& message, const int level)
{
  display(word, level);
  std::cout << message << std::endl;
  std::cout << "Enter . to quit, other input to continue" << std::endl;
  return (getCh() == '.');
}

int main(int argc, char** argv)
{
  time_t tm;
  std::time(&tm);
  std::srand(static_cast<unsigned int>(tm));
  bool quit = false;
  do 
  {
    int level = 0;
    std::string word = getNextWord();
    std::string blanked = word;
    std::string used = "";
    blankWord(blanked, '_', used);
    while (level < LEVELS)
    {
      display(blanked, level);
      std::cout << "Enter a letter, . to quit." << std::endl;
      char ch = getCh();
      std::cout << "Your input was: " << ch << std::endl;
      if (ch == '.')
      {
        quit = true;
        break;
      }
      if (ch >= 'A' && ch <= 'Z')
      {
        if (used.find_first_of(ch) != std::string::npos)
        {
          std::cout << "You have already used that letter" << std::endl;
          continue;
        }
        used += ch;

        if (word.find_first_of(ch) != std::string::npos)
        {
          blanked = word;
          if (!blankWord(blanked, '_', used))
          {
            quit = endGame(blanked, "You won! Congratulations!", level);
            break;
          }
        }
        else
        {
          if (++level == LEVELS)
          {
            quit = endGame(word, "You lost!", level);
            break;
          }
        }
      }
    }

  } while (!quit); 

  return 0;
} 


About these ads