Алгоритм решения данной задачи?

Question

[xZand]

Всем привет, пытаюсь решить данную задачку на javascript -Ссылка, но не получается описать алгоритм решения. Как правильно сравнить ключи объекта edgeTypesId, и стоит ли пушить в результирующий массив те объекты, который не прошли условия? Стоит ли ставить условие "если первые 10 элементов априори не имеют выемки, а только top: null, то проходится по массиву фильтром и пушить только такие элементы?

Буду благодарен за помощь. Очень нужно понять, как решаются такие задачи. И с чего вообще начать. PS: Буду еще более благодарен, если по пунктам опишите весь процесс решения задачи(именно алгоритм) что бы понять где ошибка и как решать.

Comments

[Александр]

Решил в свободное время задание - интересно получилось. Решал так:
1. Соединил все паззлы с их соседями (circular object/map).
2. Реализовал поворот паззлов таким образом, чтобы "ушки" совпадали (первый паззл тоже надо повернуть).
3. Т. к. все паззлы соединены - мы можем от самого первого паззла пройтись по всем соседям и собрать результативный массив.
Уверен, данный фокус можно решить легче/сложнее. Если будет интересно, могу показать решение.

[xZand]

Александр, Да, хотелось бы глянуть. Кинете ссылку на codepen или другие песочницы? Было бы интересно проанализировать ваш код.

[Александр]

xZand,

Решение

/**
 * @typedef Piece
 * @type {object}
 * @property {number} id
 * @property {PieceEdges} edges
 */

/**
 * @typedef PieceEdges
 * @type {object}
 * @property {PieceEdge|null} top
 * @property {PieceEdge|null} right
 * @property {PieceEdge|null} bottom
 * @property {PieceEdge|null} left
 */

/**
 * @typedef PieceEdge
 * @type {object}
 * @property {number} edgeTypeId
 * @property {'inside'|'outside'} type
 */

const order = ['top', 'right', 'bottom', 'left'];
const Direction = {
  Right: 1,
  Bottom: 2,
  Left: 3,
};

/**
 * @param {Piece} piece
 */
const rotatePiece = piece => {
  [piece.edges.top, piece.edges.right, piece.edges.bottom, piece.edges.left] = [
    piece.edges.left,
    piece.edges.top,
    piece.edges.right,
    piece.edges.bottom,
  ];

  return piece;
};

/**
 * @param {string} edge
 */
const oppositeEdge = edge => {
  switch (edge) {
    case 'top':
      return 'bottom';
    case 'right':
      return 'left';
    case 'bottom':
      return 'top';
    case 'left':
      return 'right';
  }
};

/**
 * @param {Piece[]} pieces
 */
const fixFirstPiece = pieces => {
  const piece = pieces[0];

  while (piece.edges.right === null || piece.edges.bottom === null) {
    rotatePiece(piece);
  }
};

/**
 * @param {Piece[]} pieces
 * @returns {Map<number, Piece>}
 */
const linkPieces = pieces => {
  const store = pieces.reduce((accumulator, piece) => {
    accumulator.set(piece.id, {
      id: piece.id,
      edges: {
        top: null,
        right: null,
        bottom: null,
        left: null,
      },
    });

    return accumulator;
  }, new Map());

  fixFirstPiece(pieces);

  const usedPieces = new Set();
  const queuedPieces = new Set();
  const currentPieces = [pieces[0]];

  while (currentPieces.length > 0) {
    const piece = currentPieces.shift();
    const storedPiece = store.get(piece.id);

    for (const edge in piece.edges) {
      if (piece.edges[edge] !== null) {
        const { edgeTypeId, type } = piece.edges[edge];
        const neighbor = pieces.find(otherPiece =>
          Object.values(otherPiece.edges).some(edge =>
            edge !== null
              ? edge.edgeTypeId === edgeTypeId && edge.type !== type
              : false
          )
        );
        const edgeIndex = Object.values(neighbor.edges).findIndex(edge =>
          edge !== null ? edge.edgeTypeId === edgeTypeId : false
        );

        let rotateCount = order.indexOf(oppositeEdge(edge)) - edgeIndex;
        if (rotateCount < 0) {
          rotateCount += order.length;
        }
        for (let index = 0; index < rotateCount; index++) {
          rotatePiece(neighbor);
        }

        if (storedPiece.edges[edge] === null) {
          storedPiece.edges[edge] = store.get(neighbor.id);

          if (!usedPieces.has(neighbor.id) && !queuedPieces.has(neighbor.id)) {
            currentPieces.push(neighbor);
            queuedPieces.add(neighbor.id);
          }
        }
      }
    }

    usedPieces.add(piece.id);
    queuedPieces.delete(piece.id);
  }

  return store;
};

