Create a chain of unique integers from single integer

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.