Project Euler – Problem 28

24 04 2009

I don’t have much to rant about, Linux has been behaving itself, and with finals coming most of my free time is spent on homework and studying. However, I did get around to solving a couple Euler Problems, so I thought I’d fill the awkward silence of my blog with one of them (although it’s so easy, I don’t expect anyone to be Googling for it).

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7 8  9 10
19  6  1 2 11
18  5 4  3 12
17 16 15 14 13

It can be verified that the sum of both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

At first glance I thought about how to generate the spiral inside an array, but after a second more of observation I decided there was no reason to. It’s fairly clear that each loop of the spiral increases the dimensions of the square by 2, meaning the corners are differing from each other by 2 more each time around the spiral. The corners then, can be found by just starting with the sum equal to 1, incrementing the current number by 2 and adding it to the sum (repeating four times), then by 4 four times, then by 6 four times.. you get the picture. Here it is thrown together in C, short and to the point.

#include 
#define SPIRAL_SIZE 1000

int main() {
	int incr, i;
	unsigned int sum = 1;
	unsigned int current_num = 1;

	for (incr = 2; incr <= SPIRAL_SIZE; incr+=2) {
		for (i = 1; i <= 4; i++) {
			current_num = current_num + incr;
			sum = sum + current_num;
		}
	}
	printf("Result: %d\n", sum);
}




Project Euler Problem 17

14 04 2009

Here’s a problem to make you shudder at the lack of logic in the English language.

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

First I put together a table of the words I’ll be using and counts of letters in them.

One     3 ten           3 eleven      6

Two    3 twenty   6 twelve       6

Three 5 thirty      6 thirteen   8

Four  4 forty        5 fortteen   8

Five   4 fifty          5 fifteen        7

Six      3 sixty       5 sixteen        7

Seven 5 seventy 7 seventeen 9

Eight  5 eighty     6 eighteen     8

Nine   4 ninety     6 nineteen    8

and 3

hundred 7

thousand 8

From here on, it’s time to get to some coding. I decided to throw something together in TCL using lists rather than bothering with C (although, in this case, the code isn’t really much shorter).

There’s basically two ways to do it, either deal with words, or deal with numbers. The former you could just write a function to convert a number to it’s English equivalent and then count the number of letters in it for each number between 1 and 1,000. The latter method, which I chose, dealed with the pure numbers by using a bunch of for loops. It’s sort of ugly, but it works.

set teenlist [list 3 6 6 8 8 7 7 9 8 8]
set oneslist [list 3 3 5 4 4 3 5 5 4]
set tenslist [list 6 6 5 5 5 7 6 6]

# 1 – 19
set lettersum 0
foreach one $oneslist {
set lettersum [expr $lettersum + $one]
}
foreach teen $teenlist {
set lettersum [expr $lettersum + $teen]
}

# 20-99
foreach ten $tenslist {
set lettersum [expr $lettersum + $ten]
foreach one $oneslist {
set lettersum [expr $lettersum + $ten + $one]
}
}

# 100 – 999
foreach hundred $oneslist {
# 100, 200, …, 300
set lettersum [expr $lettersum + $hundred + 7]

# 101-109, 201-209, …, 901-909
foreach one $oneslist {
set lettersum [expr $lettersum + $hundred + 10 + $one]
}

# 110-119, 210-219, …, 910-919
foreach teen $teenlist {
set lettersum [expr $lettersum + $hundred + 10 + $teen]
}

# 120-199, 220-299, …, 920-999
foreach ten $tenslist {
set lettersum [expr $lettersum + $hundred + 10 + $ten]
foreach one $oneslist {
set lettersum [expr $lettersum + $hundred + 10 + $ten + $one]
}
}
}

#1,000
set lettersum [expr $lettersum + 11]

puts $lettersum

I think I could have done it with paper and pencil faster than it took me to write the code though…





Project Euler Problem #15

20 03 2009

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

p_015

How many routes are there through a 20×20 grid?

First off, let me say I’ve never taken a combinatorics course, and before this problem had never seen the words “n choose k”. If you’ve taken a combinatorics course, you’ll probably figure out this problem in about 3 seconds, realizing it’s simply 40 choose 20 (which Google calculator will gladly output). Due to my lack of combinatorics, I was forced to take a very long route to get to the answer, but challenged myself a lot more in the process.

