Teaching the whole CS spec. through one problem - converting decimal to Roman numerals
Created by Richard Pawson
last edited Feb 06 2021 by Richard Pawson
This resource is part whimsical, and part serious. The background is that I have long used the example of converting decimal to Roman numerals to illustrate various aspects of programming: the problem is just simple enough to program in lesson-time, and just complex enough to be interesting. Over the years I have built a library of different implementations, illustrating different principles.
Eventually, this became something of an obsession – to try to see how many different aspects of the syllabus I could illustrate, usefully, using this one idea. OK, my sub-title is an exaggeration: it’s not the whole syllabus. But if you read on you might be surprised at the breadth of approaches that can be applied to this single problem. (Also, I don’t really mean that this is a good way to teach those topics; but I think it can be a very good way to reinforce them.)
The serious point of the undertaking is this: typically each new technique in CS is introduced using only a problem that is hand-picked to show the advantage of that technique. IMO this can sometimes lead to a weak understanding of the power of the technique. By deliberately tackling the same problem using many different approaches, I think one can gain more – or at least different – insights.
What follows are 10 illustrations of key ideas in Computer Science (the first few are relevant to GCSE, the later ones to A-level) applied to the problem of converting decimal to Roman numerals. Each of these illustrations can be used in a variety of different ways:
Example answers for each of the 10 examples are attached as downloadable files. For the first five, I have included C#, VB and Python versions.
This can be used as soon as ‘while loops’ have been covered. The challenge is to write a function that takes in a decimal integer, in the range 0 – 2099 (think of it as a ‘year’) and returns the Roman numeral equivalent as a string (zero should be returned as an empty string). The most able pupils might be able to take it from there; I suggest that most would benefit from having an algorithm sketched out for them:
Armed with this idea, write the function using a series of consecutive while loops, each one handling a single symbol. (You should end up with 13 of them).
The resulting code is not particularly elegant, but it is straightforward to write and to understand. This also gives you a very good segue to talking about what’s not good about this approach i.e. it violates the ‘DRY’ principle – Don’t Repeat Yourself.
The answer to the previous example used 13 successive while loops, all structurally identical but using different values. It would be nice to extract this common logic into one re-usable subroutine.
We can do this by creating a subroutine, where we pass in the symbol and its corresponding value, along with the current decimal value to be converted and the string result being built-up.
The problem is that the subroutine is going to alter two things: the remaining decimal value will (potentially) be reduced, and the result string potentially appended to.
In C# and VB one way to handle this is passing parameters ‘by reference’. Personally, I hate this pattern. Python, and in C# 7 onwards (we’re now on C# 9), offers a more elegant solution: passing the two results back as a tuple, and then assigning the two elements of the tuple back to the corresponding variables (a pattern known as ‘tuple deconstruction’). VB, from version 15 onwards, has supported ‘value tuples’ but does not support deconstruction – so you’d have to do the deconstruction in separate lines of code, which defeats the object of the exercise. So, for C# I have provided two solutions, one(for C# 7 onwards) using tuples, the other (for earlier versions) using passing by reference. For VB, only the ‘passing by reference’ option is provided. For discussion afterwards: How many lines of code have you ended up saving? What other advantage(s) does this design offer over the previous ones?
Pupils will need to understand how to use arrays for this exercise.
This exercise teaches an important point that is not widely understood: procedural instructions and data structures are, to some extent, interchangeable. You can often reduce the number of instructions by using a more powerful data structure, or vice versa.
So, starting from the model answer to the previous example, how could we make effective use of one or more arrays to improve the implementation? (Hint: you can hold all the symbols in a string array, and all the values corresponding to those symbols in another array – with the same number of elements.)
Once the exercise has been completed (or the example answer worked through), discuss: - What are the potential advantages and/or disadvantages of the solution using arrays compared to the previous one?
Once dictionaries have been introduced, a simple exercise is to take the model answer from the previous example and convert it from using two arrays to using a single dictionary.
I admit that I would be hard pressed to find a significant advantage of using the dictionary over two arrays – but it is useful practice, and I would argue that the code is slightly more readable, because each symbol is shown next to its value (so there’s less risk of entering them wrongly, perhaps). And you could lead on to a revision discussion, or a test, on the general characteristics of a dictionary. For example: why would you not want to try to do Roman numerals with a single array, where the value was the index into the array? (Because there are huge gaps between the values, so most of the array would be empty, which is very wasteful of memory. Dictionaries, inter alia, allow numeric keys with large gaps, with high efficiency in both memory and performance.)
This example can be used to reinforce the point that although some problems seem naturally to suggest a recursive algorithm, any algorithm involving a loop can be translated into a recursive form.
The challenge here is to re-implement the decimal to Roman numerals function using a recursive approach. Some pupils will see the idea straight away; others might need a strong hint on the algorithm, which can be done with an example:
The Roman numeral representation of ‘2021’ is ‘M’ (the symbol with the largest value that can be deducted from the decimal value) followed immediately by the Roman numeral representation of ‘1021’ (the remaining decimal after the value of that symbol has been deducted).
Once pupils have completed the exercise, or the teacher has worked through a model answer in class, invite the pupils to discuss the advantages/disadvantages that they see in the recursive approach.
Note: My solutions for this example use two arrays, as in Example 3, rather than a dictionary (Example 4). This is in case recursion is taught before dictionaries. They could all easily be converted to use the dictionary approach.
It should be no surprise that the recursive approach used in the previous example is the key to how to tackle the problem using a pure Functional Programming language such as Haskell. But the example can also illustrate other features of such languages including: functional lists, guards, and list decomposition (x: xs).
This is probably too advanced an exercise for any but your most able pupils, but as an example to work through on the board, the model answer included here might be useful.
The Roman numerals conversion problem is actually quite an interesting one to attempt in Assembly Language. It is not especially difficult – and different pupils can be given different levels of hints. It is possible to tackle this in two stages:
First, sticking strictly to the AQA Instruction Set, which supports only ‘Immediate’ and ‘Direct’ addressing modes (which is nearly a crime, IMO!). The hint here is just to translate the algorithm used in the model answer from Example 1 into assembly language.
Secondly, allowing indexed (or indirect – they’re closely related) addressing. Here you can use an approach very similar to the model answer used in Example 3. Indeed, it is worth bringing out the point that indexed addressing is how arrays are implemented at low level, and is the reason why they are O(1) performant.
My model solution takes the second approach. It will run on Peter Higginson’s ARMlite simulator. (See this resource if ARMlite is new to you).
How would you build a combinatorial logic circuit (on a logic simulator), using nothing more than AND, OR and NOT gates, to convert a number from decimal to Roman numerals?
Such an exercise can be used not only to reinforce understanding of logic circuits, but also of Boolean algebra. A very important lesson – IMO, one of the most important in Computer Science, but not explicitly part of the curriculum – is the importance of choosing the right representation. We’ve been doing that, implicitly, in some of the earlier exercises, and it will come up again in the final one that follows this. Any choice of representation makes some things easier, and others harder.
For the combinatorial logic challenge, my suggestion is:
For initial discussion: would it be possible to use a Finite State Machine (FSM) to convert decimal to Roman numerals? The problem is that FSMs do not generate output – other than an end state. You could, in theory, design an FSM that parsed an input number in the range 0-2099 and ended up in one of 2100 different ‘accept’ states, each labelled with the corresponding Roman numeral equivalent, plus an ‘Invalid Input’ state. But it wouldn’t be considered a proper use of FSMs, or be very interesting to create.
Mealy machines are class of automata that can generate output. This is worth attempting, but the resulting machines are large. I suggest you set the challenge of translating just a single decimal digit.
Build your machine starting from the lowest value up. The reason is that when the machine is presented with the input value ‘7’ say, it can output ‘V’ and then move to the state (previously built) to handle the input value for ‘2’.
Handling multiple input digits involves more work, but more able pupils might welcome the challenge. Final discussion: the hypothetical FSM involved no generalisation at all: to handle conversion of decimal in the range 0-2099 you need 2100 final states (plus intermediate states). The Mealy machine involves some generalisation, but a full implementation would still be massive. There are other classes of automata, not covered in the (AQA spec), some of which would permit greater generalisation i.e. result in smaller, more elegant designs. This leads naturally to the discussion of Turing machines.
This one almost did my head in! I do not recommend attempting it as an exercise, unless you are a really sad case, like me! The design took me many hours, and my first successful attempt involved literally thousands of transition functions. My final version has ‘just’ 317 transition functions. As the saying goes in software development: ‘Simplicity is the ultimate sophistication’.
Rather than study the transition rules directly (though you can if you want), I recommend you download the document containing the whole set, and copy and paste it into this online simulator. Then load an example date (e.g. 1489) onto the tape, and run it, adjusting the execution speed up and down as needed. The important thing is to get a feel for how the machine is tackling the problem – it should be reasonably clear.
I have to say that, personally, I found this exercise challenging – resulting in the most complex Turing Machine I have yet built – but also very instructive.
The key learning for me – yet again – was about representation, in this case the idea (deeply ingrained from having studied Engineering, incidentally) of transforming the input representation into an intermediate representation. I then realised I could do the translation in three main steps:
There’s a lot of files here and some are quite old. I’ve tested quite a few of them afresh today, but I’ve run out of time now. If you have problems running any of them, just ping me and I’ll fix them.
Finally, in homage to (another type of) Python, I’ll leave you with the question:
Apart from while-loops, subroutines, arrays, dictionaries, recursion, functional programming, assembly language, combinatorial logic, automata, and Turing machines … what have the Romans ever done for us? ;-)
Feedback and Comments
Available when logged in (join via the front page, for free):