Base-26 Arithmetic

March 23, 2012

A reader named Prashant recently wrote to suggest an exercise in base-26 arithmetic:

Write a function that takes two base-26 numbers in which digits are represented by letters with A=0, B=1, … Z=25 and returns their product using the same notation. As an example, CSGHJ × CBA = FNEUZJA.

Prashant was worried that the problem was specific to C/C++, but that’s not an issue.

Your task is to write the base-26 multiplication function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

16 Responses to “Base-26 Arithmetic”

  1. PHP CLI:

    <? $a=str_split(strtoupper($argv[1]));
    $b=str_split(strtoupper($argv[2]));
    $no=array();$c=0;$d=0;$i=0;
    foreach($a as $val)
    	$c=$c*26+(ord($val)-65);
    foreach ($b as $val)
    	$d=$d*26+(ord($val)-65);
    $e=$c*$d;
    while($e)
    {
    	$no[$i++]=chr(($e%26)+65);
    	$e=(int)($e/26);
    }
    echo strrev(join($no));?>
    
  2. Graham said

    Maybe it’s too early for me and I made a mistake, but I think that “CSGHJ” x “CBA” = “FOFVAJA”; here’s my Python:

    #!/usr/bin/env python
    
    from itertools import count, imap, izip, repeat, starmap
    from operator import mul
    from string import ascii_uppercase
    
    def powers(n):
        return imap(pow, repeat(n), count())
    
    def digits(n):
        return imap(int, str(n))
    
    def b26_to_int(s):
        return sum(starmap(mul, izip(powers(25), reversed([ascii_uppercase.index(k)
                                                           for k in s]))))
    
    def int_to_b26(n):
        if n < 25:
            return ascii_uppercase[n]
        else:
            q, r = divmod(n, 25)
            return int_to_b26(q) + ascii_uppercase[r]
    
    def b26_mul(s, t):
        return int_to_b26(b26_to_int(s) * b26_to_int(t))
    
    if __name__ == "__main__":
        print b26_mul("CSGHJ", "CBA")
    

    Changing bases seems to work fine, i.e. int_to_b26(b26_to_int(s)) == s as far as I can tell.

  3. Graham said

    Woops, never mind. I tested against 25, instead of 26; let me work on this (make sure I don’t have any more embarassing mistakes) and get back to you later.

  4. Graham said

    Yup. Changing all 25s to 26s does the trick. I won’t repost, since I’ve already filled this page with my comments.

  5. Paul G. said

    Here is a Perl solution

    use warnings;
    use strict;
    
    # declare the valid digits within the numbering system along with their values
    my @digits = ('A' .. 'Z');
    my $base = scalar(@digits);
    my %values = map { $digits[$_] => $_ } 0 .. $#digits;
    
    sub ToBaseTen {
        my ($q, $base) = @_;
        my $n = 0;
    
        foreach (split(//, $q)) {
            my $digit = uc($_);
    
            # make sure the input string is valid
            return 0 unless exists $values{$digit};
    
            # process the input number one digit at a time
            $n *= $base;
            $n += $values{$digit};
        }
    
        return $n;
    }
    
    sub FromBaseTen {
        my ($q, $base) = @_;
    
        return $digits[0] unless $q;
    
        my $n = '';
        while ($q > 0) {
            $n = $digits[$q % $base] . $n;
            $q = int($q / $base);
        }
        return $n;
    }
    
    die "Usage: $0 <base26num1> <base26num2>\n" unless scalar(@ARGV) == 2;
    print "$ARGV[0] * $ARGV[1] = " . FromBaseTen(ToBaseTen($ARGV[0], $base) * ToBaseTen($ARGV[1], $base), $base) . "\n";
    
  6. Johann Hibschman said

    Ok, I should stop, but this is good J practice for me.

    toDigits=: 65 -~ a. i. ]
    toNumber=: 26 #. toDigits
    

    Typically, I wouldn’t then bother with defining the multiply function and instead just use:

    'CSGHJ' *&.toNumber 'CBA'
    

    Of course, I could always define it if I wanted to:

    b26mul=: *&.toNumber
    'CSGHJ' b26mul 'CBA'
    

    The trick here, besides having base-conversion built-in (“#.”), is the “under” adverb, “&.”. “f &. g” translates to

    (define (under f g)
      (lambda (x y)
        ((inverse g) (f (g x) (g y)))))
    

    J is pretty clever about deducing the inverses of functions, and you can always explicitly set the inverse to a function, if it can’t figure it out.

  7. Hey! Here’s the C code :

    #include<stdio.h>
    #include<string.h>
    int main(int argc,char* argv[])
    {
    	unsigned long a=0,b=0;int i;
    	char ans[20];
    	for(i=0;i<strlen(argv[1]);i++)	a=a*26+(toupper(argv[1][i])-65);
    	for(i=0;i<strlen(argv[2]);i++)	b=b*26+(toupper(argv[2][i])-65);
    	a=a*b,i=0;
    	while(a)
    	{
    		ans[i++]=(a%26)+65;
    		a/=26;
    	}
    	printf("%s",i==0?"A":"");
    	for(i=strlen(ans)-1;i>=0;i--)	printf("%c",ans[i]);
    }
    
  8. Hey! there’s a flaw :P replace the last 3 lines with:

    if(i==0)
    printf("A");
    else
       for(i=strlen(ans)-1;i>=0;i--) printf("%c",ans[i]);
    }
    
  9. boc said

    an erlang example.

    “FNEUZJA” = base26:mult(“CSGHJ”, “CBA”).

  10. Globules said

    In Haskell, but written for conciseness at the expense of speed and safety. :-)

    import Data.Char
    import Numeric
    
    digits = ['A'..'Z']
    from = fst . head . readInt 26 (`elem` digits) (\c -> ord c - ord 'A')
    to n = showIntAtBase 26 (digits !!) n ""
    
    x `mul` y = to $ from x * from y
    
    main = putStrLn $ "CSGHJ" `mul` "CBA"
    
  11. jonathanjohansen said

    Looks long now that I’ve seen the other comments, but here’s one in Common Lisp:

    ;;;; Base-26 Multiplication
    
    (defun char-digit-value (c)
        (assert (alpha-char-p c))
        (- (char-code (char-upcase c)) #.(char-code #\A)))
    ; (char-digit-value #\B)
    ; (char-digit-value #\b)
    ; (char-digit-value #\Y)
    
    (defun value-char-digit (n)
        (assert (<= 0 n 25))
        (code-char (+ #.(char-code #\A) n)))
    ; (value-char-digit 0)
    ; (value-char-digit 1)
    ; (value-char-digit 25)
    ; (value-char-digit 26)
    
    (defun base-26-to-10 (string)
        (loop for c across (if (symbolp string) (symbol-name string) string)
              for value = (char-digit-value c)
                     then (+ (* 26 value) (char-digit-value c))
            finally (return value)))
    ; (base-26-to-10 'b)
    ; (base-26-to-10 'bc)
    
    (defun base-10-to-26 (integer)
        (when (zerop integer) (return-from base-10-to-26 "A"))
        (loop with n = integer and digits = ()
            while (plusp n)
            do (multiple-value-bind (next dig) (floor n 26)
                (push (value-char-digit dig) digits)
                (setf n next))
            finally (return (coerce digits 'string))))
    ; (base-10-to-26 1)
    ; (base-10-to-26 0)
    ; (base-10-to-26 28)
    
    (defun base-26-mult (a b)
        (base-10-to-26 (* (base-26-to-10 a) (base-26-to-10 b))))
    ; (base-26-mult 'b 'b) = "B"
    ; (base-26-mult 'bc 'ba) = "BCA"
    ; (base-26-mult 'loop 'do) = "BOXNPC"
    ; (base-26-mult 'abcdefghijklmnopqrstuvwxyz 'zyxwvutsrqponmlkjihgfedcba) = "BCBZUKWAYNTOYWGBGVSXHXROMMMNQXHXTXJEKBEWBXJNKALSWZA"
    
  12. Axio said

    Another CL version, in a slightly different style from that of Jonathan.

    (defun f26->10 (str)
      (loop for i from 0
            for j across (reverse (format nil "~:@(~a~)" str))
            sum (* (expt 26 i) (- (char-code j) 65))))
    (defun f10-26 (n &optional (r 0))
      (reverse
        (concatenate 'string
                     (loop while (> n 0)
                           do (setf (values n r) (truncate n 26))
                           collect (code-char (+ 65 r))))))
    (defun mul (a b) (f10-26 (* (f26->10 a) (f26->10 b))))
    
  13. MVUTMJAWRZ said
    from string import ascii_uppercase
    
    class WholeSym(long):
        SYM = ascii_uppercase
    
        def __new__(cls, value):
            if isinstance(value, (int,long)) and value>=0:
                return long.__new__(cls, value)
            elif isinstance(value, basestring) and all(ch in cls.SYM for ch in value):
                base = len(cls.SYM)
                digit = cls.SYM.index
                return long.__new__(cls, reduce(lambda x,y:base*x+digit(y), value, 0))
            else:
                raise ValueError("invalid literal for WholeSym()")
    
        def __repr__(self):
            if self == 0:
                digits = [self.SYM[0]]
            else:
                digits = []
                N = self
                while N != 0:
                    N,d = divmod(N, len(self.SYM))
                    digits.append(self.SYM[d])
                digits.reverse()
            return "%s(%r)" % (self.__class__.__name__, ''.join(digits))
    
        __str__ = __repr__
    

    >>> WholeSym(WholeSym(‘CSGHJ’) * WholeSym(‘CBA’))
    WholeSym(‘FNEUZJA’)
    >>> W = WholeSym
    >>> W( W(‘C’) * W(‘BL’) * W(‘CJ’) * W(‘FV’) * W(‘VHJ’) * W(‘MVUTMJAWRZ’) )
    WholeSym(‘PROGRAMMINGPRAXIS’)

  14. Siyuan said

    Also python version

    def b26_to_int(a):
    	if len(a) == 0:
    		return 0
    	return ord(a[-1]) - 97 + 26 * b26_to_int(a[0: -1])
    
    def int_to_b26(a):
    	return ''.join(chr(i+97) for i in dec_to_26(a))
    
    def dec_to_26(a):
    	if a == 0:
    		return []
    	b = dec_to_26(a//26)
    	b.insert(len(b), a%26)
    	return b
    
    def b26_mul(a, b):
    	answer = int_to_b26(b26_to_int(a.lower()) * b26_to_int(b.lower())).upper()
    	if answer == '':
    		return 'A'
    	else:
    		return answer
    
  15. Christian Siegert said

    My solution written in Go lang: https://gist.github.com/2944246

  16. @Siyuan The python one is a bit weird … int_to_b26(25) == ‘z’ int_to_b26(26) == ‘ba’ < should be 'aa'

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 615 other followers

%d bloggers like this: