Tao of Coding

Euler 078- Find First Number With Count of Unique Sums Divisible by 1,000,000

http://projecteuler.net/index.php?section=problems&id;=78

I actually solved this better then a week ago, but never got arround to the writeup. I blame Jae, and my inability to schedule time.

Technically the topic description is a lie/simplification. The problem is actually this: given p(n) defines the number of unique ways to form groups from n items (ie for 3 items you can have 3 in 1 group, 2 in 1 and 1 in 1, or all 3 in seperate groups); find the value of n for which p(n) % 1000000 = 0. This is basically the same concept from Euler 76, if I recall it correctly, where you’re looking for the number of unique sums for a given integer n: this is the exact same problem in that sense.

However, the problem itself is entirely different, and much more painful.

The first item that I recall comming across is that p(n) doesn’t fit into a 32 bit integer for the value that we’re looking for; and it doesn’t even fit in a 64 bit integer (though I don’t recall if I had figured that out the fun and exciting way before the next bit). To get arround this I decided to play arround a bit with ruby, and it’s arbitrary precision integer fun. As it turns out, Ruby is dog slow once you get into these 20+ digit simple additions; and that also got into the next issues.

Memory usage is massive for the 2D array approach to handling this. I vaguely recall quiting the application after it had gotten to 600~mb of memory usage and in either the low 20,000’s or the low 2,000’s of n. Getting a solution to this was actually relatively simple, and slighlty stolen from the discussion to the solution of problem 76. There exists a recurrence relation that defines p(n) in terms of p(~1)…p(n-1): (loosely stolen from http://mathworld.wolfram.com/PartitionFunctionP.html)

P(n)=sum(1..n on k, (-1)^(k+1) * [P(n- (3k^2-k)/2 + P(n- (3k^2+k)/2]
with P(0)=1, and P(<0)=0.

This speeds up calculation a fair bit, and cuts memory usage by… alot. (should be by a factor of n / it should be a sqrt of the original usage).

That said, calculation still took quite a bit of time, (mostly due to simple 20+ digit arthmetic, again), so I wondered if there was a better solution. And thus stole from the Project Euler forums yet agin. The key to the next step is that we don’t actually care what the value of p(n) is, just that p(n)%1000000=0 . This means that the array we use for storing p(n) only needs to concern itself with values between 0 and 999,999; meaning we can go back to C# and it’s 32bit primitive data types.

One fun thing that arose from only keeping track of a part of p(n) is that the strict / straightforward calculation of p(n) is no longer gauranteed to be positive; and I spent a fun few times trying to figure out why it would fail on me in interesting ways. But, eventually it worked… eventually.

Calculation after all these changes was a fair bit faster; and if I recall correctly, the answer was in the 50,000 range of n; a fair bit sooner then I would have expected.

Code:

public static void Main()
{
    for(int i=5;;i++)
    {
        if (NumberOfUniqueSums(i) == 0)
            Console.Write(i + "-*-*-" + NumberOfUniqueSums(i)+" ");
        //something to pass the time
        if (i % 1000 == 0)
            Console.Write(i + " ");
    }
}
 
//storage for previous lookups of P(n)
static Dictionary<int, int> sumResults = new Dictionary<int, int>();
static int NumberOfUniqueSums(int numToSum)
{
    if(numToSum < 0) return 0;
    if(numToSum==0) return 1;
    if(sumResults.ContainsKey(numToSum))
        return sumResults[numToSum];
 
    int sum=0;
    //past the sqrt, you're always looking at P(-x); always 0
    for(int k=1; k<=Math.Sqrt(numToSum)+1 && k<=numToSum; k++)
    {
        int n1 = numToSum - (k * (3 * k - 1) / 2);
        int n2 = numToSum - (k * (3 * k + 1) / 2);
        int tempSum = NumberOfUniqueSums(n1) + NumberOfUniqueSums(n2);
        int factor = (k % 2 == 1) ? 1 : -1;
        sum += factor * tempSum;
        sum %= 1000000;
    }
    sumResults[numToSum]=sum;
    return sum;
}

Light Cycles 3D- Progress Update 1

Okay, I’ve started work on a first iteration of LC3D; and I’m working on the domain portion now; plotting to do graphics last. My current plan is to implement the game in single player form to get it working, and play arround with some cools things that can be done with the graphics/interface. Specifically, I’d like to try implementing a real time glow effect (http://http.developer.nvidia.com/GPUGems/gpugems_ch21.html for reference); and something slightly more interesting for the folk that die early: maybe a simple fly through the course option, or a circling outside camera; either would work, and a ‘fly through camera’ would allow me to play arround with multiple degrees of freedom movement, something I would need to do for some of my other games.

So, to recap, I’m implementing it in single player form for now so that I can play around with getting bits of it right. When I finally finish that, I’m going to figure out the best structure for sharing state between multiple clients, and eventually fix almost everything. And it will be glorious.

On a related note; I had a thought on networking and death: what to do in the case of a player that dies (or doesn’t die) because of network latency in getting a change direction command across has been a major issue for me. Right now, my line of thinking is this: if a Player sees himself crash into a wall, then the player failed, and his client should send out the ‘I am dead’ signal. If a change direction on the part of the person he crashed into would have saved him; it doesn’t quite matter: he died living a full 20 second life. If a change direction does result in his death when he didn’t see it happen… well, thats unfortunate; but kill him anyway; and have his client report the death. (the ideal would actually be to slightly ignore it, but because of the game state implementation, that would be much more difficult then it sounds). Sadly, this is more vulnerable to cheating (player reports his own death, and only his own death), and may also be more vulnerable to the ‘what did I hit’ question; but I think the case will be rare enough that it won’t be a problem.

Hopefully.

Further completely unrelated sidenote: I now have an avatar… A gnome playing with the GTK symbol, originally put together in 1998 by someone at TAMU (http://www.isc.tamu.edu/~lewing/gallery/gnome/). I have stolen and slightly altered it, though am hopefully attributing it with this post.

Light Cycles 3D- Concept

Until a better non copyright infringing name comes along, we’re going to call this ‘Light Cycles 3D’, or LC3D.

History
As I said in the list of projects post, this has in fact been implemented once before: it was an (unsuccessful) entry into a TAGD one week game competition. Humerous fact: I went through and built it, got it finished, and everything partially working except for the jitter with network game play under C# (.NET 2.0) with Managed DirectX. Go to show it off at the one week get together, to find that the library computers are using .NET 1.1; and probably don’t have the specific Managed DirectX library needed for it. Sadly, didn’t get it converted in time for the presentation, so now one of the goals of the project is to write it using standard C++ and OpenGL.

Concept
The basic concept behind this game is to take the classic Tron/Light Cycle game on a 2D discrete grid surface, and allow movement in a confined 3D discrete grid space. Discrete grid means the space can be broken into individual squares/cubes: it is not a continuous space (as Armaegtron uses). This has a very different game play feel in that it goes from a fast-paced strategic ‘block off the enemy into a tiny box’ game play, to a slower ‘avoid death as long as possible’ style. A slightly less arcade feel, though I prefer the visuals while playing through it: sort of like flying through the Windows Pipes screen saver. Fun and enjoyable? Probably not. But interesting and visually appealing for me.

Game Play
The game takes place in a closed cube, by default a 10×10x10 shell. A player is able to see the cube through the ‘eye’ of his… ship; as opposed to the overhead view used in traditional Tron games. 6 Players start each on one side of the cube, facing the opposite side. Time then begins and each player moves at one square per time increment. The players leave an impenetrible trail behind them, and they are able to either: change direction (up, down, left, right) once per time increment, or simply go forward. If they smack into another players trail, they die, and are out of the game; their trail staying present. Last player alive wins.

An obvious multiplayer element exists: the 5 other players could be network players, AI, or (an odd and humerous side effect from testing), a clone of the single human player. Obstacles or uniquely shaped arena’s (nearly flat rectangle, donut, barbell) could be added to make game play slightly more interesting. It’s also been pointed out that this wouldn’t be too far removed from a ‘worms in 3space’ type game.

Implementation Thoughts
Because implementation is never far from my mind.

The problem with network game play in the first iteration of the game was ‘jitter’: in original game play, the game world had discrete (and visually jarring) steps: you would advance 1 unit of space every quarter or half second; to offset this eye bleeding problem, a smooth transition was added from one discrete step of the universe to the next. Whenever an update was received from the server, this was treated as ‘reseting time’; so, if the update came 100msec later then expected, the transition would move you backwards by 100msec*speed; and similar would happen on the next update (might have been 100msec early this time, etc). It was entertaining to watch, but also quite sad. This could have been fixed by varying the speed of the cycle based on updates (time dilation, woohoo), or a few other odd methods. I suspect fixing this satisfactorly is going to be a bit of a painful process, but we’ll see when we get there.

Changing subjects, one of the first things I did when I decided to do this for a one week game was figure out how facing worked with respect to changing direction of the ship: The ships facing is defined with a forward vector, and up vector, and I went through a very ungreat set of if statements to figure out the changes to these two vectors based on commands made. For example, selecting up means setting the up vector to the negative forward vector, and forward vector to the up vector. Working out the changes for turning left and right wasn’t exactly clean. I’d like to figure out how to translate that into simple matrix math; though until I have the time to work that out, I can probably just copy over the original code for it.

Euler 076- Number of Ways to write 100 as a sum

From http://projecteuler.net/index.php?section=problems&id;=76 -

Find the number of ways to write 100 as a unique sum of at least two (positive) numbers. This is actually rather similar to Euler 077, in that the same basic approach can be applied… except, brute force won’t work, directly. Going through and doing a blind recursive determination of all possible sum leads down the path of ruin, and waiting until the apocolypse. Or at least I assume so; I didn’t wait arround to find out just how slow it was.

A *slightly* better way to solve this is using a dynamic programming approach. Brute forcing in this case is problematic because it retreads and re-solves alot of subproblems. Say we wanted to solve for 5. To solve for 5 using our current algorithm, we hit ‘how many ways can you sum 1 using 4 through 1′ several times. (Haven’t actually counted it out, but take my word for it). When we try it with 100, we spend alot more time at that last level: the answer is on the order of 2*10^9; that would be about 10^9/100=10^7 times we retread the ‘how many ways to sum 1 using x through 1′ problem.

Put another way: figure out the answer to ‘how many ways is there to sum 1 using x through 1′, and use that, rather then recomputing. Apply similar logic for 2, 3, 4, 5, etc. In the end, you only do arround 100^2=10,000 computations, instead of 100 million. This is the concept of dynamic programming: solve a subproblem, store the result for use in calculating the greater problem.

Or, at least that’s my understanding of it; this may change when I finally take an algorithms class.

So. Code:

public static void Main()
{
    uniqueSumResults = new int[101, 100];
    for (int i = 0; i < uniqueSumResults.GetLength(0); i++)
        for (int j = 0; j < uniqueSumResults.GetLength(1); j++)
            uniqueSumResults[i, j] = -1;
    Console.WriteLine(NumberOfUniqueSums(5, 4));
    Console.WriteLine(NumberOfUniqueSums(100, 99));
}
 
static int[,] uniqueSumResults;
static int NumberOfUniqueSums(int numToSum, int maxSummand)
{
    if(maxSummand <= 0) return 0;
    if(numToSum < 0) return 0;
    if(numToSum == 0) return 1;
    if(uniqueSumResults[numToSum, maxSummand] != -1)
        return uniqueSumResults[numToSum, maxSummand];
 
 
    int sum = NumberOfUniqueSums(numToSum - maxSummand, maxSummand);
    sum += NumberOfUniqueSums(numToSum, maxSummand - 1);
    uniqueSumResults[numToSum, maxSummand] = sum;
    return sum;
}

Slight explanation: we use the ‘uniqueSumResults’ 2D array as a cache of results. If the value in the cache for a given set of parameters isn’t the initialized -1, then it contains the answer for the inputs; no further calculation necessary.

List of Side Projects

Euler 077- First value that can be written as sum of more then x primes

From Euler 077-

The goal is to find the first number that can be written as a sum of primes in 5,000 different ways. As an example, 10 can be written as 7+3, 2+2+2+2+2, 5+5, 5+3+2, etc.

Going about this the slow way. The first and immediate thoughts is ‘gee, I can try brute force’. The maximum number that the answer can be is 10,000 (2+2+…+2=2*5000). It’s actually a fair ammount less (2+2+2=3+3, but, my math skills are too terrible to figure out a better upper bound).

Now, I envision that determining all unique sums is quite slow for a single number. Can’t prove but envision. And slow being relative. To speed this up, we use an interesting property of these numbers.

Assume P(k) is the number of unique sums for k; P(k) <= P(k+2), as k+2 can be given simply by 2+(all solutions of k). Similar for P(k+3). I can’t prove it for P(k+1) though, sadly. This means that we could do one of two things: Either do a binary search on all even numbers, then all odd numbers to find the first number with P(k)==5000, (should be about 2*log2(10000)=26 checks, roughly); or, we can do a binary search down to a resolution of about 3, then check those final 3 numbers. It’d be about 16-19 comparisons. As the binary search across all evens then all odds is much simpler/less sticky, we’ll go that route.

Now, humerous fact: I went through all this thinking, and then did a test to see a. how slow finding unique sums is, and b. verify my ‘find unique sums’ algorithm works. The answer is less then 100, and can be found without any of the cool binary searching. I got to do precisely none of the cool things I was planning on. None of them. I feel like life is such a terrible waste, as I probably spent hours working out ways to solve the problem which would be equivelant to ‘find the first k such that P(k) is 10^(something huge)’… very dissappointing. And also, P(k)<=P(k+1) for all observed points.

Edit: Slight explanation of how to find the number of unique sums.
What we do is attempt all summations using primes in decreasing value of the prime. This ensures that any summation found will be unique. We do this recursively, and it can actually be considered dynamic programming; but, alas, the answer is already found.

Code:

static List<int> primes;
public static void Main()
{
    BuildPrimes(10000);
    for (int i = 2; i <= 100; i++)
        Console.WriteLine(i+" "+NumberOfUniqueSums(i, 0));
}
static int NumberOfUniqueSums(int k, int primeStartIndex)
{
    if(k<0) return 0;
    if (k == 0) return 1;
    int sum = 0;
    for (int primeIndex = primeStartIndex; primeIndex < primes.Count; primeIndex++)
        sum += NumberOfUniqueSums(k - primes[primeIndex], primeIndex);
    return sum;
}
static void BuildPrimes(int maxSquare)
{
    primes = new List<int> { 2};
    int maxI=((int)Math.Sqrt(maxSquare))+1;
    for (int primeCandidate = 3; primeCandidate < maxI; primeCandidate += 2)
    {
        bool isPrime = true;
        for (int i = 0; i < primes.Count && isPrime; i++)
            if (primeCandidate % primes[i] == 0)
                isPrime = false;
        if (isPrime)
            primes.Add(primeCandidate);
    }
    //max prime is now at index 0
    primes.Reverse();
}

Euler 206- Concealed Square

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

First thought was brute force by replacing blanks with numbers, and checking for a square root. This comes to a mere 10^9 possibilities, with a lot of parsing longs from string. After a bit of analysis though, you realize the last digit of the number we are looking for has to be 0. (0 being the only a*a to result in a 0 digit at the end). This also means the first blank is a 0, giving a mere 10^8 possibilities. Next is to realize that 9 can only be formed by a 3, or a 7 in the number. (Try not to forget the 7, as I did the first time through). So, we now know the target square ends in either 70 or 30.

We can move away a lot of parsing longs from strings, and sqrt’s, by just iterating over the possible answers, rather then the possible answers^2. This basically means iterating from 10^9+30 to something less then 10^10 (sqrt of 1929394959697989900; though I’m far too boring to plug that into a calculator). As already stated, we’re looking for something ending in 30 or 70, so we could start with 10^9+30 and increment by 100, then switch to +70, or alternatively alter increments of 40 and 60.

Probably the most complex thing is checking whether or not a square is of the desired format. For that I get the string representation of the square, and then in a for loop check that every other character is incrementing; with a special check for the 0 case. I envision there are better ways, but this was good enough for this problem.

Code:

static void Main(string[] args)
{
    long start = 1000000000;
    //add 100 to long on the off chance that there's a terrible loss
    //  of precision in the constant double
    long end = (long)(Math.Sqrt(1929394959697989900))+100;
    Test(start + 30, end, 100);
    Test(start + 70, end, 100);
}
static void Test(long start, long end, long incr)
{
    for (long current = start; current < end; current += incr)
    {
        string squareString = (current * current).ToString();
        bool isValid = true;
        for (int i = 1; i <= 9 && isValid; i++)
            if (squareString[2 * (i - 1)] != '0' + i)
                isValid = false;
        if (squareString[2 * (10 - 1)] != '0')
            isValid = false;
        if (isValid)
            Console.WriteLine("Solution: " + current);
    }
}

Euler 001- Starting out Easy

At least something to start the blog with.

Project Euler problem #1; sum all natural numbers less then 1000 that are multiples of 3 or 5. Natural numbers meaning positive integers. The simplest way to go about this is a for loop with a sum, something akin to:

int sum=0;
for(int i=1; i<1000; i++)  
    if(i%3==0 || i%5==0)
        sum+=i;
Console.WriteLine(sum);

Which gives us a nice and specific answer, which is correct. Fun optimization side of this:

You can consider the sum of all 3’s to be 3*sum(1..333), which can be computed as 3*(333*332/2 + 333), if math holds.

Similarly, sum of 5 is 5*sum(1..199) = 5*(199*198/2 + 199).

Next, you need to determine the sum of natural numbers divisible by 15: 15*sum(1..66)=15*67*66/2;

Finally, take the sum of the first two values, and subtract from that the last value. In this case: 166833 + 99500 – 33165 = the answer. This follows from a little too much math, and a bit of set theory: numbers divisible by 15 are counted in both the 3 and 5 cases, effectively double counted. We subtract one of these double counts to end up with a single count of all numbers; and, an O(1) solution.

Howdy

We’ll see how this turns out. I am Matt Moss, a Software Developer at the Energy Systems Lab in TEES… at Texas A&M; University. I work on a (small) variety of projects, mostly focusing on the backend of our web home energy calculators. While not working I’m also a full time undergrad student in the CompSci department. I’m an active participant in the ACM ICPC programming contests… and that’s about it for extra-curricular activity.

My evil plan for this blog is to get a slight online presence, have incentive to work on side projects, and to get better at ACM-esque problem solving. The evil details of the evil plan are to go through problems (past ACM, project Euler, etc) over this summer (2009 for ye archeaologists), and post analysis of the problem, and a solution. With any luck, I will also post details/expansions/others for ideas for side projects.

Also, Coder Tao is not a fascinating name based on the balance that should come from being able to solve complex problems semi-elegantly while also knowing the important bits of Software Engineering. Nor is it an endorsement of Asian religions. Nor is it a statement involving Torque and coding folk. Tao is the name of a gnome sorcerer. An impressive machine of destruction and chaos. And it’s now a name.

As I said, we’ll see how this turns out.

-Matt