Last active
December 11, 2015 03:56
-
-
Save Gorcenski/6b72a653a99d3e050d2a to your computer and use it in GitHub Desktop.
PE13, homebrew off-the-cuff BigInt implementation with lookahead
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.IO; | |
using System.Linq; | |
using System.Numerics; | |
namespace ProjectEuler | |
{ | |
class Problem13 | |
{ | |
const int precision = 10; // desired digits of precision -- we should get about O(log N) more than this | |
public static void Solve() | |
{ | |
// Read the numbers from a flat text file | |
List<string> lines = File.ReadAllLines("problem13.txt").ToList(); | |
string output = string.Empty; | |
int N = lines.Count(); | |
int M = lines.Max(x => x.Length); | |
// Compute how far we have to look ahead using the number of integers as a baseline. | |
int requiredPrecision = precision + (int)Math.Floor(Math.Log10((double)N)) + 1; | |
// Based on machine precision, how many digits can we take and guarantee that it won't overflow the int buffer? | |
int maxPartitionSize = (int)Math.Floor(Math.Log10((double)(int.MaxValue / N))); | |
// Some bookkeeping variables | |
int index = 0; // the point in the string representation of the number that we start from | |
int previousSum = 0; // used to append to the previous step | |
int len = 0; // how large of a chunk of the string do we take? | |
int k = 0; // residual digits | |
while (index < Math.Min(requiredPrecision - 1, M)) | |
{ | |
int sum = 0; | |
// Don't overshoot our string length when processing | |
len = Math.Min(maxPartitionSize, requiredPrecision - index); | |
if (index + len > M) | |
len = M - index; | |
// Sum as we process the list in situ. | |
foreach (var line in lines) | |
{ | |
int s = 0; | |
if (int.TryParse(line.Substring(index, len), out s)) | |
sum += s; | |
} | |
int r = sum % (int)Math.Pow(10, len - 1); // The remainder | |
int p = (sum - r) / (int)Math.Pow(10, len); // the part we have to add back in | |
string append = (previousSum + p).ToString(); | |
output += append.PadLeft(k, '0'); | |
// store for the next step | |
previousSum = sum % (int)Math.Pow(10, len); | |
// increment the position in the string from which we will take the next substring | |
index += len; | |
k = sum.ToString().Length - p.ToString().Length; | |
} | |
// Tidy up the last computed element | |
output += previousSum.ToString().PadLeft(k, '0'); | |
Console.WriteLine(output.Substring(0,Math.Min(precision, output.Length))); | |
} | |
public static void Verify() | |
{ | |
List<string> lines = File.ReadAllLines("problem13.txt").ToList(); | |
BigInteger SUM = 0; | |
foreach (var line in lines) | |
{ | |
BigInteger S = 0; | |
if (BigInteger.TryParse(line, out S)) | |
SUM += S; | |
} | |
Console.WriteLine(SUM.ToString().Substring(0,Math.Min(precision, SUM.ToString().Length))); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment