Programming Praxis

Home | Pages | Archives

Pounds, Shillings, Pence

April 7, 2015 9:00 AM

Let’s take as an example the pounds-shillings-pence system (20 12). We express a number as (7 12 3) meaning 7 poungs, 12 shillings, and 3 pence. The sum of (7 12 3) and (8 14 10) is then (16 7 1), since 3 pence and 10 pence form 1 shilling and 1 penny, 12 shillings and 14 shillings, plus the 1 shilling carried over from the pence calculation, for 1 pound and 7 shillings, and 7 pounds and 8 pounds, plus the 1 pound carried over from the shilling calculation, form 16 pounds. We never write (15 26 13), even though that is the position-by-position sum, because that is considered incorrect form, so our first function normalizes a number:

(define (normalize schema number)
  (let loop ((ss (reverse schema))
             (ns (reverse number))
             (result (list)) (carry 0))
    (drop-while zero?
      (cond ((null? ns)
              (if (zero? carry) result
                (cons carry result)))
            ((null? ss)
              (cons (+ carry (car ns)) result))
            (else (loop (cdr ss) (cdr ns)
              (cons (modulo (+ (car ns) carry) (car ss)) result)
              (let* ((x (+ (car ns) carry))
                     (q (quotient x (car ss)))
                     (r (remainder x (car ss))))
                (if (negative? r) (- q 1) q))))))))

This is tricky, for a couple of reasons. First, Scheme rounds the quotient toward zero, which does the wrong thing when one of the elements of the number is negative. Second, we want to suppress leading zeros. For instance:

> (normalize '(20 12) '(15 26 13))
(16 7 1)
> (normalize '(20 12) '(1 -2 7))
(18 7)

Then addition or subtraction just proceeds element-wise through the number-lists and normalizes at the end; we can’t say (normalize schema (map op x y)) because the numbers might have varying length:

(define (plus/minus schema op x y)
  (let loop ((xs (reverse x))
             (ys (reverse y))
             (result (list)))
    (cond ((and (null? xs) (null? ys))
            (normalize schema result))
          ((null? xs)
            (loop xs (cdr ys) (cons (car ys) result)))
          ((null? ys)
            (loop (cdr xs) ys (cons (car xs) result)))
          (else (loop (cdr xs) (cdr ys)
            (cons (op (car xs) (car ys)) result))))))

Here are some examples:

> (plus/minus '(20 12) + '(8 12 10) '(7 14 3))
(16 7 1)
> (plus/minus '(20 12) - '(8 12 10) '(7 14 3))
(18 7)
> (plus/minus '(20 12) - '(7 14 3) '(8 12 10))
(-1 1 5)

We used drop-while from the Standard Prelude. You can run the program at http://ideone.com/yojsBB.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

9 Responses to “Pounds, Shillings, Pence”

1. In Python.

   
   def number_to_mixed_radix(number, radices):
   	result = [0]*(len(radices))
   	for i in range(len(radices)-1, -1, -1):
   		result[i] = number % radices[i]
   		number = number / radices[i]
   	return result
   
   def mixed_radix_to_number(radix_number, radices):
   	result = 0
   	for i in range(len(radices)):
   		result = result * radices[i] + radix_number[i]
   	return result
   
   
   
   if __name__ == "__main__":
   	# weeks, days, hours, minutes, seconds
   	radices = [52,7,24,60,60]
   
   	# 1 second less than 1 week
   	number = 7*24*60*60-1
   	print number_to_mixed_radix(number, radices)
   
   	# 1 second less than 1 hour
   	radix_number = [0,0,1,0,-1]
   	print mixed_radix_to_number(radix_number, radices)
   
   
   	# 1000 pounds, 20 shilling, 12 pence
   	radices = [1000,20,12]
   	maximum = 1
   	for v in radices:
   		maximum *= v
   	# some random tests
   	import random 
   	for i in range(10000):
   		number = random.randint(1, maximum)
   		assert number == mixed_radix_to_number(number_to_mixed_radix(number, radices), radices)
   

   By Rutger on April 7, 2015 at 10:05 AM

2. fix markup?

   def number_to_mixed_radix(number, radices):
   result = [0]*(len(radices))
   for i in range(len(radices)-1, -1, -1):
   result[i] = number % radices[i]
   number = number / radices[i]
   return result
   
   def mixed_radix_to_number(radix_number, radices):
   result = 0
   for i in range(len(radices)):
   result = result * radices[i] + radix_number[i]
   return result
   
   if __name__ == "__main__":
   # weeks, days, hours, minutes, seconds
   radices = [52,7,24,60,60]
   
   # 1 second less than 1 week
   number = 7*24*60*60-1
   print number_to_mixed_radix(number, radices)
   
   # 1 second less than 1 hour
   radix_number = [0,0,1,0,-1]
   print mixed_radix_to_number(radix_number, radices)
   
   # 1000 pounds, 20 shilling, 12 pence
   radices = [1000,20,12]
   maximum = 1
   for v in radices:
   maximum *= v
   # some random tests
   import random
   for i in range(10000):
   number = random.randint(1, maximum)
   assert number == mixed_radix_to_number(number_to_mixed_radix(number, radices), radices)
   

   By Rutger on April 7, 2015 at 10:06 AM

3. really

   def number_to_mixed_radix(number, radices):
   	result = [0]*(len(radices))
   	for i in range(len(radices)-1, -1, -1):
   		result[i] = number % radices[i]
   		number = number / radices[i]
   	return result
   
   def mixed_radix_to_number(radix_number, radices):
   	result = 0
   	for i in range(len(radices)):
   		result = result * radices[i] + radix_number[i]
   	return result
   
   
   
   if __name__ == "__main__":
   	# weeks, days, hours, minutes, seconds
   	radices = [52,7,24,60,60]
   
   	# 1 second less than 1 week
   	number = 7*24*60*60-1
   	print number_to_mixed_radix(number, radices)
   
   	# 1 second less than 1 hour
   	radix_number = [0,0,1,0,-1]
   	print mixed_radix_to_number(radix_number, radices)
   
   
   	# 1000 pounds, 20 shilling, 12 pence
   	radices = [1000,20,12]
   	maximum = 1
   	for v in radices:
   		maximum *= v
   	# some random tests
   	import random 
   	for i in range(10000):
   		number = random.randint(1, maximum)
   		assert number == mixed_radix_to_number(number_to_mixed_radix(number, radices), radices)
   

   By Rutger on April 7, 2015 at 10:08 AM

4. Nice little problem. Here’s a solution using C arrays, handling carries and borrows as in normal decimal addition. Input can be non-normalized, but the output is always normalized (so adding or subtracting zero normalizes a number). Least significant digit first (though I’ve printed the digits in the opposite order):

   #include <stdio.h>
   
   int radixadd(int *a, const int *b, const int *r, int n) {
     for (int c = 0, i = 0; ; i++) {
       int k = a[i]+b[i]+c;
       if (i < n) {
         c = k/r[i]; a[i] = k%r[i];
       } else {
         a[n] = k; break;
       }
     }
   }
   
   int radixsub(int *a, const int *b, const int *r, int n) {
     for (int c = 0, i = 0; ; i++) {
       int k = a[i]-b[i]+c;
       if (i < n) {
         c = k/r[i]; a[i] = k%r[i];
         if (a[i] < 0) {
           a[i] += r[i]; c--; // modulus should be positive
         }
       } else {
         a[n] = k; break;
       }
     }
   }
   
   int total(int *a, const int *r, int n) {
     int c = a[n];
     for (int i = n; i > 0; i--) {
       c = r[i-1]*c + a[i-1];
     }
     return c;
   }
   
   int main()
   {
     int r[] = { 12, 20 };
     int zero[] = { 0, 0, 0 };
     int a[] = { 1729, 0, 0 };
     int b[] = { 250, 0, 0 };
     radixadd(a,zero,r,2); // Normalize
     printf("%d %d %d: %d\n", a[2],a[1],a[0], total(a,r,2));
     radixadd(b,zero,r,2); // Normalize
     printf("%d %d %d: %d\n", b[2],b[1],b[0], total(b,r,2));
     radixadd(a,b,r,2); // Add b to a
     radixadd(a,b,r,2); // Add b to a
     printf("%d %d %d: %d\n", a[2],a[1],a[0], total(a,r,2));
     radixsub(a,b,r,2); // Sub b from a
     radixsub(a,b,r,2); // Sub b from a
     printf("%d %d %d: %d\n", a[2],a[1],a[0], total(a,r,2));
     radixsub(b,a,r,2); // Sub a from b
     printf("%d %d %d: %d\n", b[2],b[1],b[0], total(b,r,2));
     radixadd(b,a,r,2); // Sub a from b
     printf("%d %d %d: %d\n", b[2],b[1],b[0], total(b,r,2));
   }
   

   By matthew on April 7, 2015 at 11:01 PM

5. radixadd and radixsub should return void there (I missed -Wall off the compilation line).

   By matthew on April 7, 2015 at 11:13 PM

6. Solution in Java. However, leading zero’s are not removed..

   package com.experiment;
   
   public class PoundsShillingsPence {
   
   	private static int[] result;
   	public static void main(String[] args) {
   		operate('+', new int[] {20, 12}, new int[] {8, 12, 10}, new int[] {7, 14, 3});
   		operate('-', new int[] {20, 12}, new int[] {8, 12, 10}, new int[] {7, 14, 3});
   		operate('-', new int[] {20, 12}, new int[] {7, 14, 3}, new int[] {8, 12, 10});
   	}
   	
   	private static void normalize(int[] scheme, int[] input) {
   		int mod, s, i, carry=0;
   		result = new int[input.length];
   		for(s = scheme.length-1, i = input.length-1;i>=0;i--,s--) {
   			if(s>=0) {
   				mod = (input[i]+carry)%scheme[s];
   				carry = (input[i]+carry)/scheme[s];
   				if(mod<0) { 
   					mod = mod+scheme[s]; 
   					carry = carry-1;
   				}
   				result[i] = mod;
   			} else {
   				result[i] = (input[i]+carry);
   			}
   		}
   		System.out.print("{");
   		for(int l=0;l<result.length;l++) {
   			System.out.print(result[l]);
   			if(l!=result.length-1)
   				System.out.print(",");
   		}
   		System.out.print("}\n");
   	}
   	
   	private static void operate(char operator, int[] schema, int[] input1, int[] input2) {
   		int i1 = input1.length;
   		int i2 = input2.length;
   		int r = i1<i2?i2:i1;
   		int result[] = new int[r];
   		
   		for(i1=i1-1,i2=i2-1,r=r-1;;i1--,i2--,r--) {
   			if(i1<0 && i2<0) {
   				break; 
   			}
   			if(i1<0) {
   				result[i2] = input2[i2];
   				continue;
   			}
   			if(i2<0) {
   				result[i1] = input1[i1];
   				continue;
   			}
   			if(operator=='+') {
   				result[r] = input1[i1]+input2[i2];
   			}
   			else if(operator=='-')
   				result[r] = input1[i1]-input2[i2];
   			else {
   				System.out.println("Invalid operator. Only + and - are supported");
   				return;
   			}
   		}
   		normalize(schema, result);
   	}
   }
   

   By Krishnan R on April 8, 2015 at 10:25 AM

7. An example in ISO Prolog (gprolog):

   :- initialization(main).

   main :-
           % Weeks, days, hours, minutes, seconds
           Number is 7*24*60*60-1, % 1 second less than 1 week
           mixed_radix_number([52,7,24,60,60], Ns, Number),
           format(‘~d weeks, ~d days, ~d hours, ~d minutes, and ~d seconds~n’, Ns),
           Hourm1sec = [0,0,1,0,-1], % 1 second less than 1 hour
           mixed_radix_number([52,7,24,60,60], Hourm1sec, Secs),
           mixed_radix_number([52,7,24,60,60], Nd, Secs),
           format(‘1 second less than 1 hour ~w = ~w = ~d seconds~n’,
                   [Hourm1sec,Nd,Secs]),
           Ym1sec = [364,0,0,-1], % 1 year – 1 second, but 7*52 = 364
           mixed_radix_number([365,24,60,60],Ym1sec,S),
           mixed_radix_number([365,24,60,60],Ym1sec,S),
           mixed_radix_number([52,7,24,60,60],Yw,S),
           format(‘1 second less than 1 year in days and time: ~w~n’,[Ym1sec]),
           format(‘1 second less than 1 year in weeks, days and time: ~w~n’,
                   [Yw]),
           format(‘ 7 weekdays * 52 weeks in days: 364~n’,[]),
           format(‘1 second less than 1 year in seconds: ~d~n’,[S]),
           % Pounds, shillings, pence
           mixed_radix_number([999999,20,12],[8,12,10],Pence),
           format(‘~d £, ~d shillings, and ~d pence are ~d pence total~n’,
                   [8,12,10,Pence]),
           mixed_radix_number([1000,20,12],Ps,Pence),
           format(‘~d pence are ~d £, ~d shillings, and ~d pence~n’,[Pence|Ps]),
           mixed_radix_number([1000,20,12],[8,12,10],Pence),
           % Degrees, minutes, seconds
           mixed_radix_number([360,60,60],[53,45,20],Seconds),
           format(’53 degrees 45”20”” W is ~d seconds west~n’,[Seconds]),
           % Binary numbers
           mixed_radix_number([2,2,2,2,2,2,2,2],B,67),
           format(’67 in a binary (octet) is ~w~n’,[B]),
           % Hexadecimal numbers
           mixed_radix_number([16,16],[7,15],Hx),
           format(‘7F hexadecimal is ~d decimal~n’, [Hx]),
           mixed_radix_number([16,16],Hx1,254),
           format(‘254 decimal is ~w hexadecimal~n’, [Hx1]),
           halt.

   % mixed_radix_number(+Radices, +Mixed, ?Number)
   % mixed_radix_number(+Radices, -Mixed, +Number)
   mixed_radix_number(Rs, Ns, S) :- nonvar(Ns), !,
           decoded_mixed_radix_number(Rs, Ns, 0, S).
   mixed_radix_number(Rs, Ns, S) :- var(Ns),
           reverse(Rs, Rs1),
           encoded_mixed_radix_number(Rs1, [], Ns, S).

   decoded_mixed_radix_number([], [], S, S).
   decoded_mixed_radix_number([R|Rs], [N|Ns], S0, S) :-
           S1 is R * S0 + N,
           decoded_mixed_radix_number(Rs, Ns, S1, S).

   encoded_mixed_radix_number([], Ns, Ns, _S).
   encoded_mixed_radix_number([R|Rs], Ns0, Ns, S) :-
           Rem is S mod R,
           S1 is floor(S / R),
           encoded_mixed_radix_number(Rs, [Rem|Ns0], Ns, S1).
   [/source/

   By Dennis Decker Jensen on April 10, 2015 at 12:08 AM

8. Alas, try again to get formatting right:

   :- initialization(main).
   
   main :-
           % Weeks, days, hours, minutes, seconds
           Number is 7*24*60*60-1, % 1 second less than 1 week
           mixed_radix_number([52,7,24,60,60], Ns, Number),
           format('~d weeks, ~d days, ~d hours, ~d minutes, and ~d seconds~n', Ns),
           Hourm1sec = [0,0,1,0,-1], % 1 second less than 1 hour
           mixed_radix_number([52,7,24,60,60], Hourm1sec, Secs),
           mixed_radix_number([52,7,24,60,60], Nd, Secs),
           format('1 second less than 1 hour ~w = ~w = ~d seconds~n',
                   [Hourm1sec,Nd,Secs]),
           Ym1sec = [364,0,0,-1], % 1 year - 1 second, but 7*52 = 364
           mixed_radix_number([365,24,60,60],Ym1sec,S),
           mixed_radix_number([365,24,60,60],Ym1sec,S),
           mixed_radix_number([52,7,24,60,60],Yw,S),
           format('1 second less than 1 year in days and time:        ~w~n',[Ym1sec]),
           format('1 second less than 1 year in weeks, days and time: ~w~n',
                   [Yw]),
           format('                    7 weekdays * 52 weeks in days: 364~n',[]),
           format('1 second less than 1 year in seconds:              ~d~n',[S]),
           % Pounds, shillings, pence
           mixed_radix_number([999999,20,12],[8,12,10],Pence),
           format('~d £, ~d shillings, and ~d pence are ~d pence total~n',
                   [8,12,10,Pence]),
           mixed_radix_number([1000,20,12],Ps,Pence),
           format('~d pence are ~d £, ~d shillings, and ~d pence~n',[Pence|Ps]),
           mixed_radix_number([1000,20,12],[8,12,10],Pence),
           % Degrees, minutes, seconds
           mixed_radix_number([360,60,60],[53,45,20],Seconds),
           format('53 degrees 45''20'''' W is ~d seconds west~n',[Seconds]),
           % Binary numbers
           mixed_radix_number([2,2,2,2,2,2,2,2],B,67),
           format('67 in a binary (octet) is ~w~n',[B]),
           % Hexadecimal numbers
           mixed_radix_number([16,16],[7,15],Hx),
           format('7F hexadecimal is ~d decimal~n', [Hx]),
           mixed_radix_number([16,16],Hx1,254),
           format('254 decimal is ~w hexadecimal~n', [Hx1]),
           halt.
   
   % mixed_radix_number(+Radices, +Mixed, ?Number)
   % mixed_radix_number(+Radices, -Mixed, +Number)
   mixed_radix_number(Rs, Ns, S) :- nonvar(Ns), !,
           decoded_mixed_radix_number(Rs, Ns, 0, S).
   mixed_radix_number(Rs, Ns, S) :- var(Ns),
           reverse(Rs, Rs1),
           encoded_mixed_radix_number(Rs1, [], Ns, S).
   
   decoded_mixed_radix_number([], [], S, S).
   decoded_mixed_radix_number([R|Rs], [N|Ns], S0, S) :-
           S1 is R * S0 + N,
           decoded_mixed_radix_number(Rs, Ns, S1, S).
   
   encoded_mixed_radix_number([], Ns, Ns, _S).
   encoded_mixed_radix_number([R|Rs], Ns0, Ns, S) :-
           Rem is S mod R,
           S1 is floor(S / R),
           encoded_mixed_radix_number(Rs, [Rem|Ns0], Ns, S1).
   

   By Dennis Decker Jensen on April 10, 2015 at 12:11 AM

9. Have mercy, this does not bode well, 3rd time:

   :- initialization(main).
   
   main :-
           % Weeks, days, hours, minutes, seconds
           Number is 7*24*60*60-1, % 1 second less than 1 week
           mixed_radix_number([52,7,24,60,60], Ns, Number),
           format('~d weeks, ~d days, ~d hours, ~d minutes, and ~d seconds~n', Ns),
           Hourm1sec = [0,0,1,0,-1], % 1 second less than 1 hour
           mixed_radix_number([52,7,24,60,60], Hourm1sec, Secs),
           mixed_radix_number([52,7,24,60,60], Nd, Secs),
           format('1 second less than 1 hour ~w = ~w = ~d seconds~n',
           [Hourm1sec,Nd,Secs]),
           Ym1sec = [364,0,0,-1], % 1 year - 1 second, but 7*52 = 364
           mixed_radix_number([365,24,60,60],Ym1sec,S),
           mixed_radix_number([365,24,60,60],Ym1sec,S),
           mixed_radix_number([52,7,24,60,60],Yw,S),
           format('1 second less than 1 year in days and time:        ~w~n',[Ym1sec]),
           format('1 second less than 1 year in weeks, days and time: ~w~n',
           [Yw]),
           format('                    7 weekdays * 52 weeks in days: 364~n',[]),
           format('1 second less than 1 year in seconds:              ~d~n',[S]),
           % Pounds, shillings, pence
           mixed_radix_number([999999,20,12],[8,12,10],Pence),
           format('~d £, ~d shillings, and ~d pence are ~d pence total~n',
           [8,12,10,Pence]),
           mixed_radix_number([1000,20,12],Ps,Pence),
           format('~d pence are ~d £, ~d shillings, and ~d pence~n',[Pence|Ps]),
           mixed_radix_number([1000,20,12],[8,12,10],Pence),
           % Degrees, minutes, seconds
           mixed_radix_number([360,60,60],[53,45,20],Seconds),
           format('53 degrees 45''20'''' W is ~d seconds west~n',[Seconds]),
           % Binary numbers
           mixed_radix_number([2,2,2,2,2,2,2,2],B,67),
           format('67 in a binary (octet) is ~w~n',[B]),
           % Hexadecimal numbers
           mixed_radix_number([16,16],[7,15],Hx),
           format('7F hexadecimal is ~d decimal~n', [Hx]),
           mixed_radix_number([16,16],Hx1,254),
           format('254 decimal is ~w hexadecimal~n', [Hx1]),
           halt.
   
   % mixed_radix_number(+Radices, +Mixed, ?Number)
   % mixed_radix_number(+Radices, -Mixed, +Number)
   mixed_radix_number(Rs, Ns, S) :- nonvar(Ns), !,
           decoded_mixed_radix_number(Rs, Ns, 0, S).
   mixed_radix_number(Rs, Ns, S) :- var(Ns),
           reverse(Rs, Rs1),
           encoded_mixed_radix_number(Rs1, [], Ns, S).
   
   decoded_mixed_radix_number([], [], S, S).
   decoded_mixed_radix_number([R|Rs], [N|Ns], S0, S) :-
           S1 is R * S0 + N,
           decoded_mixed_radix_number(Rs, Ns, S1, S).
   
   encoded_mixed_radix_number([], Ns, Ns, _S).
   encoded_mixed_radix_number([R|Rs], Ns0, Ns, S) :-
           Rem is S mod R,
           S1 is floor(S / R),
           encoded_mixed_radix_number(Rs, [Rem|Ns0], Ns, S1).
   

   By Dennis Decker Jensen on April 10, 2015 at 12:16 AM

Leave a Reply

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.