Skip to content

Instantly share code, notes, and snippets.

@Gorcenski
Last active December 11, 2015 03:56
Show Gist options
  • Save Gorcenski/6b72a653a99d3e050d2a to your computer and use it in GitHub Desktop.
Save Gorcenski/6b72a653a99d3e050d2a to your computer and use it in GitHub Desktop.
PE13, homebrew off-the-cuff BigInt implementation with lookahead
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