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!

Flex Game of Life Pt 2

I made a few user interface updates to my crappy Flex version of Conway’s Game of Life.

The board now wraps, and I added a Timer with an adjustable delay via the lovely HSlider control. I wanted to replace the cells with Sprites but it’s giving me grief and I want to play The Sims.

I’m still making my mind up about Flex, but I have to admit that aside from the Sprite issue I’ve been pleasantly surprised at how easy everything’s been coming together.

You can view source on the application, or you can download the zip.

How to issue a simple HTTPRequest in Java

I needed a way to issue an HTTPRequest in Java, and I don’t care about the return value. I wasn’t able to find a simple example so I thought I’d post my that part of my solution. I don’t know that it’s the best way, but it works.

import java.net.URL;

public class Request {
  public static void main(String[] args) throws Exception {
      if(args.length == 0) {
          System.out.println("URL required.");
          return;
      }
      URL url = new URL(args[0]);
      url.openStream().close();
  }
}

And to use it you just pass in the url via the command line

java Request http://joezack.com

Flex Game of Life

Continuing down the Flex Path, I built another really crappy version of Conway’s Game of Life. Version 2 forthcoming.

I’m still figuring out this whole Flex thing, so please, any help would be much appreciated!

<?xml version="1.0" encoding="utf-8"?>
<mx:Application
	xmlns:mx         = "http://www.adobe.com/2006/mxml"
	layout           = "vertical"
	creationComplete = "init(gameArea);"
	width            = "425"
	height           = "425"
>
	<mx:Script><![CDATA[
		import model.*;
		private var board:Board;

		private function init(application:DisplayObjectContainer):void {
			board = new Board(application, 10, 0, 0, 30, 30, 5);
		}
	]]></mx:Script>

	<mx:Canvas id="gameArea"></mx:Canvas>
	<mx:HBox>
		<mx:Button label="Reset"  click="board.reset();" />
		<mx:Button label="Update" click="board.update();" />		
	</mx:HBox>
</mx:Application>
package model {

	import flash.display.DisplayObjectContainer;

	public class Board {

		private var size:int;
		private var startX:int;
		private var startY:int;
		private var tileWidth:int;
		private var tileHeight:int;
		private var tileBuffer:int;	
		private var board:Array;
		private var container:DisplayObjectContainer;

		public function Board(
			container:DisplayObjectContainer,
			size:int,
			startX:int,
			startY:int,
			tileWidth:int,
			tileHeight:int,
			tileBuffer:int
		) {
			this.container  = container;
			this.size       = size;
			this.startX     = startX;
			this.startY     = startY;
			this.tileWidth  = tileWidth;
			this.tileHeight = tileHeight;
			this.tileBuffer = tileBuffer;
			reset();
		}

		public function reset():void {
			this.board = new Array(this.size);
			var x:int = startX;
			var y:int = startY;

			clear();

			for(var i:int = 0; i < this.size; i++) {
				this.board[i] = new Array(this.size);
				x = startX;
				for(var j:int = 0; j < this.size; j++) {
					board[i][j] = new Cell(x, y, tileWidth, tileHeight);
					x += this.tileWidth + this.tileBuffer;
					this.container.addChild(board[i][j]);
				}
				y += this.tileHeight + this.tileBuffer;
			}
		}

		public function update():void {
			var next:Array = next();
			for(var i:int = 0; i < this.size; i++) {
				for(var j:int = 0; j < this.size; j++) {
					board[i][j].update(next[i][j]);
				}
			}
		}

		public function clear():void {
			while(this.container.numChildren) {
				this.container.removeChildAt(0);
			}
		}

		public function next():Array {
			var total:int     = 0;
			var next:Array = new Array(this.size);
			for(var i:int = 0; i < this.size; i++) {
				next[i] = new Array(this.size);
				for(var j:int = 0; j < this.size; j++) {
					next[i][j] = board[i][j].next(countNeighbors(i,j));
				}
			}
			return next;
		}

		public function isValid(position:int):Boolean {
			return(position >= 0 && position < this.size);
		}

		public function stateAt(i:int, j:int):Boolean {
			if(isValid(i) && isValid(j)) {
				return board[i][j].state;
			}
			return false;
		}

		public function countNeighbors(x:int, y:int):int {
			var count:int = 0;
			
			for(var i:int = x - 1; i <= x + 1; i++) {
				for(var j:int = y - 1; j <= y + 1; j++) {
					if(!(i == x && j == y) && stateAt(i,j)) {
						count += 1;
					}
				}
			}
			return count;
		}

	}
}
package model {
	import flash.events.MouseEvent;
	
	import mx.controls.Button;

	public class Cell extends Button {

		public var state:Boolean;

		public function Cell(x:int, y:int, width:int, height:int) {
			this.x     = x;
			this.y     = y;
			this.width = width;
			this.height = height;
			this.addEventListener(MouseEvent.CLICK,swap);
			this.reset();
		}

		public function reset():void {
			this.state = false;
		}

		public function next(neighborCount:int):Boolean {
			return((this.state && neighborCount == 2) || neighborCount == 3);
		}

		public function update(state:Boolean):void {
			this.state = state;
			if(this.state) {
				this.label = "0";
			} else {
				this.label = "";
			}
		}

		public function swap(e:MouseEvent):void {
			update(!this.state);
		}

	}
}