Topic: ( Challenge ) How many 'carrys'?

[Mark]

It has been a long time since we have had a challenge around here. I hope this one keeps you occupied for a little while.

When you do addition you 'carry' the 1 if the total is greater than 9. For example if we add 109 and 209 we would have one 'carry';

  1  <- one 'carry'
109
209
---
318

Challenge:
given two integers return how many 'carrys' we have.

The attached file has a two integers per line, you can use it or user input.

Not my idea, it was borrowed.

P.S. Additional languages are allowed

[JohnK]

Oh good one. Im going to think about this one at lunch.

[VovKa]

Code: [Select]

(defun test (n1 n2)
  (if (or (zerop n1) (zerop n2))
    0
    (if (< 9 (+ (rem n1 10) (rem n2 10)))
      (1+ (if (= 9 (rem (/ n1 10) 10))
    (test (/ n1 10)
  (if (= 9 (rem (/ n2 10) 10))
    (/ n2 10)
    (1+ (/ n2 10))
  )
    )
    (test (1+ (/ n1 10)) (/ n2 10))
  )
      )
      (test (/ n1 10) (/ n2 10))
    )
  )
)


[gile]

Very nice Vovka !

[SomeCallMeDave]

Does it have to be a LISP solution?

I have been playing with Ruby and cobbled this one together

Code: [Select]

