Programming project 3

Setup for first two tasks

Please download the template source recursion1.scala and the test suite recchecksuite.scala.

Compile both files:

$ fsc recursion1.scala 
$ fsc recchecksuite.scala 
You can now run the test suite:
$ scala RecursionCheckSuite
Run starting. Expected test count is: 2
- number of threes *** FAILED ***
  scala.NotImplementedError: an implementation is missing
- print with commas *** FAILED ***
  scala.NotImplementedError: an implementation is missing
Run completed in 72 milliseconds.
Total number of tests run: 2
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 2, canceled 0, ignored 0, pending 0
*** 2 TESTS FAILED ***
When you are done with the first two tasks, the two tests will pass.

Number of threes

Implement the method numberOfThrees(num: Long): Int in recursion1.scala. It should return the number of times the digit 3 appears in the decimal representation of the non-negative integer num. For example numberOfThrees(34534) should return 2.

Your implementation must be recursive. You are not allowed to use any strings at all: You cannot convert the number to a string.

Hint: Look at how we printed numbers in any base.

Printing with commas

A convention for printing large numbers, especially for finances, is to insert commas every three digits. For example:

Implement the method printWithCommas(n: Long) in recursion1.scala to print a given positive integer number \(n > 0\) in this format.

Your method must be recursive and must not return a result: it should just print the number directly. It also may not use any string methods, in particular it must not use toString, toInt, format, or printf.

Hint: Look at how we printed numbers in any base.

Setup for Gray code tasks

Download and compile the file gray.scala:

$ fsc gray.scala 
The initial version can be run from the command line to generate a table of the binary code with a given number of bits, and to convert a binary number to decimal:
$ scala Gray binary 3
$ scala Gray binary 4
$ scala Gray bin2dec 0100110
$ scala Gray bin2dec 10101010

These are implemented using the methods makeBinary and binaryToInt. Study how they work recursively.

Gray coding

The standard binary representation, while incredibly useful in many applications, is not always the best binary representation for some applications. For example, imagine an application in which one is scanning an \(n\)-bit number and the scanner occasionally misreads one of the bits. In the standard binary representation, if the misread bit is a very significant bit, the corresponding value of the binary string may differ substantially from the intended value. For example, the five-bit binary strings 00101 and 01101 differ in only one bit but represent the numbers 5 and 13, respectively.

Gray coding (also known as reflected binary numbers) is an alternative numbering of binary strings in which strings corresponding to consecutive values always differ by exactly one bit. In the application above, if the scanner misreads at most one bit, the value of the scanned Gray code is at most one away from the correct value. In many cases, bounded errors of this type are perfectly acceptable.

Your first task is to write a recursive method makeGray(length:Int) : Array[String] that generates a list of binary strings of the specified length ordered such that consecutive strings differ by exactly one bit. Your recursive solution should be very similar to makeBinary, which generated a list of all binary strings ordered by their standard values. If the length is one, the answer is Array("0", "1"). Otherwise, your method should recursively compute makeGray(length-1) and use this to construct makeGray(length).

In the case of standard binary numbers, makeBinary(length) created two copies of the list makeBinary(length - 1). makeGray(length) should also create two copies of makeGray(length - 1). However, one of these copies should be reflected (that is, reversed). Spend a few minutes experimenting with some simple examples and see if you can implement makeGray. If you need more help, this section of the Wikipedia page on Gray codes explains the solution.

Computing the value of a Gray code

Our solution for makeGray returns a list of Gray codes ordered in ascending value. For standard binary numbers, the function binaryToInt computes the value of a binary number. To compute the decimal value of a Gray code, we will implement a function grayToBinary that converts a Gray code to the standard binary number with same value. This function can then be used to compute the value of a Gray code by evaluating binaryToInt(grayToBinary(gray)).

Implement a recursive method grayToBinary(gray) that performs this conversion. Again, this function is remarkably simple. However, deriving this function on your own may prove to be quite difficult. You can read up further on Gray codes as you work on this problem. In particular, focus on the next to last paragraph in the Wikipedia section referenced above.