Sum of strings without converting [closed]

Question

You have to take 2 string inputs and output the sum of these two strings without converting them to int or using any numeric data type.

ex.

string one = "123";
string two = "456";    
string sum = "579";

Assume the strings won't be larger than 10 digits.

This is code golf and shortest answer in characters wins. An edit to the answer in C# will make me smile :).

Edit: Converting to int can be defined as anything of this nature

Int.TryParse, (int), Convert.ToInt etc

Answer 1

80836 Assembly (57 53 bytes)

53 55 89 E5 8B 4D 0C 8B 55 10 B0 0A 30 DB 88 CF 00 C1 00 C2 49 4A 8A 01 8A 22 00 E0 00 D8 2C 30 30 DB 3C 39 7E 04 B3 01 2C 0A 88 01 88 22 38 CF 75 E2 5D 5B C3

This adds, digit by digit, right to left, without converting ascii digits '0'-'9' to the integers 0-9, and carrying over as needed. The bytecode is the code for a function, which may be called in C (see below).

The above bytecode was written by hand, from the following assembly (NASM-style, commented):

; save ebx, ebp
push ebx        ; 53
push ebp        ; 55
; copy esp
mov ebp, esp    ; 8B EC
; load arguments
mov ecx, [ebp+0x0C] ; 8B 4D 0C
mov edx, [ebp+0x10] ; 8B 55 10
; initialize stuff
mov al, 10      ; B0 0A
xor bl, bl      ; 30 DB
mov bh, cl      ; 88 CF
; send edx, ecx to end of string
add cl, al     ; 00 C1
add dl, al     ; 00 C2

; decrement everything
dec ecx         ; 49
dec edx         ; 4A

; get rightmost unprocessed digit of each number
mov al, [ecx]   ; 8A 01
mov ah, [edx]   ; 8A 22

; add two ascii digits
add al, ah      ; 00 E0
; add carry if needed
add al, bl      ; 00 D8
; subtract 0x30 ('0') to get the resulting ascii digit
sub al, 0x30    ; 2C 30

; set bl to 0
xor bl, bl      ; 30 DB

; if greater than '9': must carry over to next place
cmp al, 0x39    ; 3C 39
jle $+6         ; 7E 04
; set bl to 1 if carrying over
mov bl, 1       ; B3 01
; subtract 10 from ascii digit if carrying over
sub al, 0x0A    ; 2C 0A

mov [ecx], al   ; 88 01
mov [edx], ah   ; 88 22


; check if loop has ended
cmp bh, cl      ; 38 CF
jne $-28        ; 75 E2

; restore ebx, ebp
pop ebp         ; 5D
pop ebx         ; 5B
; return
ret             ; C3

To try this in C (gcc, linux, intel processor):

#include <stdio.h>
#include <string.h>
#include <sys/mman.h>

int main(){
    // bytecode from earlier
    char code[] = {
        0x53, 0x55, 0x8B, 0xEC, 0x8B, 0x4D, 0x0C, 0x8B, 
        0x55, 0x10, 0x31, 0xC0, 0xB0, 0x09, 0x30, 0xDB, 
        0x01, 0xC1, 0x01, 0xC2, 0x40, 0x50, 0x8A, 0x01,
        0x8A, 0x22, 0x00, 0xE0, 0x00, 0xD8, 0x2C, 0x30,
        0x30, 0xDB, 0x3C, 0x39, 0x7E, 0x04, 0xB3, 0x01,
        0x2C, 0x0A, 0x88, 0x01, 0x88, 0x22, 0x58, 0x48,
        0x49, 0x4A, 0x85, 0xC0, 0x75, 0xDF, 0x5D, 0x5B,
        0xC3,
    };
    // allocate executable memory to a function pointer called 'add'
    void __attribute__( (__cdecl__) ) (*add)(char*,char*) = mmap(0,sizeof code,PROT_WRITE|PROT_EXEC,MAP_ANON|MAP_PRIVATE,-1,0);
    memcpy(add, code, sizeof code);

    // test inputs
    char number1[] = "0878295272", number2[] = "8184206821";

    puts(number1);
    puts(number2);

    // call the bytecode as a c function
    add(number1, number2);

    // output is in the first argument
    puts(number1);

    // release allocated memory
    munmap(add, sizeof code);

    return 0;
}

Answer 2

