/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/prbU
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
// @see http://projecteuler.net/index.php?section=problems&id=275
public class Euler275 extends Sprite {
private var _tf : TextField;
public function Euler275() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
_cache = new Array((1 << 16) * 13);
// tr(recBuild((1 << 1) - 1, 8).length);
// tr(solve(6));
// _b = makeArray(0, 8, 16);
_dic = makeArray([], 13);
_b = [];
// _b[0][0] = 1;
_b.push(0, 0);
_b.push(0, 2);
recBuild();
for(var i : uint = 0;i < 13;i++){
tr(i, _dic[i].length);
}
// TODO 連結性判定
var g : int = getTimer();
tr((g - s) + " ms");
tr(_ct);
}
public function makeArray(val : *, ...rest) : Array
{
if(rest.length == 0)return null;
if(rest.length == 1){
return fill(val, new Array(rest[0]));
}else{
var s : uint = rest.shift();
var args : Array = [val].concat(rest);
var ret : Array = new Array(s);
for(var i : uint = 0;i < s;i++)ret[i] = makeArray.apply(null, args);
return ret;
}
}
// シャローコピーのfill
public function fill(v : *, a : Array) : Array
{
for(var i : uint = 0;i < a.length;i++){
if(v is Array){
a[i] = v.concat();
}else{
a[i] = v;
}
}
return a;
}
private var _b : Array;
private var _dic : Array;
private var _ct : int = 0;
private function recBuild() : void
{
_ct++;
if(_b.length == 24)return;
var i : uint, j : uint, k : uint;
var code : Array = [0, 0, 0, 0, 0, 0, 0, 0];
for(i = 0;i < _b.length;i+=2){
code[_b[i]] |= 1 << _b[i+1];
}
var n : uint = _b.length / 2;
var bs : int = binarySearch(code, _dic[n], compArray);
if(bs >= 0)return;
_dic[n].splice(-bs-1, 0, code);
for(i = 0;i < _b.length;i+=2){
for each(var d : Array in DIR){
var x : int = _b[i] + d[0];
var y : int = _b[i+1] + d[1];
if(x <= 0 || y < 0 || y >= 16 || x >= 8)continue;
for(j = 0;j < _b.length && !(_b[j] == x && _b[j+1] == y);j+=2);
if(j == _b.length){
_b.push(x, y);
recBuild();
_b.pop(); _b.pop();
}
}
}
}
private function compArray(a : Array, b : Array) : int
{
for(var i : uint = 0;i < a.length;i++){
if(a[i] != b[i]){
return a[i] - b[i];
}
}
return 0;
}
private function binarySearch(c : Array, a : Array, comp : Function) : int
{
if(a.length == 0)return -1;
var s : uint = 0;
var e : uint = a.length;
var m : uint = (s + e) >>> 1;
for(;m - s >= 1;m = (s + e) >>> 1){
var cr : int = comp(c, a[m]);
if(cr == 0)return m;
if(cr < 0){
e = m;
}else{
s = m;
}
}
cr = comp(c, a[s]);
if(cr == 0)return s;
if(cr > 0)return -2 - s;
return -1 - s;
}
private const DIR : Array = [[1, 0], [0, 1], [-1, 0], [0, -1]];
private var _cache : Array;
private function solve(N : uint) : Number
{
// _cache = new Array((1 << lim) * n);
var ret : Number = 0;
for(var i : uint = 1;i < 1 << N;i++){
var c : uint = countBit(i);
// var h : uint = highestBit(i);
var rss : Array = [];
for(var j : uint = 0;j <= N - c;j++){
rss.push(recSide(i, j, 1, 16));
}
for(j = 0;j <= (N - c) / 2;j++){
for(var k : uint = 0;k < 37;k++){
if(rss[j][k] != null && rss[N-c-j][k] != null){
ret += rss[j][k] * rss[N - c - j][k];
}
}
}
// TODO それぞれの連結性チェック
// TODO 中央との連結性チェック
}
return ret;
}
private function highestBit(n : uint) : uint
{
for(var i : uint = n, j : uint = 0;i > 0;i >>= 1, j++);
return j;
}
private function side(n : uint, lim : uint) : Array
{
return recSide((1 << lim) - 1, n, 1, lim);
}
// ret[weight] = count
private function recSide(prev : uint, left : uint, weight : uint, lim : uint) : Array
{
if(left == 0)return [1];
var sup : uint = 1 << lim;
/*
if(_cache[left * sup + prev]){
return _cache[left * sup + prev];
}
*/
var ret : Array = new Array(37);
var i : uint;
for(i = 0;i < 37;i++)ret[i] = 0;
for(i = 0;i < sup;i++){
var c : uint = countBit(i);
if(c > left)continue;
if((prev & i) == 0)continue;
var rs : Array = recSide(i, left - c, weight + 1, lim);
for(var j : uint = 0;j < rs.length;j++){
ret[j + c * weight] += rs[j];
}
}
// _cache[left * sup + prev] = ret;
return ret;
}
/*
private function recBuild(prev : uint, left : uint) : Array
{
if(left == 0)return [[]];
if(_cache[prev * 12 + left]){
return _cache[prev * 12 + left];
}
var h : uint = highestBit(prev) + left - 1;
h = 1 << h;
var ret : Array = [];
for(var i : uint = 0;i < h;i++){
var c : uint = countBit(i);
if(c > left)continue;
if((prev & i) == 0)continue;
if(left > c){
var rb : Array = recBuild(i, left - c);
for each(var r : Array in rb){
ret.push([i].concat(r));
}
}else{
ret.push([i]);
}
}
_cache[prev * 12 + left] = ret;
return ret;
}
*/
private function countBit(n : uint) : uint
{
n = (n & 0x55555555) + (n >> 1 & 0x55555555);
n = (n & 0x33333333) + (n >> 2 & 0x33333333);
n = (n & 0x0f0f0f0f) + (n >> 4 & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + (n >> 8 & 0x00ff00ff);
n = (n & 0x0000ffff) + (n >> 16 & 0x0000ffff);
return n;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
