I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)

Question

So I thought I'd teach myself C++ but I appear to have no problems with the language but I am frankly stupid.

So my idea was this. If I say a=1, b=2, z=26, aa=27 etc, I can map words to numbers, use a boolean in a hash table (bit masked of course) and have an O(1) spell checker. So writing that is no problem at all. My algorithm to do it, looks like this:

int pos;
word_key_t char_key;
word_key_t key = 0;
const char *raw = word.c_str();

cout << "Entering getKey loop with " << raw << endl;
for (pos = 0; raw[pos] != '\0'; pos++) {
    if (raw[pos] >= 'A' && raw[pos] <= 'Z') {
        char_key = raw[pos] - 'A';
    } else if (raw[pos] >= 'a' && raw[pos] <= 'z') {
        char_key = raw[pos] - 'a';
    } else {
        throw new runtime_error("Unrecognised Character");
    }

    key += (char_key + 1) * (pow(CHARS_IN_ALPHABET, pos));
}

cout << "word: " << raw << " ,score: " << key << endl;
return key;

It appears to work,

a=1 b=2 ab=53 ac=79.

I believe this is correct.

However, I'm having problems trying to decode it. This is my best attempt and it isn't working. I believe I need to be using pow(26,position) and decrementing from the end of the string but I'm just struggling to achieve this. This is some workable standalone code that does the wrong thing:

#include <iostream>
#include <inttypes.h>
#include <string.h>
 
typedef uint32_t word_key_t;
const int CHARS_IN_ALPHABET = 26;
const int BUFFER_SIZE = 255; //ignore this for now.
 
using namespace std;
 
string reverseKey(const word_key_t key); //broken algo
 
int main(int argc, char** argv) {
        reverseKey(53); // 53 = ab
        return 0;
}
 
//disassemble a word_key_t into it's original string. returns lowercase only
string reverseKey(const word_key_t key)
{
   
  char chr, buffer[BUFFER_SIZE];
  word_key_t keyc = key, isolated, pos = BUFFER_SIZE;
 
  cout << "key: " << keyc << endl;
  
  while (keyc != 0) {
      isolated = (keyc - 1) % ((word_key_t)CHARS_IN_ALPHABET + 1);
      cout << "key: " << keyc << ", isolated: " << isolated << endl;
      chr = (char)'a' + isolated - 1;
      cout << "isolated character: " << chr << endl;
      keyc = (keyc - isolated) / CHARS_IN_ALPHABET;
      cout << "new key: " << keyc << endl;
      pos++;
  }
 
  string s("test");
  return s;
 
}

If someone could nudge me toward the correct psudeocode for solving this I'd be really grateful. I have kind of gone a bit crazy and lost the plot with the solution. I just can't see it. Something is telling me to 2logX / 2log26 and I think I just need some smarter eyes on it. Then I can get back to learning C++.

Answer 1

Some editing later. I did misunderstand the generation of the key values. I think the generation of the letters from the key would be:

while ( key )
   {
   int char_key = key % 26;
   char c = 'a' + (char)( char_key - 1 );
   key /= CHARS_IN_ALPHABET;      
   }

Although I still don't think the original calculation of the key is correct. I still believe the key computation should be:

key = CHARS_IN_ALPHABET * key + char_key + 1;

Process the raw[] array in reverse order to avoid extracting them in reverse order.

Answer 2

You can trade off using slightly more space, and getting better execution time by making the base a power of 2 (say 32 in your case).

This way you can use shifts and logical operations instead of multiply, divide and mod.

For example:

void convert(int n, char *s){
    int i = 0;
    do {
        s[i++] = (n && 0x1F) + 'a';
    } while ((n >>= 5) > 0);
    s[i] = 0;
}

int convertBack(char *s){
    int i = 0;
    int n = 0;
    while (s[i]) {
        n += ( (s[i]-'a') >> 5*i;
        i++;
    }
    return n;
}

and the main should be the same as kcsoft suggested.

Answer 3

I would suggest not using any "power" functions, particularly floating point ones.

The following sets 'a' = 0, 'z' = 25, 'aa' = 26 etc and works only using integer addition, multiplication and division (no floating point). Only one multiplication is required per character encoded, and only one division is required per character decoded.

#include <cctype>
#include <iostream>
#include <string>
#include <algorithm>

template <class T>
T encode(const char* s)
{
  T result = 0;
  while (*s != 0)
  {
    result *= 26;
    result += std::tolower(*s) - 'a';
    ++s;
  }
  return result;
}

template <class T>
std::string decode(T x)
{
  std::string s;
  while (x != 0)
  {
    s += x % 26 + 'a';
    x /= 26;
  }
  std::reverse(s.begin(), s.end());
  return s;
}

int main() 
{
  std::cout << decode(encode<unsigned int>("tbce")) << std::endl;
}

Ideone code here

Answer 4

You problem actually resumes to a base to base conversion, in your case from base 10 to base 26. The difference is that a=0, b=1 and so on (0=first symbol).

Another remark is that you didn't revert the converted string (ba=53).

Here is the complete code (1st element is 0, not 1 i.e.a=0)

Like in your code, characters in the converted string are not reversed (like they should be in a normal base-to-base conversion)

#include <stdio.h>
int power(int x, int times){
    int result = 1;
    while (times--) result *= x;
    return result;
}
void convert(int n, char *s){
    int i = 0;
    do {
        s[i++] = (n % 26) + 'a';
    } while ((n /= 26) > 0);
    s[i] = 0;
}
int convertBack(char *s){
    int i = 0;
    int n = 0;
    while (s[i]) {
        n += ( (s[i]-'a') * power(26, i));
        i++;
    }
    return n;
}
void main(){
    char s[100];
    convert(53, s);
    printf("Converted:%s\n",s);
    printf("Convert back=%d", convertBack(s));
}

Answer 5

You actually have a base-27 number (aa = a*26 + b) but avoiding ever using "zeroes".

INPUT: encodedWord such that "aa" = 27, "ab" = 28, etc.
OUTPUT: The ASCII string

outString := ""
While encodedWord > 0 Do
  lastLetter = encodedWord % 27;
  encodedWord = encodedWord / 27;
  outString := toChar(lastLetter + 64) + outString;
End-while
Return outString;