solution of https://www.codewars.com/kata/link-up-play-game-series-number-7/discuss/javascript

linkup.js

class Cell {
  constructor(token, x, y) {
    this.token = token;
    this.x = x;
    this.y = y;
  }
}

class FillMap {
  static emptyMap(width, height) {
    const dataBody = new Array(height * width).fill(FillMap.F);
    return new FillMap(
      dataBody,
      width,
      height,
      [...new Array(width * height)].fill(2**width - 1),
      [...new Array(width * height)].fill(2**height - 1)
    );
  }
  static fromCellList(cellList, width, height) {
    const fillMap = FillMap.emptyMap(width, height);
    cellList.forEach(({x, y}) => fillMap.add(x, y));
    return fillMap;
  }

  constructor(dataBody, width, height, memoH, memoV) {
    this.dataBody = dataBody;
    this.width = width;
    this.height = height;
    this.memoH = memoH;
    this.memoV = memoV;
  }
  add(x, y) {
    this.dataBody[y * this.width + x] = FillMap.T;
    for (let i = 0; i <= x; ++i) {
      this.memoH[y * this.width + i] &= 2**x - 1;
    }
    for (let i = x; i < this.width; ++i) {
      this.memoH[y * this.width + i] &= 2**this.width - 2**(x + 1);
    }

    for (let i = 0; i <= y; ++i) {
      this.memoV[x * this.height + i] &= 2**y - 1;
    }
    for (let i = y; i < this.height; ++i) {
      this.memoV[x * this.height + i] &= 2**this.height - 2**(y + 1);
    }
  }
  remove(x, y) {
    this.dataBody[y * this.width + x] = FillMap.F;

    const xs = this.dataBody.slice(this.width * y, this.width * (y + 1));
    const {first: left, last: right, mask: hMask} = this.removeHelper(xs, x);
    for (let i = left; i <= right; ++i) {
      this.memoH[y * this.width + i] |= hMask;
    }

    const ys = [];
    for (let i = 0; i < this.height; ++i) {
      ys[i] = this.dataBody[this.width * i + x];
    }
    const {first: up, last: down, mask: vMask} = this.removeHelper(ys, y);
    for (let i = up; i <= down; ++i) {
      this.memoV[x * this.height + i] |= vMask;
    }
  }
  removeHelper(arr, current) {
    const firstIndex = arr.lastIndexOf(FillMap.T, current);
    const first = firstIndex === -1 ? 0 : firstIndex + 1;
    const lastIndex = arr.indexOf(FillMap.T, current);
    const last = lastIndex === -1 ? this.width - 1 : lastIndex - 1;
    const mask = 2**(last + 1) - 2**first;
    return {first, last, mask};
  }
  isReachable1(x1, y1, x2, y2) {
    if (x1 === x2) {
      return this.memoV[x1 * this.height + y1] & 2**y2;
    }
    if (y1 === y2) {
      return this.memoH[y1 * this.width + x1] & 2**x2;
    }
    return 0;
  }
  // one of (1)(2)(3)(4) must be reachable
  // (coord1)--(1)------
  //    |               |
  //   (2)             (4)
  //    |               |
  //     ------(3)---(coord2)
  isReachable3(x1, y1, x2, y2) {
    if (
      !this.isReachable1(x1, y1, x2, y1) &&
      !this.isReachable1(x1, y1, x1, y2) &&
      !this.isReachable1(x2, y2, x2, y1) &&
      !this.isReachable1(x2, y2, x1, y2)
    ) {
      return 0;
    }
    // x, y, x
    for (let x = 0; x < this.width; ++x) {
      const isReachable =
        this.isReachable1(x1, y1, x, y1) &&
        this.isReachable1(x, y1, x, y2) &&
        this.isReachable1(x, y2, x2, y2);
      if (isReachable) { return isReachable; }
    }
    // y, x, y
    for (let y = 0; y < this.height; ++y) {
      const isReachable =
        this.isReachable1(x1, y1, x1, y) &&
        this.isReachable1(x1, y, x2, y) &&
        this.isReachable1(x2, y, x2, y2);
      if (isReachable) { return isReachable; }
    }
    return 0;
  }
  print() {
    let memoHStr = '';
    for (let y = 0; y < this.height; ++y) {
      for (let x = 0; x < this.width; ++x) {
        memoHStr += this.memoH[y * this.width + x].toString(2).padStart(this.width, '0');
        memoHStr += ',';
      }
      memoHStr += '\n';
    }
    console.info(memoHStr);

    console.info('----');
    let memoVStr = '';
    for (let y = 0; y < this.height; ++y) {
      for (let x = 0; x < this.width; ++x) {
        memoVStr += this.memoV[x * this.height + y].toString(2).padStart(this.height, '0');
        memoVStr += ',';
      }
      memoVStr += '\n';
    }
    console.info(memoVStr);
  }
}
FillMap.T = 1;
FillMap.F = 0;

