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
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; } 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:
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
succ or prev.... but that's not even fun to golf. \$\endgroup\$ 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).
$ 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.
y is converted to y+1 using just regex ? and no actual addition ? Nice! \$\endgroup\$ 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.
[?1..?9].zip([?1..?9]).map{|x,y| Regex.new(x+y)}.map{/*something based on the order of results*/} \$\endgroup\$ product is better than zip \$\endgroup\$ /#{x+y}/ is shorter than Regexp.new(x+y). ;) \$\endgroup\$ i=-1;(s=(?0..?9).to_a).product(s).map{|x,y|i+=1;/#{x+y}/=>(?0..'18').each_cons(10).to_a[i/10][i%10]} gives you your regex array. \$\endgroup\$ i)... there must be another way around that... maybe just use each_cons(10) as an enumerator and next through the set? \$\endgroup\$ "Ǻᨌ⹝瀶噄頼籌◳ॶ騥箄덮庸匕帯標ឭ➻䗧㩱砡࣍㤬醻孹꽬"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.
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.
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.
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.
System.Console.WriteLine(new System.Data.DataTable()... \$\endgroup\$ Console.Write to save 4 bytes \$\endgroup\$ 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.
evalWe 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.
dc -e"$1 $2+p" technically I haven't used a number type in the native bash it's just passing a string to some implementation detail \$\endgroup\$ 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 unchanged1+: add one to each position (because the array is 1-indexed)⎕D[...]: use the result as indices into ⎕D.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; 
say is a Perl 6 thing (or you could use it in Perl 5 with these instructions, but that would be too long). Instead of say, use warn to shave a character. That will output to STDERR instead of STDOUT, but that's not against the rules of this one. :-) \$\endgroup\$ 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); } } 
char is a numeric data type ._. \$\endgroup\$ \u0030 to a string, I get "0" not "48". \$\endgroup\$ 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); } 
main=do a<-getLine b<-getLine let c d=last$takeWhile(\e->d/=(show$e-1))[0..] print$c a+c b 
f=x=>{for(i=0;i+[]!=x;i++);return i};f((p=prompt)())+f(p()) *This makes a few assumptions:
var a='123',b=321';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".
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.
