Problem
I’ve done a practice session on cyber-dojo and would like someone to review it.
Main question – is my solution too complex for such a simple task?
For example, I decided to split out printing and generating logic into ChainPrinter and NumberGenerator classes. This in my opinion conforms better with Single Responsibility and Open Closed Principles, but I can’t get rid of a feeling that I’ve over complicated it.
Feel free to comment on other aspects of solution as well.
Instructions:
Given a number, we can form a number chain by
- arranging its digits in descending order
- arranging its digits in ascending order
- subtracting the number obtained in (2) from the number
obtained (1) to form a new number- and repeat these steps unless the new number has already
appeared in the chainNote that 0 is a permitted digit. The number of distinct numbers in
the chain is the length of the chain. You are to write a program that
reads numbers and outputs the number chain and the length of that
chain for each number read.Input and Output
The input consists of a positive number, less than 10^9. The output consists of the number chain generated by the input number, followed
by its lengths exactly in the format indicated below.Examples
Example-1
Input
123456789Output
Original number was 123456789 987654321 - 123456789 = 864197532 987654321 - 123456789 = 864197532 Chain length 2Example-2
Input
1234Output
Original number was 1234 4321 - 1234 = 3087 8730 - 378 = 8352 8532 - 2358 = 6174 7641 - 1467 = 6174 Chain length 4Example-3
Input
444Output
Original number was 444 444 - 444 = 0 0 - 0 = 0 Chain length 2
Solution:
using System.Collections.Generic;
using System.Linq;
public struct NumberChainItem
{
public int Number { get; set; }
public string GenerationDescription { get; set; }
}
public class NumberChain : List<NumberChainItem>
{
public NumberChain(int startingNumber)
{
StartingNumber = startingNumber;
Items = new List<NumberChainItem>();
}
public int StartingNumber { get; private set; }
public List<NumberChainItem> Items { get; private set; }
}
public interface INextNumberGenerator
{
NumberChainItem GetNext(int input);
}
public class NumberGenerator : INextNumberGenerator
{
public NumberChainItem GetNext(int input)
{
var digits = input.ToString().Select(ch => int.Parse(ch.ToString())).ToArray();
var descending = DigitsToNumber(digits.OrderByDescending(i => i));
var ascending = DigitsToNumber(digits.OrderBy(i => i));
var number = descending - ascending;
var chainItem = new NumberChainItem
{
Number = number,
GenerationDescription = string.Format("{0} - {1}",
descending, ascending)
};
return chainItem;
}
private int DigitsToNumber(IEnumerable<int> digits)
{
var numberString = string.Join("", digits);
var number = int.Parse(numberString);
return number;
}
}
public class ChainGenerator
{
private readonly INextNumberGenerator _nextGenerator;
public ChainGenerator()
{
_nextGenerator = new NumberGenerator();
}
public ChainGenerator(INextNumberGenerator nextGenerator)
{
_nextGenerator = nextGenerator;
}
public NumberChain Run(int input)
{
var chain = new NumberChain(input);
int? previous = null;
var current = input;
while (current != previous)
{
var next = _nextGenerator.GetNext(current);
chain.Items.Add(next);
previous = current;
current = next.Number;
}
return chain;
}
}
public class ChainPrinter
{
public IEnumerable<string> Print(NumberChain chain)
{
yield return string.Format("Original number was {0}", chain.StartingNumber);
foreach (var item in chain.Items)
yield return string.Format("{0} = {1}",
item.GenerationDescription, item.Number);
yield return string.Format("Chain length {0}", chain.Items.Count());
}
}
Usage:
public void Instructions_Example1()
{
var input = 123456789;
var generator = new ChainGenerator();
var chain = generator.Run(input);
var printer = new ChainPrinter();
var result = printer.Print(chain);
}
Solution
Yes I think your design is over-complicated. But more to the point, your implementation is wrong. The spec says
repeat these steps unless the new number has already appeared in the chain
But what you implement is “repeat these steps unless the new number is equal to the previous number”. That’s wrong.
Why did you get this wrong? You didn’t create a method that clearly implements the specification, that’s why.
When I see a problem like this I try to come up with a collection of methods where each exactly implements some part of the specification, in a general way. I would have implemented that line of the spec like this:
public static IEnumerable<T> UntilDuplicate<T>(
this IEnumerable<T> items, IEqualityComparer<T> equals)
{
var seen = new HashSet<T>(equals);
foreach(var item in items)
{
if (seen.Contains(item))
yield break;
seen.Add(item);
yield return item;
}
}
Easy method. Obviously correct. And when you use it in your solution, that solution will be seen to be obviously correct because it clearly and correctly implements an idea from the specification. Programming is about correctly solving small problems and combining those solutions together.
If you build up a small collection of helper methods like this you will very quickly discover that you can write the program you want to write so that it reads very close to its specification, and this gives you confidence that it is both correct and concise.
When I was solving the problem, a pluggable
INextNumberGeneratorseemed like a good idea. Would you see this line of thinking as ‘over-engineering’?
It’s not a bad idea to encapsulate that logic somewhere. But the question to ask when you’re consider an interface is: do I need this generality? Am I really going to make two, three, a dozen different implementations of INextNumberGenerator? If not, don’t make an interface.
Rather, it strikes me as the kind of thing that could be handled by a very short method:
static IEnumerable<T> GenerateInfiniteSequence<T>(
T seed,
Func<T, T> next)
{
T current = seed;
while(true)
{
yield return current;
current = next(current);
}
}
There, done.
As another answer wisely pointed out: the mechanisms of OOP were designed for managing complexity when programming in the large, not for simple math. You just call Math.Cos. You don’t create an instance of the Trigonometry class to get its ICosineProviderFactory.
C# lets you treat arbitrary sequences as mathematical objects; take advantage of that to write concise code.
Yes, your design is overcomplicated.
Mathematical calculation suffer from OOP (Object Oriented Programming), the calculation always take an input and give an output without changing external state, and OOP’s main purpose is to menage external state changes. Thus OOP loses its main purpose and only slows down the core of the algorithm.
For concrete examples NumberChainItem should be just a number because the description can easily be generated by knowing the value and NumberChainItem and DigitsToNumber are pure functions because only the given input is used in the calculation (no class state) and no actions are performed besides returning the result.
I would write a single class with all static methods to solve this problem avoiding such unfruitful over-complication (I would write no classes at all but C# forces me to write at least one).
Design changes
Why does your NumberChain class inherits from List<NumberChain> and has Items property that contains
the numbers? You can either have the first or the later, but having both at the same time is somewhat confusing.
Usually I prefer the latter approach.
The reason is because I can create an instance of NumberChain and add items to it like this:
var chain = new NumberChain(123);
chain.Add(123);
chain.Items.Add(123);
The result is that I have two different lists both with the number 123, and not 1 list with number 123 twice.
If you go with the later approach also consider exposing Items as ICollection instead, in order to respect Liskov substitution principle.
INextNumberGenerator already exists, by the name of IEnumerable<NumberChainItem>. If you take a close look you can see the semantics of the interface are the same.
If you ever find the possibility to implement a common interface present on .NET, try to do so, instead of defining your own.
ChainPrinter has a misleading name. It doesn’t ever print anything, all it does is to return a bunch of strings that represent the chain, consider the name ChainFormatter instead.
It could be interesting to have a ToString overload on NumberChain that takes a IFormatter (implemented by ChainFormatter),
instead of using the printer on its own.
Current implementation changes
I guess the worst of your implementation lies on NumberGenerator class, but it was still a very good job.
To get the digits of a number in the int type consider subtracting with char '0'.
var digits = input.ToString().ToCharArray().Select(ch => ch - '0');
Instead of putting the number to a string and parse it consider building the number like we do in real life. n = d0 * 10^0 + d1 * 10^1 + ...
An algorithm can be done with Linq:
private int DigitsToNumber(IEnumerable<int> digits)
{
return digits.Aggregate((acc, val) => acc = acc * 10 + val);
}
I also consider that it could be wiser to have a constructor on NumberChainItem that receives your input.
It is the job of the constructor to guarantee that he object has the right state after initialization.