class TokenIter {
  *tokenPairGen() {
    for (let i = 0; i < this.cellList.length; ++i) {
      const leftCell = this.cellList[i];
      for (let j = i + 1; j < this.cellList.length; ++j) {
        const rightCell = this.cellList[j];
        if (leftCell.token === rightCell.token) {
          yield [
            [leftCell, rightCell],
            [...this.cellList.slice(0, i),
             ...this.cellList.slice(i + 1, j),
             ...this.cellList.slice(j + 1, this.cellList.length)]
          ];
        }
      }
    }
  }
  constructor(cellList) {
    this.cellList = cellList;
  }
}

class MapParseError extends Error {}
class LinkUpSolver {
  static parseMap(mapStr, width, height) {
    const splitted = mapStr
                       .split(LinkUpSolver.LINE_SEPARATOR)
                       .map(line => line.split(LinkUpSolver.TOKEN_SEPARATOR));
    if (splitted.length !== height) {
      throw new MapParseError('height error');
    }
    if (splitted.some(line => line.length !== width)) {
      throw new MapParseError('width error');
    }
    if (splitted.some(line => line.some(el => !LinkUpSolver.TOKEN.has(el)))) {
      throw new MapParseError('token error');
    }

    const tokenList = mapStr.split(
      new RegExp(`[${LinkUpSolver.TOKEN_SEPARATOR}${LinkUpSolver.LINE_SEPARATOR}]`, 'g')
    );

    const paddedCellList = tokenList.map((token, index) => {
      const originalX = index % width;
      const originalY = (index - index % width) / width;
      const paddedX = originalX + 1;
      const paddedY = originalY + 1
      return new Cell(token, paddedX, paddedY);
    });

    return new LinkUpSolver(
      paddedCellList,
      FillMap.fromCellList(paddedCellList, width + 2, height + 2),
      (1n << BigInt(height * width)) - 1n,
      [...new Array(height * width + 1)].map(_ => [])
    );
  }

  constructor(cellList, fillMap, serialized, backtrackList) {
    this.cellList = cellList;
    this.fillMap = fillMap;
    this.serialized = serialized;
    this.backtrackList = backtrackList;

    this.tokenPairIter = new TokenIter(cellList);
  }
  isSolved() {
    return this.cellList.length === 0;
  }
  *solve() {
    if (this.backtrackList[this.cellList.length].indexOf(this.serialized) !== -1) {
      return;
    }
    if (this.isSolved()) {
      yield [];
      return;
    }
    for (let [[cell1, cell2], otherCellList] of this.tokenPairIter.tokenPairGen()) {
      this.fillMap.remove(cell1.x, cell1.y);
      this.fillMap.remove(cell2.x, cell2.y);
      if (this.fillMap.isReachable3(cell1.x, cell1.y, cell2.x, cell2.y)) {
        const newLinkUpSolver = new LinkUpSolver(
          otherCellList,
          this.fillMap,
          this.serialized
            - (1n << BigInt((cell1.y - 1) * (this.fillMap.width - 2) + cell1.x - 1))
            - (1n << BigInt((cell2.y - 1) * (this.fillMap.width - 2) + cell2.x - 1)),
          this.backtrackList
        );
        for (let solution of newLinkUpSolver.solve()) {
          yield [[cell1, cell2], ...solution];
        }
      }
      this.fillMap.add(cell1.x, cell1.y);
      this.fillMap.add(cell2.x, cell2.y);
    }
    this.backtrackList[this.cellList.length].push(this.serialized);
  }
  print() {
    let arr = [...new Array(this.fillMap.height)].map(_ => new Array(this.fillMap.width).fill(' '));
    this.cellList.forEach(cell => {arr[cell.y][cell.x] = cell.token});
    console.info(arr.map(line => line.join('')).join('\n'));
  }
}
LinkUpSolver.LINE_SEPARATOR = '\n';
LinkUpSolver.TOKEN_SEPARATOR = ' ';
LinkUpSolver.TOKEN = new Set([
  'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
  'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P'
]);
LinkUpSolver.EMPTY_TOKEN = '_';

function linkUp(map) {
  const linkUpSolver = LinkUpSolver.parseMap(map, 8, 8);
  const linkUpSolverIter = linkUpSolver.solve();
  const iterResult = linkUpSolverIter.next();
  if (iterResult.done) {
    return null;
  } else {
    return iterResult.value.map(([cell1, cell2]) =>
      [[cell1.y - 1, cell1.x - 1],
       [cell2.y - 1, cell2.x - 1]]
    );
  }
}

