Evil Science A whole load of stuff

4Sep/130

Use LINQ to calculate the Greatest Common Factor of a fraction

Want to calculate the Greatest Common Factor of fraction? Use this handy piece of LINQ:

int denom = 12;
int num = 8;
int gcf = Enumerable.Range(2, num - 1).LastOrDefault(i => num % i == 0 & denom % i == 0);

//gcf == 4

It returns a value of 0 if a GCF isn't found, hence the LastOrDefault.

It's straightforwards enough I think.

Filed under: C#, Project Euler No Comments
4Sep/130

Calculate the divisors of a number

Here are two different ways of calculating the divisors of a number using C#, something you're going to find extremely helpful when tackling Project Euler.

This method uses a for loop and a generic list.

static List<int> GetDivisors(int n)
{
    List<int> div = new List<int>();
    div.Add(n);
    for (int ctr = n / 2; ctr > 0; ctr--)
        if (n % ctr == 0)
            div.Add(ctr);

    return div;
}

This one uses an Enumerable Range and LINQ, and returns the results as a generic list.


int n = 6556;
List<int> div =
Enumerable.Range(1, n / 2).Where(i => n % i == 0).Union(new List<int>{n}).ToList();

//returns 48 results

Enjoy.

Filed under: C#, Project Euler No Comments
3Sep/130

Calculate the Factors of a number

This is a C sharp implementation of the method used to calculate the factors of the number, as described at Wikihow.com. It can come in quite handy when working with Project Euler.

/// <summary>
/// Calculate the Factors of a number
/// </summary>
/// <param name="n">Number to examine</param>
/// <returns>List of factors</returns>
static List<int> FactorNumber(int n)
{
    List<int> div = new List<int>();

    int p=2;

    do
    {
	if (n == 1)
	    break;

	while (n % p !=0)
	    p++;

	do
	{
	    n /= p;
	    div.Add(p);
	} while (n % p == 0);

    } while (true);

    return div;
}

Usage is simple enough:

List<int> factor = FactorNumber(6552); //returns 2,2,2,3,3,7,13
factor = FactorNumber(17); //returns 17
factor = FactorNumber(25); //returns 5,5
factor = FactorNumber(60); //returns 2,2,3,5
factor = FactorNumber(100); //returns 2,2,5,5
factor = FactorNumber(45360); //returns 2,2,2,2,3,3,3,3,5,7
Filed under: C#, Project Euler No Comments
31Aug/130

Project Euler Problem 54

Here's my solution to Project Euler Problem 54, it's written in C Sharp and outputs the winner of each hand and how they won. It can optimised, but is still very fast.

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

namespace Euler54b
{
    class Program
    {
        static List<string> Ranks = new List<string>() { "High Card", "One Pair", "Two Pairs", "Three of a Kind", "Straight", "Flush", "Full House", "Four of a Kind", "Straight Flush", "Royal Flush" };

        /// <summary>
        /// Start Here
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {

            int p1HighestCard;
            int p2HighestCard;
            int p1Hand;
            int p2Hand;

            int p1win = 0;
            int p2win = 0;

            string hand;

            using (StreamReader sr = new StreamReader("poker.txt"))
            {
                while (!sr.EndOfStream)
                {
                    hand = sr.ReadLine();

                    ProcessHands(hand, out p1Hand, out p2Hand, out  p1HighestCard, out p2HighestCard);

                    if (p1Hand > p2Hand)
                    {
                        p1win++;
                        Console.WriteLine("    Player 1: {0}", Ranks[p1Hand]);
                    }
                    else if (p2Hand > p1Hand | p2HighestCard > p1HighestCard)
                    {
                        p2win++;
                        Console.WriteLine("    Player 1: {0}", Ranks[p2Hand]);
                    }
                    else
                    {
                        if ( p1HighestCard > p2HighestCard)
                        {
                            Console.WriteLine("    Player 1 highest card {0}", GetCard(p1HighestCard));
                            p1win++;
                        }
                        else
                        {
                            Console.WriteLine("    Player 2 highest card {0}", GetCard(p2HighestCard));
                            p2win++;
                        }
                    }

                    Console.WriteLine();

                }
            }

            Console.WriteLine();
            Console.WriteLine("Player 1 win: {0} Player 2 win: {1}", p1win, p2win);
            Console.ReadLine();
        }

