Author Archives: joe

About joe

.NET developer and board game geek located in the greater Atlanta region.

Ow!

Listen, Railo. There’s something I’ve been meaning to talk to you about. I think you’re great, fantastic even. You’re you’re elegant, quick as a squirrel, the price is right and you’ve got a lot of really nice features. But this, this makes my eyes bleed.

My Eyes!

Project Euler: Problem 28 in Ruby

I noticed a simple pattern of odd squares traveling up the rightmost corner of the spiral and after a little bit of toying around with the numbers I was able to come up with my solution. There are some truly beautiful and well explained solutions in the forums, but I’m pretty happy with mine, I could have been a nice guy and split it up, but I had a rough time coming up with appropriate variable names. This is what you get.

Problem #28

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?

def sum_corners n
  return 1 if n == 1
  4 * ((n * 2 - 1) ** 2 - (3 * n - 3)) + sum_corners(n - 1)
end

puts sum_corners((1001 + 1) / 2)

Project Euler: Problems 1 – 5 in JavaScript

I’ve been wanting to check out Rhino for a while, and I’ve been particularly interested in seeing how it compares to Ruby in terms of speed. The results have been a little varied, and it’s a deeply flawed comparison. But it’s something.

These scripts are just ports of my ruby solutions. There are a few places where I had to roll my own JavaScript functions instead of baked in Ruby methods, but other than that it was nearly line by line translation.

Problem 1Ruby solution

Add all the natural numbers below one thousand that are multiples of 3 or 5.

var total = 0;

for(var i = 0; i < 1000; i++) {
  if(i % 3 == 0 || i % 5 == 0) {
    total += i;
  }
}

print(total);

Problem 2Ruby solution

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

function fib(stack, n) {
  if(n == 0) {
    return 1;
  }
  if(n == 1) {
    return 2;
  }
  return stack[n - 1] + stack[n - 2];
}

var max   = 4000000;
var total = 0;
var stack = [];

for(var i = 0; i < max; i++) {
  stack[i] = fib(stack,i);
  if(stack[i] > max) {
    break;
  }
  if(stack[i] % 2 == 0) {
    total += stack[i]
  }
}

print(total);

Problem 3Ruby solution

Find the largest prime factor of a composite number.

function find_highest_prime_factor(n) {
  var max = Math.round(Math.sqrt(n));
  for(var i = max; i >= 2; i--) {
    if(n % i == 0 && find_highest_prime_factor(i) == 1) {
      return i;
    }
  }
  return 1;
}

var target = 600851475143;
print(find_highest_prime_factor(target));

Problem 4Ruby solution

Find the largest palindrome made from the product of two 3-digit numbers.

function get_highest_palindrome(high, low) {
  var highest = 0;
  for(var i = high; i >= low; i--) {
	for(var j = high; j >= low; j--) {
      sum = i * j;
      if(sum <= highest) {
        break;
	  }
      if(is_palindrome(sum.toString())) {
        highest = max(highest, sum);
	  }
    }
  }
  return highest;
}

function reverse(string) {
  var array = string.split('').reverse();
  var out   = '';
  for(key in array) {
	out += array[key];
  }
  return out;
}

function max(a,b) {
  if(a > b) {
	return a;
  }
  return b;
}

function is_palindrome(string) {
  return string == reverse(string);
}

print(get_highest_palindrome(999, 100));

Problem 5 - Ruby solution

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

function gcd(a,b) {
  var x = a;
  var y = b;
  var result;
  
  while (y != 0) {
	result = x % y;
    x      = y;
    y      = result;
  }
  return x;
}

function lcm(a,b) {
  return (a * b) / gcd(a, b);
}

var max = 20;
var min = 11;
var n   = min;

for(var i = min; i <= max; i++) {
  n = lcm(n,i);
}

print(n);

Project Euler: Problem 24 in Ruby

I could see that this problem was solvable by hand, but that’s no fun.

Instead I decided to implement it with a tree. Not the most efficient solution to be certain, especially the way I rolled it, but it was a fun exercise. I don’t get to play with trees often enough.

Problem #24

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

def nth_lexical_permutation values, key = "", chain = ""

  chain    = chain + key.to_s
  children = values.select { |i| i != key }

  $count -= 1 if children.size == 0
  return chain if $count == 0

  children.each do |i|
    result = nth_lexical_permutation children, i, chain
    return result if result.size > 0
  end
  ""
end

$count = 1_000_000
set    = (0..9).to_a

puts nth_lexical_permutation(set)