/**
 * @param {Piece[]} pieces
 * @returns {number[]}
 */
const solvePuzzle = pieces => {
  const linkedPieces = linkPieces(pieces);
  const length = pieces.length;
  const result = new Array(length);
  const size = Math.sqrt(length);
  const position = { x: 0, y: 0 };
  let direction = Direction.Right;
  let piece = linkedPieces.get(pieces[0].id);
  let index = 0;

  while (index < length) {
    result[position.x + position.y * size] = piece.id;
    index++;

    if (direction === Direction.Right) {
      if (piece.edges.right !== null) {
        piece = piece.edges.right;
        position.x++;
      } else {
        direction = Direction.Down;
      }
    }

    if (direction === Direction.Left) {
      if (piece.edges.left !== null) {
        piece = piece.edges.left;
        position.x--;
      } else {
        direction = Direction.Down;
      }
    }

    if (direction === Direction.Down) {
      piece = piece.edges.bottom;
      position.y++;
      if (position.x === 0) {
        direction = Direction.Right;
      } else {
        direction = Direction.Left;
      }
    }
  }

  return result;
};

Можно решить и без создания circluar map'ы. Сразу на этапе сборки искать нужного соседа, поворачивать и идти дальше.

Answer 1

[Илья Чубаров]

Понравилась задача, расскажу как сделал в итоге я.
Программа работает слева -> направо, сверху -> вниз.
Первый кусок, нам известен.
Берем правую сторону первого элемента, находим его связь, далее для следующего элемента надо найти элемент противоположной стороны.
Для примера правая сторона вот такая:
`left: { edgeTypeId: 38, type: 'outside' }`
Надо искать где edgeTypeId :38 и type:'inside'.
Элемент который будет найден, надо обратить внимание, на его сторону, и получить противоположный.
К примеру мы нашли 38 и inside, оно лежало в элементе с id:33, сторона: top, нам надо искать след элемент который будет в bottom, так как он противоположный.

И так проходим всю строку до конца.
Находим нижний элемент первого элемента первого ряда, и далее так же как и было выше, ищем связь для противоположной стороны.
Прикреплю код, его можно сделать более читабельным, но решение рабочие для этой задачи.

Осторожно код

function solvePuzzle(pieces) {
	// initial
	let result = [pieces[0].id];
	let next = {
			edgeTypeId: pieces[0].edges.bottom.edgeTypeId,
			type: pieces[0].edges.bottom.type,
	};


	for(let rowIndex = 0, step = -10;rowIndex < 10;rowIndex++, step += 10) {
		if (rowIndex !== 0) {
			next = getDownPiece(result[step], pieces)
			result.push(next.id)
			next = next.edges.bottom
		}
		for(let i = 0;i < 9;i++) {
			next = findNextEdge(next, pieces, i === 8);
			result.push(next.id)
		}
   }
  return result;
}


function findNextEdge(previousEdge, pieces, isLast = false) {
	let typeOpposite = getTypeOpposite(previousEdge.type);
	let result = {};	
	for (var i = 0; i < pieces.length; i++) {
		let nextEdge = Object.entries(pieces[i].edges).find(function(edge) {
			let [, nextEdgeCandidate] = edge
			return nextEdgeCandidate !== null && previousEdge.edgeTypeId === nextEdgeCandidate.edgeTypeId && nextEdgeCandidate.type === typeOpposite;
		});
		if (nextEdge !== undefined) {
			[typeSide] = nextEdge
			if (isLast === false) {
				result = Object.assign(pieces[i].edges[getOppositePosition(typeSide)], {id:pieces[i].id})
			} else if(isLast){
				result = Object.assign(pieces[i].edges[typeSide], {id:pieces[i].id})
			}
		}
	}
	return result;
}

function findConnectedEdge(leftEdge, pieces) {
	let typeOpposite = getTypeOpposite(leftEdge.type);
	return pieces.find(function(piece){
		return Object.entries(piece.edges).find(function(edge) {
			let [, rightEdgeCandidate] = edge
			return rightEdgeCandidate !== null && leftEdge.edgeTypeId === rightEdgeCandidate.edgeTypeId && rightEdgeCandidate.type === typeOpposite;
		});
	});
}

function getTypeOpposite(type){
  return type === 'inside' ? 'outside':'inside';
}
function getOppositePosition(position) {
	if (position === 'bottom') {
		return 'top';
	} else if(position === 'top') {
		return 'bottom'
	} else if (position === 'left') {
		return 'right';
	} else {
		return 'left';
	}
}

function getDownPiece(idUpPiece, pieces) {
	return findConnectedEdge(pieces.find(edge => {
	  return edge.id === idUpPiece;
	}).edges.left, pieces)
}

// Не удаляйте эту строку
window.solvePuzzle = solvePuzzle;