Executando verificação de segurança...
1
Jotaro157
10 min de leitura ·

Queen's Attack II, resolvendo um exercício do HackerRank com Javascript Parte II

#3 Refatoração

Este código tornou-se excessivamente extenso e, às vezes, a concepção da ideia pode sair desorganizada. É preciso polir e aprimorar constantemente. Com o tempo, é possível desenvolver habilidade para antecipar problemas e melhorar a concepção da ideia desde o início.

Nesta refatoração, vamos nos concentrar em um único aspecto que é a legibilidade. Em primeiro lugar, vamos otimizar como a matriz é criada. Em segundo lugar, vamos revisar e simplificar os oito loops usados para calcular o número de casas que a rainha pode atacar. Vamos trabalhar para deixar o código o mais elegante possível.

Essa é a nossa atual função de criação da matrix:

let matrix = [];
    for (let i = 0; i < n; i++) {
        matrix[i] = [];
        for (let j = 0; j < n; j++) {
          matrix[i][j] = 0;
        }
    }

Iremos substituir ela por algo muito mais compacto.

let matrix = Array(n).fill().map(() => Array(n).fill(0));

Esta linha de código cria uma matriz quadrática de tamanho n, preenchendo cada elemento com o valor 0. Isso é feito criando um array inicial de tamanho n usando a função Array() e preenchendo-o com o método fill(). Em seguida, aplicamos o método map() a esse array, que é uma função que permite aplicar uma outra função a cada elemento do array. A função anônima passada para o map() cria outro array de tamanho n e preenche cada elemento com 0, resultando em uma matriz quadrática com todos os seus elementos inicializados com 0 em apenas uma única linha de código.

Nosso código ainda continua excessivamente grande, precisamos arrumar uma formar de melhorar a contagem das casas que a rainha possa atacar, para isso vamos manter nossa linha de raciocínio e iremos refatorar apenas o funcionamento dos loops.

Para isso iremos organizar como iteramos sobre os movimentos possíveis da rainha. Nosso objetivo é somar a distância da rainha até os obstáculos em oito direções, como em uma rosa dos ventos, vamos criar um array que nos ajudará a iterar sobre as posições em volta da rainha. Para isso, vamos pensar na rainha como um ponto zero em um mapa [0,0], logo teremos o seguinte array.

  let directions = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [1, 1],
 [-1, 1], [1, -1]];

Cada tupla dentro do array que criamos representa uma direção para percorrermos ao redor da rainha. Por exemplo, a tupla [-1, 0] nos ajudará a iterar sobre a linha vertical acima da rainha, enquanto a tupla [0, -1] nos ajudará a iterar sobre a linha horizontal à esquerda da rainha. Dessa forma, podemos percorrer todas as direções possíveis e verificar se há algum obstáculo em nossa caminho. Isso torna o código mais claro e fácil de entender, pois estamos utilizando uma abordagem mais simples do que a anterior, agora que temos nossas direções iremos escrever as seguintes linhas.

for (let i = 0; i < directions.length; i++) {
       let row = queenLinhaArray  + directions[i][0];
       let col = queenColunaArray + directions[i][1];
      
   }

Um for que ira pegar os valores dessas direções e salvar em uma variavel, com e dentro desse loop, iremos usar essas variaveis com os valores salvos durantes as iterações para poder percorrer a nossa matriz, para isso adicioneremos mais estas linhas, deixando o código assim.

for (let i = 0; i < directions.length; i++) {
       let row = queenLinhaArray  + directions[i][0];
       let col = queenColunaArray + directions[i][1];
       while (row >= 0 && row < n && col >= 0 && col < n) {
           if (matrix[row][col] === 'X') break;
           maxMovs++;
           row += directions[i][0];
           col += directions[i][1];
       }
   }

Dentro do nosso for iremos adicioanr um while, esse while ira ter como condição as dimensões de nosso tabuleiro, ou seja, ele ira garantir que nosso loop funcione enquanto estivermos dentro do tabuleiro, uma explicação mais detalhada a seguir:

  1. A expressão começa verificando se a posição atual da linha é maior ou igual a zero.
  2. Em seguida, utilizamos o operador lógico “&&” (E) para garantir que as condições anteriores e posteriores sejam verdadeiras.
  3. A próxima condição é verificar se a linha atual é menor que o tamanho total do tabuleiro.
  4. Novamente, utilizamos o operador lógico “&&” para garantir que as condições anteriores e posteriores sejam verdadeiras.
  5. A seguir, verificamos se a posição atual da coluna é maior ou igual a zero.
  6. Finalmente, utilizamos novamente o operador lógico “&&” para verificar se a coluna atual é menor que o tamanho total do tabuleiro.

