25 Jun 09 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 1 - Ruby 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 2 - Ruby 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 3 - Ruby 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 4 - Ruby 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);

Tags: javascript, project euler, rhino

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)

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

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)
		};
	}
}