Hi.Welcome back everyone
My script is:
`class Node {
constructor(row, col) {
this.row = row;
this.col = col;
this.up = null;
this.down = null;
this.left = null;
this.right = null;
this.header = null;
}
}
class Matrix {
constructor(rows, columns) {
this.rows = rows;
this.columns = columns;
this.matrix = [];
for (let i = 0; i < rows; i++) {
const row = new Array(columns).fill(0);
this.matrix.push(row);
}
}
getColumnNodes(col) {
const nodes = [];
for (let i = 0; i < this.rows; i++) {
if (this.matrix[i][col] === 1) {
nodes.push(new Node(i, col));
}
}
return nodes;
}
setEntry(row, col, value) {
this.matrix[row][col] = value;
}
getEntry(row, col) {
return this.matrix[row][col];
}
print() {
for (let i = 0; i < this.rows; i++) {
console.log(this.matrix[i].join(' '));
}
}
getRow(row) {
return this.matrix[row];
}
getColumn(col) {
const column = [];
for (let i = 0; i < this.rows; i++) {
column.push(this.matrix[i][col]);
}
return column;
}
getNumRows() {
return this.rows;
}
getNumColumns() {
return this.columns;
}
}
class DLX {
constructor(matrix) {
this.root = new Node(-1, -1);
this.root.left = this.root;
this.root.right = this.root;
this.matrix = matrix;
this.cols = [];
this.solutionRows = [];
this.solutions = [];
this.initialize();
}
initialize() {
const numRows = this.matrix.getNumRows();
const numCols = this.matrix.getNumColumns();
const headerNodes = [];
for (let i = 0; i < numCols; i++) {
const header = new Node(-1, i);
header.left = this.root.left;
header.right = this.root;
this.root.left.right = header;
this.root.left = header;
header.up = header;
header.down = header;
headerNodes.push(header);
this.cols.push(0);
}
for (let i = 0; i < numRows; i++) {
let last = null;
for (let j = 0; j < numCols; j++) {
if (this.matrix.getEntry(i, j) === 1) {
const node = new Node(i, j);
node.header = headerNodes[j];
node.up = node.header.up;
node.down = node.header;
node.header.up = node;
node.up.down = node;
if (last === null) {
last = node;
} else {
node.left = last;
node.right = last.right;
last.right = node;
node.right.left = node;
last = node;
}
this.cols[j]++;
}
}
}
}
cover(col) {
const header = col.header;
header.left.right = header.right;
header.right.left = header.left;
for (let node = header.down; node !== header; node = node.down) {
for (let j = node.right; j !== node; j = j.right) {
j.down.up = j.up;
j.up.down = j.down;
this.cols[j.col]--;
}
}
}
uncover(col) {
if (col.header) {
const header = col.header;
for (let node = header.up; node !== header; node = node.up) {
for (let j = node.left; j !== node; j = j.left) {
j.down.up = j;
j.up.down = j;
j.header.cols++;
}
}
if (col.right) {
col.right.left = col;
}
if (col.left) {
col.left.right = col;
}
header.left = col;
header.right = col;
}
}
search() {
if (this.root.right === this.root) {
this.solutions.push([...this.solutionRows]);
return;
}
let minCols = Infinity;
let colNode = null;
for (let node = this.root.right; node !== this.root; node = node.right) {
if (this.cols[node.col] < minCols) {
minCols = this.cols[node.col];
colNode = node;
}
}
this.cover(colNode);
for (let rowNode = colNode.down; rowNode !== colNode; rowNode = rowNode.down) {
this.solutionRows.push(rowNode.row);
for (let j = rowNode.right; j !== rowNode; j = j.right) {
this.cover(j.header);
}
this.search();
this.solutionRows.pop();
for (let j = rowNode.left; j !== rowNode; j = j.left) {
this.uncover(j.header);
}
}
this.uncover(colNode);
}
getSolutions() {
while (this.root.right !== this.root) {
this.search();
this.solutionRows = [];
if (this.root.right === this.root) {
break;
}
for (let i = 0; i < this.cols.length; i++) {
if (this.cols[i] === 0) {
continue;
}
const nodes = this.matrix.getColumnNodes(i);
const candidates = [];
for (const node of nodes) {
candidates.push(node.row);
if (candidates.length === 2) {
let isValid = true;
for (const solution of this.solutions) {
if (
solution.indexOf(candidates[0]) === -1 ||
solution.indexOf(candidates[1]) === -1
) {
isValid = false;
break;
}
}
if (isValid) {
this.solutionRows.push([...candidates]);
break;
}
candidates.pop();
}
}
}
}
return this.solutions;
}
}
function getCoveringDesign() {
const v = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
const k = 3;
const t = 2;
const matrix = new Matrix(v.length * (v.length - 1) * (v.length - 2), v.length);
for (let i = 0; i < v.length; i++) {
for (let j = i + 1; j < v.length; j++) {
for (let l = j + 1; l < v.length; l++) {
const row = new Array(v.length).fill(0);
row[i] = 1;
row[j] = 1;
row[l] = 1;
matrix.matrix.push(row);
}
}
}
const dlx = new DLX(matrix);
const solutions = dlx.getSolutions();
let minSize = Infinity;
let bestSolution = null;
for (const solution of solutions) {
if (solution.length < minSize) {
minSize = solution.length;
bestSolution = solution;
}
}
const blocks = [];
for (const indices of bestSolution) {
const block = [];
for (const index of indices) {
block.push(v[index]);
}
blocks.push(block);
}
return blocks;
}
console.log(getCoveringDesign());`
It gives error:
Uncaught TypeError: Cannot read properties of null (reading 'left')
at DLX.uncover
at DLX.search
at DLX.getSolutions
at getCoveringDesign
Any suggestions? Thanks
Top comments (0)