tools/base_converter.py

   1 #!env python
   2 # vim: set fileencoding=utf8
   3 # Created: April 29, 2008
   4 # Created by: Antonio Chavez
   5 #
   6 # Base converter
   7
   8 import sys, os, string
   9 import Trits
  10
  11 MIN_VAL    = 10
  12 LOW_BOUND  = ord('A') + MIN_VAL
  13 BASE_3     = 3
  14 BALANCED_3 = 3
  15
  16 class BaseError(Exception):
  17     def __init__(self, msg):
  18         self.msg = msg
  19
  20     def __str__(self):
  21         return "BaseError: %s" % (self.msg,)
  22
  23 def base_convert(value, base_frm, base_to):
  24     ''' int_cvrt: convert the number to the left of the decimal place
  25         value: string containing value to convert
  26         from: what base to convert from. Can be positive and negative.
  27             Negative numbers will represent balanced base.  Positive
  28             will represent unbalanced base.
  29         to: what base to convert to.
  30
  31         Example: 3 = unbalanced base 3 (0, 1, 2)
  32                 -3 = balanced base 3 (-1, 0, 1)
  33         Balanced bases can only be odd integers, for the obivious reason
  34             that even numbers are not good candidates for balanced numbering
  35             Example: -4 = (-1, 0, 1, 2) or (-2, -1, 0, 1).  Either system is
  36             not balanced.  Bases must also have a magnitude greater than 1.
  37         For balanced bases greater than 3, a negative number is represented
  38             with an 'i' next to it.
  39             Example: 4i21 => 4(-2)1
  40         Currently conversion balanced bases is not supported.  If balanced
  41             base is entered, the result will be returned in base 10.
  42         A negative sign before the number will negate the result.
  43     '''
  44
  45     # check for magnitude greater than 1
  46     if abs(base_frm) < 2 or abs(base_to) < 2:
  47         raise BaseError("bases must have magnitude greater than 1")
  48
  49     # check for a balanced negative base and derive magnitude
  50     if base_frm < 0 and -base_frm % 2 != 1:
  51         raise BaseError("base_from is even: negative bases must be odd integers")
  52     elif base_frm < 0:
  53         magnitude_f = (-base_frm - 1)/2
  54     else:
  55         magnitude_f = base_frm
  56     #magnitude_f = abs(base_frm)
  57
  58     if base_to < 0 and -base_to % 2 != 1:
  59         raise BaseError("base_to is even: negative bases must be odd integers")
  60     elif base_to < 0:
  61         magnitude_t = (-base_to - 1)/2
  62     else:
  63         magnitude_t = base_to
  64     #magnitude_t = abs(base_to)
  65
  66     sum   = 0   # base 10 equivalent summation
  67     neg   = 1   # used when 'i' is encountered, it negates the previous digit
  68     sign  = 1   # sign of summation
  69     count = 1   # amount to multiply next digit by
  70     prev  = 1   # the value of the next digit
  71     cur   = 0   # current digit
  72
  73     if magnitude_f >= MIN_VAL:
  74         max_val = magnitude_f - MIN_VAL
  75
  76     for i in range(len(value) - 1, -1, -1):
  77
  78         if base_frm == -3:
  79             # Base 3 conversion
  80             if value[i] in Trits.trit_integer:
  81                 sum = sum + (Trits.trit_integer[value[i]]) * count
  82                 count = count * abs(base_frm)
  83             else:
  84                 raise BaseError("0: invalid input %s" % (value[i],))
  85
  86         elif value[i].isdigit():
  87             # 0 <-> 9
  88             cur = int(value[i])
  89
  90             if cur > magnitude_f:
  91                 raise BaseError("1: invalid input %s" % (value[i],))
  92             if i != len(value) - 1:
  93                 sum = sum + prev * neg * count
  94
  95                 # reset variables to appropiate values
  96                 neg = 1
  97                 count = count * abs(base_frm)
  98
  99             prev = cur
 100
 101         elif value[i] == '-' and i == 0:
 102             # negate the whole number
 103             sign = -1
 104         elif value[i] == 'i':
 105             # negate prev number
 106             neg = -1
 107         elif magnitude_f >= MIN_VAL and value[i].isalpha():
 108             # 10 <-> magnitude_f
 109             cur = ord(value[i].upper()) - LOW_BOUND
 110
 111             if cur > magnitude_f:
 112                 raise BaseError("2: invalid input %s" % (value[i],))
 113
 114             if i != len(value) -1:
 115                 sum = sum + prev * neg * count
 116
 117                 # reset variables to appropriate values
 118                 neg = 1
 119                 count = count * abs(base_frm)
 120
 121             prev = cur
 122
 123         else:
 124             raise BaseError("3: invalid input %s at index = %s" % (value[i], i))
 125
 126     # sum up remaining digit
 127     if base_frm != -3:
 128         sum = sum + prev * neg * count
 129         sum = sign * sum
 130
 131     # if requested base 10, then we are done
 132     if base_to == 10 or sum == 0:
 133         return "" + str(sum)
 134
 135     if base_to == -3:
 136         rslt = balanced_conversion(sum, base_to)
 137         return rslt
 138     # return base 10 if desired base is balanced
 139     elif base_to < 0:
 140         return "" + str(sum)
 141
 142     # compute unbalanced conversion
 143     result    = ""
 144     quotient  = sum
 145     remainder = 0
 146
 147     while quotient != 0:
 148         remainder = quotient % magnitude_t
 149         quotient  = quotient / magnitude_t
 150         result    = str(remainder) + result
 151
 152     return result
 153
 154 def balanced_conversion(sum, base_to):
 155
 156     #check for no need for conversion
 157     if sum == 0:
 158         return "0"
 159
 160     tmp_sum =  0
 161     if sum > 0:
 162         count  = 1
 163         result = []
 164         while tmp_sum < sum:
 165             tmp_sum = tmp_sum + count
 166             result.insert(0, "1")
 167             count   = count*BASE_3
 168
 169         #if max value then we are  done
 170         if tmp_sum == sum:
 171             tmp_str = string.join(result, '')
 172             return tmp_str
 173
 174         found, rslt = find_balanced_3(sum, result, len(result) - 1)
 175         tmp_str = string.join(result, '')
 176         return tmp_str
 177
 178     elif sum < 0:
 179         count  = -1
 180         result = []
 181         while tmp_sum > sum:
 182             tmp_sum = tmp_sum + count
 183             result.insert(0, "i")
 184             count   = count * BASE_3
 185
 186         #if max value then we are  done
 187         if tmp_sum == sum:
 188             tmp_str = string.join(result, '')
 189             return tmp_str
 190
 191         found, rslt = find_balanced_3(sum, result, len(result) - 1)
 192         tmp_str = string.join(result, '')
 193         return tmp_str
 194
 195
 196 def find_balanced_3(value, result, iteration):
 197
 198     if iteration < 0:
 199         return False, ""
 200
 201     # set result[iteration] to "0"
 202     result.pop(iteration)
 203     result.insert(iteration, "0")
 204     tmp_sum = balanced_3_value(result)
 205     if tmp_sum == value:
 206         return True, result
 207     # iterate down to lower indexes
 208     found, str_rslt = find_balanced_3(value, result, iteration - 1)
 209     if found:
 210         return True, str_rslt
 211
 212     # set result[iteration] to "i"
 213     result.pop(iteration)
 214     result.insert(iteration, "i")
 215     tmp_sum = balanced_3_value(result)
 216     if tmp_sum == value:
 217         return True, result
 218     # iterate down to lower indexes
 219     found, str_rslt = find_balanced_3(value, result, iteration - 1)
 220     if found:
 221         return True, str_rslt
 222
 223     # set result[iteration] to "1"
 224     result.pop(iteration)
 225     result.insert(iteration, "1")
 226     tmp_sum = balanced_3_value(result)
 227     if tmp_sum == value:
 228         return True, result
 229     # iterate down to lower indexes
 230     found, str_rslt = find_balanced_3(value, result, iteration - 1)
 231     if found:
 232         return True, str_rslt
 233
 234     return False, ""
 235
 236 def balanced_3_value(value):
 237
 238     sum   = 0
 239     count = 1
 240
 241     for i in range(len(value) - 1, -1, -1):
 242         # Base 3 conversion
 243         sum   = sum + (Trits.trit_integer[value[i]]) * count
 244         count = count * BASE_3
 245
 246     return sum
 247
 248 ''' NOTES
 249     useful things to know for implementation
 250     char to int: ord('a') = 97 ASCII
 251     int to char: chr(97)  ASCII
 252     char to int: int('4')
 253     a = "hi6"
 254     a[0].isalpha() => true
 255     a[2].isdigit() => true
 256     a[0].upper()   => "H"
 257     a[2].upper()   => "1"
 258
 259     s.split(".")   => returns list of strings broken up by "."
 260     "1010.3930"    => ["1010", "3930"]
 261
 262     s = ".".join(lis_digits) => combine elements in list by "."
 263 '''
 264
 265 if __name__ == "__main__":
 266     assert base_convert("8", 10, -3) == "10i", \
 267             "8 doesn't convert to 10i in balanced trinary"
 268
 269     while True:
 270         print ">> ",
 271         line = unicode(sys.stdin.readline(), "utf8")
 272         if len(line) == 0:
 273             break
 274         line = line.strip()
 275         print
 276
 277         try:
 278             parts = line.split(",")
 279             if len(parts) == 1:
 280                 # Assume input is base 10, output is balanced 3
 281                 val = parts[0]
 282                 frm = 10
 283                 to = -3
 284             elif len(parts) != 3:
 285                 print "Usage: value-to-convert[,from-radix,to-radix]"
 286                 print "Negative radixes indicate balanced."
 287                 print "For example: 8,10,-3 to convert 8 to balanced trinary"
 288                 print "If ommitted, from-radix and to-radix default to 10 and -3"
 289                 continue
 290             else:
 291                 val, frm, to = parts
 292                 frm = int(frm)
 293                 to  = int(to)
 294
 295             print base_convert(val, frm, to)
 296         except Exception, e:
 297             print "Failed: %s %s" % (type(e), e,)