Project Euler: Problem 13 - Large Sum

Question

I've written some code to solve this problem:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

My solution functions correctly, but I'm having some trouble deciding how I should be handling exceptions, especially with regards to the class's constructor.

I went the route of creating a BigNumber class, even though it's not necessary, as I've never solved a problem involving arbitrary-length numbers before. Here's the class, sans constructors:

class BigNumber
{
 public static int MaxComponentValue = 999999999;
 public static int MaxComponentDigits = MaxComponentValue.ToString().Length;
 public bool Add(string source)
 {
 List<int> comps = this.SplitIntoComponents(source);
 // Not sure about this
 if (comps == null)
 return false;
 this.AllocateComponentSpace(comps.Count);
 for (int i = 0; i < comps.Count; i++)
 {
 int componentSpace = MaxComponentValue - this.components[i];
 int amountToCarry = comps[i] - componentSpace;
 if (amountToCarry > 0)
 {
 while (amountToCarry > MaxComponentValue)
 {
 amountToCarry -= MaxComponentValue + 1;
 this.components[i + 1]++;
 }
 this.components[i] = 0;
 this.components[i + 1]++;
 this.components[i] += amountToCarry - 1;
 }
 else
 this.components[i] += comps[i];
 }
 return true;
 }
 public override string ToString()
 {
 if (this.components.Count() > 1)
 {
 StringBuilder output = new StringBuilder();
 var activeComponents = this.components.Reverse().SkipWhile(i => i == 0).ToList();
 output.Append(activeComponents[0].ToString());
 // Skip the first element as we've already added output for it.
 foreach (var c in activeComponents.Skip(1))
 output.Append(String.Format("{0:000000000}", c));
 return output.ToString();
 }
 return this.components[0].ToString();
 }
 private List<int> SplitIntoComponents(string source)
 {
 if (source == null)
 throw new ArgumentNullException("source");
 List<int> comps = new List<int>();
 for (int i = source.Length; i > 0; i -= MaxComponentDigits)
 {
 string token;
 if (i < MaxComponentDigits)
 token = source.Substring(0, i);
 else
 token = source.Substring(i - MaxComponentDigits, MaxComponentDigits);
 int comp;
 if (int.TryParse(token, out comp))
 comps.Add(comp);
 else
 return null;
 }
 return comps;
 }
 private void AllocateComponentSpace(int count)
 {
 // The + 1 accounts for the possibility that there
 // will be an amount to carry over from the last token.
 // E.g 99 + 99 would result in the need for two components
 // to store the result 198 - the first one for 98 and the second for 1.
 if (this.components.Length < count)
 Array.Resize(ref this.components, count + 1);
 }
 private int[] components = new int[1];
}

Problem 1

In the private method SplitIntoComponents, if int.TryParse fails, I'm failing early and returning null. In the Add method, I call SplitIntoComponents, check if it has returned null and then return false to the caller if it has. The consequence of that is the Add method fails early, before modifying the data stored in the BigNumber instance.

I have two questions. Firstly, should SplitIntoComponents be throwing instead of returning null? Secondly, should Add return false to the caller, or should that really be throwing an ArgumentException? I'm thinking SplitIntoComponents should stay as it is and then I should throw from Add.

Problem 2

I want to define a constructor that takes a string argument. This is what I have so far:

public BigNumber(string source)
{
 if (source == null)
 throw new ArgumentNullException("source");
 List<int> comps = this.SplitIntoComponents(source);
 if (comps == null)
 throw new ArgumentException();
 // Not implemented yet
}

In this case, I feel as though I should be throwing the ArgumentException because I'm unable to return anything to the caller. The problem here is obviously the inconsistency between how I'm handling the return value of SplitIntoComponents in the constructor and in the Add method.

Should I opt for that and throw ArgumentException?

General Observations

1. I should overload the '+' operator to allow addition of multiple BigNumbers.
2. Add some support for Linq (would that even work for Sum?)

Any other suggestions?

• Gareth Rees: What was wrong with System.Numerics.BigInteger?
• John H: @GarethRees I wanted to learn something new. My algorithmic skills are a little weaker than I'd like, so this was a good exercise for me.

Answer 1

(削除) IMHO returning null as error handling is a misconception. (削除ここまで) I was wrong there, it is ok, but you have to use it consequently!

Because you may have to make the "exception handling" in the consumer class twice. One time for Exceptions and another time for null as return value.

And as i can already see in your code it may cause you to make only a part of the exeption handling. Since your Add method handles the case that SplitIntoComponents returns null but doesn't handle the case that it may throw an ArgumentNullException. This may be intentional i can't tell that because i can't see the call for Add.

Use TryParse and throw a meaningfull exeption, instead of returning null . Or return null, instead of throwing an exception if source is null. Both ways are ok, but only when they aren't used at the same time. (Which results in two Ways of exception handling in the consumer again.)

• John H: Thank you for the response. Since your Add method handles the case that SplitIntoComponents returns null but doesn't handle the case that it may throw an ArgumentNullException. This is basically where my confusion lies, which is probably why my intention is unclear. My specific thinking was that as I'm checking for source being null, when it's passed to Add, does it still make sense to check for source being null when it's passed to SplitIntoComponents, bearing in mind that it's a private method?
• John H: In fact, that problem is the whole reason I decided to return bool from Add - to signify whether or not the operation was successful. However, that also seems unintuitive. It seems to make more sense for Add to have a void return type, simply throwing exceptions where necessary. So in that sense, perhaps it would be better to check for source being null and then if (comps == null) throw new ArgumentException("Must only contain numbers.", "source");.
• John H: As for your last point about TryParse, I'm not sure I understand. TryParse doesn't throw, which is why I chose it. My thinking was that if I throw from SplitIntoComponents, because of source being an invalid argument, the real problem lies in what was passed to Add, so throwing from SplitIntoComponents, rather than Add, obfuscates the problem.
• Marguth: " In fact, that problem is the whole reason I decided to return bool from Add - to signify whether or not the operation was successful. However, that also seems unintuitive." Some my say that, but i like to do it that way ,too. Just make sure it doesnt throw an exception in any case, or you have to handle two cases again.
• Marguth: @John H I edited my answere to be more clear, i hope it includes your comments now.

Answer 2

I'll self-answer this as my approach now is quite different from anything else mentioned here.

The constructor idea was essentially the root of the problem, because I was asking it to do too much. With that said, I decided to create a static method to separately handle the parsing of a string:

public static BigNumber Parse(string source)
{
 //
}

This now means two things:

1. I can make the exception handling logic consistent between the Parse and Add methods, allowing me to refactor it further at some point.
2. The constructor is no longer responsible for handling parsing (which it shouldn't have been to begin with).