Euler 038- Find the largest 1..9 pandigital
A simple problem for today. A 1..9 Pandigital is defined as a nine digit number that contains digits 1 through 9. Find the largest pandigital that can be formed by concatenated multiplications. Specifically, given a number (192), multiply by, say, 1, 2, and 3 to get 192, 384, 576; the concatenated multiplication would be 192384576; which happens to be a pandigital. Multiplication factors have to be increasing, (1,2; 1,2,3; etc); and can’t be only 1.
So, my simple approach involves trying number of factors (n) of 2 through 8, and iterating through all possible factors that should be roughly less then a 9 digit number. Roughly/maybe/sort of. Overall the code isn’t that complex.
At least one optimization exists in realizing that the first digit of the factor has to be a 9, limiting the number of numbers to try; though in this case iterating over all possibilities is fast enough that that doesn’t really factor in.
public static void Main() { //the only pangdigital with n=9 is 1 //n>1 is required List<string> panDigitals = new List<string>(); for (int n = 2; n < 9; n++) panDigitals.AddRange(FindPandigitals(n)); panDigitals.Sort(); foreach (string pan in panDigitals) Console.WriteLine(pan); } public static List<string> FindPandigitals(int n) { List<string> results = new List<string>(); int digitCount=(9/n)+1; int maxI = (int)Math.Pow(10, digitCount); for(int i=1; i<maxI; i++) { string s=""; for (int a = 1; a <= n; a++) s += i * a; if (IsPandigital(s)) results.Add(s); } return results; } public static bool IsPandigital(string s) { if (s.Length != 9) return false; for (char a = '1'; a <= '9'; a++) if (!s.Contains(a)) return false; return true; }
Side note: I suspect next I’m going to try an ACM problem… or maybe something from Google CodeJam… who knows?
Slight Update, and Math is Cool
First, the blog shouldn’t be considered dead. It’s just with the summer Math class, and my lack of a game night on Saturdays to ignore while working on implementing Euler (or ACM problems if I get to it) the past two weeks has shot my productivity. That, and working on LC3D has come to a slow halt; though I’m continuing to blame that on a lack of time.
So, let’s chat about that Math class, and the second part of that thar title. I’m taking my first 400 level Math class, ‘Mathematics of Probability’. So far it has been like a combination of statistics and discrete math; and I like it. It’s not the proof intensive class of nightmares that I was worried it might be, which is comforting. And as I already said, I like it. Here’s one specific problem I like:
In how many ways can 4 rooks be placed on a chessboard such that no two rooks can capture each other. For the Chess-o-phobes, rooks capture horizontally and vertically, and board is an 8×8 grid. There are two ways to think about the solution to the problem.
The first way is my personal favorite. You can place the first rook in any of 64 squares, followed by 49 squares, then 36, then 25 squares. That is (8*7*6*5)^2 = (P8,4)^2; or number of permutations of 8 objects, of which 4 are relevant, e.g. 8!/4!. Now, we’ve selected these locations in such a way that order matters; e.g. if we place the first rook in the top right and second in bottom left; that is distinct from placing the first rook in the bottom left, and the second in the top right. To fix that problem we realize we are working with permutations of 4 objects, and divide by 4!. In the end, we get 8!^2/4!^3 ; or (P8,4)^2/4!.
The second way involves conceptualizing it as choosing the rows and columns in which the rooks will be placed: choosing 4 columns, and 4 rows can be done in (C8,4)^2 = (8!/(4!*4!))^2. When we’ve done that we look only at the intersections of these rows and columns, basically a 4×4 grid, in which we will place a pawn on each row, and each column. On the first row, there are 4 locations to place a pawn; on the second there will be only 3; third will have only 2; and the final row can have a pawn in only one location, after the other three rows have been chosen. This means there are 4! ways to place the rooks on a grid that can be chosen in C8,4^2 ways. Multiplication gives you that this can be done in 8!^2/4!^3 = 4!*(C8,4)^2 ways. That might look familiar if you read the last paragraph.
Formula actually comes out to be identical, but there are in fact two ways to arrive at it.
Interesting fact about me: I have a strong, persistent fear of math. I actually like it quite a bit: taking an integral over the volume of a sphere, solving brine tank differential equations using matricies, figuring out the number of unique ways that you can order books on a book shelf, all manner of interesting little math problems. I like knowing how to solve these things which to my knowledge have yet to come up in my life. Not quite true; I’ve actually used bits of Calculus 3, twice, long after I had forgotten the relevant portion that I needed.
But, while I enjoy math, I also have that fear thing. I think it’s based on a fear that, at some point, I’m going to encounter something which I flat out can’t understand; and that anything past that point would be impossible for me to understand. Given that fear explanation, being able to find answers in multiple ways actually gives a fair ammount of comfort to me. Even if this is a rather basic example.
So, that’s my update, and minor thoughts for the day.
Euler 208- Robot Walk
http://projecteuler.net/index.php?section=forum&id;=208 -
This is a fun one, which I approached in a way which can be classified as ‘entirely more painful then it had to be’. I should probably add a disclaimer to these posts “Not neccessarily a good way to solve the problem”; but alas, the solution is here irregaurdless of its suitability.
In this problem we have a robot; and we want to know, given that it will move 70 units, turning left or right each time (at 72 degrees, or one fifth a circular arc), how many unique paths will end back at the origin. I thought about it off and on for a few weeks. The immediate thing that jumps out are there are 2^70 distinct paths. Clearly immune to normal brute forcing.
First odd thoughts were that there might be something in the realm of combinatorics… I experimented with establishing if there was an obvious tie in between number of left/right turns and solutions; I couldn’t’ find one. I made the discovery that there should be equal number of end points facing all directions: (70 end points, so 70/5=14 points should face in each direction, 0 degrees, 72, 144, 216, 288, 360=0). But, I couldn’t figure out how to combine this knowledge with the fact that only two possible values can occur after a specific value (e.g. you can’t go from facing 0 to facing 216), while also maintaining that each end point needs to occur equally. Also, I’m sorry for the fictional people that read that last paragraph. I didn’t even understand it. All that said, there actually is an odd combination of combinatorics and dynamic programming which I didn’t find; I’ll chat about it after I give my own terrible solution.
So, we already discussed that we can’t brute force it. We can take a different approach though. While there are 2^70 distinct paths, there are considerably fewer unique ending points to paths. As an example, after 5 movements, there are two paths that end at the origin; after 10, there are at least 4 (and possibly more); similar occurs for several other end points.
So, my approach is to build a list of ending points (direction, and ending x and y coordinates, assuming start from origin), and the number of paths that end there. When we have that, we can combine any two paths by rotating the second path according to the first paths direction, and we know how many paths will end there: number of the first path * number of second path. The end result is we save alot of duplication of calculation. That said, this is by no means a fast solution.
We’ll start with the definition of a Location:
class Location { public double ActualX; public double ActualY; public int CloseX; public int CloseY; public int Rotation; public Location(double x, double y, int rotation) { ActualX = x; ActualY = y; CloseX = (int)(100 * x); CloseY = (int)(100 * y); Rotation = rotation % 360; if (Rotation < 0) Rotation += 360; } public static Location operator +(Location left, Location right) { double angle=left.Rotation*Math.PI/180; double co=Math.Cos(angle); double si=Math.Sin(angle); double rotatedX = right.ActualX * co - right.ActualY * si; double rotatedY = right.ActualX * si + right.ActualY * co; return new Location(left.ActualX + rotatedX, left.ActualY + rotatedY, left.Rotation + right.Rotation); } public override bool Equals(object obj) { Location loc = (Location)obj; return loc.CloseX == CloseX && loc.CloseY == CloseY && loc.Rotation == Rotation; } public override int GetHashCode() { return ((Rotation/72) << 28) + (CloseX << 14) + CloseY; } }
We see a few things about this. First, we’ve set it up to work in a Dictionary (as HashMaps are the most useful ADT ever created) by writing the GetHashCode and Equals methods; and we performed a minor ‘optimization’ of these, by using an integer approximation of the actual floating point location. This also solves a common problem in that checking equality on doubles is often spotty at best: 1.0000000001 != 1.0000000002. Basically, because of how we chose the CloseX and CloseY values, we assume that no two paths will get within 1/100th of a unit distance from each other, and not actually be at the same point. Experimentally, this results in the same number of distinct paths as using a 10,000 multiplier; so it probably works.
This can also sort of be verified mathamatically: because there are only 5 basic movements, the number of areas that can be visited is much decreased: you can’t visit every point on the plane using this robot. Or, somewhat closer to math terms: the movements that can be made do not form a Basis for the plane. (I’m fairly sure that’s a terrible butchering of Linear Algebra terminology; but it works for me). This is mostly because it can’t move at arbitrary factors of the directions it can move in: ie it can’t reverse, it can’t move pi steps in a given direction, and so on.
With those boring parts explained, we also have the plus operator. Given two Locations, it returns the Location that would be formed by following the path that lead to the first Location; then following the path that lead to the second Location given the new starting orientation and position. Basically, what it’s doing is rotating the second point around the origin, then adding that to the first point, and recalculating the rotation. Fairly simple. The rotation is stolen from Linear Algebra, and more specifically, I beleive I stole it from the wikipedia article on Rotation. (Sad fact: College Linear Algebra spent about 5 minutes on the topic, and never came up again).
With our Location defined, let’s look at the algorithms/code:
class E208 { private static Dictionary<int, Dictionary<Location, long>> paths; public static void Main() { paths = new Dictionary<int, Dictionary<Location, long>>(); GenerateStartingPaths(); GeneratePaths(70); Console.WriteLine("Count of 0's: "+paths[70][new Location(0, 0, 0)]); GeneratePaths(25); Console.WriteLine("Count of 0's: " + paths[25][new Location(0, 0, 0)]); } private static void GenerateStartingPaths() { paths[1] = new Dictionary<Location, long>(); double x = Math.Cos(72 * Math.PI / 180); double y = Math.Sin(72 * Math.PI / 180); paths[1][new Location(x, y, 72)] = 1; paths[1][new Location(x, -y, 4*72)] = 1; Combine(1, 1); //generate length 2 paths } private static void GeneratePaths(int length) { while(!paths.ContainsKey(length)) { int maxKey = 1; foreach (int key in paths.Keys) if (key < length) maxKey = Math.Max(maxKey, key); int otherKey=Math.Min(length-maxKey,2); Combine(maxKey, otherKey); } } private static void Combine(int firstKey, int secondKey) { Dictionary<Location, long> first = paths[firstKey]; Dictionary<Location, long> second = paths[secondKey]; Console.WriteLine("Combining " + firstKey + " " + secondKey+" with "+first.Count+" and "+second.Count+" paths"); Dictionary<Location, long> result = new Dictionary<Location, long>(2*first.Count); foreach (KeyValuePair<Location, long> firstKvp in first) foreach (KeyValuePair<Location, long> secondKvp in second) { Location newPoint = firstKvp.Key + secondKvp.Key; long count = firstKvp.Value * secondKvp.Value; long currentValue; if (result.TryGetValue(newPoint, out currentValue)) result[newPoint] = currentValue + count; else result[newPoint] = count; } paths[firstKey + secondKey] = result; } }
So, we have a few large things here. First note that we keep track of all paths of a given length that were created. So, in that paths Dictionary, we have a list of all paths of length 1, length 2, length 4 … length 70. With that out of the way, let’s get started.
First thing we’ll chat about is combining. Combining takes two sets of paths of given lengths, and then finds all combinations of those two sets as a result set. This gives you all paths of length firstLength + secondLength. It does this by going through each path in the first set, and adding to it each path in the second set. This gives us a new location, and we know that the number of ways to get to that new location are number of ways in first set * number of ways in second set.
Not the cleanest of explanations I understand. A better way to think about it might be to say ‘if I wanted to get to Location X + Y, I could take any path from this first set of paths that take me to X, then any path in the second set of paths that take me to Y. I can thus take number of first paths * number of second paths unique routes.’ Basically.
Moving on from my terrible explanation attempts, we’ll look at GeneratePaths. This has an interesting story to it. When I first wrote this, I would go through, and select the largest two paths that would sum to near the desired length. It made sense to me: take this route, you perform only log n combine operations, and everyone ends up happy. With this approach, calculating paths for length 70 took ~280 seconds. And I spent a while trying to improve this to no avail. As it turns out, this would happen because combining a 32 length path with a 32 length path requires 18,000*18,000 = ~350,000,000 sets of operations (a set of operations being dictionary lookups, cos/sin, memmory allocations, math). What I found was, that by doing only paths of length 2, we decrease the number of operations needed to get to path length 70 by about a factor of 100. More specifically, path length 68 had 324,000 unique paths; if we assume all paths (except length 2, having 4 elements) had 324,000 unique elements, and we needed perform 68/2 Combinations, we would need to perform only 324,000*68/2*4 = 44,000,000 operations. It’s actually a fair bit less, I’d say on the order of 20,000,000. This leads to a total calculation time of only about 8 seconds. Very nice.
As to what it’s actually doing, it goes through, finds the largest key smaller then the length we’re looking for, then tries to combine it with the paths of length 2, or paths of length 1 if it happens that the desired length and max key are only different by a length of 1.
GenerateStartingPaths has the first two paths hard coded, and then goes on to generate paths of length 2, to make the code for generating arbitrary length paths a bit nicer.
Main is fairly obvious: Generates the starting paths, and calls for paths of length 70, then looks up the value of Location 0,0; facing North. Nice and simple. Sort of. This post makes me question the economics of >100 line solutions in a blog format. But, it was fun.
Now, for that nice combinatoric/DP solution.
static Dictionary<long, long> values=new Dictionary<long,long>(); public static void Main() { Console.WriteLine(Calculate(5, 5, 5, 5, 5)); Console.WriteLine(Calculate(14, 14, 14, 14, 14)); } static long Calculate(long n1, long n2, long n3, long n4, long n5) { if (n1 < 0 || n2 < 0 || n3 < 0 || n4 < 0 || n5 < 0) return 0; if ((n1 + n2 + n3 + n4 + n5) == 0) return 1; long key = n1 + 15 * (n2 + 15 * (n3 + 15 * (n4 + 15 * n5))); if (values.ContainsKey(key)) return values[key]; long result = Calculate(n2, n3, n4, n5, n1-1) + Calculate(n5-1, n1, n2, n3, n4); values[key] = result; return result; }
It executes in under a second (and is based off code by ‘hirak99′ in the Project Euler forums). I almost/barely understand what it is doing. First, consider each movement as a move in x,y; rather then having a rotation component, and other complexities. If you look at it that way, then you need equal number of moves in each of 5 directions to get back to the origin. But, you can only move in one of two directions when at a specific location; this algorithm accounts for that by keeping track of how many moves we’ve made, and rotating them arround to account for ‘I’m turning left’ or ‘I’m turning right’.
As a slightly better (or worse) example, envision you start at the origin, turn left, then turn right. You were at 0,0; you moves to a point at cos(-72),sin(72), then move again to in that same basic direction (actually you move at cos(0),sin(0) rotated 72 degrees). You end up at the point 2x,2y, as the algorithm dictates. Which was the hardest bit for me to understand about it. And I still couldn’t explain this to (non-tech/math relative)… but I found it cool none-the-less.
