Project Euler #4

projecteuler-problem4.cs

// A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
// Find the largest palindrome made from the product of two 3-digit numbers.
// https://projecteuler.net/problem=4
void Main()
{
	// xyz * XYZ = abccba
	foreach (var p in sixDigitPalindroms())
	{
		foreach (var prm in permutationsOf(dividersOf(p)).Distinct(new Cmp()))
		{			
			var answer = Enumerable.Range(1, prm.Count())
				.Select(l => prm.Take(l).Aggregate(1, (r,n)=>r*n))
				.Where(_=>99<_ && _ < 999)
				.Select(_ => p / _)
				.Where(_ => 99 < _ && _ < 999)
				.FirstOrDefault();

			if (0 < answer)
			{
				new StringBuilder()
					.Append(answer)
					.Append(" x ")
					.Append(p/answer)
					.Append(" = ")
					.Append(p)
					.ToString().Dump();
				return;
			}
		}
	}
}

public class Cmp : IEqualityComparer<IEnumerable<int>>
{
	public bool Equals(IEnumerable<int> a, IEnumerable<int> b)
	{
		if (a.Count() != b.Count())
		{
			return false;
		}
		
		return 0 == a.Zip(b, (_a, _b)=>_a-_b).Max();
	}
	
	public int GetHashCode(IEnumerable<int> a)
	{
		return a.Aggregate(new StringBuilder(),
				(c, n) => c.Append(n).Append("-"))
				.ToString().GetHashCode();
    }
}


IEnumerable<IEnumerable<int>> permutationsOf(IEnumerable<int> l)
{
	if (1 == l.Count())
	{
		yield return new List<int>(new int[] { l.ElementAt(0) });
	}
	else
	{
		foreach (var i in Enumerable.Range(0, l.Count()))
		{
			var n = l.ElementAt(i);

			var listNoI = new List<int>(l);
			listNoI.RemoveAt(i);

			foreach (var prm in permutationsOf(listNoI))
			{
				var answer = new List<int>(prm);
				answer.Insert(0, n);

				yield return answer;
			}
		}
	}
}

IEnumerable<int> sixDigitPalindroms()
{
	var A = Enumerable.Range(1, 9).Reverse();
	var B = Enumerable.Range(0, 9).Reverse();
	var C = Enumerable.Range(0, 9).Reverse();
	
	return
		A.Select(a=> 
			B.Select(b=> 
				C.Select(c=> a*100001+b*10010+c*1100)
			)
		)
		.SelectMany(_ => _)
		.SelectMany(_ => _);
}

IEnumerable<int> dividersOf(int n)
{
	var dividers = Enumerable.Range(2,Convert.ToInt16(Math.Sqrt(n)));
	
	var firstP = dividers.FirstOrDefault(p=> n%p == 0);

	if (firstP == 0)
	{
		return new List<int>(new int[] {n});
	}
	
	return new List<int>(dividersOf(n/firstP)).Prepend(firstP);
}