Challenge: Lexicographic permutations

Posted on: October 19, 2016 2:12:46 AM
This challenge is to calculate the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Thinking back to my math classes in high school, I remembered that the maximum number of permutations possible for a given number can be calculated by n!. Knowing this, you can calculate any permutation value you want quickly without brute force. To figure out the first number, we need to calculate how many times we need to permutate 9!. 9! = 362880, so we know the first 362880 numbers start with 0, 362881 - 725760 start with 1, and 725761 - 1088640 start with 2. Because 1088640 is greater than the number we're attempting to look for, we know the first number in the answer has to be 2. Because we only know for sure that the 725761th permutation is 2013456789, we know we're 1000000 - 725761 or 274239 permutations away from the answer. We can keep using this method to narrow down to the final answer.
Program.cs
using Common.Math;
using System;
using System.Collections.Generic;

namespace ProjectEuler_24
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            List permNumbers = new List { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            int[] answer = new int[10];
            // the number of permutations remaining is 1 less than the number we are
            // looking for because the first perumation is our starting point
            int permutationsRemaining = 999999;
            int answerIdx = 0;

            for (int i = 1; i < 10; i++)
            {
                // because the most permutations possible is described as n!
                // we want to figure out how many times we have to go through,
                // this gives us the first number
                int factorialVal = (10 - i).Factorial();
                int x = permutationsRemaining / factorialVal;

                // now we need to calculate how many permutations remain after
                // we set the first number to continue narrowing down our calculation
                permutationsRemaining = permutationsRemaining % factorialVal;

                // set the answer then increment the index
                answer[answerIdx++] = permNumbers[x];

                // can't use the number again, remove it
                permNumbers.RemoveAt(x);

                // make sure we haven't already calculated the permuation value
                // we're trying to get
                if (permutationsRemaining == 0)
                {
                    break;
                }
            }

            Console.WriteLine($"The 1000000th lexicographic permutation is: {string.Join("", answer)}");
        }
    }
}
Factorial Code
        public static int Factorial(this int num)
        {
            if (num < 0)
            {
                return 0;
            }

            int result = 1;
            for (int i = 1; i <= num; i++)
            {
                result *= i;
            }

            return result;
        }
The Factorial extension I've added to my common math library from the previous post. I've only posted the code to generate it rather than the full class since it's the only portion relevant.

Challenge: Non-abundant sums

Posted on: October 19, 2016 12:57:48 AM
This challenge wants you to find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. An abundant number is described as the sum of the proper divisors are greater than the original number. For example, 12 is the smallest abundant number with it's divisors 1, 2, 3, 4, 6 summed together being 16. Where 12 is the smallest abundant number, 24 is would be the smallest abundant sum.
Program.cs
using Common.Math;
using System;
using System.Collections.Generic;
using System.Linq;

namespace ProjectEuler_23
{
    internal class Program
    {
        private const int HighestNumNotAbundantSum = 28123;

        private static bool IsAbundant(int i)
        {
            int[] factors = i.GetFactors().Distinct().ToArray();
            int sum = factors.Sum() - i;

            return sum > i;
        }

        private static void Main(string[] args)
        {
            int sum = 0;
            bool[] isAbundantSum = new bool[HighestNumNotAbundantSum + 1];
            List abundantNumbers = new List();

            //12 is the lowest abundant number
            for (int i = 12; i < HighestNumNotAbundantSum - 12; i++)
            {
                if (IsAbundant(i))
                {
                    abundantNumbers.Add(i);

                    for (int x = 0; x < abundantNumbers.Count; x++)
                    {
                        int abundantSum = i + abundantNumbers[x];

                        if (abundantSum <= HighestNumNotAbundantSum)
                        {
                            isAbundantSum[abundantSum] = true;
                        }
                    }
                }
            }

            for (int i = 1; i < isAbundantSum.Length; i++)
            {
                if (!isAbundantSum[i])
                {
                    sum += i;
                }
            }

            Console.WriteLine($"Sum of all numbers than can't be the sum of two abundant numbers: {sum}");
        }
    }
}
MathExtensions.cs
using System.Collections.Generic;
using System.Linq;

