3

Estava resolvendo um problema que era basicamente:

Um prisioneiro foi sentenciado a realizar um trabalho onde ele deveria quebrar todas as pedras que eram fornecidas a ele, mas ele não poderia usar nenhuma ferramenta para isso. Para realizar a tarefa, ele decidiu que a melhor opção seria quebrar duas pedras batendo umas nas outras, até restar somente uma pedra ou nenhuma. Além disso, o prisioneiro decidiu quebrar as maiores pedras primeiro, portanto, em ordem decrescente.

Se o prisioneiro bater duas pedras que possuem o mesmo tamanho, ambas as pedras são quebradas, e se uma pedra for menor que a outra, o tamanho da pedra maior é reduzido pelo tamanho da pedra menor (por exemplo, 6-3 = 3).

Dadas as informações, escreva uma função que retorna o tamanho da última pedra quebrada pelo prisioneiro, ou 0 se não houverem pedras restantes.

Dito isso, o problema fornece uma quantidade de test-cases para validar a solução.

Como exemplo, um test-case fornece o array [4, 2, 3, 5] que, quando ordenado, resultaria no vetor [2, 3, 4, 5] e teria a seguinte sequência de cálculos:

5 - 4 = 1

1 - 3 = 2 (a pedra 3 reduz seu tamanho em 1 unidade)

2 - 2 = 0

Portanto, resultado final: 0

Outro exemplo, um array [10, 40, 20, 30, 35, 70] seria ordenado para [10, 20, 30, 35, 40, 70] e teria as seguintes etapas:

70 - 40 = 30

30 - 35 = -5 (portanto, 5)

5 - 30 = -25 (portanto, 25)

25 - 20 = 5

5 - 10 = -5 (portanto, 5)

Resultado final: 5

A função criada para resolver o problema foi:

const lastStoneWeight = arr => {
    arr = arr.sort(compareValues);
    let current;
    return arr.reduceRight((sum = 0, value) => {
        current = sum - value;
        return current < 0 ? -current : current;
    });
};

const compareValues = (a, b) => a < b ? -1 : a > b ? 1 : 0;

Essa função funcionou para alguns dos test-cases (como os citados acima), mas não funcionou para outros, como um que fornece o array:

[
    32, 
    46188086, 
    339992587, 
    742976890, 
    801915058, 
    393898202, 
    717833291, 
    843435009, 
    361066046, 
    884145908, 
    668431192, 
    586679703, 
    792103686, 
    85425451, 
    246993674, 
    134274127, 
    586374055, 
    923288873,  
    292845117, 
    399188845, 
    842456591, 
    410257930, 
    333998862, 
    16561419, 
    624279391, 
    459765367, 
    969764608, 
    508221973, 
    82956997, 
    437034793,
    553121267, 
    554066040, 
    199416087
];

O resultado (segundo o site de teste) é 64 mil e poucos (não me recordo o valor exato), enquanto eu cheguei a 10556317.

Imaginei que talvez minha abordagem utilizando o reduce não fosse a correta, então implementei a função de outro modo, tendo o mesmo resultado:

function lastStoneWeight(arr) {
    arr = arr.sort(compareValues);
    let current;
    while (arr.length > 1) {
        current = arr[arr.length - 1] - arr[arr.length - 2];
        arr[arr.length - 2] = current < 0 ? -current : current;
        arr.pop();
    }
    return arr[0];
};

Seria possível explicar o motivo pelo qual a solução correta não está sendo encontrada? Qual edge-case eu não consegui abordar com as soluções apresentadas?

EDIT: Uma versão alternativa da função compareValues:

function compareValues(a, b) {
    if (a < b) return -1
    if (a > b) return 1
    return 0
}
11
  • É um problema de subtração e a subtração não é uma operação comutativa. Ex: 7 - 3 = 4 porém 3 - 7 = -4 Quando você ordena o array arr = arr.sort(compareValues); você altera a ordem dos termos gerando uma nova sequencia operações resultando em um valor diferente do pretendido. 14/03/2019 às 2:19
  • A ordenação é um requerimento do problema, as pedras devem estar em uma ordem onde as maiores devem ser quebradas primeiro. Sobre subtração não ser operação cumulativa: Exatamente por isso eu introduzi o fragmento "return current < 0 ? -current : current;", já que 7 -3 é a mesma coisa que - (3 - 7) 14/03/2019 às 3:26
  • O primeiro exemplo "[2, 3, 4, 5]" o resultado final não seria "0"? Ex: (5-4) => (1 - 3) => (2 - 2) => 0 , sabe informar o valor exato do terceiro caso (onde o array tem 33 elementos)? Testei aqui e para "[2, 3, 4, 5]" deu 0, para "[10, 20, 30, 35, 40, 70]" deu 5 e para "[32, 16561419, 46188086, 82956997, 85425451.............................]" deu 10556317.
    – RDyego
    14/03/2019 às 18:33
  • É verdade, desculpa, eu acabei colocando o exemplo de forma errada (estou editando o texto para fazer essa alteração, obrigado!). O exemplo do problema era [3, 4, 5] (que resultava em 2), eu testei com [2, 3, 4, 5] (a plataforma possibilitava Custom Test Cases pelo usuário) e acabei exemplificando erroneamente. Eu não tenho mais acesso ao problema mas, como havia dito na descrição, a resposta era algo em torno de 64 mil. E cheguei ao mesmo resultado que você, o que me deixou encabulado. 15/03/2019 às 17:15
  • Marcos, qual o valor da função compareValues? Poderia editar a resposta incluindo-a no código? :) 15/03/2019 às 17:40

3 Respostas 3

3

Utilize um while com a condição de saída verificando o tamanho do array resultante. Dentro do while ordene o array usando sort. Pegue os 2 primeiros valores do array usando shift e garantindo que eles saiam dos valores que podem ser utilizados. Faça o cálculo da diferença absoluta deles usando Math.abs e adicione o resultado no array novamente, caso seja diferente de 0.

const calcular = (pedras) => {
  const copia = [...pedras];

  while (![0, 1].includes(copia.length)) {
    copia.sort((a, b) => b - a);
    const a = copia.shift();
    const b = copia.shift();
    const diferenca = Math.abs(a - b);

    if (diferenca !== 0) {
      copia.push(diferenca);
    }
  }

  if (copia.length === 0) {
    return 0;
  } else if (copia.length === 1) {
    return copia[0];
  }
};

// Teste

const pedras = [
  32,
  46188086,
  339992587,
  742976890,
  801915058,
  393898202,
  717833291,
  843435009,
  361066046,
  884145908,
  668431192,
  586679703,
  792103686,
  85425451,
  246993674,
  134274127,
  586374055,
  923288873,
  292845117,
  399188845,
  842456591,
  410257930,
  333998862,
  16561419,
  624279391,
  459765367,
  969764608,
  508221973,
  82956997,
  437034793,
  553121267,
  554066040,
  199416087
];

console.log(calcular(pedras));

1
  • +1. Mesmo não explicando por que a solução do autor não funcionou, gostei da sua resolução, apesar de que o ![0, 1].includes(copia.length) no while dificulta um pouco o entendimento e torna a função um pouquinho mais complexa. :) 15/03/2019 às 19:53
2

Consegui resolver o problema usando a seguinte abordagem:

function lastRockWeight(originalRockList) {
  // Função para sortear os elementos.
  function sortFunction(a, b) {
    return b - a
  }

  // Sortear os elementos antes de começar o loop.
  let rockList = originalRockList.sort(sortFunction)

  while (rockList.length > 1) {
    const [greater, secondGreater] = rockList

    // Remover o primeiro (maior) elemento.
    rockList.shift()

    // Trocar o atual primeiro elemento pela diferença entre o antigo primeiro e
    // ele. Note que estamos usando a função `Math.abs` para transformar o
    // número de negativo para positivo.
    rockList[0] = Math.abs(greater - secondGreater)

    // Sortear novamente.
    rockList = rockList.sort(sortFunction)
  }

  const [final] = rockList
  return final
}

console.log(lastRockWeight([4, 2, 3, 5]))
console.log(lastRockWeight([10, 40, 20, 30, 35, 70]))

console.log('Problema final:')
console.log(lastRockWeight([32, 46188086, 339992587, 742976890, 801915058, 393898202, 717833291, 843435009, 361066046, 884145908, 668431192, 586679703, 792103686, 85425451, 246993674, 134274127, 586374055, 923288873, 292845117, 399188845, 842456591, 410257930, 333998862, 16561419, 624279391, 459765367, 969764608, 508221973, 82956997, 437034793, 553121267, 554066040, 199416087]))

Após desenvolver a minha própria solução e com uma olhada nas duas abordagens que você desenvolveu, posso afirmar que o problema das suas soluções é que após cada iteração, você não reordenou os elementos novamente, simplesmente adicionando o elemento calculado ao final do array (em cada loop).

