puzzlinator.js

const TOP = 'top';
const BOTTOM = 'bottom';
const LEFT = 'left';
const RIGHT = 'right';

const OUTSIDE = 'outside';
const INSIDE = 'inside';

const SIDES = [TOP, RIGHT, BOTTOM, LEFT];
const SIDES_LENGTH = SIDES.length;
const SIDES_HALF_LENGTH = SIDES_LENGTH / 2;

const X_DIRECTIONS = {
  [TOP]: 0,
  [BOTTOM]: 0,
  [LEFT]: -1,
  [RIGHT]: 1,
};

const Y_DIRECTIONS = {
  [TOP]: 1,
  [BOTTOM]: -1,
  [LEFT]: 0,
  [RIGHT]: 0,
};

function solvePuzzle(pieces) {
  if (!Array.isArray(pieces) || pieces.length === 0) {
    return [];
  }

  const partsMap = {};
  const edgesMap = {};

  pieces.forEach(part => {
    partsMap[part.id] = part;

    for (let sideIndex = 0; sideIndex < SIDES_LENGTH; sideIndex++) {
      const edge = part.edges[SIDES[sideIndex]];

      if (edge) {
        edgesMap[edge.edgeTypeId] = edgesMap[edge.edgeTypeId] || {};
        edgesMap[edge.edgeTypeId][edge.type] = {
          id: part.id,
          sideIndex: sideIndex,
        };
      }
    }
  });

  const getRelatedPartData = (edge) => {
    const edgesByTypeId = edgesMap[edge.edgeTypeId];

    if (!edgesByTypeId) {
      return undefined;
    }

    if (edge.type === OUTSIDE) {
      return edgesByTypeId[INSIDE];
    } else {
      return edgesByTypeId[OUTSIDE];
    }
  };

  const table = {};
  const visited = {};

  const setTableValue = (x, y, value) => {
    table[x] = table[x] || {};
    table[x][y] = value;
  };

  const setPartTableValues = (part, x, y, rotate) => {
    setTableValue(x, y, part.id);
    visited[part.id] = true;

    for (let sideIndex = 0; sideIndex < SIDES_LENGTH; sideIndex++) {
      const side = SIDES[sideIndex];

      if (!part.edges[side]) {
        continue;
      }

      const relatedPartData = getRelatedPartData(part.edges[side]);

      if (!relatedPartData) {
        throw new Error('Unable to solve puzzle');
      }

      if (visited[relatedPartData.id]) {
        continue;
      }

      const nextSideIndex = (sideIndex + rotate) % SIDES_LENGTH;
      const normalRelatedSideIndex = (nextSideIndex + SIDES_HALF_LENGTH) % SIDES_LENGTH;
      const relatedSideIndex = relatedPartData.sideIndex;

      const nextSide = SIDES[nextSideIndex];
      const nextRotate = (SIDES_LENGTH + normalRelatedSideIndex - relatedSideIndex) % SIDES_LENGTH;

      setPartTableValues(
        partsMap[relatedPartData.id],
        x + X_DIRECTIONS[nextSide],
        y + Y_DIRECTIONS[nextSide],
        nextRotate
      );
    }
  };

  setPartTableValues(pieces[0], 0, 0, 0);

  const result = [];

  const xKeys = Object.keys(table).map(x => parseInt(x)).sort((a, b) => b - a);

  for (let i = 0; i < xKeys.length; i++) {
    const x = xKeys[i];
    const yKeys = Object.keys(table[x]).map(y => parseInt(y)).sort((a, b) => b - a);
    for (let j = 0; j < yKeys.length; j++) {
      const y = yKeys[j];
      result.push(table[x][y]);
    }
  }

  return result;
}