/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/7K9J
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
// @see http://projecteuler.net/index.php?section=problems&id=
public class Euler extends Sprite {
private var _tf : TextField;
public function Euler() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
tr(solve(14));
// tr(enumPartition(18).join('\n'));
var g : int = getTimer();
tr((g - s) + " ms");
}
private var _c : Array;
private function enumPartition(N : uint) : Array
{
_c = new Array(N+1);
for(var i : uint = 0;i < N+1;i++){
_c[i] = new Array(N+1);
}
return enumPartitionCore(N, N);
}
private function enumPartitionCore(N : uint, M : uint) : Array
{
if(N == 0)return [[]];
if(_c[N][M])return _c[N][M];
var ret : Array = [];
for(var i : uint = 1;i <= M;i++){
for each(var v : Array in enumPartitionCore(N - i, Math.min(N - i, i))){
var val : Array = v.concat();
val.push(i);
ret.push(val);
}
}
_c[N][M] = ret;
return ret;
}
private function solve(N : uint) : Number
{
// var ss : Array = [null, [1, 1]];
var ps : Array = [null, [1, 1]];
enumPartition(N);
var i : uint, j : uint, k : uint;
var set : Object, seed : Array, nseed : Array;
var p : uint, q : uint, r : uint, s : uint;
var np : uint, nq : uint, g : uint, h : Number;
var vp : Array, evp : uint, se : Array;
var plus : Array;
for(i = 2;i <= N;i++){
enumPartitionCore(i, i-1);
}
var ct : uint = 0;
for(i = 2;i <= N;i++){
plus = [];
set = {};
for each(vp in _c[i][i-1]){ // partition
seed = null;
for each(evp in vp){ // part
if(seed == null){
seed = [];
for(j = 0;j < ps[evp].length;j+=2){
seed.push(ps[evp][j+1], ps[evp][j]);
}
continue;
}
if(evp == 1){
for(j = 0;j < seed.length;j+=2){
seed[j] += seed[j+1];
}
continue;
}
se = ps[evp];
nseed = [];
// TODO 途中の計算結果をメモ化
for(j = 0;j < se.length;j+=2){ // serial
q = se[j];
p = se[j+1];
for(k = 0;k < seed.length;k+=2){ // seed
r = seed[k];
s = seed[k+1];
np = p*s+q*r; nq = q*s;
g = GCD(np, nq); np /= g; nq /= g;
nseed.push(np, nq);
ct++;
}
}
seed = nseed;
}
for(k = 0;k < seed.length;k+=2){ // seed
h = seed[k] * 1000000 + seed[k+1];
if(!set[h]){
plus.push(seed[k], seed[k+1]);
set[h] = 1;
}
}
}
ps.push(plus);
}
tr("ct", ct);
for(i = 1;i <= 10;i++){
tr(i, ps[i].length);
}
return ps[N].length - 1;
}
/*
private function solve(N : uint) : Number
{
var ss : Array = [null, [1, 1]];
var ps : Array = [null, [1, 1]];
enumPartition(N);
var i : uint, j : uint, k : uint;
var set : Object, seed : Array, nseed : Array;
var p : uint, q : uint, r : uint, s : uint;
var np : uint, nq : uint, g : uint, h : Number;
var vp : Array, evp : uint, se : Array;
var plus : Array;
for(i = 2;i <= N;i++){
enumPartitionCore(i, i-1);
}
var ct : uint = 0;
for(i = 2;i <= N;i++){
plus = [];
set = {};
for each(vp in _c[i][i-1]){ // partition
seed = null;
for each(evp in vp){ // part
if(seed == null){
seed = ss[evp].concat();
continue;
}
if(evp == 1){
for(j = 0;j < seed.length;j+=2){
seed[j] += seed[j+1];
}
continue;
}
se = ss[evp];
nseed = [];
for(j = 0;j < se.length;j+=2){ // serial
p = se[j];
q = se[j+1];
for(k = 0;k < seed.length;k+=2){ // seed
r = seed[k];
s = seed[k+1];
np = p*s+q*r; nq = q*s;
g = GCD(np, nq); np /= g; nq /= g;
nseed.push(np, nq);
ct++;
}
}
seed = nseed;
}
for(k = 0;k < seed.length;k+=2){ // seed
h = seed[k] * 1000000 + seed[k+1];
if(!set[h]){
plus.push(seed[k], seed[k+1]);
set[h] = 1;
}
}
}
ps.push(plus);
plus = [];
set = {};
for each(vp in _c[i][i-1]){ // partition
seed = null;
for each(evp in vp){ // part
if(seed == null){
seed = ps[evp].concat();
continue;
}
if(evp == 1){
for(j = 0;j < seed.length;j+=2){
seed[j+1] += seed[j];
}
continue;
}
se = ps[evp];
nseed = [];
for(j = 0;j < se.length;j+=2){ // serial
p = se[j];
q = se[j+1];
for(k = 0;k < seed.length;k+=2){ // seed
r = seed[k];
s = seed[k+1];
np = p*r; nq = p*s+q*r;
g = GCD(np, nq); np /= g; nq /= g;
nseed.push(np, nq);
ct++;
}
}
seed = nseed;
}
for(k = 0;k < seed.length;k+=2){ // seed
h = seed[k] * 1000000 + seed[k+1];
if(!set[h]){
plus.push(seed[k], seed[k+1]);
set[h] = 1;
}
}
}
ss.push(plus);
}
tr(ss[2]);
tr(ps[2]);
tr("ct", ct);
tr(ss[N].length/2, ps[N].length/2);
return (ss[N].length + ps[N].length) / 2;
}
*/
/*
private function solve(N : uint) : Number
{
var a : Array = [null, [1, 1]];
for(var i : uint = 2;i <= N;i++){
var ct : uint = 0;
var set : Object = {};
var e : Array = [];
for(var j : uint = 1;j <= i / 2;j++){
var aj : Array = a[j];
var aij : Array = a[i-j];
for(var k : uint = 0;k < aj.length;k+=2){
var p : uint = aj[k];
var q : uint = aj[k+1];
for(var l : uint = 0;l < aij.length;l+=2){
var r : uint = aij[l];
var s : uint = aij[l+1];
var np : uint;
var nq : uint;
var g : uint;
var h : Number;
np = p*s+q*r; nq = q*s;
g = GCD(np, nq); np /= g; nq /= g;
h = np * 1000000 + nq;
if(!set[h]){
e.push(np, nq);
set[h] = 1;
}else{
ct++;
}
np = p*r; nq = p*s+q*r;
g = GCD(np, nq); np /= g; nq /= g;
h = np * 1000000 + nq;
if(!set[h]){
e.push(np, nq);
set[h] = 1;
}else{
ct++;
}
}
}
}
tr(e.length / 2, ct);
a.push(e);
}
// tr(a[N].join('\n'));
return a[N].length / 2;
}
*/
private static function GCD(a : uint, b : uint) : uint
{
while(b > 0){
var c : uint = a;
a = b;
b = c % b;
}
return a;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