Com a condição estabelecida, o código irá interromper sua execução sempre que encontrar um “X” no tabuleiro. Isso irá interromper o loop “while” e reiniciar o loop “for” para verificar as próximas direções. Se nenhum “X” for encontrado durante a verificação, adicionaremos uma unidade à nossa variável “maxMovs” e atualizaremos as variáveis “row” e “col” para verificar as próximas casas utilizando o array “directions” como um meio de simular a movimentação da rainha naquela determinada direção escolhida quando o array começou a ser iterado pelo loop “for”.

Se você chegou até aqui, parabéns! Conseguimos refatorar nosso código e o resultado final é este.

function queensAttack(n, k, r_q, c_q, obstacles) {
    let queenLinhaArray = n-r_q;
    let queenColunaArray= c_q-1;
    let matrix = Array(n).fill().map(() => Array(n).fill(0));
    let maxMovs = 0;
    
    for (let i =0; i<k; i++){
        let obstacleRow = n-(obstacles[0][0]);
        let obstacleCol = (obstacles[0][1])-1;
        [matrix[obstacleRow][obstacleCol]] = ['X']        
        obstacles.shift();
    }
    
   [matrix[queenLinhaArray][queenColunaArray]] = ['Q'];

   let directions = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [1, 1], [-1, 1], [1, -1]];
   for (let i = 0; i < directions.length; i++) {
       let row = queenLinhaArray  + directions[i][0];
       let col = queenColunaArray + directions[i][1];
       while (row >= 0 && row < n && col >= 0 && col < n) {
           if (matrix[row][col] === 'X') break;
           maxMovs++;
           row += directions[i][0];
           col += directions[i][1];
       }
   }

   return [maxMovs, matrix]
}


console.log(queensAttack(5,2,1,1, [[1,2],[4,2]]))

Bem mais bonito e ocupando menos espaço do que a nossa primeira versão, porem ainda temos um problema, o que acontece se eu tentar rodar uma ele em um tabuleiro gigante com um N maior do que 20000, sera que nosso código ira conseguir atender a um tabuleiro tão grande?

#4 Checkmate

Nesta última etapa, vamos analisar uma das principais falhas do nosso código. Se você tentou executá-lo com um valor de “tamanho do tabuleiro” maior que 20.000, provavelmente percebeu que o código não funciona corretamente. Lembra-se no início do artigo, quando mencionei que criar uma matriz poderia causar problemas? Bem, esses problemas finalmente se apresentaram. Criar uma matriz é muito pesado computacionalmente, criar uma matriz de 20.000x20.000 com certeza não é uma tarefa simples, seriam 400.000 casas dentro dessa matriz. É provável que seu computador tente criar um segundo sol na Terra ao tentar executar esse código. Então, qual é a solução? A solução mais viável é recomeçar do zero. Pode parecer loucura, mas não é. Desde o início, os fundamentos estabelecidos para resolver esse problema estavam errados. Tentar fazer gambiarras para melhorar o desempenho desse código não é algo muito agradável. Pode ser possível rodá-lo em computadores melhores, mas se há uma maneira mais simples de ser feita, ela deve ser feita. Ainda que não seja a mais simples do ponto de vista da implementação, performa muito melhor em computação.

À medida que continuamos, entraremos no código de um programador hábil e experiente. Não se sinta intimidado se algumas partes parecerem confusas. Pois até mesmo programadores experientes irão demorar para compreender o codigo daqui em diante.

Focaremos nas constantes até chegar ao resultado final. Para começar, organizaremos os dados dos obstáculos criando duas constantes.

const sortedHorizontally = [...obstacles].sort(([firstRow, firstCol], 
[secondRow, secondCol]) => firstCol - secondCol);

const sortedVertically = [...obstacles].sort(([firstRow, firstCol], 
[secondRow, secondCol]) => firstRow - secondRow);

