Trees Made to Order

Trees Made to Order.js

// 2017/2/25 20:40:17
// http://poj.org/problem?id=1095
// node Trees Made to Order.js
// https://gist.github.com/kanasimi/4f8911cabb8721123a472f60408bd30d

'use strict';

var MAX_NO = 5e8,
// count: Catalan numbers
count = [1],
start_NO = [0];

// initialization
for (var nodes = 0;; nodes++) {
	start_NO[nodes + 1] = start_NO[nodes] + count[nodes];
	if (start_NO[nodes + 1] >= MAX_NO) break;

	// 計算下一個節點數 的 tree數量。
/*
	// 較慢的方法，見下方解釋。
	var c = 0;
	for (var n = 0; n <= nodes; n++) {
		c += count[n] * count[nodes - n];
	}
	count[nodes + 1] = c;
*/
	// @see https://en.wikipedia.org/wiki/Catalan_number
	count[nodes + 1] = 2 * (2 * nodes + 1) / (nodes + 2) * count[nodes];
}

// count: Catalan numbers
// count: 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700
// start_NO: 0,1,2,4,9,23,65,197,626,2056,6918,23714,82500,290512,1033412,3707852,13402697,48760367,178405157,656043857

// count[3] =  5, start_NO[3] = 4: 3個節點的tree共 5個，自 NO 4 開始至 NO (4+ 5-1= 8)
// count[4] = 14, start_NO[4] = 9: 4個節點的tree共14個，自 NO 9 開始至 NO (9+14-1=22)

// count[3] = count[0]*count[2] + count[1]*count[1] + count[2]*count[0]
// count[4] = count[0]*count[3] + count[1]*count[2] + count[2]*count[1] + count[3]*count[0]
// 參見下方 增進理解用 output


function draw(NO, close) {
	if (!(NO >= 1)) {
		return '';
	}
	// all node count
	var nodes = 1;
	// 判別本NO應有幾顆節點nodes
	while (!(start_NO[++nodes] > NO)) {}
	--nodes;

	// 可把下面process.stdout.write(),console.log()打開以增進理解。
	if (!close) {
		//process.stdout.write('NO ' + NO + ', ' + nodes + ' nodes' + ' + remainder ' + (NO - start_NO[nodes]) + '\t');
	}
	// 求取remainder
	// 提示:n顆節點與n+1顆節點間會按照此remainder的順序按規則排下去。
	NO -= start_NO[nodes];

	// 判斷 left node count
	var left = nodes - 1,
	tmp;
	// remainder = 左節點NO * 右節點 + 右節點NO
	// 看看本remainder為第幾批。 -1: the 1 is root node
	while (NO >= (tmp = count[nodes - 1 - left] * count[left])) {
		NO -= tmp;
		left--;
	}

	var right_NO = start_NO[nodes - 1 - left] + (NO / count[left] | 0),
	left_NO = start_NO[left] + (NO % count[left]);
	if (!close) {
		//console.log([nodes - 1 - left, left], [right_NO, left_NO]);
	}
	tmp = draw(right_NO, true) + 'X' + draw(left_NO, true);
	return close ? '(' + tmp + ')' : tmp;
}

console.assert(draw(1) === 'X');
console.assert(draw(20) === '((X)X(X))X');
console.assert(draw(31117532) === '(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)');
console.assert(draw(MAX_NO) === '(X(((X(X(X((X(X))X(((X((X)X))X((X)X))X)))))X)X))X(X)');


process.exit();

// 增進理解用
function nodes_of(result) {
	if (result >= 0) {
		result = draw(result, true);
	}
	return result.replace(/[^X]+/g, '').length;
}
for (var NO = 1; NO < 80; NO++) {
	var result = draw(NO);
	// 先看看下一個NO之nodes，若與本NO之nodes不同則加個分隔線。
	if (nodes_of(result) !== nodes_of(NO + 1)) {
		console.log('-'.repeat(60));
  }
}