Yep, there’s a global in there. It just made things easier. There are actually quite a few things I don’t like about this program. But it’s late. And I’m tired.

Project Euler: Problem 23 in Ruby

Looks like I took a pretty common approach on this one. First I calculated all the abundant numbers and dropped the sums in a hash. Then I just summed up to the given upper bound of 28,124 excluding those abundant sums.

Ruby1.9 solves it on my computer in about 15 seconds. After reading through the forums, some people were using a much lower upper limit of 20,200 which brought my run time down to a much respectable 6 seconds.

Problem #23

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

def sum_proper_divisors n
  sum = 1
  (2..Math.sqrt(n)).each do |i|
    if n % i == 0
      result = n / i
      sum += result unless result == i
      sum += i
    end
  end
  sum
end

def next_abundant repo
  i = repo.last + 1
  while( sum_proper_divisors(i) <= i)
    i += 1
  end
  i
end

max   = 20_200
repo  = [12]
sums  = {24 => nil}
total = 0

while repo.last < max do
  repo << next_abundant(repo)
  repo.each do |i|
    sum = repo.last + i
    if sum > max
      break
    end
    sums.store sum, nil
  end
end

max.times do |i|
  total += i unless sums.include? i
end

puts total

Announcing GeoHashFlash!

Okay, so it’s hardly an announcement, but I’ve been working on a flex app for determining your daily official xkcd meetup location via the geohashing method described in comic 426.

Much love to:

I’m still learning Flex and this is my first adventure with Google Map, so it’s rough. And there’s still a lot of work to do, like, validation, error checking, or testing for example. But hey, first pass!

Here’s the code for the actual GeoHash class. I have “view source” disabled because it currently contains my API key, but you can download the key-less zip.

public class GeoHasher {

	private var date:Date;
	private var dow:Number;
	private var latitude:Number;
	private var longitude:Number;

	private var dateHash:String;
	private var dowHash:String;

	private var ready:Boolean;

	public function GeoHasher() {
		this.ready = false;
	}

	public function reset(
		date:Date,
		dow:Number,
		latitude:Number,
		longitude:Number
	):void {
		this.date      = date;
		this.dow       = dow;
		this.latitude  = latitude;
		this.longitude = longitude;

		this.ready     = true;

		setHashValues();
	}

	public function getDestination():Object {
		if(ready) {
			var hash:Object = getHashAsDecimal();
			return {
				latitude: toOrdinal(latitude, hash.date),
				longitude: toOrdinal(longitude, hash.dow)
			};	
		}
		return { latitude: "", longitude: "" };
	}

	// privates

	private function setHashValues():void {
		var formattedDate:String = Utilities.dateFormat(date,"-");
		var string:String = formattedDate + "-" + dow.toString();
		var hash:String   = MD5.encrypt(string); 

		dateHash = hash.slice(0,hash.length / 2);
		dowHash  = hash.slice(hash.length / 2,hash.length);
	}

	private function toOrdinal(pre:Number, post:Number):String {
		return (Math.floor(pre) + post).toString();
	}

	private function getHash():Object {
		return { date: dateHash, dow: dowHash };
	}

	private function getHashAsDecimal():Object {
		var hash:Object = getHash();
		return {
				date: Utilities.fractionalHexToDecimal(hash.date),
				dow: Utilities.fractionalHexToDecimal(hash.dow)
		};
	}
}

Converting Fractional Hex to Decimal in ActionScript

I’m working on a little Flex Geohashing application which required me to convert a fractional Hex value to decimal and the net was no help. It’s a trivial algorithm, but it’s not the kind of thing I want to spend my time writing. So, Here you go, future!

public function fractionalHexToDecimal(hex:String):Number {
	var total:Number = 0;
	for(var i:int = 0; i < hex.length; i++) {
		total += (parseInt("0x" + hex.charAt(i)) / Math.pow(16,i+1));
	}
	return total;
}

Only pass in the fractional. No "0x". No decimal point. Here's how it do.

fractionalHexToDecimal("1");
// 0.0625

fractionalHexToDecimal("0a");
// 0.0390625

fractionalHexToDecimal("db9318c2259923d0");
// 0.8577132677070023

Geohashing App forthcoming.

Mid Year Resolutions

I’ve always liked the month of June. It’s my birth month, but it’s also close enough to the middle of the year, which makes it a great time to re-evaluate my New Years Resolutions.

I’ve done pretty terrible on that list. However, I’ve made a lot of progress in areas I hadn’t anticipated 6 months ago.

All in all, it’s been a pretty good year and things are looking up!