1 /* This solution performs all operations on strings with the mixed radix.
    2  *
    3  * Author: Matt Eastman
    4  */
    5 
    6 #include <assert.h>
    7 #include <stdio.h>
    8 #include <string.h>
    9 #include <unistd.h>
   10 
   11 #define FALSE 0
   12 #define TRUE 1
   13 
   14 #define BUF_SIZE 100
   15 
   16 typedef struct
   17   {
   18     int valid;
   19     char value[BUF_SIZE];
   20   } CrazyInt;
   21 
   22 static const char* kCrazyInt_Charset = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
   23 
   24 void CrazyInt_Parse(char* value, CrazyInt* out);
   25 void CrazyInt_Copy(CrazyInt* a, CrazyInt* out);
   26 
   27 int CrazyInt_Validate(char* value);
   28 int CrazyInt_Sign(CrazyInt* a);
   29 int CrazyInt_Compare(CrazyInt* a, CrazyInt* b);
   30 int CrazyInt_Index(char c);
   31 
   32 void CrazyInt_Neg(CrazyInt* a, CrazyInt* out);
   33 void CrazyInt_Add(CrazyInt* a, CrazyInt* b, CrazyInt* out);
   34 void CrazyInt_Sub(CrazyInt* a, CrazyInt* b, CrazyInt* out);
   35 void CrazyInt_Dec(CrazyInt* a);
   36 void CrazyInt_AddSubInternal(CrazyInt* a, CrazyInt* b, int add, CrazyInt* out);
   37 
   38 void CrazyInt_Parse(char* value, CrazyInt* out)
   39 {
   40   out->valid = CrazyInt_Validate(value);
   41   if (out->valid)
   42     {
   43       strcpy(out->value, value);
   44     }
   45 }
   46 
   47 void CrazyInt_Copy(CrazyInt* a, CrazyInt* out)
   48 {
   49   out->valid = a->valid;
   50   if (out->valid)
   51     {
   52       strcpy(out->value, a->value);
   53     }
   54 }
   55 
   56 int CrazyInt_Validate(char* value)
   57 {
   58   if (value[0] == '-')
   59     return CrazyInt_Validate(&value[1]);
   60   int len = strlen(value);
   61   if (len == 0 || len >= 36)
   62     return FALSE;
   63 
   64   int i;
   65   int base = len + 1;
   66   for (i = 0; i < len; i++)
   67     {
   68       int digit = CrazyInt_Index(value[i]);
   69       if (digit < 0 || digit >= base)
   70         return FALSE;
   71       base--;
   72     }
   73   return TRUE;
   74 }
   75 
   76 int CrazyInt_Sign(CrazyInt* a)
   77 {
   78   assert(a->valid);
   79   if (a->value[0] == '-')
   80     return -1;
   81   if (strcmp(a->value, "0") == 0)
   82     return 0;
   83   return 1;
   84 }
   85 
   86 int CrazyInt_Compare(CrazyInt* a, CrazyInt* b)
   87 {
   88   assert(a->valid && b->valid);
   89   if (CrazyInt_Sign(a) < CrazyInt_Sign(b)) return -1;
   90   if (CrazyInt_Sign(a) > CrazyInt_Sign(b)) return 1;
   91   if (CrazyInt_Sign(a) < 0)
   92     {
   93       CrazyInt temp1;
   94       CrazyInt_Neg(a, &temp1);
   95       CrazyInt temp2;
   96       CrazyInt_Neg(b, &temp1);
   97       return CrazyInt_Compare(&temp2, &temp1);
   98     }
   99   if (strlen(a->value) < strlen(b->value)) return -1;
  100   if (strlen(a->value) > strlen(b->value)) return 1;
  101   return strcmp(a->value, b->value);
  102 }
  103 
  104 int CrazyInt_Index(char c)
  105 {
  106   int i;
  107   for (i = 0; kCrazyInt_Charset[i] != '\0'; i++)
  108     {
  109       if (kCrazyInt_Charset[i] == c)
  110         return i;
  111     }
  112   return -1;
  113 }
  114 
  115 void CrazyInt_Neg(CrazyInt* a, CrazyInt* out)
  116 {
  117   out->valid = a->valid;
  118   if (a->valid)
  119     {
  120       char buf[BUF_SIZE];
  121       switch (CrazyInt_Sign(a))
  122         {
  123         case -1:
  124           CrazyInt_Parse(&a->value[1], out);
  125           break;
  126         case 0:
  127           CrazyInt_Copy(a, out);
  128           break;
  129         case 1:
  130           buf[0] = '-';
  131           strcpy(&buf[1], a->value);
  132           CrazyInt_Parse(buf, out);
  133           break;
  134         default:
  135           assert(FALSE);
  136         }
  137     }
  138 }
  139 
  140 void CrazyInt_Add(CrazyInt* a, CrazyInt* b, CrazyInt* out)
  141 {
  142   if (!a->valid || !b->valid)
  143     {
  144       out->valid = FALSE;
  145     }
  146   else if (CrazyInt_Sign(a) < 0)
  147     {
  148       /* if (a < 0) out = -(-a + -b) */
  149       CrazyInt temp1;
  150       CrazyInt_Neg(a, &temp1);
  151       CrazyInt temp2;
  152       CrazyInt_Neg(b, &temp2);
  153       CrazyInt temp3;
  154       CrazyInt_Add(&temp1, &temp2, &temp3);
  155       CrazyInt_Neg(&temp3, out);
  156     }
  157   else if (CrazyInt_Sign(b) < 0)
  158     {
  159       /* if (b < 0) out = a - -b */
  160       CrazyInt temp1;
  161       CrazyInt_Neg(b, &temp1);
  162       CrazyInt_Sub(a, &temp1, out);
  163     }
  164   else
  165     {
  166       CrazyInt_AddSubInternal(a, b, TRUE, out);
  167     }
  168 }
  169 
  170 void CrazyInt_Sub(CrazyInt* a, CrazyInt* b, CrazyInt* out)
  171 {
  172   if (!a->valid || !b->valid)
  173     {
  174       out->valid = FALSE;
  175     }
  176   else if (CrazyInt_Sign(a) < 0)
  177     {
  178       /* if (a < 0) out = -(-a - -b) */
  179       CrazyInt temp1;
  180       CrazyInt_Neg(a, &temp1);
  181       CrazyInt temp2;
  182       CrazyInt_Neg(b, &temp2);
  183       CrazyInt temp3;
  184       CrazyInt_Sub(&temp1, &temp2, &temp3);
  185       CrazyInt_Neg(&temp3, out);
  186     }
  187   else if (CrazyInt_Sign(b) < 0)
  188     {
  189       /* if (b < 0) out = a + -b */
  190       CrazyInt temp1;
  191       CrazyInt_Neg(b, &temp1);
  192       CrazyInt_Add(a, &temp1, out);
  193     }
  194   else if (CrazyInt_Compare(a, b) < 0)
  195     {
  196       /* if (a < b) out = -(b - a) */
  197       CrazyInt temp1;
  198       CrazyInt_Sub(b, a, &temp1);
  199       CrazyInt_Neg(&temp1, out);
  200     }
  201   else
  202     {
  203       CrazyInt_AddSubInternal(a, b, FALSE, out);
  204     }
  205 }
  206 
  207 void CrazyInt_Dec(CrazyInt* a)
  208 {
  209   CrazyInt temp1;
  210   CrazyInt_Parse("1", &temp1);
  211   CrazyInt temp2;
  212   CrazyInt_Sub(a, &temp1, &temp2);
  213   CrazyInt_Copy(&temp2, a);
  214 }
  215 
  216 void CrazyInt_AddSubInternal(CrazyInt* a, CrazyInt* b, int add, CrazyInt* out)
  217 {
  218   int buf[BUF_SIZE];
  219   char char_buf[BUF_SIZE + 1];
  220   memset(buf, 0, sizeof(buf));
  221   memset(char_buf, 0, sizeof(char_buf));
  222   int len = strlen(a->value);
  223   int offset = BUF_SIZE - len;
  224   int i;
  225   for (i = 0; i < len; i++)
  226     {
  227       buf[offset + i] += CrazyInt_Index(a->value[i]);
  228     }
  229   len = strlen(b->value);
  230   offset = BUF_SIZE - len;
  231   for (i = 0; i < len; i++)
  232     {
  233       if (add)
  234         buf[offset + i] += CrazyInt_Index(b->value[i]);
  235       else
  236         buf[offset + i] -= CrazyInt_Index(b->value[i]);
  237     }
  238 
  239   int last_non_zero = BUF_SIZE - 1;
  240   int base = 2;
  241   for (i = BUF_SIZE - 1; i >= 0; i--)
  242     {
  243       if (buf[i] >= base)
  244         {
  245           buf[i - 1] += buf[i] / base;
  246           buf[i] %= base;
  247         }
  248       while (buf[i] < 0)
  249         {
  250           buf[i] += base;
  251           buf[i - 1]--;
  252         }
  253       char_buf[i] = kCrazyInt_Charset[buf[i]];
  254       if (buf[i] != 0)
  255         last_non_zero = i;
  256       base++;
  257     }
  258 
  259   CrazyInt_Parse(&char_buf[last_non_zero], out);
  260 }
  261 
  262 int main(int argc, char** argv)
  263 {
  264 #ifdef DEBUG
  265   FILE* fp = fopen("input", "r");
  266   assert(fp != NULL);
  267   dup2(fileno(fp), fileno(stdin));
  268 #endif
  269 
  270   int num_lines;
  271   assert(scanf("%d", &num_lines) == 1);
  272   int i;
  273   for (i = 0; i < num_lines; i++)
  274     {
  275       char str_a[1024];
  276       char str_b[1024];
  277       char op;
  278       assert(scanf(" %s %c %s", str_a, &op, str_b) == 3);
  279       CrazyInt a;
  280       CrazyInt_Parse(str_a, &a);
  281       CrazyInt b;
  282       CrazyInt_Parse(str_b, &b);
  283       CrazyInt result;
  284       CrazyInt_Parse("", &result);
  285       if (op == '+') CrazyInt_Add(&a, &b, &result);
  286       else if (op == '-') CrazyInt_Sub(&a, &b, &result);
  287 
  288       if (result.valid)
  289         printf("%s\n", result.value);
  290       else
  291         printf("Invalid\n");
  292     }
  293   return 0;
  294 }
  295