As duas constantes utilizam o operador spread “…” para copiar o array de obstáculos. O método sort é aplicado em cada uma, organizando as tuplas de acordo com as seguintes regras: na constante sortedHorizontally, é comparada a primeira coluna com a segunda coluna, enquanto que na constante sortedVertically, é comparada a primeira linha com a segunda linha. Isso garante que as tuplas estejam organizadas em ordem crescente.

Com as tuplas organizadas em duas constantes em ordem crescente, iremos agora procurar as tuplas mais proximas a rainha nas honrizontais e verticais.

const greaterVertically = sortedVertically.find(([row, col]) 
=> row > r_q && col === c_q) || [n + 1, c_q];
const lesserVertically = [...sortedVertically].reverse().find(([row, col]) 
=> row < r_q && col === c_q) || [0, c_q];

const greaterHorizontally = sortedHorizontally.find(([row, col])
=> col > c_q && row === r_q) || [r_q, n + 1];
const lesserHorizontally = [...sortedHorizontally].reverse().find(([row, col]) 
=> col < c_q && row === r_q) || [r_q, 0];

Aqui, utilizamos novamente o spread operator “…” para copiar o array de obstáculos. Utilizamos então o método find() para procurar por valores que correspondem aos nossos parâmetros definidos (row > r_q && col === c_q) ou [n + 1, c_q]. Assim conseguimos salvar no greaterVertically a tupla mais proxima da rainha na vertifical positiva, que é a da direita. Já no lado lesserVertically seguimos a mesma ideia, porem aplicamos uma reverse na nossa lista de tuplas pois queremos a tupla com o valor mais proximo a da rainha. Também fizemos um ajuste na condição de comparação < r_q && col === c_q) ou [0, c_q].

Nas etapas seguintes, buscaremos encontrar o obstáculo mais próximo nas diagonais, utilizando um método semelhante ao utilizado nas buscas horizontais e verticais, porém, devido à complexidade das diagonais, essa tarefa se mostra um pouco mais desafiadora de ser organizada.

const greaterDiagonallyFromBottomLeft = 
sortedHorizontally.find(([row, col]) => col > c_q && col - c_q === row - r_q)
|| [r_q + 1 + Math.min(n - r_q, n - c_q), c_q + 1 + Math.min(n - r_q, n - c_q)];

const lesserDiagonallyFromBottomRight = 
sortedHorizontally.find(([row, col]) => col > c_q && col - c_q === r_q - row)
|| [r_q - 1 - Math.min(r_q - 1, n - c_q), c_q + 1 + Math.min(r_q - 1, n - c_q)];


const lesserDiagonallyFromTopRight =
 [...sortedHorizontally].reverse().find(([row, col]) 
=> col < c_q && c_q - col === r_q - row) 
|| [r_q - Math.min(r_q, c_q), c_q - Math.min(r_q, c_q)];

const greaterDiagonallyFromTopLeft =
 [...sortedHorizontally].reverse().find(([row, col]) 
=> col < c_q && c_q - col === row - r_q) 
|| [r_q + 1 + Math.min(n - r_q, c_q - 1), c_q - 1 - Math.min(n - r_q, c_q - 1)];

Nesta parte do código, pode ser um pouco difícil de se compreender, pois, como mencionei anteriormente, não sou o autor do código e pode ser desafiador explicar o raciocínio que levou até aqui. No entanto, com um pouco de esforço, podemos interpretar o que essas linhas de código fazem.

Ao trabalhar com diagonais, o código busca estabelecer uma condição semelhante àquela que fizemos na refatoração, mas, como estamos lidando apenas com diagonais e não estamos usando uma matriz, precisamos lidar com menos direções e um pouco mais de matemágica.

A primeira linha procura por obstáculos mais próximos na diagonal inferior esquerda (onde a coluna é maior que c_q e a diferença entre a coluna e c_q é igual à diferença entre a linha e r_q). A segunda linha procura por obstáculos mais próximos na diagonal inferior direita (onde a coluna é maior que c_q e a diferença entre a coluna e c_q é igual à diferença entre r_q e a linha). A terceira linha procura por obstáculos mais próximos na diagonal superior direita (onde a coluna é menor que c_q e a diferença entre c_q e a coluna é igual à diferença entre r_q e a linha). A quarta linha procura por obstáculos mais próximos na diagonal superior esquerda (onde a coluna é menor que c_q e a diferença entre c_q e a coluna é igual à diferença entre a linha e r_q). Caso a primeira condição não seja satisfeita, temos sempre uma segunda a ser correspondida, essa é determinada por um código que busca determinar o menor valor entre dois números. Essa coordenada representa a posição do próximo obstáculo mais próximo nas diagonais.

