Tag: math

Last februari/march, I’ve been working again on an old obsession from ten years ago (when I was eighteen): to write a Minesweeper program that could solve very big maps as well or better than the best human player. At the time I did this because I thought that this was actually a million dollar challenge from the Clay Mathematics Institute. Now, I understand that the problem I solved at the time was not actually what was required, but still, once upon a time (such as early this year), I like to revisit the old problem and try to redo my old segfault generator as something that benefits from the fact that I’m now working with 10 years of programming experience instead of 1.

Minesweeper is grid-based, and I wanted to be able to express a coordinate in something more natural than two numbers. My Coords class has a toString() method which I wanted to output a Spreadsheet-like coordinate comprised of a letter (for the column index) and a number (for the row index). It took me some time to find a nice method to convert an integer to hexavigesimal. (Hexavigesimal is base 26 and 26 happens to be the number of letters in the English alphabet.)

This is what I ended up with:

std::string
Coords::toString()
{
    Coord x = getCol()+1, y = getRow()+1;
    int dividend = x;
    int modulo;
    std::string base26column = "";
 
    while (dividend > 0)
    {  
        modulo = (dividend - 1) % 26;
        base26column = (char)(65 + modulo) + base26column;
        dividend = (int)((dividend - modulo) / 26);
    }
 
    char row[(y / 10) + 1];
    sprintf(row, "%d", (int)y);
 
    return base26column + row;
}

I used the following sources:

• Base Conversion Method [math.com] for general mathematic understanding of converting between bases (using base 26 as an example).
• Here’s another explanation of base 26 conversion by Dr. Math on his Math Forum.
• This Stack Overflow question had a decent solution.
• This one was horrible.
• And this one (from dreamincode.net) was almost as bad.

Maybe I’ll soon start fooling with this again. Finishing this draft of eleven months old actually makes my fingers ache to play with a real close-to-the-metal programming language again. An over-engineered minesweeper clone in C++ might be fun to play with some more.