Isso é um problema tendo em vista que, assim como antes de iniciarmos o loop, também devemos ordenar os elementos após cada iteração, pois não temos como garantir que todos os resultados de cada iteração serão sempre menores que o anterior:

5 - 4 = 1 (`1` adicionado ao final, logo, ficaria algo assim: [... , 1]

1 - 3 = 2 (`2` adicionado ao final: [... , 1, 2] (`2` maior que o anterior (`1`))

Logo, se você adicionar o sort após cada iteração, a sua segunda solução funciona:

function compareValues(a, b) {
  if (a < b) return -1
  if (a > b) return 1
  return 0
}

function lastStoneWeight(arr) {
  arr = arr.sort(compareValues)
  let current
  while (arr.length > 1) {
    current = arr[arr.length - 1] - arr[arr.length - 2]
    arr[arr.length - 2] = current < 0 ? -current : current
    arr.pop()

    // Note abaixo:
    arr = arr.sort(compareValues)
  }
  return arr[0]
}

const output = lastStoneWeight([
  32,
  46188086,
  339992587,
  742976890,
  801915058,
  393898202,
  717833291,
  843435009,
  361066046,
  884145908,
  668431192,
  586679703,
  792103686,
  85425451,
  246993674,
  134274127,
  586374055,
  923288873,
  292845117,
  399188845,
  842456591,
  410257930,
  333998862,
  16561419,
  624279391,
  459765367,
  969764608,
  508221973,
  82956997,
  437034793,
  553121267,
  554066040,
  199416087
])

console.log(output, 659043 === output)


Em relação a:

Imaginei que talvez minha abordagem utilizando o reduce não fosse a correta [...]

Não é o fato de usar ou não métodos como o reduce que farão o código ficar errado. Geralmente é um mínimo detalhe que deixamos para trás.


E vejo que você utilizou um operador ternário para determinar o valor absoluto do número calculado:

current < 0 ? -current : current;

Para simplificar, você pode usar a função Math.abs, apesar de ambos resultados chegarem no mesmo resultado. :)


Referência:

1
  • Primeiramente, obrigado pela sugestão sobre o Math.abs. Realmente é uma função da linguagem que esqueci de utilizar. Eu percebi o motivo de não funcionar através da sua solução, e vou colocar a motivação matemática como uma resposta para elaborar mais. Muito obrigado, você ajudou demais! \o/ 15/03/2019 às 19:54
1

Primeiramente, obrigado a todos que colaboraram, tanto com seu conhecimento quanto com seu tempo, de coração.

TLDR: O resultado de um conjunto de operações absolutas sob subtrações depende da ordem dos valores, pois a ordem determina o momento em que a operação absoluta irá alterar o sinal da operação.

Sobre o problema: através da solução fornecida pelo @Luiz, percebi que o que ocorreu foi uma falha de conceito matemático, que também foi apontada pelo @Augusto em um comentário da pergunta (mas somente se aplica se todos os números forem positivos).

Como exemplo, gostaria de fornecer o seguinte caso:

Considere ABS como tendo o mesmo comportamento de Math.abs ou a < 0? -a : a

Fatos:

1) O valor absoluto da soma de dois elementos pode ser calculada através da operação:

abs(a+b)

2) O valor absoluto da subtração de dois elementos pode ser calculada através da operação:

abs(a-b)

Considerando dois elementos a e b isolados, a operação de valor absoluto não se apresenta como um problema para a solução, pois a - b = - (a - b); entretanto, o mesmo não se aplica quando existem múltiplas operações em sequência.

Considere o seguinte vetor (um fragmento do vetor apresentado como exemplo na pergunta)

[a, b, c, d, e, f, g, h, i, j] => [32, 16561419, 46188086, 82956997, 85425451, 134274127, 199416087, 246993674, 292845117, 333998862]

Ordenado, o vetor se tornaria:

[333998862, 292845117, 246993674, 199416087, 134274127, 85425451, 82956997, 46188086, 16561419, 32]

Considere, também, que as seguintes operações são realizadas:

(implementação ingênua)
1) Ordenação -> abs(abs(abs(abs(abs(abs(abs(abs(abs(a - b) - c) - d) - e) - f) - g) - h) - i) - j)