First off, I thought to myself, there must be some function f(n) for an n x n grid that will give me the result, and I just need to find it. In order to simplify things, I changed the grid to a set of equally spaced points in a plane. For a 2×2 grid, there would be 9 points (2+1)(2+1). Then I traced through the grid again, looking for some simple pattern. I quickly noticed that once you hit the bottom or right edge, you must go straight to the end point using a single path (along the edge). Otherwise, you have two choices (down or right). In my diagram below, I drew arrows on the points that I had a choice, and simply put a line through the points on the edges that had no choice. I also took note that for an n x n grid, there would be n movements in the right direction, n movements in the down direction, and 2n movements total.

paths2I was also on the bus at the time, so no access to a computer, which explains the badly scribbled diagrams.

The only pattern I could deduce from this, is that because there is 2n number of moves, all of which n must be down and n must be right, I could do something like this.

Down = 0

Right = 1

Paths to end in my 2×2 grid (from left to right, top to bottom in the diagram): 1100, 1001, 1010, 0011, 0101, 0110.

Nifty, but how do I make an algorithm to actually create these numbers? I could simply check using a brute force method, generating all the binary numbers from 0 to 15, and then checking if they meet the requirements. To solve the problem though, I would need to generate all the numbers from 0 to 2^(40). That’s a lot of numbers to check. 1,099,511,627,776 of them to be exact. I found the result of the 3×3 grid by hand, through painful searching. There’s 20 of them, so I don’t bother to show the result. If anyone finds an easy algorithm to use this method, I’d be interested in seeing it.

As things were, I hadn’t gotten far, and decided to take another approach. After staring at 1’s and 0’s for so long, I was ready to stare at something more graphical, and decided to represent the 3×3 grid paths as a binary tree, in the back of my mind thinking I could use a linked list in C to actually make such a structure and maybe get somewhere. First off, I put all the points into an array (in my head anyway) so I could easily keep track of them. P11, P12, P13, P21, etc for labels. Then, for a down branch, go left on the tree, and for a right branch, go right.

pathtreeThen I spent quite some time trying to make out patterns. First off, I began noting the paths from a point down to the bottom, which you can see in the small numbers on the lines and under the points. Then I noticed the tree diagrams for a 1×1 (red) and 2×2 (blue) grid were actually inside the 3×3 (green) grid. Nifty! Closer I thought I was, to finding a simple recursive function to find the answer I seek. Unfortunately, I couldn’t devise a simple function to generate the number of paths from the next tree diagram. Then, it came to me, looking at the path lengths.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

20

Eureka! It’s Pascal’s  triangle up-side-down! The result I seek for a n x n grid is the middle number of the 2*n’th row of pascal’s triangle. Not only that, but this is also the sum of the terms squared of the n’th row (one of many odd patterns in the triangle). Finally all I had to do was write a program to calculate the first 20 lines of Pascal’s triangle, and then square the terms of that last row and add them together.

to calculate the triangle,

#include 

#define ROWS 21
#define COLS 21

int main() {
        int triangle[ROWS][COLS];
        int i, j;

        for (i = 0; i < ROWS; i++) {
                for (j = 0; j <= i; j++) {
                        triangle[i][j] = 0;
                        if (i == j || j == 0) {
                                triangle[i][j] = 1;
                        } else {
                                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
                        }
                        printf("%d ", triangle[i][j]);
                }
                printf("\n");
        }
}

Resulting in,

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1
1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1

Taking all the elements of the last row, squaring them, and adding them,

1^2 + 20^2 + 190^2…. = 137,846,528,820 paths to the end in a 20×20 grid. That’s a lot of paths, I’m glad I didn’t have to resort to a pure brute force approach, it would have taken quite a long time.





Project Euler

20 03 2009

I’ve recently come across a nifty page known as Project Euler. It’s filled with over 230 math related programming problems to solve. Don’t worry if your math is rusty, most of the problems can be brute forced easily enough, but knowing some math can certainly help make your programs faster. Trying to find all the divisors of a number for example, will crawl to a halt when you get to large numbers, but there’s a shortcut to find the result of the divisor function just by the prime factorization of a number. This will help solve one of the problems in about .8 seconds instead of about 20 minutes of computation.

Most of my solutions are very hacked together and brute force, but they work well enough. I’ve been focusing more on solving each problem quickly and correctly, rather than coming up with the best code, resulting in a lot of code that falls into the burn after compiling catagory. I’ve been doing most of them in C, but some I’ve resorted to Java and other languages to make things easier, or to reuse code (there’s one challenge to write a program to solve Su Doku puzzles, something I wrote in Java and mentioned here).

If I come up with a particularly ingenious solution to one of them I might post it here. I’m current finishing up the 14th problem (doing them mostly in order).