Grade School Multiplication

November 18, 2011

Two weeks ago, on November 5th, the ACM sponsored its 2011 Mid-Central Regional Programming Contest for college student programmers. The seven problems, which were to be solved in five hours by teams of three programmers with a single shared computer, have been published. Today’s exercise asks you to solve the first problem involving grade school multiplication:

An educational software company, All Computer Math (ACM), has a section on multiplication of integers. They want to display the calculations in the traditional grade school format, like the following computation of 432 × 5678:

    432
   5678
-------
   3456
  3024
 2592
2160
-------
2452896

Note well that the final product is printed without any leading spaces, but that leading spaces are necessary on some of the other lines to maintain proper alignment. However, as per our regional rules, there should never be any lines with trailing white space. Note that the lines of dashes have length matching the final product.

As a special case, when one of the digits of the second operand is a zero, it generates a single 0 in the partial answers, and the next partial result should be on the same line rather than the next line down. For example, consider the following product of 200001 × 90040:

     200001
      90040
-----------
    8000040
180000900
-----------
18008090040

The rightmost digit of the second operand is a 0, causing a 0 to be placed in the rightmost column of the first partial product. However, rather than continue to a new line, the partial product of 4 × 200001 is placed on the same line as that 0. The third and fourth least-significant digits of the second operand are zeros, each resulting in a 0 in the second partial product on the same line as the result of 9 × 200001.

As a final special case, if there is only one line in the partial answer, it constitutes a full answer, and so there is no need for computing a sum. For example, a computation of 246 × 70 would be formatted as

  246
   70
-----
17220

Your job is to generate the solution displays.

Input: The input contains one or more data sets. Each data set consists of two positive integers on a line, designating the operands in the desired order. Neither number will have more than 6 digits, and neither will have leading zeros. After the last data set is a line containing only 0 0.

Output: For each data set, output a label line containing “Problem ” with the number of the problem, followed by the complete multiplication problem in accordance with the format rules described above.

Warning: A standard int type cannot properly handle 12-digit numbers. You should use a 64-bit type (i.e., a long in Java, or a long long in C++).

Example Input: Example Output:
432 5678
200001 90040
246 70
0 0
Problem 1
    432
   5678
-------
   3456
  3024
 2592
2160
-------
2452896
Problem 2
     200001
      90040
-----------
    8000040
180000900
-----------
18008090040
Problem 3
  246
   70
-----
17220

Your task is to solve Problem A. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below. As a special added bonus, feel free to solve any of the other problems in the programming contest, and to post your solution in the comments below.

About these ads

Pages: 1 2

6 Responses to “Grade School Multiplication”

  1. DGel said

    My quickly hacked together version in Python. Would love to see more elegant versions, but right now can’t think of one.

    #!/usr/bin/python
    
    import sys
    
    def expand_string(a, n):
        diff = n - len(a)
        if diff > 0:
            a = ' ' * diff + a
        return a
    
    def pprint_mult(i, j, counter):
        print "Problem", counter
        res = int(i) * int(j)
        length = len(str(res))
        separator = '-' * length
        print expand_string(i, length)
        i = int(i)
        print expand_string(j, length)
        print separator
        
        n_printed = 0
        printstring = ''
        printlen = length
        for pos in range(len(j)):
            if j[len(j) - 1 - pos] == '0':
                printstring += '0'
            else:
                print expand_string(str(int(j[len(j) - 1 - pos]) * i) + printstring, printlen)
                n_printed += 1
                printlen = length - pos - 1
                printstring = ''
        if n_printed > 1:
            print separator
            print res
        
    
    with open(sys.argv[1], 'r') as dfile:
        counter = 1
        for line in dfile:
            a, b = line.split()
            if a == '0' and b == '0':
                break
            pprint_mult(a, b, counter)
            counter += 1
    
  2. DGel said

    minor correction: instead of writing my expand_string() function, I could have used something like:

    ('{0: >' + str(printlen) + '}').format(int(j[len(j) - 1 - pos]) * i) + printstring)
    
  3. DGel said

    sigh… correction on my correction: I should leave the string conversion in :)

  4. ”’
    My python solution
    ”’
    i1=int(raw_input(‘enter first no’))
    i2=int(raw_input(‘enter second no’))
    print i1,’\n’,i2
    print ‘————‘
    t=i2
    cnt=0
    x=0
    while t!=0:
    x=(t%10)*i1
    if cnt==0 and x!=0:
    print x
    elif x!=0:
    print x*(cnt*10)
    t=t/10
    cnt+=1
    print ‘————‘
    print i1*i2

  5. 
    i1=int(raw_input('enter first no'))
    i2=int(raw_input('enter second no'))
    print i1,'\n',i2
    print '------------'
    t=i2
    cnt=0
    x=0
    while t!=0:
        x=(t%10)*i1
        if cnt==0 and x!=0:
            print x
        elif x!=0:
            print x*(cnt*10)
        t=t/10
        cnt+=1
    print '------------'
    print i1*i2
    
  6. A Clojure solution:

    (defn digits [n]
    	(loop [k n acc ()]
    		(if (zero? k) 
    			acc 
    			(recur (quot k 10) (conj acc (rem k 10))))))
    
    (defn partials [a b]
    	(map #(* % a) (digits b)))
    
    (defn repeated [n x]
    	(apply str (repeat n x)))
    
    (defn rpad [len pad n]
    	(str (repeated (- len (count (digits n))) pad) n))
    
    (defn print-multiplication [a b]
    	(let [r (* a b) rlen (count (digits r)) ps (reverse (partials a b))]
    		(println  (rpad rlen " " a) "x")
    		(println  (rpad rlen " " b))
            (when (not (= 1 (count (filter #(not (zero? %)) ps))))
    		  (println  (repeated rlen "-"))
              (loop [p ps i 0 suffix ""]
                  (when (seq p)
                      (when (not (zero? (first p)))
                          (println (str (rpad (- rlen i) " " (first p)) suffix)))
                      (recur 
                          (rest p) 
                          (inc i)
                          (if (zero? (first p)) (str suffix "0") "")))))
    		(println (repeated rlen "-"))
    		(println r)))
    
    (defn problem-a [filename]
      (let [stream (java.util.Scanner. (java.io.File. filename))]
            (while (.hasNextInt stream)
              (let [a (.nextInt stream) b (.nextInt stream)]
                (when (and (> a 0) (> b 0))
                  (print-multiplication a b))))))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 617 other followers

%d bloggers like this: