using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
namespace ProjectEulerExercises.Problems
{
///
/// The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
///
/// 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
///
/// Let us list the factors of the first seven triangle numbers:
///
/// 1: 1
/// 3: 1,3
/// 6: 1,2,3,6
/// 10: 1,2,5,10
/// 15: 1,3,5,15
/// 21: 1,3,7,21
/// 28: 1,2,4,7,14,28
/// We can see that 28 is the first triangle number to have over five divisors.
///
/// What is the value of the first triangle number to have over five hundred divisors?
///
public class Problem12 : Problem {
//I put in this limit just to limit the number of tasks that can be running concurrently.
//I'd almost deem it unecessary if it weren't for the chance of tasks completing out of order since we're
// not guaranteed that the first answer is the correct one. You have to wait for the number of
// tasks in this limit to complete first.
static readonly int TASK_NUMBER_LIMIT = Environment.ProcessorCount * 4;
///
/// Finds the first triangle number to have over n divisors.
///
/// The number of divisors.
///
public static long Method1(int number = 500) {
long triangle = 0;
int divisors = 0;
long currentNumber = 0;
while(divisors <= number)
{
currentNumber++;
triangle += currentNumber;
divisors = FindDivisors(triangle).Count;
}
return triangle;
}
///
/// A multithreaded approach to the solution.
///
///
///
public static long Method2(int number = 500) {
long triangle = 0;
long currentNumber = 0;
bool found = false;
List>> tasks = new List>>();
while(found == false) {
currentNumber++;
triangle += currentNumber;
//Apparently you should always prefer Task.Run over Task.Factory.StartNew.
//tasks.Add(Task>.Factory.StartNew(() => FindDivisors(triangle)));
//ALSO mutable types can be changed between the time a task creation and initialization
//See - https://www.dotnetforall.com/correct-way-provide-input-parameter-task/
//tasks.Add(Task>.Run(() => FindDivisors(triangle)));
//So use a temp with the same scope.
long temp = triangle;
tasks.Add(Task>.Run(() => FindDivisors(temp)));
//Check if any task has finished AND found an answer.
//If so, WAIT FOR ALL TASKS TO FINISH
//We have to wait for them all to finish just in case a higher answer completed before a lower correct answer.
//Then check all task's return values to see if any found an answer and if they did, use the lowest one.
//Then set found to true and triangle to the triangle number.
while (tasks.Any(t => t.Status == TaskStatus.RanToCompletion) || tasks.Count > TASK_NUMBER_LIMIT) {
Task> complete = Task.WhenAny>(tasks).Result;
HashSet result = complete.Result;
//Uncomment to see how the number of tasks grows and shrinks
//Console.WriteLine("Tasks: " + tasks.Count);
if (result.Count > number) {
var completedTasks = Task.WhenAll>(tasks).Result;
found = true;
//Uncomment to see that the same triangle values are not being computed more than once.
//foreach(var t in completedTasks) {
// Console.WriteLine("Task: " + t.Max());
//}
//Making sure the return value is correct.
triangle = completedTasks.Where(t => t.Count > number).Select(t => t.Max()).OrderBy(t => t).First();
tasks = new List>>();
}
else {
tasks.Remove(complete);
}
}
}
return triangle;
}
///
/// Finds all divisors for the given number.
///
/// List of divisors
///
private static HashSet FindDivisors(long number)
{
HashSet divisors = new HashSet();
long max = (long)Math.Ceiling(number / 3.0);
for(int i = 1; i < max; i++)
{
if(number % i == 0)
{
long b = number / i;
divisors.Add(i);
divisors.Add(b);
}
}
return divisors;
}
}
}