Sunday, February 5, 2012

When in Rome...

Let's start with the problem of adding Roman numerals, from Programming Praxis:
Your task is to write a function that takes two roman numerals (character strings) as input and returns their sum as a roman numeral as output. Be sure that input can be given in either the additive or subtractive forms of Roman numerals; give output using the subtractive form. What is add-roman("CCCLXIX", "CDXLVIII")?
Roman numerals are a natural development from tallying and finger counting. Some examples:
  • 1 = I = extend one finger on right hand
  • 2 = II = two fingers
  • 3 = III = three fingers
  • 4 = IIII = four fingers
  • 5 = V = right thumb
  • 6 = VI = right thumb and one finger
  • 9 = VIIII = right thumb and four fingers
  • 10 = X = one finger on left hand
  • 15 = XV = one finger on left hand and thumb on right hand
  • 50 = L = thumb on left hand
  • 77 = LXXVII = left thumb and two fingers, right thumb and two fingers
  • 99 = LXXXXVIIII = extend all fingers on both hands
  • 100 = C = out of fingers!
  • 500 = D
  • 1000 = M
These examples all take the additive form of Roman numerals, which I call "old style".  A later innovation, driven by desire for compactness is to use position and subtraction to avoid repetition of 4 symbols in a row.

Key cases:
  • 4 = IIII = IV
  • 9 = VIIII = IX
  • 40 = XXXX = XL
  • 90 = LXXXX = XC
  • 400 = CCCC = CD
  • 900 = DCCCC = CM
Please note that this more compact form is a step backwards in terms of computation: The beauty of tallying (and additive notations) is that you can add by simple collecting like symbols and then reducing.  For example:

LXXXX + LXXXX 
= LL XXXXX XXX (collect the like symbols)
= C L XXX  (since LL reduces to C and XXXXX reduces to L)

In other words, addition with (additive) Roman numerals is simpler than conventional arabic addition:

90 + 90 = 180 (in this case)

There's less to remember, and no carrying to worry about.  The full reduction rules form an easy pattern:
  • IIIII -> V
  • VV -> X
  • XXXXX -> L
  • LL -> C
  • CCCCC -> D
  • DD -> M
Easy, and forming a logical pattern.  Of course, ultimately, the arabic place-value system is far superior for an array of reasons, but for adding and subtracting small positive numbers, tallying and its extensions are arguably better.

By contrast, I know of no simple, direct way to perform addition with subtractive roman numerals, and would normally convert to another representation -- arabic or additive -- do the computation there, and then convert back.

Here's some Python code for inter-converting between both styles of Roman numerals and the more familiar arabic representation, plus addition of additive Roman numerals using reduction rules -- the more authentic method -- and addition of subtractive Roman numerals via arabic form.

Notes on the code:
  • I use a rule-based form so that the same algorithm (with different rule-sets for additive and subtractive conventions) converts Roman numerals <-> arabic
  • The practice of iteratively reducing a number to zero or chomping through a string until there is nothing left while building up the result is a common pattern
  • There's no error-checking yet for ill-formed roman numerals: we're avoiding that pain for the moment.
Ideas for extensions and explorations: 
  1. Subtraction and multiplication of additive Roman numerals via reduction rules
  2. Devise an augmented Roman numeral system with six more symbols for five thousand, ten thousand, fifty thousand, one hundred thousand, five hundred thousand, and one million; extend the code and do some sums.
  3. Explore the connections between Roman numerals and the (Roman) abacus

Saturday, February 4, 2012

Post number 0

What's the first number?  
Historically, people will count from one, raising a digit to any other answer, but computer scientists typically start from zero, because many formulas turn out more simply.  Since we're in the 21st century, let's be modern and count from zero: this is post number 0, or my zeroth post.

What's this blog for?
I've decided to return to my programming roots, and embark on an exploration of programming mainly for pleasure, and in order to make it a more reflective exercise, I'm going to blog about the process.  

I'll be drawing on problems from where-ever find them, but starting with problem-sites like Programming Praxis, CodeKata, and Project Euler.  

I'm more interested in elegance, approach, creativity and process -- the craft, if you will -- than sheer ingenuity, so I'm looking for problems that are not easy and not too hard to get going.  Hopefully, these problems will drive me (us?) towards more general principles and creative exploration.

Pleasure and Pain?
The pleasures of programming include: problem-solving, creation and invention, fixing something broken, extending one's mind, learning, control, intellectual flow, and showing off.

The pains include: frustration, getting stuck, admitting ignorance, and conceding defeat.

Part of the craft of professional programming is discovering ways to minimize the pain and maximize the pleasure.

Onwards!

Time to find out if the plan's gonna work ...