        /// <summary>
        /// Build the hand and sort it by rank
        /// </summary>
        /// <param name="pHand">String containing hand</param>
        /// <returns>Generic list of hand</returns>
        static List<string> GetHand(string pHand)
        {
            return pHand.Split(new string[] { " " }, StringSplitOptions.None).OrderBy(c => GetCardValue(c)).ToList();
        }

        /// <summary>
        /// Return a numeric value representing the provided card
        /// </summary>
        /// <param name="pCard">Card to examine</param>
        /// <returns>Numeric value</returns>
        static int GetCardValue(string pCard)
        {
            int result;
            int.TryParse(pCard.Substring(0, 1), out result);

            if (result == 0)
            {
                switch (pCard.Substring(0, 1))
                {
                    case "T":
                        return 9;
                    case "J":
                        return 10;
                    case "Q":
                        return 11;
                    case "K":
                        return 12;
                    case "A":
                        return 13;

                }
            }

            return result;
        }

        /// <summary>
        /// Get a string representing a card value from its numeric value
        /// </summary>
        /// <param name="pValue">Numeric value of card</param>
        /// <returns>String value</returns>
        static string GetCard(int pValue)
        {
            if (pValue < 9)
                return pValue.ToString();
            else
            {
                switch (pValue)
                {
                    case 9:
                        return "T";
                    case 10:
                        return "J";
                    case 11:
                        return "Q";
                    case 12:
                        return "K";
                    case 13:
                        return "A";
                }
            }

            return "";
        }


        /// <summary>
        /// Process the player hands
        /// </summary>
        /// <param name="pHands">String representing the player hands</param>
        /// <param name="p1Hand">Out variable: the rank of hand 1</param>
        /// <param name="p2Hand">Out variable: the rank of hand 2</param>
        /// <param name="p1HighestCard">Out variable: highest card in hand 1</param>
        /// <param name="p2HighestCard">Out variable: highest card in hand 2</param>
        static void ProcessHands(string pHands, out int p1Hand, out int p2Hand, out int p1HighestCard, out int p2HighestCard)
        {

            List<string> Player1 = GetHand(pHands.Substring(0, 14));
            List<string> Player2 = GetHand(pHands.Substring(15, 14));

            Console.WriteLine("Player 1: {0}", string.Join(" ", Player1.ToArray()));
            Console.WriteLine("Player 2: {0}", string.Join(" ", Player2.ToArray()));

            p1Hand = RankHand(Player1, out p1HighestCard);
            p2Hand = RankHand(Player2, out p2HighestCard);

            if ((p1Hand == p2Hand))
            {
                while (p1HighestCard == p2HighestCard)
                {
                    p1HighestCard = GetHighestValue(Player1, p1HighestCard);
                    p2HighestCard = GetHighestValue(Player2, p2HighestCard);
                };
            }
        }


        /// <summary>
        /// Get the highest value in the hand that occurs before the current highest card
        /// </summary>
        /// <param name="hand">Hand to examine</param>
        /// <param name="pHighestCardIndex">Current highest card</param>
        /// <returns></returns>
        static int GetHighestValue(List<string> hand, int pHighestCardIndex)
        {
            //create a list of the cards with an accompanying index of it's value
            var vals = from h in hand
                      select new { card = h, index = GetCardValue(h) };

            //if the current highest card is the lowest in the list, then return that.
            if (pHighestCardIndex == vals.First().index)
                return pHighestCardIndex;
            else
                //get the last value in the above list that is lower that current highest card
                return (from v in vals
                        where v.index < pHighestCardIndex
                        select v.index).Last();
        }

        /// <summary>
        /// Rank the provided hand
        /// </summary>
        /// <param name="pHand">Hand to rank</param>
        /// <param name="pHighestValue">Highest value in the hand</param>
        /// <returns>The rank of hand</returns>
        static int RankHand(List<string> pHand, out int pHighestValue)
        {
            //check for consecutive values
            bool straight = true;
            for (int i = 1; i < pHand.Count(); i++)
                if (GetCardValue(pHand[i]) - 1 != GetCardValue(pHand[i - 1]))
                    straight = false;

            //check for same suit
            bool samesuit = pHand.Select(h => h.Substring(1, 1)).Distinct().Count() == 1;

            //is it royal
            bool royal = String.Join("", pHand.Select(h => h.Substring(1, 1)).ToArray()) == "TJQKA";

            //the current haighest value is the last
            pHighestValue = GetCardValue(pHand.Last());

            if (samesuit &amp; royal)
                return 9;//royal flush
            else if (samesuit &amp; straight)
                return 8;//straight flush
            else if (samesuit)
                return 5;//flush
            else if (straight)
                return 4; //straight



            //count the occurences of cards
            var c = from h in pHand
                    group h by h.Substring(0, 1) into g
                    orderby g.Count()
                    select new { card = g.Key, cnt = g.Count() };

            pHighestValue = GetCardValue(c.Last().card);

            if (c.Count() == 5) //all values different
            {
                pHighestValue = GetCardValue(pHand.Last());
                return 0;
            }
            else if (c.Count() == 4)
            {
                return 1; //one pair
            }
            else if (c.Count() == 3)
            {
                if (c.Last().cnt == 3)
                    return 3; //three of a kind
                else
                    return 2;//two pairs
            }
            else
            {
                if (c.Last().cnt == 4)
                    return 7;//four of kind
                else
                    return 6;//full house (three of a kind and a pair)
            }

        }
    }
}
Filed under: Project Euler No Comments
31Mar/110

ASieve of Atkin prime number generator using TSQL

I worked out an implementation of the Sieve of Atkin for use in solving Project Euler problems. It's probably not as efficient as it could be, but it does the trick for me.

set nocount on

drop table #atkin
create table #atkin
(
	num float
	, isPrime bit
)
create clustered index primenums
	on #atkin(num)

declare @limit as bigint
declare @sqrt as float
declare @x as int
declare @y as int
declare @n as int

set @limit = 1000000
set @sqrt = sqrt(@limit)
set @x = 1

print 'begin outer loop'

/*
	put in candidate primes:
	integers which have an odd number of representations by certain quadratic forms
*/

while (@x <= @sqrt)
	begin

		set @y = 1

		while (@y <=@sqrt)
			begin

				set @n = (4 * (@x * @x)) + (@y * @y)
				if ((select num from #atkin where num =@n) is null)
					insert into #atkin (num, isPrime) values (@n,0)

				if (@n <= @limit AND (@n % 12 = 1 or @n % 12 =5))
					update #atkin set isPrime = isPrime ^ 1 where num = @n

				set @n = (3 * (@x * @x)) + (@y * @y)
				if ((select num from #atkin where num =@n) is null)
					insert into #atkin (num, isPrime) values (@n,0)

				if (@n <= @limit AND @n % 12 = 7)
					update #atkin set isPrime = isPrime ^ 1 where num = @n

				set @n = (3 * (@x * @x)) - (@y * @y)
				if ((select num from #atkin where num =@n) is null)
					insert into #atkin (num, isPrime) values (@n,0)

				if (@x >= @y AND @n <= @limit  AND @n % 12 = 11)
					update #atkin set isPrime = isPrime ^ 1 where num = @n

				set @y = @y + 1

			end

		set @x = @x + 1

	end 

declare @nsqr as bigint
declare @k as bigint

/*
	eliminate composites by sieving
*/
set @n = 5
while ( @n <= @sqrt)

	begin

		print @n

		if ((select isprime from #atkin where num = @n)=1)
			begin

				set @nsqr = @n * @n

				set @k = @nsqr

				while (@k <= @limit)

					begin

						update #atkin set isPrime = 0 where num = @k

						set @k = @k + @nsqr
						print '@k increment ' + str(@k)

					end

			end

		set @n = @n + 1

		print '@n increment ' + str(@n)

	end

	insert into #atkin (num, isPrime) values (2,1)
	insert into #atkin (num, isPrime) values (3,1)

delete from	#atkin where isprime <> 1
28Mar/110

Project Euler Problem 37 Solution in TSQL

This is a solution for Project Euler Problem 37. It makes uses of a temporary table called #atkin which is populated with prime numbers using the TSQL routine that uses the Sieve of Atkin, which is also located on this site.

Easy! There are, however, a couple of deliberate errors, that can be easily located with some patience. I don’t want to make things to easy for you little scamps, do I?

/*
process the prime number list
*/

/*
the number we are examining can't be single digits or contain zeros
*/
drop table #candidates
select num
into #candidates
from #atkin
where charindex('0', cast(num as varchar)) = 0

declare @ctr as integer
declare @del as integer

set @ctr = 1
set @del = 0

/*
delete from the candidate list any number that doesn't have a
shorter counterpart in the list of prime numbers, increasing
the string size by 1 with every loop, and bailing out of when
we stop deleting things
*/
while (@del > 0)

begin

delete from #candidates
from #candidates c1
left outer join #atkin a1
on left(c1.num,@ctr) = a1.num
left outer join #atkin a2
on right(c1.num,@ctr) = a2.num
where a1.num is null
or a2.num is not null

set @del = @@rowCount
set @ctr = @ctr + 1

end

/*
output the answer
*/
select sum(num)
from #candidates
Filed under: Project Euler No Comments
27Mar/110

Project Euler Problem 61 Solution in TSQL

/*
	generate the number range
*/
create table #polygonalnumbers 
(
	ctr int
	, val bigint
	, poltype varchar(3)
)


declare @ctr as integer 
set @ctr = 1

while (@ctr < 1000)

	begin
	
		insert into #polygonalnumbers
		select	@ctr,(@ctr*(@ctr+1))/2,'tri'

		insert into #polygonalnumbers
		select	@ctr,@ctr * @ctr *@ctr,'sqr'
		
		insert into #polygonalnumbers
		select	@ctr,(@ctr*((3*@ctr)-1))/2	,'pnt'	
		
		insert into #polygonalnumbers
		select	@ctr,(@ctr*((2*@ctr)-1))	,'hex'		
		
		insert into #polygonalnumbers
		select	@ctr,(@ctr*((5*@ctr)-3))/2	,'hep'		
		
		insert into #polygonalnumbers
		select	@ctr,(@ctr*((3*@ctr)-2))	,'oct'		
		
		set @ctr = @ctr + 1
		
	end
	
/*
	disregard
*/
	delete from	#polygonalnumbers
	where   LEN(val) <> 4
	
	
/*
	output the answer
*/
			
select	distinct  num1.val + num2.val + num3.val + num4.val + num5.val + num6.val

from	#polygonalnumbers num1
		inner join #polygonalnumbers num2
			on RIGHT (num1.val,2) = LEFT(num2.val,1)
			and num2.poltype <> num1.poltype
		inner join #polygonalnumbers num3
			on RIGHT (num2.val,2) = LEFT(num3.val,2)
			and num3.poltype <> num2.poltype
			and num3.poltype <> num1.poltype
		inner join #polygonalnumbers num4
			on RIGHT (num3.val,2) = LEFT(num4.val,2)
			and num4.poltype <> num3.poltype
			and num4.poltype <> num2.poltype
			and num4.poltype <> num1.poltype
		inner join #polygonalnumbers num5
			on RIGHT (num4.val,2) = LEFT(num5.val,2)
			and num5.poltype <> num4.poltype
			and num5.poltype <> num3.poltype
			and num5.poltype <> num2.poltype
			and num5.poltype <> num1.poltype
		inner join #polygonalnumbers num6
			on RIGHT (num5.val,2) = LEFT(num6.val,2)
			and num6.poltype <> num5.poltype
			and num6.poltype <> num4.poltype
			and num6.poltype <> num3.poltype
			and num6.poltype <> num2.poltype
			and num6.poltype <> num1.poltype
			and RIGHT (num6.val,2) = LEFT(num1.val,2)

Easy! There are, however, a couple of deliberate errors, that can be easily located with some patience. I don't want to make things to easy for you little scamps, do I?

Filed under: Project Euler No Comments