namespace Common.Math
{
    public static class MathExtensions
    {
        public static int[] GetFactors(this int num)
        {
            List factors = new List { 1, num };
            int root = (int)System.Math.Sqrt(num);

            for (int i = 2; i <= root; i++)
            {
                if (num % i == 0)
                {
                    factors.Add(i);
                    factors.Add(num / i);
                }
            }

            return factors.OrderBy(x => x).ToArray();
        }
    }
}
This code is pretty straight forward, first we loop starting at 12 since it's the lowest known abundant number up to the highest non-abundant number known subtract 12. Then we determine if the number is abundant and store it. To use as few loops as possible, we then calculate out all the possible sums and store those values into a BitArray. Last, we loop through the BitArray and sum all the false values to get the answer.
As a note: I've moved the generating of factors code into a common library that I'm going to start referencing in projects that require it because it is a pretty common math function needed for these. This will likely be the last time I post the code for it, if you're following my posts, you should have this function working for your future projects as well.

Google Authenticator Service in .NET Core

Posted on: September 12, 2016 1:43:16 AM
I'm in the process of converting my websites from ASP.NET 4 to .NET Core and one thing some of my sites use for added security is two factor authentication. .NET has a very nice built in handler for many types of authentication, including two factor; however, there was not any native support for Google Authenticator. Rather than try to switch my two factor to something already supported, I decided to take on the challenge of adding a new type. There is little to no documentation on how to do this as of my writing this, so it took a lot of research and digging into the source code of many .NET Core libraries. It was my goal to have the framework handle most of the leg work rather than do it myself.
GoogleAuthenticatorService.cs
    public class GoogleAuthenticatorService<TUser> : TotpSecurityStampBasedTokenProvider<TUser> where TUser : class
    {
        private static readonly DateTime UNIX_EPOCH = new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc);

        public override Task<bool> CanGenerateTwoFactorTokenAsync(UserManager<TUser> manager, TUser user)
        {
            return manager.GetTwoFactorEnabledAsync(user);
        }

        public string GenerateSecret()
        {
            byte[] buffer = new byte[9];

            using (var rng = RandomNumberGenerator.Create())
            {
                rng.GetBytes(buffer);
            }

            return Convert.ToBase64String(buffer).Substring(0, 10).Replace('/', '0').Replace('+', '1');
        }

        public string GetCode(string secret, long counter)
        {
            return GeneratePassword(secret, counter);
        }

        public string GetCode(string secret)
        {
            return GetCode(secret, GetCurrentCounter());
        }

        public long GetCurrentCounter()
        {
            return GetCurrentCounter(DateTime.UtcNow, UNIX_EPOCH, 30);
        }

        public bool IsValid(string secret, string code, int checkAdjacentIntervals = 1)
        {
            if (code == GetCode(secret))
                return true;

            for (int i = 1; i <= checkAdjacentIntervals; i++)
            {
                if (code == GetCode(secret, GetCurrentCounter() + i))
                    return true;

                if (code == GetCode(secret, GetCurrentCounter() - i))
                    return true;
            }

            return false;
        }

        public override async Task<bool> ValidateAsync(string purpose, string token, UserManager<TUser> manager, TUser user)
        {
            return IsValid(await manager.GetSecurityStampAsync(user), token);
        }

        private string GeneratePassword(string secret, long iterationNumber, int digits = 6)
        {
            byte[] counter = BitConverter.GetBytes(iterationNumber);

            if (BitConverter.IsLittleEndian)
                Array.Reverse(counter);

            byte[] key = Encoding.ASCII.GetBytes(secret);
            byte[] hash;

            using (HMACSHA1 hmac = new HMACSHA1(key))
            {
                hash = hmac.ComputeHash(counter);
            }

            int offset = hash[hash.Length - 1] & 0xf;

            int binary =
                ((hash[offset] & 0x7f) << 24)
                | ((hash[offset + 1] & 0xff) << 16)
                | ((hash[offset + 2] & 0xff) << 8)
                | (hash[offset + 3] & 0xff);

            int password = binary % (int)Math.Pow(10, digits);

            return password.ToString(new string('0', digits));
        }

        private long GetCurrentCounter(DateTime now, DateTime epoch, int timeStep)
        {
            return (long)(now - epoch).TotalSeconds / timeStep;
        }
    }
The biggest thing I want to point out in this class is the base class TotpSecurityStampBasedTokenProvider<TUser> This is the class that allows us to register the class as a TokenProvider within .NET Core.
Startup.cs
        public void ConfigureServices(IServiceCollection services)
        {
            services.AddSingleton(typeof(IConfigurationRoot), Configuration);

            // Add framework services.
            services.AddApplicationInsightsTelemetry(Configuration);

           services.AddIdentity<ApplicationUser, IdentityRole>()
                .AddEntityFrameworkStores<AuthDbContext>()
                .AddTokenProvider<GoogleAuthenticatorService<ApplicationUser>>("Google");

            services.AddMvc();

            services.Configure<IdentityOptions>(options =>
            {
                options.Lockout.DefaultLockoutTimeSpan = TimeSpan.FromMinutes(10);
                options.Lockout.MaxFailedAccessAttempts = 10;
            });
            services.Configure<CookieAuthenticationOptions>(options =>
            {
                options.LoginPath = new PathString("/Admin/Login");
            });
        }
You can see that we register the new TokenProvider and name it "Google".
AdminController.cs
        [AllowAnonymous, HttpPost, ValidateAntiForgeryToken]
        public async Task<IActionResult> Login(LoginViewModel loginModel, string returnUrl = null)
        {
            ViewData["ReturnUrl"] = returnUrl;
            if (ModelState.IsValid)
            {
                var result = await _signInManager.PasswordSignInAsync(loginModel.Username, loginModel.Password, false, true);

                if (result.Succeeded)
                {
                    return RedirectToLocal(returnUrl);
                }
                else if (result.RequiresTwoFactor)
                {
                    return View("TwoAuth");
                }
                else if (result.IsLockedOut)
                {
                    return View("Login");
                }
            }

            loginModel.Password = null;
            return View(loginModel);
        }

        [AllowAnonymous]
        public async Task<IActionResult> TwoAuth(string returnUrl = null)
        {
            ViewData["ReturnUrl"] = returnUrl;
            var user = await _signInManager.GetTwoFactorAuthenticationUserAsync();
            if (user == null)
            {
                return View("Login");
            }

            return View();
        }

        [AllowAnonymous, ValidateAntiForgeryToken, HttpPost]
        public async Task<IActionResult> TwoAuth(string code, string returnUrl = null)
        {
            ViewData["ReturnUrl"] = returnUrl;
            var user = await _signInManager.GetTwoFactorAuthenticationUserAsync();
            if (user != null)
            {
                var result = await _signInManager.TwoFactorSignInAsync("Google", code, false, false);

                if (result.Succeeded)
                {
                    return RedirectToLocal(returnUrl);
                }
                else if (result.IsLockedOut)
                {
                    return View("Login");
                }
            }

            return View();
        }
Here is a snippet of my AdminController that requires an authenticated user. As you can see, it checks if two factor auth is required. If it is, it tells it where to go to get the code. All of the details are taken care of using the built-in SignInManager.

Challenge: Amicable Numbers

Posted on: August 11, 2016 1:40:06 AM
This challenge describes an amicable number as:
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
The challenge is to get the sum of all the amicable numbers less than 10,000.
Program.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ProjectEuler_21
{
    internal class Program
    {
        private static int[] GetFactors(int num)
        {
            List factors = new List { 1, num };
            int root = (int)Math.Sqrt(num);

            for (int i = 2; i <= root; i++)
            {
                if (num % i == 0)
                {
                    factors.Add(i);
                    factors.Add(num / i);
                }
            }

            return factors.Distinct().OrderBy(i => i).ToArray();
        }

        private static int GetFactorsSum(int num)
        {
            int[] factors = GetFactors(num);
            int sum = 0;

            // don't include the actual num in the sum
            for (int i = 0; i < factors.Length - 1; i++)
            {
                sum += factors[i];
            }

            return sum;
        }

        private static void Main(string[] args)
        {
            Dictionary cache = new Dictionary();
            List amicableNumbers = new List();
            int amicableCount = 0;

            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 9999; i > 0; i--)
            {
                int factorSum = 0;

                if (!cache.ContainsKey(i))
                {
                    factorSum = GetFactorsSum(i);
                    cache[i] = factorSum;
                }
                else
                {
                    factorSum = cache[i];
                }

                if (!cache.ContainsKey(factorSum))
                {
                    cache[factorSum] = GetFactorsSum(factorSum);
                }

                if (cache[factorSum] == i && i != factorSum)
                {
                    amicableCount++;
                    amicableNumbers.Add(i);
                    amicableNumbers.Add(factorSum);
                }
            }
            sw.Stop();

            amicableNumbers = amicableNumbers.Distinct().OrderBy(i => i).ToList();

            Console.WriteLine("Number of amicable numbers under 10000: {0}\r\nSum of amicable numbers: {2}\r\nAmicable Numbers: {3}\r\nElapsed time: {1} ms", amicableCount, sw.ElapsedMilliseconds, amicableNumbers.Sum(), string.Join(", ", amicableNumbers));
        }
    }
}
From another challenge, we know how to easily and quickly calculate the factors of a number. So we can easily add to that logic by summing the factors to help us get an amicable number. I decided to cache the values, even though there really aren't many numbers we'd have to calculate twice. It ended up skimming off a couple of milliseconds.

Challenge: Maximum Path Sum

Posted on: July 29, 2016 2:00:43 AM
This challenge wants you to find the maximum sum of a triangle of numbers by only moving to downward adjacent numbers. In this example, the maximum sum is 23:
3
7 4
2 4 6
8 5 9 3
The challenge triangle is 15 rows large. This wouldn't be hard or take long to brute force to find the answer, but we want to be able to do it in a more clever way that can easily handle much larger triangles quickly. The challenge itself says that another challenge later on is the same problem, but scaled out to a triangle with 100 rows, which you couldn't brute force. I was able to accomplish this using a learning algorithm, also known as dynamic programming. Here is my code with the triangle hard coded in:
Program.cs
using System;

namespace ProjectEuler_18
{
    internal class Program
    {
        private static int[][] GetGreatestPathSum(int[][] triangle, int index)
        {
            if (index < triangle.Length - 1)
            {
                triangle = GetGreatestPathSum(triangle, index + 1);
            }

            if (index - 1 < 0)
            {
                return triangle;
            }

            int[] top = triangle[index - 1];
            int[] bottom = triangle[index];
            int[] result = new int[top.Length];

            for (int i = 0; i < top.Length; i++)
            {
                result[i] = Math.Max(top[i] + bottom[i], top[i] + bottom[i + 1]);
            }

            triangle[index - 1] = result;

            return triangle;
        }

        private static void Main(string[] args)
        {
            string triangle =
@"75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23";

            string[] triangleLines = triangle.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);
            int[][] intTriangle = new int[triangleLines.Length][];

            for (int i = 0; i < triangleLines.Length; i++)
            {
                string[] numberStrings = triangleLines[i].Split(' ');
                int[] numbers = new int[numberStrings.Length];

                for (int x = 0; x < numberStrings.Length; x++)
                {
                    numbers[x] = int.Parse(numberStrings[x]);
                }

                intTriangle[i] = numbers;
            }

            int sum = GetGreatestPathSum(intTriangle, 0)[0][0];

            Console.WriteLine("Greatest path sum: {0}", sum);
        }
    }
}
GetGreatestPathSum will call itself until it is at the bottom row of the triangle. It will then calculate the maximum paths the row before could take to that row and replace the previous row with the results. It will then pass this value back so that as it unwinds the stack, the triangle value at [0][0] will eventually be the greatest path value.