Algorithm for solving this problem?

Question

JavaScript

Hello everyone, I'm trying to solve this problem in javascript - Link , but I can't describe the solution algorithm. How to correctly compare the keys of the edgeTypesId object, and is it worth pushing into the resulting array those objects that did not pass the conditions? Is it worth setting the condition "if the first 10 elements a priori do not have a notch, but only top: null, then it passes through the array with a filter and pushes only such elements?

I would be grateful for your help. It is very necessary to understand how such tasks are solved. And where to start in general PS: I would be even more grateful if you describe the whole process of solving the problem (namely the algorithm) point by point in order to understand where the error is and how to solve it.

Answer 1

I liked the task, I'll tell you how I did it in the end.
The program works from left -> right, top -> down.
The first piece, we know.
We take the right side of the first element, find its connection, then for the next element we need to find the element of the opposite side.
For example, the right side is like this:
`left: { edgeTypeId: 38, type: 'outside' }`
You need to look for where edgeTypeId :38 and type: 'inside'.
The element that will be found, you need to pay attention to its side, and get the opposite.
For example, we found 38 and inside, it was in the element with id: 33, side: top, we need to look for the trace of the element that will be in the bottom, since it is the opposite.
And so we go through the entire line to the end.
We find the lower element of the first element of the first row, and then, just as it was above, we are looking for a connection for the opposite side.
I will attach the code, it can be made more readable, but the solution is working for this task.

Caution Code

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;