namenum usaco problem keeps getting bad_alloc errors

Question

I'm currently working on the "Name That Number" USACO training problem.

It takes a number as input and outputs any matching names found in a dictionary using touch tone telephone keymapping.

The full code consistently gets a bad_alloc thrown on the USACO grader. I've been coding in a replit and it runs fine each time. I've also tried commenting out different parts of the code and running it on the USACO grader but sometimes it runs fine and sometimes it gets a bad_alloc thrown. I think it has something to do with my 2d array of vectors but I'm not sure exactly what or how to fix it.

   /*
ID:*****
TASK: namenum
LANG: C++14            
*/
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

//function that takes letter and returns associated number
int convert(int letter){ //implicit conversion
  if (letter < 81){ 
    letter = letter - 65; 
  }
  else {
    letter = letter - 66;
  }
  int modify = letter % 3;
  letter = (letter - modify) / 3 + 2;
  return letter;
}

int main() {
  ifstream numin ("namenum.in");
  ifstream dictin ("dict.txt");
  ofstream fout ("namenum.out");

  //2d array storing vectors that will store matching names for that index
  vector<string> names[8][8]{}; 
  
  //read names in from dict and store in table
  while (dictin.good()) 
  {
    string name{};
    dictin >> name;
    if (name[0] != 'Z' && name[1] != 'Z'){
      int i = convert(name[0]) - 2;
      int j = convert(name[1]) - 2;
      names[i][j].push_back(name);
    }
  }
  //read in digits from input
  string digits{};
  numin >> digits;

  //output matches
  int index1 = static_cast<int>(digits[0]) - 50;
  int index2 = static_cast<int>(digits[1]) - 50;

  string output{};
  
  //check for matches
  if (index1 >= 0 && index1 <= 8 && index1 >= 0 && index1 <= 8){
    for (int i = 0; i < names[index1][index2].size(); i++){
      string matchdigits{};
      for (int j = 0; j < names[index1][index2][i].length(); j++){
        matchdigits += static_cast<char>(convert(names[index1][index2][i][j]) + 48);
      }
      if (matchdigits == digits){
        output = names[index1][index2][i] + "\n";
      }
    }
  }
  
  if (output == ""){
    output = "NONE\n";
  }
  
  fout << output;
  
  return 0;
}

The shown code exhibits many unsafe programming practices, like lack of bounds checking that will result in undefined behavior. I can see at least several possible ways to exploit the logic, with specific input. The mysterious grader must be intentionally using input that excersizes every possible edge cases, in order to guarantee 100% compliance with whatever the stated conditions are. Unfortunately, nobody on Stackoverflow has access to this mysterious grader, and can tell you what input it uses, so that you can debug your program's logic. You will need to figure it out, yourself. — Sam Varshavchik, Jan 27 '23 at 00:00
@tadman There is nothing wrong with `static_cast`'ing between a `char` and an `int`. A more pressing problem is the lack of user input validation and bounds checking that is missing throughout this code. — Remy Lebeau, Jan 27 '23 at 00:00
Beware of `while (dictin.good())` it tests for success BEFORE the value is read. You always want to read and then test and then, depending on the outcome of the test, either use the value read or handle the error. They typical solution to the problem looks something like `string name{}; while (dictin >> name) { use name }` — user4581301, Jan 27 '23 at 00:14
@user4581301 thank you!! added that and bounds checking and it works now — msuf, Jan 27 '23 at 00:19
Good job. Probably worth self-answering to explain what went wrong, why, and how you fixed it to help future askers. — user4581301, Jan 27 '23 at 00:20

namenum usaco problem keeps getting bad_alloc errors

0 Answers0