/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/jPgr
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
// @see http://projecteuler.net/index.php?section=problems&id=107
public class Euler107 extends Sprite {
private var _tf : TextField;
public function Euler107() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
_tf.appendText(solve(DMAT).toString() + "\n");
var g : int = getTimer();
_tf.appendText((g - s).toString() + " ms\n");
}
public const test : Array = [
[0, 5, 2, 4, 99, 99],
[5, 0, 99, 2, 4, 99],
[2, 99, 0, 3, 99, 6],
[4, 2, 3, 0, 3, 2],
[99, 4, 99, 3, 0, 99],
[99, 99, 6, 2, 99, 0]
];
private function solve(dmat : Array) : int
{
var primret : int = prim(dmat);
var origret : int = 0;
var n : int = dmat.length;
for(var i : int = 0;i < n;i++){
for(var j : int = 0;j < i;j++){
if(dmat[i][j] != "-"){
origret += dmat[i][j];
}
}
}
return origret - primret;
}
// O(n^2)
private function prim(dmat : Array) : int
{
// var clink : Object = {};
var sum : int = 0;
var i : int, j : int;
var n : int = dmat.length;
var cnodes : Array = new Array(n);
var froms : Array = new Array(n);
cnodes[0] = 0;
froms[0] = 0;
for(i = 1;i < n;i++){
cnodes[i] = int.MAX_VALUE;
}
var prev : int = 0;
for(var phase : int = 1;phase < n;phase++){
for(i = 0;i < n;i++){
if(cnodes[i] == 0)continue;
var v : int = dmat[prev][i] == "-" ? int.MAX_VALUE : dmat[prev][i];
if(v < cnodes[i]){
cnodes[i] = v;
froms[i] = prev;
}
}
var mind : int = int.MAX_VALUE;
var minfrom : int = -1;
var minto : int = -1;
for(i = 0;i < n;i++){
if(cnodes[i] > 0 && cnodes[i] < mind){
mind = cnodes[i];
minto = i;
minfrom = froms[i];
}
}
cnodes[minto] = 0;
sum += mind;
prev = minto;
}
return sum;
}
// O(n^3)
/*
private function prim(dmat : Array) : int
{
// var clink : Object = {};
var cnodes : Array = [];
var sum : int = 0;
var i : int, j : int;
var n : int = dmat.length;
for(i = 0;i < n;i++)cnodes.push(0);
cnodes[0] = 1;
for(var phase : int = 1;phase < n;phase++){
var mini : int = -1;
var minj : int = -1;
var mind : int = int.MAX_VALUE;
for(i = 0;i < n;i++){
if(cnodes[i] == 1){
for(j = 0;j < n;j++){
if(cnodes[j] == 0){
if(dmat[i][j] != "-" && dmat[i][j] < mind){
mind = dmat[i][j];
mini = i;
minj = j;
}
}
}
}
}
cnodes[minj] = 1;
sum += mind;
}
return sum;
}
*/
private const DMAT : Array = [
["-","-","-",427,668,495,377,678,"-",177,"-","-",870,"-",869,624,300,609,131,"-",251,"-","-","-",856,221,514,"-",591,762,182,56,"-",884,412,273,636,"-","-",774],
["-","-",262,"-","-",508,472,799,"-",956,578,363,940,143,"-",162,122,910,"-",729,802,941,922,573,531,539,667,607,"-",920,"-","-",315,649,937,"-",185,102,636,289],
["-",262,"-","-",926,"-",958,158,647,47,621,264,81,"-",402,813,649,386,252,391,264,637,349,"-","-","-",108,"-",727,225,578,699,"-",898,294,"-",575,168,432,833],
[427,"-","-","-",366,"-","-",635,"-",32,962,468,893,854,718,427,448,916,258,"-",760,909,529,311,404,"-","-",588,680,875,"-",615,"-",409,758,221,"-","-",76,257],
[668,"-",926,366,"-","-","-",250,268,"-",503,944,"-",677,"-",727,793,457,981,191,"-","-","-",351,969,925,987,328,282,589,"-",873,477,"-","-",19,450,"-","-","-"],
[495,508,"-","-","-","-","-",765,711,819,305,302,926,"-","-",582,"-",861,"-",683,293,"-","-",66,"-",27,"-","-",290,"-",786,"-",554,817,33,"-",54,506,386,381],
[377,472,958,"-","-","-","-","-","-",120,42,"-",134,219,457,639,538,374,"-","-","-",966,"-","-","-","-","-",449,120,797,358,232,550,"-",305,997,662,744,686,239],
[678,799,158,635,250,765,"-","-","-",35,"-",106,385,652,160,"-",890,812,605,953,"-","-","-",79,"-",712,613,312,452,"-",978,900,"-",901,"-","-",225,533,770,722],
["-","-",647,"-",268,711,"-","-","-",283,"-",172,"-",663,236,36,403,286,986,"-","-",810,761,574,53,793,"-","-",777,330,936,883,286,"-",174,"-","-","-",828,711],
[177,956,47,32,"-",819,120,35,283,"-",50,"-",565,36,767,684,344,489,565,"-","-",103,810,463,733,665,494,644,863,25,385,"-",342,470,"-","-","-",730,582,468],
["-",578,621,962,503,305,42,"-","-",50,"-",155,519,"-","-",256,990,801,154,53,474,650,402,"-","-","-",966,"-","-",406,989,772,932,7,"-",823,391,"-","-",933],
["-",363,264,468,944,302,"-",106,172,"-",155,"-","-","-",380,438,"-",41,266,"-","-",104,867,609,"-",270,861,"-","-",165,"-",675,250,686,995,366,191,"-",433,"-"],
[870,940,81,893,"-",926,134,385,"-",565,519,"-","-",313,851,"-","-","-",248,220,"-",826,359,829,"-",234,198,145,409,68,359,"-",814,218,186,"-","-",929,203,"-"],
["-",143,"-",854,677,"-",219,652,663,36,"-","-",313,"-",132,"-",433,598,"-","-",168,870,"-","-","-",128,437,"-",383,364,966,227,"-","-",807,993,"-","-",526,17],
[869,"-",402,718,"-","-",457,160,236,767,"-",380,851,132,"-","-",596,903,613,730,"-",261,"-",142,379,885,89,"-",848,258,112,"-",900,"-","-",818,639,268,600,"-"],
[624,162,813,427,727,582,639,"-",36,684,256,438,"-","-","-","-",539,379,664,561,542,"-",999,585,"-","-",321,398,"-","-",950,68,193,"-",697,"-",390,588,848,"-"],
[300,122,649,448,793,"-",538,890,403,344,990,"-","-",433,596,539,"-","-",73,"-",318,"-","-",500,"-",968,"-",291,"-","-",765,196,504,757,"-",542,"-",395,227,148],
[609,910,386,916,457,861,374,812,286,489,801,41,"-",598,903,379,"-","-","-",946,136,399,"-",941,707,156,757,258,251,"-",807,"-","-","-",461,501,"-","-",616,"-"],
[131,"-",252,258,981,"-","-",605,986,565,154,266,248,"-",613,664,73,"-","-",686,"-","-",575,627,817,282,"-",698,398,222,"-",649,"-","-","-","-","-",654,"-","-"],
["-",729,391,"-",191,683,"-",953,"-","-",53,"-",220,"-",730,561,"-",946,686,"-","-",389,729,553,304,703,455,857,260,"-",991,182,351,477,867,"-","-",889,217,853],
[251,802,264,760,"-",293,"-","-","-","-",474,"-","-",168,"-",542,318,136,"-","-","-","-",392,"-","-","-",267,407,27,651,80,927,"-",974,977,"-","-",457,117,"-"],
["-",941,637,909,"-","-",966,"-",810,103,650,104,826,870,261,"-","-",399,"-",389,"-","-","-",202,"-","-","-","-",867,140,403,962,785,"-",511,"-",1,"-",707,"-"],
["-",922,349,529,"-","-","-","-",761,810,402,867,359,"-","-",999,"-","-",575,729,392,"-","-",388,939,"-",959,"-",83,463,361,"-","-",512,931,"-",224,690,369,"-"],
["-",573,"-",311,351,66,"-",79,574,463,"-",609,829,"-",142,585,500,941,627,553,"-",202,388,"-",164,829,"-",620,523,639,936,"-","-",490,"-",695,"-",505,109,"-"],
[856,531,"-",404,969,"-","-","-",53,733,"-","-","-","-",379,"-","-",707,817,304,"-","-",939,164,"-","-",616,716,728,"-",889,349,"-",963,150,447,"-",292,586,264],
[221,539,"-","-",925,27,"-",712,793,665,"-",270,234,128,885,"-",968,156,282,703,"-","-","-",829,"-","-","-",822,"-","-","-",736,576,"-",697,946,443,"-",205,194],
[514,667,108,"-",987,"-","-",613,"-",494,966,861,198,437,89,321,"-",757,"-",455,267,"-",959,"-",616,"-","-","-",349,156,339,"-",102,790,359,"-",439,938,809,260],
["-",607,"-",588,328,"-",449,312,"-",644,"-","-",145,"-","-",398,291,258,698,857,407,"-","-",620,716,822,"-","-",293,486,943,"-",779,"-",6,880,116,775,"-",947],
[591,"-",727,680,282,290,120,452,777,863,"-","-",409,383,848,"-","-",251,398,260,27,867,83,523,728,"-",349,293,"-",212,684,505,341,384,9,992,507,48,"-","-"],
[762,920,225,875,589,"-",797,"-",330,25,406,165,68,364,258,"-","-","-",222,"-",651,140,463,639,"-","-",156,486,212,"-","-",349,723,"-","-",186,"-",36,240,752],
[182,"-",578,"-","-",786,358,978,936,385,989,"-",359,966,112,950,765,807,"-",991,80,403,361,936,889,"-",339,943,684,"-","-",965,302,676,725,"-",327,134,"-",147],
[56,"-",699,615,873,"-",232,900,883,"-",772,675,"-",227,"-",68,196,"-",649,182,927,962,"-","-",349,736,"-","-",505,349,965,"-",474,178,833,"-","-",555,853,"-"],
["-",315,"-","-",477,554,550,"-",286,342,932,250,814,"-",900,193,504,"-","-",351,"-",785,"-","-","-",576,102,779,341,723,302,474,"-",689,"-","-","-",451,"-","-"],
[884,649,898,409,"-",817,"-",901,"-",470,7,686,218,"-","-","-",757,"-","-",477,974,"-",512,490,963,"-",790,"-",384,"-",676,178,689,"-",245,596,445,"-","-",343],
[412,937,294,758,"-",33,305,"-",174,"-","-",995,186,807,"-",697,"-",461,"-",867,977,511,931,"-",150,697,359,6,9,"-",725,833,"-",245,"-",949,"-",270,"-",112],
[273,"-","-",221,19,"-",997,"-","-","-",823,366,"-",993,818,"-",542,501,"-","-","-","-","-",695,447,946,"-",880,992,186,"-","-","-",596,949,"-",91,"-",768,273],
[636,185,575,"-",450,54,662,225,"-","-",391,191,"-","-",639,390,"-","-","-","-","-",1,224,"-","-",443,439,116,507,"-",327,"-","-",445,"-",91,"-",248,"-",344],
["-",102,168,"-","-",506,744,533,"-",730,"-","-",929,"-",268,588,395,"-",654,889,457,"-",690,505,292,"-",938,775,48,36,134,555,451,"-",270,"-",248,"-",371,680],
["-",636,432,76,"-",386,686,770,828,582,"-",433,203,526,600,848,227,616,"-",217,117,707,369,109,586,205,809,"-","-",240,"-",853,"-","-","-",768,"-",371,"-",540],
[774,289,833,257,"-",381,239,722,711,468,933,"-","-",17,"-","-",148,"-","-",853,"-","-","-","-",264,194,260,947,"-",752,147,"-","-",343,112,273,344,680,540,"-"]
];
}
}
