Problems with array manipulation to find result

Question

I was solving a problem that was basically:

A prisoner was sentenced to perform a job where he was to break all the stones that were provided to him, but he could not use any tool for it. To accomplish the task, he decided that the best option would be to break two stones beating each other, until only one stone or none remains. In addition, the prisoner decided to break the biggest stones first, therefore in descending order.

If the prisoner hits two stones that are the same size, both stones are broken, and if one stone is smaller than the other, the size of the larger stone is reduced by the size of the smaller stone (e.g., 6-3 = 3).

Given the information, write a function that returns the size of the last broken stone by the prisoner, or 0 if there are no remaining stones.

That said, the problem provides an amount of test cases to validate the solution.

As an example, a test-case provides the array [4, 2, 3, 5] which, when ordered, would result in the vector [2, 3, 4, 5] and would have the following sequence of calculations:

5 - 4 = 1

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

2 - 2 = 0

Portanto, resultado final: 0

Another example, an array [10, 40, 20, 30, 35, 70] would be ordered to [10, 20, 30, 35, 40, 70] and would have the following stages:

70 - 40 = 30

30 - 35 = -5 (portanto, 5)

5 - 30 = -25 (portanto, 25)

25 - 20 = 5

5 - 10 = -5 (portanto, 5)

Resultado final: 5

The function created to solve the problem was:

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;

This function worked for some of the test cases (as mentioned above), but it did not work for others, as one that provides the 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
];

The result (according to the test site) is 64 thousand and few (I do not remember the exact amount), while I reached 10556317.

I imagined that maybe my approach using reduce was not the correct one, so I implemented the function differently, having the same result:

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];
};

Would it be possible to explain why the correct solution is not being found? Which edge-case I could not approach with the solutions presented?

EDIT: An alternative version of the compareValues function:

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

Answer 1

Use a while with the output condition by checking the size of the array resulting. Within the while order the array using sort. Take the first 2 values from array using shift and ensuring that they come out of the values that can be used. Calculate their absolute difference using Math.abs and add the result to array again, if different from 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));

Answer 2

I was able to solve the problem using the following approach:

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]))

After developing my own solution and taking a look at the two approaches you developed, I can say that the problem with your solutions is that after each iteration, you didn’t reorder the elements again, simply by adding the calculated element to the end of the array (on each loop).

This is a problem since, just as before we start the loop, we should also sort the elements after each iteration, because we cannot guarantee that all the results of each iteration will always be smaller than the previous one:

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, if you add the sort after each iteration, your second solution works:

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)

---

In relation to:

I figured maybe my approach using reduce wasn’t the right one [...]

It is not the fact of using or not methods like the reduce that will make the code go wrong. It is usually a minor detail that we leave behind.

---

And I see you used a ternary operator to determine the absolute value of the calculated number:

current < 0 ? -current : current;

To simplify, you can use the function Math.abs, despite both results reaching the same result. :)

---

Reference:

• Math.abs().

Answer 3

First of all, thank you to all who have collaborated, both with your knowledge and with your time, from the heart.

DRT: The result of a set of absolute operations under subtractions depends on the order of the values, as the order determines the time when the absolute operation will change the signal of the operation.

About the problem: through the solution provided by @Luiz, I realized that what happened was a flaw in the mathematical concept, which was also pointed out by @Augusto in a question comment (but only applies if all numbers are positive).

As an example, I would like to provide the following case:

Consider ABS to have the same behavior as Math.abs or a < 0? -a : a

Facts:

1) The absolute value of summing up of two elements can be calculated through the operation:

abs(a+b)

2) The absolute value of subtraction of two elements can be calculated through the operation:

abs(a-b)

Recital two to and b the operation of absolute value does not present itself as a problem for the solution because a - b = - (a - b); however, this does not apply where there are multiple operations in sequence.

Consider the following vector (a fragment of the vector presented as an example in the question)

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

Ordered, the vector would become:

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

Also consider that the following operations are carried out:

(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)

In the first case, the sequence of operations that would take place:

=> [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

Therefore, result 24673806

In the second case:

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

Therefore, result 8126462

It is noticed that the difference in results when the vector is ordered after each operation of absolute value becomes more apparent the larger the numbers used, which helps to explain why the first tests worked (with small numbers) but the rest of the tests (with larger numbers) failed.

A change of function, based on the responses of @Luiz and of @Sorack as a basis (to facilitate reading and understanding) could be:

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))

That’s it! Thank you all for your cooperation!