Ruby, 109 71

Cheesy. If you can't bring Mohammad to the mountain....

j=$*
r=n=d=0
(d+=x=j.count{|v|n.to_s==v}
r+=x*n
n+=1)until d>1
p r.to_s

Algorithm:

1. Compare an int's string representation to input 1 and input 2.
2. Add that int to the result per match.
3. Increment and repeat until you've done it twice.
4. Vomit on yourself

Changelog

71 shorter as an array.

85 removed method declaration and consolidate calls to n.to_s

92 applied some tips

101 save a char

102 use x for incrementing

109 initial commit

Answer 3

sed, 359 bytes (without the fancy formatting)

I'm still not sure if this is a dup of Add without addition (or any of the 4 basic arithmetic operators). In the meantime, let me cross post my answer for that question. It's not going to win any golfing, but its a start, and I think easily meets the spec:

                       s/([^ ]+) ([^ ]+)/\1:0::\2:/
                       :d /^([^:]+):\1::([^:]+):/tx
                       s/(:[^:]*)9([_:])/\1_\2/g;td
s/(:[^:]*)8(_*:)/\19\2/g;s/(:[^:]*)7(_*:)/\18\2/g;s/(:[^:]*)6(_*:)/\17\2/g
s/(:[^:]*)5(_*:)/\16\2/g;s/(:[^:]*)4(_*:)/\15\2/g;s/(:[^:]*)3(_*:)/\14\2/g
s/(:[^:]*)2(_*:)/\13\2/g;s/(:[^:]*)1(_*:)/\12\2/g;s/(:[^:]*)0(_*:)/\11\2/g
                       s/:(_+:)/:1\1/g; y/_/0/; # #
                       bd;  :x  s/.*::([^:]+):/\1/;
                       # # # # # # #  # # # # # # #

Input is taken from STDIN in the form "x y". That is first transformed to "x:0::y:". Then we increment all numbers that come after ":" characters, until we get "x:x::(x+y):". Then we finally return (x+y).

Output

$ printf "%s\n" "0 0" "0 1" "1 0" "9 999" "999 9" "12345 67890" "123 1000000000000000000000"  | sed -rf add.sed
0
1
1
1008
1008
80235
1000000000000000000123
$

Note that this only works for the natural numbers. However (in theory at least) it works for arbitrarily large integers. Because we are doing x increment operations on y, ordering can make a big difference to speed: x < y will be faster than x > y.

Answer 4

Ruby - 485 432 265

This seems more in the spirit of what you were looking for in the question.

It basically solves the problem how a human would on paper -- by "memorizing" all single digit addition results, adding each column, and understanding how to "carry the one" when necessary.

This is also using one "numeric data type" (variable i), which is prohibited by the question, but its only for string indexing. I'll try removing this and edit my answer.

def s p
(y=(?0..?9).to_a).product(y).map{|x|/#{x.join}/}.zip((?0..'18').to_a.each_cons(10).to_a.flatten).each{|k,v|return v if k=~p.sort.join}
end
a,b=$*.map{|n|n.rjust(10,?0).reverse}
r=?0
c=''
(0..9).each{|i|d=s [a[i],b[i]]
c=s([d[-1],r])+c
r=d[-2]||?0}
puts r+c

Somewhat ungolfed:

def s p
  y = (?0..?9).to_a
  y.product(y).map{ |x|
    /#{x.join}/
  }.zip(
    (?0..'18').to_a.each_cons(10).to_a.flatten
  ).each{ |k,v|
    return v if k =~ p.sort.join
  }
end

a,b=$*.map{ |n| n.rjust(10,?0).reverse }

r = ?0
c = ''

(0..9).each { |i|
  d = s [ a[i], b[i] ]
  c = s([ d[-1], r ]) + c
  r = d[-2] || '0'
}

puts r+c

EDIT: Used some ideas from the comments to generate the "memorized" mapping table instead of just hardcoding it.

Answer 5

CJam, 95 92 80 72 70 44 characters

"Ǻᨌ⹝瀶噄頼୅籌◳ॶ騥箄덮庸匕帯標ឭ⹞➻䗧㩱砡࣍㤬醻孹꽬"2G#b127b:c~

which translates to

lW%'0A*+S/zW%{{A,__m*{_1b\saa*~}%\{_saa*~}%+\aa/,(s_,({(@+\}*}%_Wf<s}g

This can definitely be golfed a lot. I really don't know if my approach is optimal or not yet.

UPDATE - Inline the sum matrix creation to save bytes. Due to this, the program now runs 10 times slower, but still a constant time for any kind of input.

Try it online here

Reads the line containing two numbers from STDIN as string and outputs as a array of characters which is a string itself.

For example:

123 4567

The output contains preceding 0. Let me know if that is an issue.

Answer 6

C# - 128 108 104

Thanks to Compass, BMac and Shawn for suggesting improvements.

First try at Code Golf, and using C# seems to be a handicap here...

By using .Compute() you can use the string values and sum them directly. As a bonus this works for other operators aside from just "+".

Golfed:

static void t(string a,string b){System.Console.Write(new System.Data.DataTable().Compute(a+"+"+b,""));}

Ungolfed:

static void t(string a, string b)
{
    System.Console.Write(new System.Data.DataTable().Compute(a+"+"+b,""));
}

Calling t("123","456"); gets you 579.

Answer 7

GNU sed, 266 bytes

Uses a different approach than DigitalTrauma's solution. As an effect, this one performs even poorer, using O(m+n). Convert both operands to unary, concatenate, convert back to decimal (all using regex of course—sed doesn't have the concept of an integer).

As a bonus, this program sums up all the natural integers given on stdin (in the first line), meaning you can feed it nothing, one number or ten numbers and it'll do the right thing regardless.

The idea behind this code is vaguely inspired by an old PPCG sed submission of mine, though I don't remember for what question it is an answer.

Here it is, "pretty"-printed for your "convenience", to borrow another idea from DigitalTrauma. :D

                s/9/x8/g;
                s/8/x7/g;
                s/7/x6/g;
                s/6/x5/g;
                s/5/x4/g;
                s/4/x3/g;
  s/3/x2/g;s/2/x1/g;s/1/x0/g;s/0\b//g;;
  :l;s/x0/0xxxxxxxxxx/;/x0/bl;s/[^x]//g
  s/^$/0/;:m;s/x{10}/!/g;s/!\b/&0/;;;;;
  s/0x/1/;s/1x/2/;s/2x/3/;s/3x/4/;;;;;;
  s/4x/5/;s/5x/6/;s/6x/7/;s/7x/8/;;;;;;
                s/8x/9/;;
                s/!/x/g;;
                /x{10}/bm
                /x/!q;;;;
                s/^/0/;bm
                #sum.sed#

(To obtain the 266-byte version, remove trailing semicolons, leading whitespace and the final comment, preferably using sed.)

Borrowing some tests from DigitalTrauma:

% printf "%s\n" "0 0" "0 1" "1 0" "9 999" "999 9" "12345 6789" "123 100" | while read l; do sed -rf /tmp/sum.sed <<<"$l"; done 
0
1
1
1008
1008
19134
223

I tweaked the really large tests a bit because of the terrible space (in)efficiency. Due to the use of q only the first line is processed, hence the while loop in the test.

Answer 8

Java 6 (181 characters)

Not to be outdone by the handicap known as C#, Java in all its glory. So much boilerplate! Usage is providing the arguments separated by a space, i.e. 123 456

import javax.script.*;class T {public static void main(String[] a) throws Exception {System.out.print(new ScriptEngineManager().getEngineByName("JavaScript").eval(a[0]+"+"+a[1]));}}

Ungolfed:

import javax.script.*;

class T {
    public static void main(String[] a) throws Exception {
        System.out.print(new ScriptEngineManager()
                .getEngineByName("JavaScript").eval(a[0] + "+" + a[1]));
    }
}

By using the JavaScript engine available in javax, we can make another language do the work for us, and technically follow the rules of not using any numeric types in the native language, or converting.

Justification for using eval

We have not converted the values to int for JavaScript to eval. We've created a String that is "123+456" which is not a number. JS Engine digests the formula and evaluates the String as number literals, which are not numeric data types. Java cheesy logic! As an aside, this also works for double math.

Answer 9

APL (61)

I think this falls within the rules.

{⎕D[1+{∨/T←9<Z←0,⍵:∇T↓⍨~×⊃T←(1⌽T)+Z-10×T⋄⍵}+⌿⌽↑⌽¨¯1+⎕D∘⍳¨⍺⍵]}

This is a function that takes two string arguments, and returns a string:

      '123'{⎕D[1+{∨/T←9<Z←0,⍵:∇T↓⍨~×⊃T←(1⌽T)+Z-10×T⋄⍵}+⌿⌽↑⌽¨¯1+⎕D∘⍳¨⍺⍵]}'456'
579
      ⍝ show dimensions (if it was a number, this would give the empty list)
      ⍴'123'{⎕D[1+{∨/T←9<Z←0,⍵:∇T↓⍨~×⊃T←(1⌽T)+Z-10×T⋄⍵}+⌿⌽↑⌽¨¯1+⎕D∘⍳¨⍺⍵]}'456'
3

It's reasonably fast too, it adds the number formed by 999999 9s to itself in an instant.

It finds the index of each character in ⎕D (which is the string '0123456789'), then does grade school addition on each index separately, carrying as needed, then looks up the resulting digits in ⎕D. (I think the ⎕D lookup falls within the rules, it's basically just doing 'x'-48).

Explanation:

• ⎕D∘⍳¨⍺⍵: look up the indices in ⎕D for each character in both strings.
• ¯1+: subtract 1 from each, because the arrays are 1-based by default.
• ⌽↑⌽¨: reverse both, turn into a matrix (filling empty squares with zeroes), then reverse the matrix.
• +⌿: sum the columns of the matrix
• {...}: carry over:
  • ∨/T←9<Z←0,⍵: add an extra 0 in front of the list. Find out which 'digits' are higher than 9, and store this in T. If any digits were higher than 10:
    • Z-10×T: subtract 10 from each position that is higher than 10,
    • T←(1⌽T)+: add 1 to each position next to each position that was higher than 10, and store in T.
    • T↓⍨~×⊃T: if T starts with a zero, remove it,
    • ∇: apply the carry function to the result.
  • ⋄⍵: otherwise, return the value unchanged
• 1+: add one to each position (because the array is 1-indexed)
• ⎕D[...]: use the result as indices into ⎕D.

Answer 10

Perl - 136 119 115 bytes

I'm learning Perl, this seemed like good practice. Tips are appreciated!

Cheesy answer, to get that out of the way:

print$ARGV[0]+$ARGV[1]; #Adding strings

Actual answer:

($x,$y)=@ARGV;while($x.$y.$s){$s-=48-ord$&if$x=~s/.$//;$s-=48-ord$&if$y=~s/.$//;$r=chr($s%10+48).$r;$s=$s>9;}print$r;

Uncompressed:

($x,$y)=@ARGV;
while($x.$y.$s){
$s-=48-ord$&if$x=~s/.$//;
$s-=48-ord$&if$y=~s/.$//;
$r=chr($s%10+48).$r;
$s=$s>9;
}
print$r;

Answer 11

Java 7, Score = 252

Uses no integers, longs, bytes, shorts, doubles, floats, or any built in library functions for adding. Wrap in a class body and call with t(String1,String2). Please pad strings with 0's so that they have equal length.

t("123","234") returns "0357".

Golfed:

char c,d,e,f,g,k;String t(String a,String b){g++;char[]h=a.toCharArray(),i=b.toCharArray(),j=new char[h.length + 1];for(d=(char)h.length;d>f;)j[--d+1]=(c=(e=(char)(h[d]+i[d]-'0'+c))>'9'?g:f)==g?(char)(e-'\n'):e;j[0]=(char)('0'+c);return new String(j);}

Golfed Expanded with class:

public class T{

    public static void main(String[] args){
        System.out.println(new T().t(args[0],args[1]));
    }

    char c,d,e,f,g,k;
    String t(String a,String b){
        g++;
        char[]h=a.toCharArray(),i=b.toCharArray(),j=new char[h.length + 1];
        for(d=(char)h.length;d>f;)
            j[--d+1]=(c=(e=(char)(h[d]+i[d]-'0'+c))>'9'?g:f)==g?(char)(e-'\n'):e;
        j[0]=(char)('0'+c);
        return new String(j);
    }
}

Partially golfed expanded:

public class TrickSum{

    public static void main(String[] args){
        System.out.println(new TrickSum().trickSum(args[0], args[1]));
    }

    char carry, i, aSum,nullChar,oneChar;
    public String trickSum(String a, String b){
        oneChar++;
        char[] number1 = toCharArray(a), number2 = toCharArray(b), sum = new char[number1.length + 1];
        for (i = (char) number1.length; i > nullChar;)
            sum[--i + 1] = (carry = (aSum = (char) (number1[i] + number2[i] - '0' + carry)) > '9' ? oneChar : nullChar) == oneChar ? (char) (aSum - '\n') : aSum;
        sum[0] = (char)('0' + carry);
        return new String(sum);
    }

    char[] toCharArray(String string){
        return string.toCharArray();
    }
}

100% Expanded:

public class TrickSum{

    public static void main(String[] args){
        System.out.println(trickSum(args[0], args[1]));
    }

    public static String trickSum(String a, String b){
        char[] number1 = a.toCharArray();
        char[] number2 = b.toCharArray();
        char[] sum = new char[number1.length + 1];
        char carry = '\u0000';
        for (char i = (char)(number1.length - 1); i != '\uFFFF'; i--){
            char aSum = (char) (number1[i] + number2[i] - '0' + carry);
            carry = aSum > '9' ? '\u0001' : '\u0000';
            aSum = (carry == '\u0001') ? (char) (aSum - '\n') : aSum;
            sum[i + 1] = aSum;
        }
        sum[0] = (char)('0' + carry);
        return new String(sum);
    }
}

Answer 12

Java - 257 Characters

as everyone knows java there is no better language for golfing than java

    class A{public static void main(String[]s){char[]a=s[0].toCharArray();char[]b=s[1].toCharArray();int c=a.length;int d=b.length;int e=0;String f="";for(int i=0;i<Math.max(c,d);i++){f=f+(((i<c?a[i]-48:0)+(i<d?b[i]-48:0)+e)%10);e/=10;}System.out.println(f);}}

this is ungolfed solution

public static void main(String[] args) {
        char[] aa = args[0].toCharArray();
        char[] bb = args[1].toCharArray();
        int aal = aa.length;
        int bbl = bb.length;
        
        int reminder = 0;
        String result ="";
        for(int i=0;i<Math.max(aal,bbl);i++){
            result=result+(((i<aal?aa[i]-48:0)+(i<bbl?bb[i]-48:0)+reminder)%10);
            reminder/=10;
        }
        System.out.println(result);
    }

Answer 13

Haskell - 98 94 bytes

main=do
 a<-getLine
 b<-getLine
 let c d=last$takeWhile(\e->d/=(show$e-1))[0..]
 print$c a+c b

Answer 14

JavaScript (ES6), 55 66 59*

 f=x=>{for(i=0;i+[]!=x;i++);return i};f((p=prompt)())+f(p())

*This makes a few assumptions:

• We're in an ES6 REPL environment (ex. FireFox 33.1 browser console)
• Performance does not matter (seriously, '9999999999','9999999999' took about 20 minutes to return)
• Converting from Integer to String is allowed
• Input is defined in variables a and b, ex: var a='123',b=321'; Changed to getting input from prompt (+11).
• Input has no leading zeros.

Answer 15

Python 2.7, 196 137 chars

version 2 (shorter by initialising the dictionary with code):

n={}
for i in range(10):n[`i`]=i*' '
def q(a,b):f=lambda x:''.join([10**p*n[s] for p,s in enumerate(reversed(x))]);return len(f(a)+f(b))

Previous version 1 (196 chars):

def q(a,b):n,f={0:'','1':' ','2':'  ','3':'   ','4':4*' ','5':5*' ','6':6*' ','7':7*' ','8':8*' ','9':9*' '}, lambda x:''.join(
    [10**p*n[s] for p,s in enumerate(reversed(x))]);return len(f(a)+f(b))

e.g.

>>> print q('123','111')
234

The dictionary keys are strings, the dictionary values only include number constants to shorten the code, and the calculation is done by concatenating two strings and getting the resulting length, so I hope it counts as "not converting them to ints".

Python small-print rule-cheat version

class z(int):0
def s(a,b): return z(a)+z(b)

Note:

>>> type(z('4'))
<class '__main__.z'>

Type z is a custom type I define as: definitely not a numeric type by whatever definition the questioner uses, but behaves close enough to a numeric type to be useful in limited circumstances. Type z behaviours are only partially implemented in this code sample, and if the CPython interpreter uses 'int' to implement z, that's an merely an implementation detail and not related to the problem at hand.