/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/6CBb
*/
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(1, 2));
var g : int = getTimer();
tr((g - s) + " ms");
}
private var _used : Array;
private var m : uint;
private var n : uint;
private var _cross : Array;
private function solve(m : uint, n : uint) : Number
{
this.m = m; this.n = n;
_used = new Array(m * n * 4);
_cross = new Array((m+1)*(n+1));
for(var i : uint = 0;i < _cross.length;i++){
_cross[i] = 0;
}
return rec(0, 0, 0, 0);
}
private const LEFT : Array = [
4<<15|6<<9|0<<6|2<<0,
0<<15|2<<9|4<<6|6<<0
];
private const RIGHT : Array = [
1<<21|3<<18|5<<12|7<<3,
5<<21|7<<18|1<<12|3<<3
];
private const TOP : Array = [
0<<18|1<<9|3<<3|6<<0,
3<<18|6<<9|0<<3|1<<0
];
private const BOTTOM : Array = [
5<<21|7<<15|2<<12|4<<6,
2<<21|4<<15|5<<12|7<<6
];
private var INVRULE : Object = {};
private const CROSS : Array = [
6<<21|7<<18|4<<15|5<<12|2<<9|3<<6|0<<3|1<<0,
6<<21|7<<18|5<<15|3<<12|4<<9|5<<6|0<<3|1<<0,
2<<21|3<<18|4<<15|5<<12|6<<9|7<<6|0<<3|1<<0,
2<<21|5<<18|6<<15|3<<12|4<<9|7<<6|0<<3|1<<0,
6<<21|7<<18|4<<15|5<<12|0<<9|1<<6|2<<3|3<<0,
4<<21|5<<18|6<<15|7<<12|0<<9|1<<6|2<<3|3<<0,
6<<21|7<<18|0<<15|3<<12|4<<9|1<<6|2<<3|5<<0,
6<<21|7<<18|0<<15|1<<12|2<<9|3<<6|4<<3|5<<0,
0<<21|5<<18|6<<15|3<<12|4<<9|1<<6|2<<3|7<<0,
0<<21|5<<18|6<<15|1<<12|2<<9|3<<6|4<<3|7<<0,
0<<21|1<<18|4<<15|5<<12|2<<9|3<<6|6<<3|7<<0,
0<<21|1<<18|2<<15|3<<12|4<<9|5<<6|6<<3|7<<0
];
// (x,y)
// arc:下から反時計周り
private function rec(x : uint, y : uint, arc : uint, dir : uint) : Number
{
if(x == 0 && y == 0 && arc == 3 && dir == 0)return 1;
var code : uint = (x*n+y)*m+arc;
if(_used[code] == 1)return 0;
_used[code] = 1;
var ret : Number = 0;
// 1
if(x == 0 && y == n - 1 && arc == 2 && dir == 0){ret = rec(x, y, 3, 0); _used[code] = 0; return ret;}
if(x == 0 && y == n - 1 && arc == 3 && dir == 1){ret = rec(x, y, 2, 1); _used[code] = 0; return ret;}
if(x == m - 1 && y == 0 && arc == 0 && dir == 0){ret = rec(x, y, 1, 0); _used[code] = 0; return ret;}
if(x == m - 1 && y == 0 && arc == 1 && dir == 1){ret = rec(x, y, 0, 1); _used[code] = 0; return ret;}
if(x == m - 1 && y == n - 1 && arc == 1 && dir == 0){ret = rec(x, y, 2, 0); _used[code] = 0; return ret;}
if(x == m - 1 && y == n - 1 && arc == 2 && dir == 1){ret = rec(x, y, 1, 1); _used[code] = 0; return ret;}
var indir : uint = [7, 1, 3, 5, 2, 4, 6, 0][dir*4+arc];
var tx : uint = x + [1, 1, 0, 0, 0, 1, 1, 0][dir*4+arc];
var ty : uint = y + [0, 1, 1, 0, 0, 0, 1, 1][dir*4+arc];
var tc : uint = tx*(n+1)+ty;
tr(x, y, arc, dir, tx, ty);
// 2
var p : uint;
var o : uint;
var ndir : uint, nx : uint, ny : uint, narc : uint;
var set : Array = CROSS;
if(tx == 0)set = LEFT;
if(ty == 0)set = BOTTOM;
if(tx == m)set = RIGHT;
if(ty == n)set = TOP;
for each(p in set){
if((_cross[tc] | p) == p){
narc = (p >> (3*indir)) & 7;
o = _cross[tc];
_cross[tc] |= narc << (3*indir) | indir << (3*narc);
ndir = dir ^ ((indir - narc) % 2 == 0 ? 1 : 0);
nx = tx - [1, 1, 0, 0, 0, 1, 1, 0][ndir*4+narc];
ny = ty - [0, 1, 1, 0, 0, 0, 1, 1][ndir*4+narc];
ret += rec(nx, ny, narc, ndir);
_cross[tc] = o;
}
}
_used[code] = 0;
return ret;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
