# Create a chain of unique integers from single integer

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

1. arranging its digits in descending order
2. arranging its digits in ascending order
3. subtracting the number obtained in (2) from the number obtained (1) to form a new number
4. and repeat these steps unless the new number has already appeared in the chain

Note 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

123456789


Output

Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2


Example-2

Input

1234


Output

Original number was 1234
4321 - 1234 = 3087
8730 - 378 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
Chain length 4


Example-3

Input

444


Output

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
{

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);

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);
}

• this time your question looks much better ;-) – t3chb0t Aug 24 '16 at 12:43
• Yep. Didn't have much time to read rules. TL;DR; But you guys forced me to :) – Roman Gudkov Aug 24 '16 at 12:45
• Heya there, I've edited your question to make the challenge description readable without scrolling and put it into quotes. This should make reading your question even easier :) – Vogel612 Aug 24 '16 at 12:46
• Please state only the purpose of the code in the title, concerns should be stated only in the question body. – Caridorc Aug 24 '16 at 12:48
• @Vogel612 Thanks, mate. I already scanned through your changes to use them next time – Roman Gudkov Aug 24 '16 at 12:49

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;
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 INextNumberGenerator seemed 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.

• Thanks for a great answer. When I was solving the problem, a pluggable INextNumberGenerator seemed like a good idea. Would you see this line of thinking as 'over-engineering'? – Roman Gudkov Aug 24 '16 at 21:27
• @RGudkov: You're welcome. I've added some text considering your follow-up question. – Eric Lippert Aug 24 '16 at 21:53
• @RGudkov: Also I would encourage you to read stackoverflow.com/questions/21692193/why-not-inherit-from-listt/… – Eric Lippert Aug 24 '16 at 21:55
• I understand it to be generally discouraged to call Contains before Add on a HashSet, as it requires doing the lookup twice. Do you think that people would misunderstand if (seen.Add(item)) yield return item; else yield break;? – Peter Taylor Aug 25 '16 at 8:16
• Yeah like I thought INextNumberGenerator could be mapped to IEnumerable however I didn't take the time to see how. Nice addition. – Bruno Costa Aug 25 '16 at 8:20

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).

• TL;DR Try simulations (either of the real-world or of a complex game) to practice OOP, forcing a tool (OOP) to a domain it was not built for (Math) won't work in your favour. – Caridorc Aug 24 '16 at 13:28
• I somewhat agree but the truth is that without OOP mathlab wouldn't exist. – Bruno Costa Aug 24 '16 at 14:02
• @BrunoCosta Any technique can be used to write anything, but OOP does not shine in Mathematical programming as it does in simulation – Caridorc Aug 24 '16 at 14:16

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);


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.

• It seems the correct interface is ICustomFormatter, for the ChainFormatter – Bruno Costa Aug 24 '16 at 14:19
• In your Aggregate it doesn't do anything except confuse that you assign back to acc – Esben Skov Pedersen Aug 24 '16 at 18:36
• @EsbenSkovPedersen Well it's true that I do not have to assign acc, but it does what is supposed to. – Bruno Costa Aug 24 '16 at 18:40
• Then why not remove "acc = " then. This is code review and code should be precise. We don't go and make arbitrary statements even if "it does whats it's supposed to do" – Esben Skov Pedersen Aug 24 '16 at 18:44
• @EsbenSkovPedersen Just because when I wrote i thought it as a sum loop. On those kind of loops you normally write something like accumulattor += value. So I do not really mind having that same ideia here as well. – Bruno Costa Aug 24 '16 at 18:47