Project Euler #014

/**
 * Copyright hycro ( http://wonderfl.net/user/hycro )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/1weA
 */

package {
	import flash.display.Sprite;
	import flash.text.TextField;
	
	public class ProjectEuler extends Sprite {
		private var _textField:TextField;
		
		public function ProjectEuler() {
			initialize();
			writeAnswer(new Problem014);
		}
		
		private function writeAnswer(problem:AbstructProblem):void {
			var answer:String = problem.getAnswer();
			_textField.appendText(answer);
		}
		
		private function initialize():void {
			_textField = new TextField();
			_textField.width = stage.stageWidth;
			_textField.height = stage.stageHeight;
			addChild(_textField);
			_textField.wordWrap = true;
		}
	}
}
//import flash.utils.Dictionary;

class AbstructProblem {
	final public function getAnswer():String {
		var answer:String;
		try {
			answer = solve().toString();
		} catch (err:Error) {
			answer = err.getStackTrace();
		}
		return answer;
	}
	
	protected function solve():Number {
		throw new Error("unsolved");
	}
}

class Problem014 extends AbstructProblem {
	override protected function solve():Number {
		var answer:Number;
		
		var length:uint = 0;
		var max:uint = 0;
		for (var n:Number=2; n <= 1000000; n++) {
			length = calcCollatzSequence(n);
			if (max < length) {
				max = length;
				answer = n;
			}
		}
		
		return answer;
				
		
		/*
		var map:Dictionary = new Dictionary();
		var start:uint = 2;
		map[1] = 0;
		
		var maxLength:uint = 0;
		while (start = getNextStart(start, map)) {
			var length:uint =  calcCollatzSequence(start, map);
			if (maxLength < length) {
				maxLength = length
				answer = start;
			}
		}

		
		return answer;
		*/
	}
	
	private function calcCollatzSequence(n:Number):uint {
		var length:uint = 0;
		while (n != 1) {
			n = (n % 2) ? n * 3 + 1 : n / 2;
			length++;
		}
		return length;
	}
	
	/*
	private function calcCollatzSequence_orz(start:uint, map:Dictionary):uint {
		if (start == 1) {
			return 0;
		}
		var n:uint = start;
		var route:Vector.<uint> = new Vector.<uint>();
		while (n != 1) {
			if (map[collatz(n)]) {
				map[n] = map[collatz(n)] + 1;
				return map[n];
			}
			
			route.push(n);
			n = collatz(n);
		}
		
		var length:uint = 0;
		while (route.length) {
			length++;
			map[route.pop()] = length;
		}
		
		return length;
	}
	
	private function getNextStart(prevStart:uint, map:Dictionary):uint {
		for (var i:uint = prevStart+1; i <= max; i++) {
			if (map[i] == undefined) {
				return i;
			}
		}
		return 0;
	}
	
	private function collatz(n:uint):uint {
		if (n % 2 == 0) {
			return n / 2;
		} else {
			return 3 * n + 1;
		}
	}
	*/
}

class Utils {
	// 整数値の桁数の取得
	static public function digits(n:Number, radix:uint=10):Number {
		var d:Number = 0;
		
		n = Math.abs(n);
		while (n / radix != 0) {
			n = Math.floor(n / radix);
			d++;
		}
		
		return d;
	}
	
	// 指定した桁の値を取得
	static public function numberAt(n:Number, digit:Number, radix:Number=10):Number {
		var number:Number;
		
		while (--digit) {
			n = Math.floor(n / radix);
		}
		
		return n % radix
	}
	
	// 素因数分解
	static public function primeFactorization(n:Number):Vector.<Number> {
		var prime:Number = 2;
		var sequence:Vector.<Number> = new Vector.<Number>();
		
		while (n != 1) {
			while (n % prime != 0) {
				prime++;
			}
			sequence.push(prime);
			n /= prime;
		}
		return sequence;
	}
	
	// 素数を列挙
	static public function getPrimeList(limit:uint):Vector.<uint> {
		var sequence:Vector.<uint> = new Vector.<uint>(limit);
		
		for (var i:uint = 2; i < limit; i++) {
			sequence[i] = i;
		}
		
		for (i=2; i < limit; i++) {
			if (sequence[i]) {
				for (var j:uint = i+i; j < limit; j+=i) {
					sequence[j] = 0;
				}
			}
		}
		
		var primeList:Vector.<uint> = new Vector.<uint>();
		for (i=2; i < limit; i++) {
			if (sequence[i]) {
				primeList.push(i);
			}
		}
		
		return primeList;
	}
	
	
	// 約数の数を取得
	static public function countFactor(n:uint):uint {
		var primes:Vector.<Number> = Utils.primeFactorization(n);
		var counts:Vector.<uint> = new Vector.<uint>();
		
		var prev:Number = 0;
		for each(var prime:Number in primes) {
			if (prime == prev) {
				counts[counts.length-1]++;
			} else {
				counts[counts.length] = 1;
				prev = prime;
			}
		}
		
		var count:uint = 1;
		for each (var n:uint in counts) {
			count *= n + 1;
		}
		
		return count;
	}
}