def count_the_carry(string1, string2)
  #assumes strings are same length and numeric
  array1 = string1.split(//).collect{|x| x.to_i}
  array2 = string2.split(//).collect{|x| x.to_i}
  sum_array = Array.new
  array1.size.times {|i| sum_array[i]=array1[i]+array2[i]}
  carry_count = 0
  sum_array.each {|x| carry_count += 1 if x >=10}
  carry_count
end

input_file = File.new("c:/jobs/random_ints.txt", "r" )
output_file = File.new("c:/jobs/counts.txt", "w")
while (line = input_file.gets)
   nums = line.split
   count = count_the_carry(nums[0], nums[1])
   output_file.write(count.to_s + "\n")
end
input_file.close
output_file.close



My answers are attached

[VovKa]

thanx gile
i'm sorry but there was a mistake in the routine
i hope now it's ok

[Mark]

Does it have to be a LISP solution?

P.S. Additional languages are allowed

Nope!

[SomeCallMeDave]

Thanks, Mark.

Not only did I not read the original post correctly, I posted a solution that doesn't work. 

There is a particular case where my algorithm fails.  I won't spoil everyone else's fun by post it now.

Back to the drawing board for me.  At least Ruby is fun to play with.

[Tuoni]

For example if we add 109 and 209 we would have one 'carry';

...

To me that's two carries... you carry once into the 10's column then once into the 100's column?  Am I alone in this?

[ElpanovEvgeniy]

Code: [Select]

(defun test1 (a b)
 (if (zerop a)
  0
  (+ (/ (+ (rem a 10) (rem b 10)) 10) (test1 (/ a 10) (/ b 10)))
 ) ;_  if
)

[ronjonp]

Code: [Select]

(defun test1 (a b)
 (if (zerop a)
  0
  (+ (/ (+ (rem a 10) (rem b 10)) 10) (test1 (/ a 10) (/ b 10)))
 ) ;_  if
)

That's slick :kewl:

[VovKa]

ElpanovEvgeniy,
(test1 89 11) -> 1
should be 2

[ElpanovEvgeniy]

To me that's two carries... you carry once into the 10's column then once into the 100's column?  Am I alone in this?

Code: [Select]

(defun test-lst (l)
 ;;;(test-lst '(250 250 259 259))
 (if (cdr l)
  ((lambda (a)
    (+ a (test-lst (cons a (vl-remove 0 (mapcar '(lambda (a) (/ a 10)) l)))))
    )
   (/ (apply '+ (mapcar '(lambda (a) (rem a 10)) l)) 10)
  )
  0
 ) ;_  if
)

[ElpanovEvgeniy]

ElpanovEvgeniy,
(test1 89 11) -> 1
should be 2

Correction:

Code: [Select]

(defun test1 (a b)
 (if (zerop a)
  0
  ((lambda (c) (+ c (test1 (/ (+ c a) 10) (/ b 10))))
   (/ (+ (rem a 10) (rem b 10)) 10)
  )
 ) ;_  if
)

[VovKa]

ElpanovEvgeniy,
(test1 99 11) -> 1
should be 2

[MP]

python 3.x:

Code: [Select]

def carries (a, b):
    return (a%10 + b%10)//10 + carries (a//10, b//10) if a else 0

is cleaner, but may execute slower than:

Code: [Select]

def carries (a, b):
    return 0 if not a else (a%10 + b%10)//10 + carries (a//10, b//10)

or

Code: [Select]

def test (a, b):
    if a: return (a%10 + b%10)//10 + carries (a//10, b//10)           
    return 0


[ElpanovEvgeniy]

ElpanovEvgeniy,
(test1 99 11) -> 1
should be 2

My strategy was unsuccessful...

[ElpanovEvgeniy]

Code: [Select]

(defun test1 (a b) (test-lst (list a b)))(test1 99 11) => 2

[uncoolperson]

not pretty, but I had fun

Code: [Select]

(DEFUN carry (num1 num2)
  (SETQ carried 0
tocarry 0
index 0
str1 (ITOA num1)
str2 (ITOA num2)
  )
  (SETQ list1 (REVERSE
(MAPCAR '(LAMBDA (someitem) (ATOI (CHR someitem)))
(VL-STRING->LIST str1)
)
      )
  )
  (SETQ list2 (REVERSE
(MAPCAR '(LAMBDA (someitem) (ATOI (CHR someitem)))
(VL-STRING->LIST str2)
)
      )
  )
  (WHILE (< index (MAX (LENGTH list1) (LENGTH list2)))
    (IF (NOT
  (ZEROP
    (SETQ tocarry (REM (+ (NTH index list1) (NTH index list2) tocarry)
       10
  )
    )
  )
)
      (SETQ carried (1+ carried))
    )
    (SETQ index (1+ index))
  )
)

and again (same idea, kinda but funner)

Code: [Select]

(DEFUN carry (num1 num2)
  (SETQ carried 0
tocarry 0
index 0
str1 (ITOA num1)
str2 (ITOA num2)
  )
  (SETQ list1 (REVERSE
(MAPCAR '(LAMBDA (someitem) (ATOI (CHR someitem)))
(VL-STRING->LIST str1)
)
      )
  )
  (SETQ list2 (REVERSE
(MAPCAR '(LAMBDA (someitem) (ATOI (CHR someitem)))
(VL-STRING->LIST str2)
)
      )
  )
  (dowork list1 list2 0)
)


(DEFUN dowork (list1 list2 carry)
  (COND ((AND list1 list2)
(+ (COND ((> (SETQ tocarry (/ (+ (CAR list1) (CAR list2) carry) 10))
      0
   )
   1
  )
  (T 0)
    )
    (dowork (CDR list1) (CDR list2) tocarry)
)
)
(list1 (dowork list1 '(0) carry))
(list2 (dowork '(0) list2 carry))
(T 0)
  )
)

[ElpanovEvgeniy]

Code: [Select]

(defun test-lst (l)
 (if (cdr l)
  ((lambda (a) (+ a (test-lst (vl-remove 0 (cons a (mapcar '(lambda (a) (/ a 10)) l))))))
   (/ (apply '+ (mapcar '(lambda (a) (rem a 10)) l)) 10)
  )
  0
 ) ;_  if
) ;_  defun
(defun test2 (/ f l)
 (setq f (open "D:\\random_ints.txt" "r"))
 (while (car (setq l (cons (read-line f) l))))
 (close f)
 (setq f (open "D:\\carry.txt" "a"))
 (foreach a (reverse (cdr l)) (write-line (itoa (test-lst (read (strcat "(" a ")")))) f))
 (close f)
)

[CAB]

My kludge. 

Code: [Select]

(defun carries (a b / c clast)
  (setq clast 0
        c 0)
  (and (= (type a) 'INT) (setq a (float a)))
  (and (= (type b) 'INT) (setq b (float b)))
  (mapcar
    (function
      (lambda(m n)
        (if (> (+ m n clast -96) 9)
          (setq c (1+ c)
                clast 1)
          (setq clast 0)
        )
       )
      )
    (reverse(vl-remove 46(vl-string->list(rtos a 2 10))))
    (reverse(vl-remove 46(vl-string->list(rtos b 2 10))))
    )
  c
)
test code:

Code: [Select]

(defun c:test ()
  (princ (carries 9999 8888))           ;#=> 4
  (princ (carries 1111 8888))           ;#=> 0
  (princ (carries 56 45))               ;   #=> 2
  (princ (carries 11 89))               ;   #=> 2
  (princ (carries 11 79))               ;    1
  (princ (carries 99 11))               ;  2
  (princ (carries 99.795 11.54))        ;  4
  (princ)
)

[SomeCallMeDave]

Revised Ruby

Code: [Select]

def count_the_carry2(string1, string2)
  #assumes strings are same length and numeric
  array1 = string1.split(//).collect{|x| x.to_i}.reverse!
  array2 = string2.split(//).collect{|x| x.to_i}.reverse!
  carry = 0
  carry_count = 0
  array1.size.times {|i|
    sum = array1[i]+array2[i]
    carry_count += ((sum+carry) >= 10 ? 1 : 0 )
    carry = (sum >= 10 ? 1 : 0)
  }
  carry_count
end


Tests

Code: [Select]

puts count_the_carry2("9999", "8888")   #=> 4
puts count_the_carry2("1111", "8888")   #=> 0
puts count_the_carry2("56", "45")          #=> 2
puts count_the_carry2("11", "89")          #=> 2
puts count_the_carry2("11", "79")          #=> 1


[gile]

Hi,

LISP

Code: [Select]

(defun test (a b)
  (if (zerop a)
    0
    ((lambda (d / c)
       (+ c (/ d 10) (test d (/ b 10)))
     )
      (+ (/ a 10) (setq c (/ (+ (rem a 10) (rem b 10)) 10)))
    )
  )
)
C#

Code: [Select]

public static int test(int a, int b)
        {
            int c = (a % 10 + b % 10) / 10, d = a / 10 + c;
            return (a == 0) ? 0 : c + d / 10 + test(d , b / 10);
        }

[ElpanovEvgeniy]

Hi gile!

(test 11 89) => ; error: bad argument type: numberp: nil

 

[ElpanovEvgeniy]

Hi CAB!

(carries 9 91) => 1

[gile]

Corrected (I hope...)

LISP

Code: [Select]

(defun test (a b / c d)
  (if (zerop a)
    0
    (progn
      (setq c (/ (+ (rem a 10) (rem b 10)) 10)
    d (/ a 10)
      )
      (+ c (test d c) (test (+ d c) (/ b 10)))
    )
  )
)
C#

Code: [Select]

public static int test(int a, int b)
        {
            int c = (a % 10 + b % 10) / 10, d = a / 10;
            return (a == 0) ? 0 : c + test(d, c) + test(d + c , b / 10);
        }

[ElpanovEvgeniy]

Good code gile!

[ElpanovEvgeniy]

Not recursion...

Code: [Select]

(defun carries (a b / c i)
 (setq c 0 i 0)
 (while (not (zerop (+ a b)))
  (setq c (/ (+ (rem a 10) (rem b 10) c) 10)
        i (+ c i)
        a (/ a 10)
        b (/ b 10)
  )
 )
 i
)

[CAB]

Hi CAB!

(carries 9 91) => 1

Thanks for testing.

Code: [Select]

(defun carries (a b / c clast)
  (setq clast 0
        c 0)
  (and (= (type a) 'INT) (setq a (float a)))
  (and (= (type b) 'INT) (setq b (float b)))
  (setq a (reverse(vl-remove 46(vl-string->list(rtos a 2 10)))))
  (setq b (reverse(vl-remove 46(vl-string->list(rtos b 2 10)))))
  (if (> (length a)(length b)) ; add leading zero
    (setq a (append a (list 48)))
    (setq b (append b (list 48)))
  )
  (while (> (length a)(length b)) (setq b (append b (list 48))))
  (while (> (length b)(length a)) (setq a (append a (list 48))))
  (mapcar
    (function
      (lambda(m n)
        (if (> (+ m n clast -96) 9)
          (setq c (1+ c) clast 1)
          (setq clast 0)
        )
       )
      )
    a b
    )
  c
)

Code: [Select]

(defun c:test ()
  (print (carries 9999 8888))           ;  4
  (print (carries 1111 8888))           ;  0
  (print (carries 56 45))               ;  2
  (print (carries 11 89))               ;  2
  (print (carries 11 79))               ;  1
  (print (carries 99 11))               ;  2
  (print (carries 99.795 11.54))        ;  4
  (print (carries 99 1))                ;  2
  (princ)
)