Programming Praxis

6 Responses to “Casting Out Nines”

1. chaw said

   November 17, 2017 at 2:06 PM

   This code tries to stay true to the spirit of the “by hand”
   procedure (as opposed to being efficient for a computer). For
   instance, it uses a naive conversion to digits as one would do by
   hand (by simply “writing digits separately”). The code uses only
   addition, subtraction, and comparison of small numbers (in
   particular, no division). One point of divergence is that it only
   considers digits sequentially when casting out nines; i.e.,
   non-consecutive digits that sum to 9 are not eliminated (e.g., the
   3 and 6 from the first two addends of the example).

   (import (scheme base)
           (scheme write)
           (only (srfi 1)
                 fold first second))
   
   (define addends-101 '(3074 6017 13814 1810 27 3611))
   
   (define sum-101 28353)
   
   (define (add-mod-9 a b)
     (let ((s (+ a b)))
       (if (< s 9)
           s
           (- s 9))))
   
   (define (digits n)
     (map string->number
          (map string
               (string->list (number->string n)))))
   
   (define (cast-out-nines n)
     (let f ((n n))
       (if (< n 9)
           n
           (f (fold add-mod-9 0 (digits n))))))
   
   (define (cast-out-nines/casts ds)
     (let f ((ds ds))
       (if (null? (cdr ds))
           (car ds)
           (f (cons (add-mod-9 (first ds)
                               (second ds))
                    (cddr ds))))))
   
   (define (check-addition/casting-out-nines addends sum)
     (= (cast-out-nines/casts (map cast-out-nines addends))
        (cast-out-nines sum)))
   
   (display (check-addition/casting-out-nines addends-101 sum-101))
   (newline)
   
2. chaw said

   November 17, 2017 at 2:28 PM

   On second thought, my earlier code can be much simplified. (I decided
   to use fold part-way through and didn’t finish the job.)

   (import (scheme base)
           (scheme write)
           (only (srfi 1)
                 fold first second delete))
   
   (define addends-101 '(3074 6017 13814 1810 27 3611))
   
   (define sum-101 28353)
   
   (define (add-mod-9 a b)
     (let ((s (+ a b)))
       (if (< s 9)
           s
           (- s 9))))
   
   (define (digits n)
     (map string->number
          (map string
               (string->list (number->string n)))))
   
   (define (cast-out-nines n)
     (cast-out-nines/casts (delete 9 (digits n))))
   
   ;; each d is in 0..8
   (define (cast-out-nines/casts ds)
     (fold add-mod-9 0 ds))
   
   (define (check-addition/casting-out-nines addends sum)
     (= (cast-out-nines/casts (map cast-out-nines addends))
        (cast-out-nines sum)))
   
   (display (check-addition/casting-out-nines addends-101 sum-101))
   (newline)
   
3. matthew said

   November 18, 2017 at 10:54 AM

   Goes quite nicely into a double fold:

   import Data.Digits (digits)
   
   addmod k n m = (n+m) `mod` k
   
   f = foldl (addmod 9)
   
   main =
     print (f 0 (digits 10 28353)) >>
     print (foldl f 0 (map (digits 10) [3074, 6017, 13814, 1810, 27, 3611]))
   
4. matthew said

   November 19, 2017 at 5:15 PM

   Here’s a generalization to any radix (so we are “casting out n’s” for radix n+1). More Haskell:

   import Data.Digits (digits)
   
   cast radix = foldl (foldl addmod) 0 . map (digits radix)
     where addmod n m = mmod (n+m) (radix - 1)
           mmod n k = if n < k then n else n-k
   
   -- cast radix s = (sum s) mod (radix-1)
   main =
     print (map (28353 `mod`) [1..19]) >>
     print (map (flip cast [28353]) [2..20]) >>
     print (map (flip cast [3074, 6017, 13814, 1810, 27, 3611]) [2..20])
   -- [0,1,0,1,3,3,3,1,3,3,6,9,0,3,3,1,14,3,5]
   -- [0,1,0,1,3,3,3,1,3,3,6,9,0,3,3,1,14,3,5]
   -- [0,1,0,1,3,3,3,1,3,3,6,9,0,3,3,1,14,3,5]
   
5. Alex B said

   November 22, 2017 at 5:14 AM

   Python 3 solution, not using recursion.

   def cast_nines(n):
       if not isinstance(n, int):
           raise TypeError('Expected integer')
       if n < 0:
           raise ValueError('Must be positive')
   
       running_sum = 0
   
       while n > 0:
           n, last_digit = divmod(n, 10)
           running_sum += last_digit
           if running_sum >= 9:
               running_sum -= 9
       return running_sum
   

   And the test:

   >>> assert all(cast_nines(i) == i%9 for i in range(1001)), 'FAILED'
   >>> 
   
6. Daniel said

   December 11, 2017 at 1:14 AM

   Here’s a solution in Ruby.

   # Returns the digits in a number
   # E.g., digits(39412) -> [3,9,4,1,2]
   def get_digits(number)
     output = []
     number = number.abs
     while number > 0
       number, digit = number.divmod(10)
       output.push(digit)
     end
     output.reverse
   end
   
   # Sums numbers
   def sum(numbers)
     numbers.inject(0, :+)
   end
   
   # Multiplies numbers
   def multiply(numbers)
     numbers.inject(1, :*)
   end
   
   def cast_out_nines(number)
     loop do
       digits = get_digits(number)
       # digit_table maps digits to counts (indices correspond to digits)
       digit_table = [0] * 10
       digits.each { |digit| digit_table[digit] += 1 }
       # cast out nines
       digit_table[9] = 0
       # cast out pairs that sum to nine:
       #   (1,8), (2,7), (3,6), (4,5)
       # (0,9) excluded since 9 already cast out.
       (1..4).each do |digit|
         other_digit = 9 - digit
         digit_count = digit_table[digit]
         other_digit_count = digit_table[other_digit]
         num_cast_outs = [digit_count, other_digit_count].min
         digit_table[digit] -= num_cast_outs
         digit_table[other_digit] -= num_cast_outs
       end
       # add remaining digits
       number = sum((0..9).zip(digit_table).map(&method(:multiply)))
       break if number < 9
     end
     number
   end
   
   puts "cast_out_nines(input)"
   puts cast_out_nines(
            cast_out_nines(3074)  +
            cast_out_nines(6017)  +
            cast_out_nines(13814) +
            cast_out_nines(1810)  +
            cast_out_nines(27)    +
            cast_out_nines(3611)
        )
   puts "cast_out_nines(output)"
   puts cast_out_nines(28353)
   

   Output:

   cast_out_nines(input)
   3
   cast_out_nines(output)
   3