(implementação correta)
2) Ordenação -> abs(a - b) -> Ordenação -> abs(a - b) -> Ordenação -> abs(a - b) -> Ordenação -> abs(a - b) -> Ordenação -> abs(a - b) -> Ordenação -> abs(a - b) -> Ordenação -> abs(a - b) -> Ordenação -> abs(a - b) -> Ordenação -> abs(a - b)

No primeiro caso, a sequência de operações que se daria:

=> [333998862, 292845117, 246993674, 199416087, 134274127, 85425451, 82956997, 46188086, 16561419, 32]
=> abs(abs(abs(abs(abs(abs(abs(abs(abs(333998862 - 292845117) - 246993674) - 199416087) - 134274127) - 85425451) - 82956997) - 46188086) - 16561419) - 32)
=> abs(abs(abs(abs(abs(abs(abs(abs(304714351 - 246993674) - 199416087) - 134274127) - 85425451) - 82956997) - 46188086) - 16561419) - 32)
=> abs(abs(abs(abs(abs(abs(abs(57720677 - 199416087) - 134274127) - 85425451) - 82956997) - 46188086) - 16561419) - 32)
=> abs(abs(abs(abs(abs(abs(141695410 - 134274127) - 85425451) - 82956997) - 46188086) - 16561419) - 32)
=> abs(abs(abs(abs(abs(7421283 - 85425451) - 82956997) - 46188086) - 16561419) - 32)
=> abs(abs(abs(abs(78004168 - 82956997) - 46188086) - 16561419) - 32)
=> abs(abs(abs(4952829 - 46188086) - 16561419) - 32)
=> abs(abs(41235257 - 16561419) - 32)
=> abs(24673838 - 32)
=> 24673806

Portanto, resultado 24673806

No segundo caso:

Ordenação   ->  [333998862, 292845117, 246993674, 199416087, 134274127, 85425451, 82956997, 46188086, 16561419, 32]
abs(a - b)  ->  [333998862 - 292845117, 246993674, 199416087, 134274127, 85425451, 82956997, 46188086, 16561419, 32]
Ordenação   ->  [246993674, 199416087, 134274127, 85425451, 82956997, 46188086, *41153745*, 16561419, 32]
abs(a - b)  ->  [246993674 - 199416087, 134274127, 85425451, 82956997, 46188086, 41153745, 16561419, 32]
Ordenação   ->  [134274127, 85425451, 82956997, *47577587*, 46188086, 41153745, 16561419, 32]
abs(a - b)  ->  [134274127 - 85425451, 82956997, 47577587, 46188086, 41153745, 16561419, 32]
Ordenação   ->  [82956997, *48848676*, 47577587, 46188086, 41153745, 16561419, 32]
abs(a - b)  ->  [82956997 - 48848676, 47577587, 46188086, 41153745, 16561419, 32]
Ordenação   ->  [47577587, 46188086, 41153745, *34108321*, 16561419, 32]
abs(a - b)  ->  [47577587 - 46188086, 41153745, 34108321, 16561419, 32]
Ordenação   ->  [41153745, 34108321, 16561419, *1389501*, 32]
abs(a - b)  ->  [41153745 - 34108321, 16561419, 1389501, 32]
Ordenação   ->  [16561419, *7045424*, 1389501, 32]
abs(a - b)  ->  [16561419 - 7045424, 1389501, 32]
Ordenação   ->  [*9515995*, 1389501, 32]
abs(a - b)  ->  [9515995 - 1389501, 32]
Ordenação   ->  [*8126494*, 32]
abs(a - b)  ->  [8126494 - 32]
=> 8126462

Portanto, resultado 8126462

Percebe-se que a diferença de resultados quando ordena-se o vetor após cada operação de valor absoluto torna-se mais aparente quanto maiores forem os números utilizados, o que colabora a explicar o porquê dos primeiros testes terem funcionado (com números pequenos) mas o restante dos testes (com números maiores) terem falhado.

Uma alteração da função, utilizando como base as respostas do @luiz e do @Sorack como base (para facilitar a leitura e entendimento) poderia ser:

const compareValues = (a, b) => b - a;

const values = [32, 16561419, 46188086, 82956997, 85425451, 134274127, 199416087, 246993674, 292845117, 333998862]

const lastStoneWeight = originalArray => {
    let a, b, arr = [...originalArray];
    while (arr.length > 1) {
        arr = arr.sort(compareValues)
        a = arr.shift();
        b = arr.shift();
        arr.push(Math.abs(a - b))
    }
    return arr[0]
};

console.log(lastStoneWeight(values))

É isso! Obrigado a todos pela colaboração!

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .