8
\$\begingroup\$

I was messing around with base conversion between decimal and Base26 (alphabet) with no 0th case because I needed it for the Google Sheets API in order to find specific cell values from a 3 dimensional list of all of the entered cell values on a spreadsheet. Remember that with spreadsheets, the columns are counted with no 0th case and A == 1 Z == 26 BA == 53.

Some test cases for conversion between the two bases would be

"zyz" == 18252, "aa" == 27, "zz" == 702

When I went to go write the code, I looked for simple solutions, but could not find anything using recursion so I wrote this in Python:

def base10ToBase26Letter(num):
    ''' Converts any positive integer to Base26(letters only) with no 0th 
    case. Useful for applications such as spreadsheet columns to determine which 
    Letterset goes with a positive integer.
    '''
    if num <= 0:
        return ""
    elif num <= 26:
        return chr(96+num)
    else:
        return base10ToBase26Letter(int((num-1)/26))+chr(97+(num-1)%26)

def base26LetterToBase10(string):
    ''' Converts a string from Base26(letters only) with no 0th case to a positive
    integer. Useful for figuring out column numbers from letters so that they can
    be called from a list.
    '''
    string = string.lower()
    if string == " " or len(string) == 0:
        return 0
    if len(string) == 1:
        return ord(string)-96
    else:
        return base26LetterToBase10(string[1:])+(26**(len(string)-1))*(ord(string[0])-96)

I am aware that the first function outputs lowercase letters which can be bypassed by using base10ToBase26Letter(num).upper().

I used this to test the consistency of the values being output:

for x in range(0,100000):
    if x == base26LetterToBase10(base10ToBase26Letter(x)):
        print(x)
  1. Is recursion the best way to approach this problem efficiently, or should I be looking for something else?
  2. If I were to look at readability, is this way the easiest to read?
  3. Does this problem have a shorter solution?
  4. It seems that after about 11 letter digits, this program is no longer accurate, is there a way to make the functions accurate further? (Even if such numbers will never be used in a spreadsheet)
\$\endgroup\$
  • \$\begingroup\$ As a generalized solution for spreadsheets, it's worth noting that Excel's cells are referenced by two numbers: (A:1) is actually (1:1) programmaticly. \$\endgroup\$ – ben rudgers Dec 14 '17 at 16:24
  • \$\begingroup\$ If you want it to give capital letters and take capital letters just do + and - 64 instead of 96 \$\endgroup\$ – 13ros27 Dec 15 '17 at 18:44
6
\$\begingroup\$

As others already said, recursion doesn't quite fit here. But I’d say it doesn't fit because strings are immutable. In your implementation, you are either concatenating strings or slicing them, which are operations that will produce new strings each time where it shouldn't be necessary.

Instead, iteration is more natural in Python, and you have several builtins that can help you so. The first ones being reversed and enumerate that give you the ability to iterate over each letter in a string in reverse order while knowing the index of the letter: usefull when converting from base alphabet to base 10. And for the base 10 to alphabet conversion, you can extract individual "digits" using divmod and join the generated letters.

Lastly, I’d recommend to stick to the lower_case_with_underscore naming convention for functions as recommended per PEP8.


A_UPPERCASE = ord('A')
ALPHABET_SIZE = 26


def _decompose(number):
    """Generate digits from `number` in base alphabet, least significants
    bits first.

    Since A is 1 rather than 0 in base alphabet, we are dealing with
    `number - 1` at each iteration to be able to extract the proper digits.
    """

    while number:
        number, remainder = divmod(number - 1, ALPHABET_SIZE)
        yield remainder


def base_10_to_alphabet(number):
    """Convert a decimal number to its base alphabet representation"""

    return ''.join(
            chr(A_UPPERCASE + part)
            for part in _decompose(number)
    )[::-1]


def base_alphabet_to_10(letters):
    """Convert an alphabet number to its decimal representation"""

    return sum(
            (ord(letter) - A_UPPERCASE + 1) * ALPHABET_SIZE**i
            for i, letter in enumerate(reversed(letters.upper()))
    )

But, you could use recursion in _decompose in order to not have to reverse the string produced by join:

A_UPPERCASE = ord('A')
ALPHABET_SIZE = 26


def _decompose(number):
    """Generate digits from `number` in base alphabet, most significants
    bits first.
    """

    number -= 1  # Account for A in base alphabet being 1 in decimal rather than 0
    if number < ALPHABET_SIZE:
        yield number
    else:
        number, remainder = divmod(number, ALPHABET_SIZE)
        yield from _decompose(number)
        yield remainder


def base_10_to_alphabet(number):
    """Convert a decimal number to its base alphabet representation"""

    return ''.join(
            chr(A_UPPERCASE + part)
            for part in _decompose(number)
    )


def base_alphabet_to_10(letters):
    """Convert an alphabet number to its decimal representation"""

    return sum(
            (ord(letter) - A_UPPERCASE + 1) * ALPHABET_SIZE**i
            for i, letter in enumerate(reversed(letters.upper()))
    )
\$\endgroup\$
  • \$\begingroup\$ Isn't your second _decompose manually doing what reversed does? \$\endgroup\$ – Peilonrayz Dec 14 '17 at 12:58
  • \$\begingroup\$ @Peilonrayz somehow, but I cannot use reversed on a generator \$\endgroup\$ – Mathias Ettinger Dec 14 '17 at 13:25
  • \$\begingroup\$ Interesting. Could you please take a look at my answer? I'd be happy to get some feedback. \$\endgroup\$ – Eric Duminil Dec 14 '17 at 14:05
  • 1
    \$\begingroup\$ Is exponentiation really the best way to do this? \$\endgroup\$ – Snowbody Dec 14 '17 at 16:26
  • 2
    \$\begingroup\$ @Snowbody This is the way that I feel (and I may be wrong, of course) convey the best the base to decimal convertion aspect. Don't know if it qualifies as best though. \$\endgroup\$ – Mathias Ettinger Dec 14 '17 at 17:03
4
\$\begingroup\$
  • Recursion here is unnatural (especially since Python does not eliminate tail recursion). However, a tail recursion elimination is a purely mechanical procedure (sorry for the shameless self-promotion). Consider an iterative reimplementation.

    A purely iterative approach would also avoid repeated exponentiation in base26LetterToBase10, which also feels very uncomfortable.

  • Magic numbers (26, 96, 97) better have meaningful symbolic names.

  • base26LetterToBase10 does not validate its input, and will happily convert any string. I am not sure it is a desirable behavior.

\$\endgroup\$
  • \$\begingroup\$ unless the number is hundreds of digits or more, the Recursion and Iteration would have only silent difference in performance. \$\endgroup\$ – phy nju Dec 14 '17 at 7:22
3
\$\begingroup\$

Theory

  • The goal of recursion is to only consider 1 base case, and modify your input until you reach this base case. That's why you shouldn't check if num <= 26 or len(string) == 1. Just wait one more recursive call until num is 0 or string is empty.

  • You should write tests, even if they are simple and use ==.

  • You could replace magic numbers with a single definition, e.g. ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'. If you need them, 26, 96, 97 can be calculated from ALPHABET.

  • Use a // b instead of int(a/b).

  • Recursion doesn't really fit base26LetterToBase10.

  • You could run autopep8 on your script.

  • Python function names should be written in snake_case.

  • column_id_to_int should probably raise an error if the input string is incorrect.

  • There's no reason the code shouldn't work with more than 11 chars. Below is an example with 26 chars.

Code

Here's a way to integrate those tips. I'd say the code became a bit clearer, more flexible and more robust:

ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'  # or string.ascii_uppercase
N = len(ALPHABET)
ALPHABET_INDEX = {d: i for i, d in enumerate(ALPHABET, 1)}


def int_to_column_id(num):
    ''' Converts any positive integer to Base26(letters only) with no 0th 
    case. Useful for applications such as spreadsheet columns to determine which 
    Letterset goes with a positive integer.
    '''
    if num < 0:
        raise ValueError("Input should be a non-negative integer.")
    elif num == 0:
        return ""
    else:
        q, r = divmod(num - 1, N)
        return int_to_column_id(q) + ALPHABET[r]


def column_id_to_int(string):
    ''' Converts a string from Base26(letters only) with no 0th case to a positive
    integer. Useful for figuring out column numbers from letters so that they can
    be called from a list. Raises a ValueError unless every character is a letter.
    '''
    result = 0
    try:
        for char in string.upper():
            result = result * N + ALPHABET_INDEX[char]
        return result
    except KeyError:
        raise ValueError("Input string should only contain letters.")

Tests

Here are the tests you mentioned and some more for large or incorrect inputs:

import unittest


class TestColumnIdToInt(unittest.TestCase):

    def test_large_input(self):
        self.assertEqual(int_to_column_id(
            256094574536617744129141650397448476), ALPHABET)

    def test_every_int(self):
        for i in range(100000):
            self.assertEqual(column_id_to_int(int_to_column_id(i)), i)

    def test_lower_case_input(self):
        self.assertEqual(column_id_to_int("abc"), column_id_to_int("ABC"))

    def test_incorrect_input(self):
        with self.assertRaises(ValueError):
            column_id_to_int("T3ST")
        with self.assertRaises(Exception):
            column_id_to_int(1234)


