3

I'm trying to re-order some Excel columns using JExcel. I also need to find references to other cells and then re-map them to reference the correct cells. I feel like I've done a lot of the hard work, but I've hit a stumbling block.

I found this code on wikipedia, as linked to from SO:

 public static String toBase26(int number){
        number = Math.abs(number);
        String converted = "";
        // Repeatedly divide the number by 26 and convert the
        // remainder into the appropriate letter.
        do
        {
            int remainder = number % 26;
            converted = (char)(remainder + 'A') + converted;
            number = (number - remainder) / 26;
        } while (number > 0);

        return converted;
    }

But when I run the number 35 into it, this is what happens:

  1. number = 35
  2. remainder = 9
  3. converted= char(9+'A')+"" = J
  4. number = (35-9)/26 = 1
  5. 1>0
  6. remainder = 1
  7. char(1+'A') = B
  8. converted= char(1+'A')+"J" = BJ

Which is, in a way expected, as Base 10 (35) = Base 26 (19). But I'm actually wanting to refer to column AJ.

I can't untangle what change I need to make to get the right letters out. Whenever I try to work it out on paper, I end up ruining the previous letters extracted. For instance, I don't think this would work, as it means I end up with remainder as 8, the first time, and then that would be converted into I, unless I've missed something?

Any help on this would be greatly appreciated. I've looked around and wasted enough time on this. I just want some help to get it to work.

Community
  • 1
  • 1
AncientSwordRage
  • 7,086
  • 19
  • 90
  • 173

2 Answers2

5

The stumbling block behind this 'hexavidecimal system' is that it has a 0, but the units column skips the 0 and ranges only from A-Z. Consider the following conversion from decimal:

A 1 (0*26 + 1)
...
Z 26 (0*26 + 26)
AA 27 (1*26 + 1)
...
AZ 52 (1*26 + 26)
BA 53 (2*26 + 1)
...
BZ 78 (2*26 + 26)
CA 79 (3*26 + 1)
...
ZZ 702 (26*26 + 26)
AAA 703 (1*26*26 + 1*26 + 1)

See the problem? There are missing 'zeroes' in the hexavidecimal numbers:

00A 1
...
00Z 26
0AA 27
...
0AZ 52
0BA 53
...
0BZ 78
0CA 79
...
0ZZ 702 (26*26 + 26)
AAA 703 (1*26*26 + 1*26 + 1)

However, the units column does NOT have the zeroes ever!

Obviously we do not print these zeroes, but it should aid your understanding of what is going wrong.

Here's our algorithm. I wrote the algorithm under the assumption that decimal 0 = hexavidecimal A, 1 -> B, 25 -> Z, 26 -> AA and so on because it makes it easier for me to wrap my head around. If this isn't the assumption you want just subtract 1 before running the code :)

0. If number =< 0, return.

1. Modulo by 26. Convert 0-25 to 'A'-'Z'. //This is our units column.

Loop {

    2. Divide the number by 26 (integer division rounding down).

    3. If number =< 0, return.

    4. Modulo by 26. Convert 0-25 to 'Z','A'-'Y'. //This is our next column (prepend to string output).

}

Example

Converting decimal 730 -> ABC hexavigesimal

Modulo of 730 by 26 = 2 -> 'C' for units column

Divide 730 by 26 = 28

Modulo 28 by 26 = 2 -> 'B' for tens column

Divide 28 by 26 = 1

Modulo 1 by 26 = 1 -> 'A' for hundreds column

Divide 1 by 26 = 0

Number is empty, therefore return 'ABC'

AncientSwordRage
  • 7,086
  • 19
  • 90
  • 173
Patashu
  • 21,443
  • 3
  • 45
  • 53
  • Hmm, I had considered this, and thought it would throw off my 9->J conversion, as that's what I'm after, but now I'm thinking about it, I *might* be after *I*, not *J*. I'll have to go away and check. Thanks for forcing me to rethink this. – AncientSwordRage Apr 24 '13 at 11:39
  • @Pureferret I finally puzzled through hexavidecimal logic, and I have pseudocode for you to read! :D – Patashu Apr 24 '13 at 11:49
  • Thanks for going to the effort of writing out an algorithm for me! I see an issue with your logic though. How does 2 map to C *AND* B? I think you either want 731, or ABB (ACC). Either way, I'll work out my issue and get back to you later hopefully. – AncientSwordRage Apr 24 '13 at 12:09
  • @Pureferret Please read the pseudocode, and note that the units column is treated differently in my algorithm than the other two columns (it doesn't feel very pretty to do it like that, but it works on all the cases I tried) – Patashu Apr 24 '13 at 12:13
  • Ahh, I hadn't realised that fact. When I get back to you, I'll hopefully have an improvement on that which doesn't need a 'special' case. – AncientSwordRage Apr 24 '13 at 12:16
  • If we let A =1, and AA=11, then it's obvious that A should always be converted to 1, so we accept starting at one. That means we should use: `converted = (char)(remainder + 64) + converted;`. I.e. replace 'A' with `64` – AncientSwordRage Apr 24 '13 at 14:17
  • Using this algorithm, I get `fn(675) == "yz"` and `fn(676) == "aza"`, which cannot be right. Perhaps I have a mistake in my implementation (run this on [pythonanywhere](https://www.pythonanywhere.com/gists/75abe5b9766130ea655e/bijective-impl-1.py/ipython2)): https://gist.github.com/theazureshadow/75abe5b9766130ea655e – theazureshadow Jan 05 '16 at 04:52
4

Here is a simple Python function to compute the hexavigesimal representation of a number (in an arbitrary base), where a is equal to 1 (not 0).

The tricky part of the problem is that at each step you're taking between 1 and 10 off the remainder, so you need to account for that in your modulo. The code below accounts for it by subtracting 1 from the number each time. Then 0 becomes a very convenient end condition, because you cannot represent 0 in hexavigesimal (the wikipedia entry denotes it λ).

# Formats a number as a bijective base N string.
def bijective(n, base):
  chars = ''
  while n != 0:
    chars = chr((n - 1) % base + 97) + chars
    n = (n - 1) / base

  return chars

# Examples!
if __name__ == '__main__':
  base = 26
  for n in range(1, 2 * base * base):
    print('{}: {}'.format(n, bijective(n, base)))

See it in action on pythonanywhere.

I included a javascript version in this gist.

theazureshadow
  • 9,499
  • 5
  • 33
  • 48