const maps = [
`J L N O K F L G
M D E A K B I K
I O J L L M B P
P C G J F D O E
I N F O N M D H
I N D K J E C G
A M H B E P C H
C F A A B H P G`,
`F H L F H L C K
I L B K K I A N
O I K F O P H P
C G F M M I A N
N A E J B J D G
M O C B G E L P
H C E G D D P B
O J M A J E N D`,
`K C O J P N M C
E D F L C K A C
H B L N M B G G
L E B O E M M J
F A J G D G D L
F A H P F O N O
I P H J H A K P
N D I K I E I B`,
`H B E M K K O D
F C K F O F B C
G M E E M C J H
I A G I H A J M
L B N N I P L P
B D E L C A N O
F H D O K L G G
J A P I J N D P`,
`M J A F C D L J
O G B F P L D M
O K K L H I N G
C B G N F G P C
O I E A H A D D
O K J N B H E E
I H J K C F B P
A N M E L I P M`,
`B K N H D A O O
B G J F P B D N
P L F C N F P C
C I J J A D C M
E L F I N M E G
E O G A K P J I
E K M M K D O B
H G H I L L H A`,
`K G I O A D H F
F J P D H H P D
J M N M B F E M
M A L A L L J E
G A C L E I N K
P J B O K H N C
O E O D K N P I
G G B C B F C I`,
`L F O G C D J O
K D N O N L E H
F E F I E I J D
K J A N F G C A
C H E I B D I B
P L C G M H P L
P O P B M H A J
K G B M K A M N`,
`J J F C M H I O
C P P E D A D C
B F A N O C M E
J E A I K N B G
M D B D I G N I
G L O B P P H A
N L E O G H K F
L K J L M H K F`,
`M G B B P G O H
D J H C M B I C
K J A L A N O M
K J G P E F N L
M G A C L P E A
I F D N K L J B
C P O D I H N E
H F K D I E O F`,
`F I N G M L C O
E H L G F M P E
D A C L C N K G
M D L N M N P O
K D J H B H A D
O P J I P B K J
C I K A E H I G
O F B F E A J B`,
`H O D D G P I O
L F G C P B O D
J A N J L K H F
O C L H E B I A
L D N F N M P C
E E A G M B M E
G M J B J H F K
P I C N A I K K`,
`L D F K M C N C
O A C J L J I K
P E H D H F B H
G C P D J M A B
K G G F H B G N
F D L E M O O J
M I L P A N E B
A O E K I I P N`,
`M G I F B M J K
L E D J N F C N
J C O C A O H L
P O B K H P J H
E N N M B D A L
C K K D D G M I
H B P P A L G O
G F E I I F E A`,
`D I H J E G M P
F I N A L M H O
P I E C A F E D
O F L D J F H B
C M L N P K J L
K C B K B O C O
H D B K I M G N
G G A N J E P A`,
`E C A J D O L A
I F H M P P D D
B M H E J B F O
G J P K L K I H
K K A M N C E F
B A L P I E J N
C G O H D O B C
F M L I N G N G`,
`F J O H H D F O
P G O M L J B L
K D N I D I N H
F B P I P M A C
M A N L A G O C
I K C E G G F K
D C B E E J M K
E P J L N H A B`,
`F H J K D D O A
L M N J P B N G
C B K I L M E M
A C C G I E D O
F P N F H B D O
I G N P A M A P
F E C G L I H J
B E K H O K J L`,
`C G P H E D C J
L G M H G C H A
M N I O N I E J
B L F A K M D P
D K P A J F J N
I H F B E C P D
O F L O K I O E
B M B N G L K A`,
`I B E B C I K J
O F P C L J G H
H M A N M I B L
A N G I G N E G
K B D A O D E L
E A M K C M P K
P O D J O J N F
H F C P L H D F`,
`N P I D O F K L
J C G D D A B K
M L E D J N J H
K B C M I E I M
C A A H P H O I
O M F E P K G F
F B H G L B A P
N L E G C O N J`,
`L B N O D K C F
L L D L P N G K
I A O H M N H B
A M I N E J E C
K M G H F A F P
I E D C J I J O
K B P H J F G B
C O G D M P E A`,
`L L C I D L O O
N K B N M A E A
C J J K I D M P
N K A A G C D E
K F H I I B M P
J D G O H E J M
G P P C E F L B
O F F H B N G H`,
`L D H E O J L G
I D P E D C A M
I L J N P F B O
K M I M G J H F
B K N I M O J E
F P K O B L A G
K N C D E A H C
F G C P B H A N`,
`D H G A N M L F
E N I D I E K N
P L B G A F M J
P L J O F J O L
O C E A K D K I
B B C O N M C B
G D E G A F J M
P C P I H K H H`,
`M G G F F N P D
D B C D O E I I
M J F J K H C F
E A K P C H N N
O L G H P E K E
L A O M J L D I
N B B L B C G I
A J O A K H P M`
];
console.info(maps.length);
console.time(`total`);
maps.forEach((map, index) => {
console.time(`map${index}`);
linkUp(map);
console.timeEnd(`map${index}`);
});
console.timeEnd(`total`);