PROJECT EULER #79

Link to Project Euler problem 79

A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

Did this by hand but then I felt like I had to come up with a coded solution too.

using System;
using System.Collections.Generic;
using System.IO;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 79
            DateTime start = DateTime.Now;
            var sr = new StreamReader(@"../../keylog.txt");
            var keys = new List<string>();
            while (!sr.EndOfStream)keys.Add(sr.ReadLine());
            for (int i = 0; i < keys.Count - 1; i++)
                for (int j = i + 1; j < keys.Count; j++)
                    if (keys[i] == keys[j])
                        keys.Remove(keys[j]);
            var cList = new List<char>();
            foreach (string s in keys)
            {
                char[] c = s.ToCharArray();
                foreach (char c1 in c)
                    if (!cList.Contains(c1))
                        cList.Add(c1);
            }
            var answer=new char[cList.Count];
            foreach (char c in cList)
            {
                var digitsRight = new List<char>();
                foreach (string s in keys)
                    if (s.Contains(c.ToString()))
                    {
                        int n = s.IndexOf(c);
                        if (n != s.Length - 1)
                            for (int i = n + 1; i < s.Length; i++)
                            {
                                char d = char.Parse(s.Substring(i, 1));
                                if (!digitsRight.Contains(d))
                                    digitsRight.Add(d);
                            }
                    }
                answer[cList.Count-(digitsRight.Count+1)] = c;
            }
            Console.WriteLine(new string(answer));
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

PROJECT EULER #78

Link to Project Euler problem 78

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.

OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O

Find the least value of n for which p(n) is divisible by one million.

Well this was difficult, not to mention memory hungry. This solution ate about 4-5 gigs of ram before coming up with the answer in the nick of time. It's a variation on the two previous problems.

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 78
            DateTime start = DateTime.Now;
            var pOfN = new List<int[]> { new[] { 1 }, new[] { 1,1 } };
            int max = 0;
            bool success = false;
            int n = 1;
            while (!success)
            {
                n++;
                int[] thisN = new int[n+1];
                thisN[0] = 0;
                thisN[1] = 1;
                for (int i = 2; i < n+1; i++)
                {
                    int k = n - i;
                    if (k < 0)
                        thisN[i] = thisN[i - 1];
                    else if (i < k)
                        thisN[i] = thisN[i - 1] + pOfN[k][i];
                    else
                        thisN[i] = thisN[i - 1] + pOfN[k][k];
                    if (thisN[i] > 10000000)
                        thisN[i] = thisN[i]%1000000;
                }
                if (thisN[thisN.Length - 1]%10000 == 0)
                    Console.WriteLine(thisN[thisN.Length - 1] + ", " + n);
                pOfN.Add(thisN);
                if (thisN[thisN.Length-1]%1000000==0)
                {
                    max = n;
                    success = true;
                }
            }
            Console.Write(pOfN[max][max]+", "+max);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

PROJECT EULER #77

Link to Project Euler problem 77

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

A modification of the previous algorithm

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 77
            DateTime start = DateTime.Now;
            var primes = GeneratePrimes(80);
            int maxNumber = 80,target=0,sum=0;
            int[,] a = new int[maxNumber + 1, maxNumber + 1];
            for (int i = 0; i < maxNumber + 1; i++)
            {
                a[i, 0] = 0;
                a[0, i] = 1;
            }
            int n = 2;
            while (sum < 5000)
            {
                    if (n%2 == 0) a[n, 1] = 1;
                    else a[n, 1] = 0;
                    for (int j = 2; j < primes.Count; j++)
                    {
                        int k = n - primes[j];
                        if (k < 0)
                            a[n, j] = a[n, j - 1];
                        else
                            a[n, j] = a[n, j - 1] + a[k, j];
                        if (a[n, j] > 5000)
                        {
                            target = n;
                            sum = a[n, j];
                            break;
                        }
                    }
                n++;
            }
            Console.WriteLine(sum + "  " +target);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        public static bool IsPrime(int n)
        {
            if (n < 2) return false;
            if (n == 2) return true;
            for (long i = 2; i <= Math.Sqrt(n); i++)
                if (n % i == 0) return false;
            return true;
        }
        public static List<int> GeneratePrimes(int n)
        {
            var primeNumbers = new List<int> { 0,2, 3 };
            for (int i = 5; i <= n; i += 2)
                if (IsPrime(i))
                    primeNumbers.Add(i);
            return primeNumbers;
        }
    }
}

PROJECT EULER #76

Link to Project Euler problem 76

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

Here we go...yet more virgin territory for me, but isn't that the point?
Partitions....the clue is to store values somewhere, so we do it in a 2-D grid.

using System;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 76
            DateTime start = DateTime.Now;
            int n = 100;
            int[,] a = new int[n + 1, n + 1];
            for (int i = 0; i < n + 1; i++)
            {
                a[i, 0] = 0;
                a[0, i] = 1;
            }
            for (int i = 1; i < n + 1; i++)
            {
                a[i, 1] = 1;
                for (int j = 2; j < n + 1; j++)
                {
                    int k = i - j;
                    if (k < 0)
                        a[i, j] = a[i, j - 1];
                    else
                        a[i, j] = a[i, j - 1] + a[k, j];
                }
            }
            Console.WriteLine(a[n, n - 1]);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}

PROJECT EULER #75

Link to Project Euler problem 75

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L 2,000,000 can exactly one integer sided right angle triangle be formed?

Using the two integer (m,n) technique for generating Pythagorean triples,I verify that they are primitive (using the IsRelativelyPrime method) then generate the non-primitives by simple scaling. Most of the time used goes to generate the list of prime factors of every number up to 2100000. The rest of the code uses 600 ms.

using System;
using System.Collections.Generic;

namespace project_euler
{
  class Program
  {
      public static Dictionary<int,List<int>> primeFactors = GeneratePrimeFactors(2100000);
      static void Main()
      {
          //Problem 75
          DateTime start = DateTime.Now;
          var pythagorasRecord = new Dictionary<long, int>();
          int count = 0;
          for (int m = 2; m < 1000000/m; m++)
              for (int n = 1; n < m; n++)
              {
                  long littleLeg = 2*m*n;
                  long bigLeg = m*m - n*n;
                  long hypotenuse = m*m + n*n;
                  if (IsRelativelyPrime(bigLeg, littleLeg))
                  {
                      long perimeter = littleLeg + bigLeg + hypotenuse;
                      long sum = perimeter;
                      while (sum <= 2000000)
                      {
                          if (pythagorasRecord.ContainsKey(sum))
                              pythagorasRecord[sum] += 1;
                          else
                              pythagorasRecord.Add(sum, 1);
                          sum += perimeter;
                      }
                  }
              }
          foreach (KeyValuePair<long, int> pair in pythagorasRecord)
              if (pair.Value == 1)
                  count++;
          Console.WriteLine(count);
          TimeSpan time = DateTime.Now - start;
          Console.WriteLine("This took {0}", time);
          Console.ReadKey();
      }
      public static bool IsRelativelyPrime (long m,long n)
      {
          foreach (long i in primeFactors[(int)m])
              if (n % i == 0) return false;
          return true;
      }
      public static Dictionary<int,List<int>> GeneratePrimeFactors(int n)
      {
          var primes = GeneratePrimes(n);
          var pF = new Dictionary<int, List<int>>();
          pF.Add(0,new List<int>{0});
          for (int i = 1; i <= n; i++)
              pF.Add(i,new List<int>());
          if (n == 1) return pF;
          foreach (int i in primes)
              for (int j = i; j <= n; j += i)
                  pF[j].Add(i);
          return pF;
      }
      public static bool IsPrime(int n)
      {
          if (n < 2) return false;
          if (n == 2) return true;
          for (long i = 2; i <= Math.Sqrt(n); i++)
              if (n % i == 0) return false;
          return true;
      }
      public static List<int> GeneratePrimes(int n)
      {
          var primeNumbers = new List<int> { 2, 3 };
          for (int i = 5; i <= n; i += 2)
              if (IsPrime(i))
                  primeNumbers.Add(i);
          return primeNumbers;
      }
  }
}

PROJECT EULER #74

Link to Project Euler problem 74

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:
169 -> 363601 -> 1454 -> 169
871 -> 45361 -> 871
872 -> 45362 -> 872
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
69 -> 363600 -> 1454 -> 169 -> 363601 (-> 1454)
78 -> 45360 -> 871 -> 45361 (-> 871)
540 -> 145 (-> 145)
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

This took too long (38 s) but I don't see any obvious optimisations (yet).

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        public static List<long> factorials = GenerateFactorials(9);
        static void Main()
        {
            //Problem 74
            DateTime start = DateTime.Now;
            int sixties = 0;
            for (int i = 1; i < 1000000; i++)
            {
                int count = 0;
                var cycle = new List<long>();
                long number = i;
                while (!cycle.Contains(number))
                {
                    count++;
                    cycle.Add(number);
                    number = GenerateSumOfFactorials(number);
                }
                if (count == 60)
                    sixties++;
            }
            Console.WriteLine(sixties);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        public static List<long> GenerateFactorials(int n)
        {
            var factorialList = new List<long> { 1 };
            for (int i = 1; i <= n; i++)
            {
                long factorial = 1;
                for (int j = 1; j <= i; j++)
                    factorial *= j;
                factorialList.Add(factorial);
            }
            return factorialList;
        }
        public static long GenerateSumOfFactorials(long n)
        {
            string s = n.ToString();
            long sum = 0;
            for (int i = 0; i < s.Length; i++)
                sum += factorials[int.Parse(s.Substring(i, 1))];
            return sum;
        }
    }
}

PROJECT EULER #73

Link to Project Euler problem 73

Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d <= 10,000?

Yet again a big thanks to my mentor: After trying to brute-force this by generating all the fractions using the a/b < c/d ...insert (a+c) /(b+d) if b+d = n, type of solution (I stopped the program after 40 mins) he suggested looking at this strategy (took 1.05 s):

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 73
            DateTime start = DateTime.Now;
            int number =10000;
            var primeFactors = GeneratePrimeFactors(number);
            int max = 0,min=0,sum=0;
            for (int i = number; i > 3; i--)
            {
                int count = 0;
                max = (int) Math.Floor((decimal) i/2);
                min=(int)Math.Ceiling((decimal) i/3);
                for (int j = min; j <=max; j++)
                {
                    int test = primeFactors[i].Count;
                    foreach (int k in primeFactors[i])
                        if (j%k == 0)
                            test--;
                    if (test == primeFactors[i].Count)
                        count++;
                }
                sum += count;
            }
            Console.WriteLine(sum);
            Console.WriteLine();
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        public static List<List<int>> GeneratePrimeFactors(int n)
        {
            var primes = GeneratePrimes(n);
            var primeFactors = new List<List<int>> {new List<int> {0}};
            for (int i = 1; i <= n; i++)
                primeFactors.Add(new List<int>());
            if (n==1) return primeFactors;
            foreach (int i in primes)
                for (int j = i; j <= n; j += i)
                    primeFactors[j].Add(i);
            return primeFactors;
        }
        public static bool IsPrime(int n)
        {
            if (n < 2) return false;
            if (n == 2) return true;
            for (long i = 2; i <= Math.Sqrt(n); i++)
                if (n % i == 0) return false;
            return true;
        }
        public static List<int> GeneratePrimes(int n)
        {
            var primeNumbers = new List<int> { 2, 3 };
            for (int i = 5; i <= n; i += 2)
                if (IsPrime(i))
                    primeNumbers.Add(i);
            return primeNumbers;
        }
    }
}