Jump to content
  • Advertisement
Sign in to follow this  
choffstein

Numbers to Letters algorithm

This topic is 3738 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all, I am trying to solve this algorithm and my brain is having a bit of trouble. Basically, I am trying to go from a number to a set of letters. 0-25 would be A-Z 26-51 would be AA-AZ 52-77 would be BA-BZ ... 676-701 would be ZA-ZZ 702-727 would be AAA-AAZ 728-753 would be ABA-ABZ etc, etc My initial thought was to basically figure out what power of 26 the values were under, but then the offset issue came up (basically, for AA-ZZ, we aren't starting over at 0, we are starting at 26) ... and now my brain hurts and I have a bunch of spaghetti code Any thoughts? Thanks, Corey

Share this post


Link to post
Share on other sites
Advertisement
std::string identifier(std::size_t count)
{
std::string letters = "abcdefghijklmnopqrstuvwxyz";
std::string result;
while (true)
{
result = letters.substr(count % 26, 1) + result;
count /= 26;
if (!count)
{
break;
}
--count;
}
return result;
}

I just so happened to need the same thing myself a week ago.

Σnigma

Share this post


Link to post
Share on other sites
template< typename elem_type >
int LetterValue( std::basic_string<elem_type> &str, unsigned long value )
{
str.clear();

for( int length = 0; value; length++ )
{
str.append( 'A' + ( value % 26 ) );
value /= 26;
}

return length();
}

Share this post


Link to post
Share on other sites
You may want to look into arithmetic coding if you want to extend this method to infinite precision numbers (and thus strings) in a practical manner. This is essentially a special-case of arithmetic coding except with fixed equal-weight codes. Frankly I find it fascinating that this can be made work (elegantly) with only fixed-precision arithmetic, although it actually took computer science decades to solve the problem and it's still a patent minefield..

Oh, and to let this number itself determine the length of the string then you need to extend the alphabet to 27 symbols by including a special terminator (e.g. use division and modulo by 27 and let the resulting zero end the string).

Share this post


Link to post
Share on other sites
In Layman's terms, it looks to me like a conversion from base-10 to base-26. Which is exactly what all the posted code is doing [smile] Just thought I'd point that out.

Share this post


Link to post
Share on other sites
Not quite. In base 26, A would be zero and AA would also be zero. In the required system, A is zero but AA is 26. I think you just need to subtract 1 from the leftmost digit or something.

Share this post


Link to post
Share on other sites
Thought I'd have a go at a couple of n-gram functions:

Iterative solution:
std::string ngram(unsigned int index)
{
const char * symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const unsigned int size = 26;

std::string result;
do
{
result.insert(0, &symbols[index % size], 1);
}
while ((index /= size)-- > 0);

return result;
}

Recursive solution:
std::string & ngram(unsigned int index, std::string & result)
{
const char * symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const unsigned int size = 26;

if (index > size)
ngram(index / size - 1, result);

return result += symbols[index % size];
}

I'm rather liking the elegance of the latter one [smile]

Share this post


Link to post
Share on other sites
This is a somewhat interesting problem in that a "sub-optimal" solution may actually be best.

Main problem with this type of algorithms comes from the need to append characters at front, requiring either insertions, re-allocations or checking for overruns.

The length of resulting string turns out to be floor(log((count+1)(n-1)+1)/log(n)).

Calculating this would allow in-place construction of string, but even at best, evaluating the length would be expensive, if not suffer from inaccuracies.

This is an important observation because of latest std::string implementation (at least under MVC++), which reserves a small buffer (16 bytes, I believe, much more than even long long could produce) before performing any dynamic allocations.

While std::string is often considered clumsy or inefficient, it turns out that in this case, it's surprisingly efficient, and should be almost identical to passing char[16], possibly not even performing any extra allocations.

Share this post


Link to post
Share on other sites
Quote:
Original post by Daggerbot
*** Source Snippet Removed ***


1) Strings already know their length, so what are you hoping to gain by counting it manually and returning it?

2) I think you're going to need, at minimum, to static_cast the 'A' to instantiate the template for types other than char.

3) Like Kylotan said.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!