class TestIntToColumnId(unittest.TestCase):

    def test_common_ints(self):
        self.assertEqual(int_to_column_id(0), "")
        self.assertEqual(int_to_column_id(1), "A")
        self.assertEqual(int_to_column_id(26), "Z")
        self.assertEqual(int_to_column_id(27), "AA")
        self.assertEqual(int_to_column_id(702), "ZZ")
        self.assertEqual(int_to_column_id(18252), "ZYZ")

    def test_large_input(self):
        self.assertEqual(column_id_to_int(ALPHABET),
                         256094574536617744129141650397448476)

    def test_incorrect_input(self):
        with self.assertRaises(ValueError):
            int_to_column_id(-1234)
        with self.assertRaises(TypeError):
            int_to_column_id("Wrong")

if __name__ == '__main__':
    unittest.main()

All tests pass:

.......
----------------------------------------------------------------------
Ran 7 tests in 0.600s

OK
\$\endgroup\$
  • \$\begingroup\$ Column numbers 0 and below are illegal. So I think the proper behavior for int_to_column_id would be to raise ValueError('Column number must be positive') and let the caller catch that and translate it to the empty string if appropriate. May need to make a helper function. \$\endgroup\$ – Snowbody Dec 14 '17 at 17:28
  • \$\begingroup\$ Instead of using both % and // check out the divmod() function (though you'll need a temporary variable) \$\endgroup\$ – Snowbody Dec 14 '17 at 17:30
  • \$\begingroup\$ For testing and creating test cases, the pythonic way to do it is to use the unittest module (docs.python.org/3/library/unittest.html ) \$\endgroup\$ – Snowbody Dec 14 '17 at 17:32
  • \$\begingroup\$ @Snowbody: Excellent comments, thanks. Both methods work fine with empty string or 0, I like that I can test every i in range(100000). Non-negative numbers aren't accepted anymore, and I wrote some unittests. It's more pythonic indeed, but the amount of boilerplate code always reminds me of the bad aspects of Java. \$\endgroup\$ – Eric Duminil Dec 14 '17 at 21:33
  • \$\begingroup\$ The boilerplate code is unnecessary and should be factored out. Your tests are written in python too, so you can easily make up a list of tuples or a dictionary and iterate over it, with only one self.assertEqual(int_to_column_id(...),...) inside the loop. \$\endgroup\$ – Snowbody Dec 14 '17 at 22:36
2
\$\begingroup\$

There is a lot of sound advice in other answers, so I will only touch on aspects that I think are worth considering, but are not yet addressed (or that I misunderstood).

Recursion

I like recursion. But when I find myself trying to use it in Python I stop and reconsider. Using recursion in Python is possible, but doing so is usually an exercise in snake wrestling more than it is productive programming.

while_stmt ::=  "while" expression ":" suite
                ["else" ":" suite]

On the other hand, the while statement is very similar conceptually. The syntactical differences from recursion are:

  1. The test is true when the inductive base case is false.
  2. The action on the base case comes at the end.

Other answers show examples of how to use while and it might be worth looking at them and trying "to see" them as recursive. It is probably worth using while instead of recursion if you plan to share Python code with other people because in the context of Python's community, recursive code is harder to understand.

Magic Numbers

The Danish alphabet has 29 letters. Icelandic has 32. Russian, 33. The length of the Latin alphabet, 26, is hard coded into the functions. These languages use characters that are not directly representable in ASCII. The code assumes that they are and hard codes the offset 97.

It may be the case that the Latin 26 character alphabet is hard coded into Google Sheets, now. If it is, that assumption should be made explicitly in one place so that maintenance will be easier if Google changes (or if there already is localization). Magic numbers are a "code smell". Sprinkling the same numbers throughout the code is another.

A => 1

Python is zero indexed. Indexing the Latin alphabet from 1 is fighting against the language. I can follow your rationales for wrestling the snake. But I have to think too much about your rationales in order to understand your code. If you had created a Domain Specific Language in Python and then were writing your functions in that, 1-indexing would make sense. But your code is in Python. The biggest advantage of Python is that people know what to expect. They don't expect 1-indexing.

Data Architecture

Zero-indexing versus one-indexing is mostly a matter of not conceptually separating the internal data representation of your application from the external interface of the Google API. The architecture of your application is:

Deserialize from API -> Manipulate -> Serialize to API

The decision to use One-indexing is due to letting the data abstractions of Google's API leak into your Python code. It makes your code brittle and harder to reason about. Nobody should have to think about Google's API when looking at the internals of the Manipulateportion of the architecture. It is probably better if all your wrestling with Google's API happens in Deserialize and Serialize and Manipulate just works and make sense with zero knowledge of Google (or any other) API's.

