Project Euler #15

Posted on October 7th, 2012

This is just a short little post about some fun I had this afternoon. Hopefully soon I’ll be starting a game app using canvas and jquery and will have much more useful and exciting things to say.

Project Euler Problem number fifteen is as follows:

Starting in the top left corner of a 2X2 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 20X20 grid?

I decided to take a mathematical approach to it since my math is pretty crusty and that depresses me. So, I got pretty quickly caught up on my combinations/Binomial Coefficient and wrote a little Python and here it is:

import math

# Below assumes a square
def getit(a):
    test = math.factorial(a*2)/math.factorial(a)**2
    print test

getit(20)

I made one that doesn’t depend on equal number sides as well, but am not sure if it’s correct yet. It is (along with this) in github.

Click here to view and leave comments!

ProjectEuler Problems 18/67 Solution. At Last!

Posted on September 3rd, 2012

I’ve been using projecteuler.net as a fun way to practice solving logic problems. For whatever reason, I got stuck on #18 (which is the same as #67, the difference being 67 cannot be solved using brute force) and skipped over it. Just could not figure out how not to add every possible path! Yesterday I finally came up with a solution, tested it out today and it’s super fast.

Here you go, in PHP:

NOTE: The syntax highlighter is really messing up my code, but it can be viewed here in github.

$handle = @fopen("input.txt", "r");
$tri_array = array();
while (($buffer = fgets($handle)) !== false){
    $tri_array[] = explode(" ", $buffer);
}
$x = count($tri_array)- 1;
$new_row = $tri_array[$x];
while($x > 0){
    $x--;
    $row = $tri_array[$x];
    $temp_arr = array();
    foreach($row as $key=>$value){
            $temp_arr[] = $new_row[$key] > $new_row[$key + 1] ? $value + $new_row[$key] : $value + $new_row[$key + 1];
    }
    $new_row = $temp_arr;
}
var_dump($new_row);

Super easy!

Click here to view and leave comments!

Next Page »