Neste último passo, calcularemos a diferença entre as distâncias dos obstáculos mais próximos à rainha nas mesmas linhas, em direções opostas. Subtrairemos dois, pois adicionamos duas casas, a da rainha, no intervalo. Dessa forma, obteremos o total de casas em cada ângulo calculado. Em seguida, basta somar os ângulos e ter o total de casas acessíveis pela rainha.

const squaresHorizontally = greaterHorizontally[1] - lesserHorizontally[1] - 2;
const squaresDiagonallyFromBottomLeft = greaterDiagonallyFromBottomLeft[0] - lesserDiagonallyFromTopRight[0] - 2;

const squaresVertically = greaterVertically[0] - lesserVertically[0] - 2;
const squaresDiagonallyFromTopLeft = greaterDiagonallyFromTopLeft[0] - lesserDiagonallyFromBottomRight[0] - 2;

const totalSquares = squaresDiagonallyFromBottomLeft + squaresDiagonallyFromTopLeft + squaresHorizontally + squaresVertically;

Pronto, agora é só retornar o valor de totalSquares e acabamos o exercicio, eis o código completo para a execução caso tenha interesse.

function queensAttack(n, k, r_q, c_q, obstacles) {
    const sortedHorizontally = [...obstacles].sort(([firstRow, firstCol], [secondRow, secondCol]) => firstCol - secondCol);
    const sortedVertically = [...obstacles].sort(([firstRow, firstCol], [secondRow, secondCol]) => firstRow - secondRow);

    const greaterVertically = sortedVertically.find(([row, col]) => row > r_q && col === c_q) || [n + 1, c_q];
    const lesserVertically = [...sortedVertically].reverse().find(([row, col]) => row < r_q && col === c_q) || [0, c_q];

    const greaterHorizontally = sortedHorizontally.find(([row, col]) => col > c_q && row === r_q) || [r_q, n + 1];
    const lesserHorizontally = [...sortedHorizontally].reverse().find(([row, col]) => col < c_q && row === r_q) || [r_q, 0];

    const greaterDiagonallyFromBottomLeft = sortedHorizontally.find(([row, col]) => col > c_q && col - c_q === row - r_q) || [r_q + 1 + Math.min(n - r_q, n - c_q), c_q + 1 + Math.min(n - r_q, n - c_q)];
    const lesserDiagonallyFromBottomRight = sortedHorizontally.find(([row, col]) => col > c_q && col - c_q === r_q - row) || [r_q - 1 - Math.min(r_q - 1, n - c_q), c_q + 1 + Math.min(r_q - 1, n - c_q)];

    const lesserDiagonallyFromTopRight = [...sortedHorizontally].reverse().find(([row, col]) => col < c_q && c_q - col === r_q - row) || [r_q - Math.min(r_q, c_q), c_q - Math.min(r_q, c_q)];
    const greaterDiagonallyFromTopLeft = [...sortedHorizontally].reverse().find(([row, col]) => col < c_q && c_q - col === row - r_q) || [r_q + 1 + Math.min(n - r_q, c_q - 1), c_q - 1 - Math.min(n - r_q, c_q - 1)];



    const squaresHorizontally = greaterHorizontally[1] - lesserHorizontally[1] - 2;
    const squaresDiagonallyFromBottomLeft = greaterDiagonallyFromBottomLeft[0] - lesserDiagonallyFromTopRight[0] - 2;

    const squaresVertically = greaterVertically[0] - lesserVertically[0] - 2;
    const squaresDiagonallyFromTopLeft = greaterDiagonallyFromTopLeft[0] - lesserDiagonallyFromBottomRight[0] - 2;

    const totalSquares = squaresDiagonallyFromBottomLeft + squaresDiagonallyFromTopLeft + squaresHorizontally + squaresVertically;
 
    return totalSquares;
}
 console.log(queensAttack(5,2,1,1, [[1,2],[5,2]]))
Carregando publicação patrocinada...