loading...

Daily Challenge #287 - 16+18=214

thepracticaldev profile image dev.to staff ・1 min read

For this challenge, forget everything you know about adding two large numbers together.
248+208=4416

Like in this photo, you'll be adding two numbers together without carrying numbers. Write a function that will take two numbers as input and will add them together without carrying. Write down every value you get.

Examples

2 + 11 = 13

16 + 18 = 214
1 + 1 = 2
6 + 8 = 14

122 + 81 = 1103
1 + 0 = 1
8 + 2 = 10
2 + 1 = 3

Tests

1222 + 30277
1236 + 30889
49999 + 49999

Good luck!


This challenge comes from CodeChrisB on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

Discussion

markdown guide
 

A quickie in Typescript
Each digit is enumerated in turn by skimming off the ones digit off each number (using num%10, then dividing the number by 10) until there are no more digits.
The accumulated sum is simply a string with each sum added to its left-hand side.

function piecewiseAdd(addendA: number, addendB: number): number {
  let sumString = '';
  while (addendA || addendB) {
    sumString = (addendA % 10) + (addendB % 10) + sumString;
    addendA = Math.floor(addendA / 10);
    addendB = Math.floor(addendB / 10);
  }
  return +sumString;
}

Testn

> piecewiseAdd(0,0)
< 0
> piecewiseAdd(1222, 30277)
< 31499
> piecewiseAdd(1236, 30889)
< 31101115
> piecewiseAdd(49999, 49999)
< 818181818
 

You already did the skimming, but you could also avoid stringification altogether: dev.to/qm3ster/comment/14en6

 

Thanks, that's a fair point. Here's the tweaked code:

function piecewiseAdd_numeric(addendA: number, addendB: number) : number {
  let sum = 0, cursor = 1;
  while (addendA || addendB) {
    const digitSum = (addendA % 10) + (addendB % 10);
    sum += cursor * digitSum;
    cursor *= digitSum < 10 ? 10 : 100;
    addendA = Math.floor(addendA / 10);
    addendB = Math.floor(addendB / 10);
  }
  return sum;
}

Benchmark here -- numeric method has it by a nose most of the time you run it, sometimes a bit more. For smaller inputs they're pretty much even.

In C or Rust or something closer to the metal Mihail's post is definitely the way to go (imo).
In JS strings are pretty quick and numbers are surprisingly slow to deal with (there's no support for integers, etc) and I find the language doesn't really reward that kind of close-knit optimization, so I felt it wasn't worth the additional complication.

I wonder what the result with asm.js would be.
There are some claims that in the process of implementing asm.js V8 in particular just optimized normal code to the speed of corresponding asm.js, but some extra assertions might still help?

 

EDIT:
I quite liked purely arithmetic solutions by @willsmart and @qm3ster , so I reimplemented same idea in Haskell:

import Numeric.Natural (Natural)

(^+^) :: Natural -> Natural -> Natural
(^+^) = reducer 1
  where
    reducer c 0 0 = 0
    reducer c a b =
      let sum = a `mod` 10 + b `mod` 10
          delta = if sum < 10 then 10 else 100
      in c * sum + reducer (c * delta) (shift a) (shift b)
    shift x = floor $ fromIntegral x / 10

Solution in Haskell:

import Numeric.Natural (Natural)
import Data.Char (digitToInt)

(^+^) :: Natural -> Natural -> Natural
(^+^) n1 n2 = read $ sumHead n1' n2' <> sumTail n1' n2'
  where
    sumHead x y = maybe "" reverse $ zipRemain x y
    sumTail x y = concat . reverse . fmap (show . add) $ zip x y
    add (x,y) = digitToInt x + digitToInt y
    n1' = reverse $ show n1
    n2' = reverse $ show n2

zipRemain :: [a] -> [a] -> Maybe [a]
zipRemain [] [] = Nothing
zipRemain xs [] = Just xs
zipRemain [] ys = Just ys
zipRemain (_:xs) (_:ys) = zipRemain xs ys

Essentially zips up digit by digit in reverse order, sums and concats the result. zipRemain utility function helps retrieving leftover part of the longer of two zipped lists.

Example for the zipping problem:

a = ["1", "2", "3", "4", "5"]
b = ["a", "b", "c"]
zipAB = zip a b -- [("1","a"), ("2","b"), ("3","c")] 
zipRemainAB = zipRemain a b -- ["4", "5"]
 

Solution in Bash and some general commands:

#!/bin/bash
noCarryAddition () {
  p=$(( $1 > $2 ? $1 : $2 ));
  eval paste '<(printf "%${#p}d" $'{1,2}' | grep -o .)' |
    awk '{printf $1+$2}' | awk 4
}

noCarryAddition 2 11   # => 13
noCarryAddition 16 18  # => 214
noCarryAddition 122 81 # => 1103
 

This reminds me of the quote: "Whatever you do, there is an asian doing it better."
Nice solution!!

 
const noCarryAddition = (num1, num2) => {
  let result = [];
  if (num1.length >= num2.length) {
    num1.toString().split('').reverse().map((n1, index) => result.push(+n1 + +(num2.toString().split('').reverse()[index] || 0)));
  } else {
    num2.toString().split('').reverse().map((n2, index) => result.push(+n2 + +(num1.toString().split('').reverse()[index] || 0)));
  }
  return result.reverse().join('');
}

Took a slightly bigger approach, but it works :)

 

Ruby, because Ruby has built-in divmod, because you need both at least as often as you need either.

def piecewise_add(n1, n2)
  return n1+n2 if n1*n2 == 0
  d1, m1 = n1.divmod(10)
  d2, m2 = n2.divmod(10)
  m3 = m1+m2
  mult = m3 > 9 ? 100 : 10
  mult*piecewise_add(d1, d2)+m3
end
 

Rust

(without stringification)

fn euthanize(mut a: u64, mut b: u64) -> u64 {
    let mut out = 0;
    let mut cursor = 1;
    loop {
        let sum = a % 10 + b % 10;
        out += sum * cursor;
        cursor *= if sum < 10 { 10 } else { 100 };
        a /= 10;
        b /= 10;
        if a == 0 && b == 0 {
            return out;
        }
    }
}

// test

fn main() {
    assert_eq!(euthanize(2, 11), 13);
    assert_eq!(euthanize(16, 18), 214);
    assert_eq!(euthanize(122, 81), 1103);
    dbg!(euthanize(1222, 30277));
    dbg!(euthanize(1236, 30889));
    dbg!(euthanize(49999, 49999));
}

(look at it go)

 
// Author: Tanuj Raghav <anwailuisa>

#include<bits/stdc++.h>
using namespace std;

#define fastIO ios_base::sync_with_stdio(false); cin.tie(0);

int main(){
    fastIO;
    string a,b;
    cin>>a>>b;
    if(a.size()<b.size())
        for(int i=0;i<b.size()-a.size();i++)
            a.insert(0,"0");
    else if(b.size()<a.size())
        for(int i=0;i<a.size()-b.size();i++)
            b.insert(0,"0");
    vector<int> sum;
    for(int i=a.size()-1;i>=0;i--)
        sum.push_back(int(a[i])+int(b[i])-96);
    for(int i=sum.size()-1;i>=0;i--)
        cout<<sum[i];
    cout<<"\n";
}
 

Here is my simple solution with Python:

def add(num1, num2):
    num_string1 = str(num1)
    num_string2 = str(num2)

    is_done = False
    if len(num_string1) > len(num_string2):
        length = len(num_string1) - len(num_string2)
        num_string2 = '0' * length + num_string2
        is_done = True
    if len(num_string1) < len(num_string2) and is_done is False:
        length = len(num_string2) - len(num_string1)
        num_string1= '0' * length + num_string1

    ans = ''
    index = 0

    while index < len(num_string1):
        ans += str(int(num_string1[index]) + int(num_string2[index]))
        index += 1

    return int(ans)
 

Old school JS version, not super optimized, but should be faster than, map, join, split etc

function noCarryAddition(n0, n1) {

        var a = n0.toString();
        var b = n1.toString();
        var maxLength = Math.max(a.length, b.length);
        var s = '';

        for (var i = maxLength - 1; i >= 0; --i) {

            var indexA = a.length - (i + 1);
            var indexB = b.length - (i + 1);

            var valueA = (indexA >= 0)? parseInt(a[indexA]) : 0;
            var valueB = (indexB >= 0)? parseInt(b[indexB]) : 0;

            s += (valueA + valueB);
        }

        return s;
    }
 

Hardcore? Yeah, I'm diggin' into that.

def add(n1, n2):
    nums = [str(n1), str(n2)]
    nums = list(map(lambda s: s.zfill(max(map(len, nums))), nums))

    result = [str(int(v1) + int(v2)) for v1, v2 in zip(*nums)]

    return int(''.join(result))
 

Python 🐍

Not the solution i like but it does the job.


def sum_(first: int, second: int) -> int:
  first_mapped = str(first)
  second_mapped = str(second)

  # Fill the smallest list with '0' on left
  if len(first_mapped) > len(second_mapped):
    second_mapped = second_mapped.zfill(len(first_mapped))
  elif len(second_mapped) > len(first_mapped):
    first_mapped = first_mapped.zfill(len(second_mapped))

  result = ''
  for x, y in zip(first_mapped, second_mapped):
    result += str(int(x) + int(y))

  return int(result)
 

Technically correct, but I tended to think of the solution backward, so it does way more reversing then it should to get things back in place to finish it.