1

I'm trying to implement DLX in Javascript and I'm running into problems with building circular references.

This function takes a binary matrix and returns a matrix where every '1' of the matrix is an object referencing it's closed '1' in all cardinal directions.

export const constructDataObjects = matrix => {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix.length; j++) {
      let u = j - 1;
      let d = j + 1;
      let l = i - 1;
      let r = i + 1;

      if (matrix[i][j] === 0) continue;

      // Check edge cases.
      if (u < 0) u = matrix.length - 1;
      if (d >= matrix.length) d = 0;
      if (l < 0) l = matrix.length - 1;
      if (r >= matrix.length) r = 0;

      // Increment and decrement directions and bound check.
      // On hitting a bound, circle around and start from the other side.
      while (matrix[i][u] === 0) u = u - 1 < 0 ? matrix.length - 1 : u - 1;
      while (matrix[i][d] === 0) d = d + 1 >= matrix.length ? 0 : d + 1;
      while (matrix[l][j] === 0) l = l - 1 < 0 ? matrix.length - 1 : l - 1;
      while (matrix[r][j] === 0) r = r + 1 >= matrix.length ? 0 : r + 1;
      matrix[i][j] = {
        u: matrix[i][u],
        d: matrix[i][d],
        l: matrix[l][j],
        r: matrix[r][j],
      };
    }
  }

  return matrix;
};

I believe this problem can be reduced to:

let a = arr => {
  for(let i = 0; i < arr.length; i++) {
    n[i] = {
      curr: arr[i],
      first: arr[0],
    }
  }
  return arr
}

now

a([1,2])

Produces

[ { curr: 1, first: 1 },
  { curr: 2, first: { curr: 1, first: 1 } } ]

What I want is

[ { curr: 1, first: { curr: 1, first: 1 } } },
  { curr: 2, first: { curr: 1, first: 1 } } ]

How can I assign first: arr[0] to the reference of the a[0] object instead of a[0]'s value at the time of assignment?

I realize

n[i] = {
  curr: arr[i],
  first: arr[0],
}
n[i].first = n[0]

would work, but I don't see that working in constructDataObjects because the relationships are not known until all elements have been traversed.

Red Mercury
  • 3,971
  • 1
  • 26
  • 32

0 Answers0