Thinking about Test driving the 3 n plus 1 problem solution
10 Aug 2019
Problem source: Programming Challenged: The Programming Contest Training Manual
Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when the value is 1. For an input n, the cycle length of n is the number of numbers generated up to and including the 1. The cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.
I'm building the solution to the above problem using Pharo, which is a pure object-oriented language based on Smalltalk. I am not confident with object-oriented design or test-driving solutions, so I'm trying to correct that by building out as many solutions as I can.
First, I solve the problem myself. Then I ask for feedback from developers who know object-oriented design and test-driving better than I do. This entry is the solution I built first by myself.
The first thing I did was read through the problem to make sure I understood it properly.
The second thing I did was set up an empty Pharo project with version control and a test environment.
Setting up Test class
I started my program by creating a class called
I wrote a class comment which explains what the class represents, what it's responsibilites are and what other classes it collaborates with. This is based on the CRC approach developed by Kent Beck and Ward Cunningham (who argue that index cards are better than a digital representation for this). Here is what the comment says:
I represent the test suite for the 3nPlusOne class.
I make sure that:
- Even numbers are correctly divided by two
- Odd numbers are correctly multiplied by three with one added to the result.
- That a range of numbers is correctly converted to an array representing collatz conjecture values
- That the number of cycles it takes for a number to reach one is correctly returned
- That the largest cycle number from each individual numebr in the range of numbers is correctly returned
I work with the 3nPlusOne class API
The code for my test class initilization was:
TestCase subclass: #TestthreeNPlusOne instanceVariableNames: '' classVariableNames: '' package: '3-n-plus-one'
- The test class inherits from a parent class called 'TestCase'.
- The name of the class is the same as the name of the class we are testing with it, but with the capitalised word 'Test' prefixed so that Pharo knows it is a class for tests.
- No instance variables or class variables were set.
- The test class belongs to the project package which I named '3-n-plus-one'. I could also have called it 'collatz-conjecture'. but that is a math jargon term that is less intuitive to understand unless you happen to know the term for this type of problem.
First failing test: if even divide by two
The first message (method) I gave my test class was initialized as follows:
testIfEvenDivideByTwo | threeNPlusOne | threeNPlusOne := ThreeNPlusOne new. self assert: (threeNPlusOne ifEvenDivideByTwo: 2) equals: 1.
I decided to test that numbers can be correctly divided by two as my first test. My assumption is that this is a behaviour that my program needs to be able to perform. I'm not sure if I'm able to identify the 'right' kind of behaviours to test yet. So I'm just doing it this way and will rely on feedback to steer me in a better direction if needed.
It's pretty scary being this open with my development process when I know I still have a lot to learn so may not be doing things in the best way. But later down the line, this documentation will serve as a record of improvement and capture the changes in thought processes as I learn more, which is going to be really interesting to look back on.
- The message is called 'testIfEvenDivideByTwo'. As with our test class name, the message name is the same as the real message we are testing, this time prefixed with the lowercase word 'test' so that Pharo knows it is a test message.
- I created a variable called 'threeNPlusOne' to store a new instance of a 'ThreeNPlusOne' class that I haven't created yet. This is so that when I write multiple test assertions, I don't have to create a new instance every time.
- The final line is a test assertion which says: When our threeNPlusOne class recieves the message 'if even divide by 2' with the number two as the message argument, then the result returned should be equal to 1.
When I saved and ran this test, the test successfully failed (I love that phrasing haha).
The quality assistant provided a bunch of messages (called critic text) to inform me of the reasons why my test failed. It is a good idea to get in the habit of reading all of these messages and understanding how to fix them. So I'm going to write them down along with the explanation of what they mean, and how I fixed them one by one.
Fixing my failing test step-by-step
[ThreeNPlusOne] References an undeclared variable.
You are referencing a variable that is not declared anywhere. There is no temp, instance var, class var, or a global variable that can be bound to by this reference. Most likely you got into this state by writing an entirely correct code, but then the variable was removed.
Firstly, how cute was that message!? I wrote my test before writing any code, so the ThreeNPlusOne class doesn't exist yet. Creating the class removed this message.
[assert:ifEvenDivideByTwo:equals:]Messages sent but not implemented.
Checks for messages that are sent by a method, but no class in the system implements such a message. Reported methods will certainly cause a doesNotUnderstan: message when they are executed.
Same problem, I have send a message to threePlusOne which divides even numbers by two, but the code which implements this message does not exist yet. Creating a message in the 'ThreeNPlusOne' class that accepts an argument removes this message.
[assert:ifEvenDivideByTwo:equals:] Super and Self Messages sent but not implemented.
Checks if messages sent to self or super exist in the hierarchy, since these can be statically typed. Reported methods will certainly cause a doesNotUnderstand: message when they are executed.
This critic text is a little more complicated for me to understand, so I'll break it down. Super refers to the class that our current class inherits from. All classes in Pharo inherits from a super class. Self refers to the current class we are working within, the reciever of our message and not the message itself.
I don't know what the messages being statically typed has anything to do with whether the super or self exists in the hierarchy, so will google the error message to find out more. Googling the error messages provided the same information already given. So I'll google 'pharo statically typed inheritance' to see if that leads anywhere.
Found some info here. This article says that statically typed languages have a universal base class, so if an object inherits from that, it can also inherit from any other class in the hierarchy. So what the critic text was saying is does the message exist in either the self or the parent class, and because the language is statically typed, this could mean looking for the message in the universal base class. Writing the message in the self class will remove this critic text.
To make my test pass, I created a class called 'ThreeNPlusOne', whose CRC comment was written as follows:
I represent the 3-n-plus-one-problem, otherwise known as the 'Collatz Conjecture'.
I have a number range. For that number range I count how many cycles it takes for each individual number to reach 1 using the collatz conjecture math approach. Then I return the longest of those cycles.
I'm not sure who I collaborate with yet.
Then I added the if even divide by two message to the class which returns the number one, as follows:
ifEvenDivideByTwo: evenNumber ^ 1.
- The message is a binary message that accepts an argument. Our argument is a variable named 'evenNumber' because that is what the message will be working on.
- The message returns one. When test driving code, you only write the simplest, bare-minimum code you need to get the test to pass. In this case, we only needed to return 1 to get the test to pass. We can use additional tests to force our messages to be more general, which we will do later.
We now have a passing test, which I committed to version control.
After writing the first few tests, I realised that I need to spend some time working through some Pharo solution examples because I have no idea how to use the language properly, which was preventing me from moving forward. So I'm going to work through Learning Object-Oriented Programming, Design with TDD Pharo which will get me to a better place.