/*
// 增進理解用 output: 請注意最後一個數(右tree之NO)，並對照各NO之數量。
// 例如 NO 9–13 之右tree NO 即為按照 NO 4–8 累增。

//				[right nodes, left nodes] [right_NO, left_NO]
NO 1, 1 nodes + remainder 0     [ 0, 0 ] [ 0, 0 ]
------------------------------------------------------------
NO 2, 2 nodes + remainder 0     [ 0, 1 ] [ 0, 1 ]

NO 3, 2 nodes + remainder 1     [ 1, 0 ] [ 1, 0 ]
------------------------------------------------------------
NO 4, 3 nodes + remainder 0     [ 0, 2 ] [ 0, 2 ]
NO 5, 3 nodes + remainder 1     [ 0, 2 ] [ 0, 3 ]

NO 6, 3 nodes + remainder 2     [ 1, 1 ] [ 1, 1 ]

NO 7, 3 nodes + remainder 3     [ 2, 0 ] [ 2, 0 ]
NO 8, 3 nodes + remainder 4     [ 2, 0 ] [ 3, 0 ]
------------------------------------------------------------
NO 9, 4 nodes + remainder 0     [ 0, 3 ] [ 0, 4 ]
NO 10, 4 nodes + remainder 1    [ 0, 3 ] [ 0, 5 ]
NO 11, 4 nodes + remainder 2    [ 0, 3 ] [ 0, 6 ]
NO 12, 4 nodes + remainder 3    [ 0, 3 ] [ 0, 7 ]
NO 13, 4 nodes + remainder 4    [ 0, 3 ] [ 0, 8 ]

NO 14, 4 nodes + remainder 5    [ 1, 2 ] [ 1, 2 ]
NO 15, 4 nodes + remainder 6    [ 1, 2 ] [ 1, 3 ]

NO 16, 4 nodes + remainder 7    [ 2, 1 ] [ 2, 1 ]
NO 17, 4 nodes + remainder 8    [ 2, 1 ] [ 3, 1 ]

NO 18, 4 nodes + remainder 9    [ 3, 0 ] [ 4, 0 ]
NO 19, 4 nodes + remainder 10   [ 3, 0 ] [ 5, 0 ]
NO 20, 4 nodes + remainder 11   [ 3, 0 ] [ 6, 0 ]
NO 21, 4 nodes + remainder 12   [ 3, 0 ] [ 7, 0 ]
NO 22, 4 nodes + remainder 13   [ 3, 0 ] [ 8, 0 ]
------------------------------------------------------------
NO 23, 5 nodes + remainder 0    [ 0, 4 ] [ 0, 9 ]
NO 24, 5 nodes + remainder 1    [ 0, 4 ] [ 0, 10 ]
NO 25, 5 nodes + remainder 2    [ 0, 4 ] [ 0, 11 ]
NO 26, 5 nodes + remainder 3    [ 0, 4 ] [ 0, 12 ]
NO 27, 5 nodes + remainder 4    [ 0, 4 ] [ 0, 13 ]
NO 28, 5 nodes + remainder 5    [ 0, 4 ] [ 0, 14 ]
NO 29, 5 nodes + remainder 6    [ 0, 4 ] [ 0, 15 ]
NO 30, 5 nodes + remainder 7    [ 0, 4 ] [ 0, 16 ]
NO 31, 5 nodes + remainder 8    [ 0, 4 ] [ 0, 17 ]
NO 32, 5 nodes + remainder 9    [ 0, 4 ] [ 0, 18 ]
NO 33, 5 nodes + remainder 10   [ 0, 4 ] [ 0, 19 ]
NO 34, 5 nodes + remainder 11   [ 0, 4 ] [ 0, 20 ]
NO 35, 5 nodes + remainder 12   [ 0, 4 ] [ 0, 21 ]
NO 36, 5 nodes + remainder 13   [ 0, 4 ] [ 0, 22 ]

NO 37, 5 nodes + remainder 14   [ 1, 3 ] [ 1, 4 ]
NO 38, 5 nodes + remainder 15   [ 1, 3 ] [ 1, 5 ]
NO 39, 5 nodes + remainder 16   [ 1, 3 ] [ 1, 6 ]
NO 40, 5 nodes + remainder 17   [ 1, 3 ] [ 1, 7 ]
NO 41, 5 nodes + remainder 18   [ 1, 3 ] [ 1, 8 ]

NO 42, 5 nodes + remainder 19   [ 2, 2 ] [ 2, 2 ]
NO 43, 5 nodes + remainder 20   [ 2, 2 ] [ 2, 3 ]

NO 44, 5 nodes + remainder 21   [ 2, 2 ] [ 3, 2 ]
NO 45, 5 nodes + remainder 22   [ 2, 2 ] [ 3, 3 ]

NO 46, 5 nodes + remainder 23   [ 3, 1 ] [ 4, 1 ]
NO 47, 5 nodes + remainder 24   [ 3, 1 ] [ 5, 1 ]
NO 48, 5 nodes + remainder 25   [ 3, 1 ] [ 6, 1 ]
NO 49, 5 nodes + remainder 26   [ 3, 1 ] [ 7, 1 ]
NO 50, 5 nodes + remainder 27   [ 3, 1 ] [ 8, 1 ]

NO 51, 5 nodes + remainder 28   [ 4, 0 ] [ 9, 0 ]
NO 52, 5 nodes + remainder 29   [ 4, 0 ] [ 10, 0 ]
NO 53, 5 nodes + remainder 30   [ 4, 0 ] [ 11, 0 ]
NO 54, 5 nodes + remainder 31   [ 4, 0 ] [ 12, 0 ]
NO 55, 5 nodes + remainder 32   [ 4, 0 ] [ 13, 0 ]
NO 56, 5 nodes + remainder 33   [ 4, 0 ] [ 14, 0 ]
NO 57, 5 nodes + remainder 34   [ 4, 0 ] [ 15, 0 ]
NO 58, 5 nodes + remainder 35   [ 4, 0 ] [ 16, 0 ]
NO 59, 5 nodes + remainder 36   [ 4, 0 ] [ 17, 0 ]
NO 60, 5 nodes + remainder 37   [ 4, 0 ] [ 18, 0 ]
NO 61, 5 nodes + remainder 38   [ 4, 0 ] [ 19, 0 ]
NO 62, 5 nodes + remainder 39   [ 4, 0 ] [ 20, 0 ]
NO 63, 5 nodes + remainder 40   [ 4, 0 ] [ 21, 0 ]
NO 64, 5 nodes + remainder 41   [ 4, 0 ] [ 22, 0 ]
------------------------------------------------------------
NO 65, 6 nodes + remainder 0    [ 0, 5 ] [ 0, 23 ]
NO 66, 6 nodes + remainder 1    [ 0, 5 ] [ 0, 24 ]
NO 67, 6 nodes + remainder 2    [ 0, 5 ] [ 0, 25 ]
NO 68, 6 nodes + remainder 3    [ 0, 5 ] [ 0, 26 ]
NO 69, 6 nodes + remainder 4    [ 0, 5 ] [ 0, 27 ]
NO 70, 6 nodes + remainder 5    [ 0, 5 ] [ 0, 28 ]
NO 71, 6 nodes + remainder 6    [ 0, 5 ] [ 0, 29 ]
NO 72, 6 nodes + remainder 7    [ 0, 5 ] [ 0, 30 ]
NO 73, 6 nodes + remainder 8    [ 0, 5 ] [ 0, 31 ]
NO 74, 6 nodes + remainder 9    [ 0, 5 ] [ 0, 32 ]
NO 75, 6 nodes + remainder 10   [ 0, 5 ] [ 0, 33 ]
NO 76, 6 nodes + remainder 11   [ 0, 5 ] [ 0, 34 ]
NO 77, 6 nodes + remainder 12   [ 0, 5 ] [ 0, 35 ]
NO 78, 6 nodes + remainder 13   [ 0, 5 ] [ 0, 36 ]
NO 79, 6 nodes + remainder 14   [ 0, 5 ] [ 0, 37 ]

*/