Naming

Consider deserialize_column_name and serialize_column_name as the names of your functions because those are your functions' functions. Base 26 is not really the important part of how someone uses it. That the output is a letter is not really the important part. Those are implementation details of Google's API protocol that can be described in the DocStrings. People will have to read the DocString with the current names, anyway.

\$\endgroup\$
1
\$\begingroup\$

You can easily adjust the number 97 to 96 to make the code work for 1-based situation. Answering the op's question, with 'a' = 1, 'b' = 2 ... and so on...

def base26LetterToBase10_A_is_ONE(string):  ### 1-based
    ''' Converts a string from Base26(letters only) with no 0th case to a positive
    integer. Useful for figuring out column numbers from letters so that they can
    be called from a list.
    '''
    string = string.lower()

    a = [ ord(x) - 96  for x in string if x.isalpha()]
    if len(a) == 0:
        return 0
    return reduce(lambda x, y : 26 * x + y, a)

and the reverse convert is

def base10ToBase26Letter_A_is_ONE(num):  ### 1-based
    ''' Converts any positive integer to Base26(letters only) with no 0th 
    case. Useful for applications such as spreadsheet columns to determine which 
    Letterset goes with a positive integer.
    '''
    if num <= 0:
        return ""
    s = ""
    while (num > 0):
        s+=(chr(97+(num-1)%26))
        num -= 1
        num//=26
    return s[::-1]

Now this below is for normal Base26 conversion, with 'a' = 0, 'b' = 1 and so on .

def base26LetterToBase10_A_is_ZERO(string):  ### 0-based
    ''' Converts a string from Base26(letters only) with 0th case to a positive
    integer. Useful for figuring out column numbers from letters so that they can
    be called from a list.
    '''
    string = string.lower()

    a = [ ord(x) - 97  for x in string if x.isalpha()]
    if len(a) == 0:
        return 0
    return reduce(lambda x, y : 26 * x + y, a)

and the reverse converter is

def base10ToBase26Letter_A_is_ZERO(num):  ### 0-based
    ''' Converts any positive integer to Base26(letters only) with  0th 
    case. Useful for applications such as spreadsheet columns to determine which 
    Letterset goes with a positive integer.
    '''
    if num < 0:
        return ""
    if num == 0:
        return "a"

    s = ""
    while (num > 0):
        s+=(chr(97+num%26))
        num//=26
    return s[::-1]

How big difference they could be.

\$\endgroup\$
  • 2
    \$\begingroup\$ Did you test it? \$\endgroup\$ – Eric Duminil Dec 14 '17 at 8:07
1
\$\begingroup\$

The column_name_to_column_number function would be a good match for using functools.reduce. It operates on any sequence type (including str, the type of strings) and allows you to build up a result piece by piece while parsing through the sequence. You need to write a 2-param lambda expression or function to process each piece and update the intermediate value. There's even a way to specify a special case creating the starting value (i.e. what's in the intermediate storage before the first element of the sequence is applied).

Or, this also works (though it's ugly and unreadable)

transtable=str.maketrans(string.ascii_uppercase,"0123456789ABCDEFGHIJKLMNOP")
return int((chr(1+ord(s[0]))+s[1:]).translate(transtable),26)+1
\$\endgroup\$
  • \$\begingroup\$ Can you add some code to illustrate what you are talking about? I'm not familiar with the ideas. \$\endgroup\$ – ben rudgers Dec 15 '17 at 13:50
  • \$\begingroup\$ @ben rudgers Check out the documentation for functools.reduce that I linked, and also Phy Nju's answer codereview.stackexchange.com/a/182751/11647 \$\endgroup\$ – Snowbody Dec 15 '17 at 13:56
  • \$\begingroup\$ A wise person once wrote : How hard is it to run a local python interpreter, or to run it through repl.it or one of the other online code generators? I mean the test cases are even right there for you in the original question! Answer the question that the poster actually asked, not the question that you wanted to answer. \$\endgroup\$ – Eric Duminil Dec 16 '17 at 12:41
  • \$\begingroup\$ @EricDuminil No, that wasn't a wise person. That was me. That was a harsh comment i made to Phy Nju when I was impatient and frustrated (not an excuse) about his code not working. He improved his code, and I upvoted it. All the Stack Exchange sites are about helping out the original question-asker. The code I would have added in response to benrudgers' question, ended up being identical to the code Phy Nju eventually wrote. Why duplicate his work? \$\endgroup\$ – Snowbody Dec 17 '17 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.